деревья

А вот я тут делал какое-то упражнение на LC, и обнаружил, что я не умею деревья. Всё понимаю, кроме того, как определять в какую ветку вставлять. Я понимаю зачем, я понимаю как работают bst, и даже понимаю как b-tree перебалансируется (и почему ему это можно делать).

А вот как в обычное дерево вставлять элементы так, чтобы получилось сбалансированное дерево, а не длинный странный список с небольшими ответвлениями - не понимаю.

Я сейчас говорю про простейшее двоичное дерево без выкрутасов и удалений. Просто вставлять так, чтобы дерево было более-менее равномерно заполнено.

Разумеется, я сейчас пойду и почитаю, но сначала я хочу осознать проблему.

Когда нам надо вставить новый элемент и мы находимся в ноде, в которой есть None в одном из направлений, всё понятно - мы туда и вставляем, потому что это самое близкое к root направление (выбирая между вставить ниже в полного соседа или вставить в другую половину "тут-и-сейчас" очевидно, что "тут-и-сейчас" даст локально оптимальнее решение).

Но когда у нас есть элемент слева и элемент справа, то мы должны выбрать куда вставлять...

Стоп. А в чём смысл куда-либо вставлять, если мы не можем найти элемент "просто так"? Получается, что "просто так деревьев" не бывает, и должна быть причина для выбора вставления влево или вправо.

На самом деле, моя задача была более узкая - у меня есть вектор с элементами, у которых есть one-to-one описание структуры дерева и мне надо его воспроизвести. Пустые элементы в списке отмечены как null. То есть мне нужно этот список хитро сканировать и обходить (на самом деле, конструировать) дерево в том порядке, как сказали.

И чуть раньше у меня была задача про in-order, которую я не понял. Кажется, тут какое-то слепое пятно у меня.

Это какая-то известная нотация для записывания деревьев в список, или мне свою надо придумать? Я сейчас попробую подумать над правилами обработки списка, может быть я сам до чего-то очевидного догадаюсь...

Пока инсайт: абстрактных сферических в вакууме деревьев не существует (особенно, на вставление и/или удаление). Дерево может быть "просто дерево" на какие-то операции с уже существующим деревом, но мы не можем построить дерево без правил его построения, то есть правила построения дерева обязательны и нет никакого "правила по-умолчанию".