Дерево(tree) - набор связанных узлов.
Узел(node) - данные + ссылка на следующий узел.
Корень(root) - первый узел, без родителя.
Ребро - путь между узлами/листами.
Лист - конечный узел без последующих за ним узлов или листьев.
Внутренний узел - ветка, промежуточный узел имеющий потомков.
Дерево - рекурсивная структура.
Каждый узел содержит другие узлы, похожие на своего родителя, некий факториал.
Глубина - длинна пути от корня до узла.
Высота - самый длинный путь от узла до листа, кол-во ребер.
У каждого узла не более 2 потомков.
Сбалансированное двоичное дерево:
Разница высоты между правым и левым поддеревом не превышает k. [k = 1]
Не сбалансированное двоичное дерево:
Любое другое двоичное дерево.
@ слева <- Данные -> @ справа
[todo]
Слева - все узлы меньше корня.
Справа - все узлы больше корня.
Двоичный поиск - O(Log N)
Добавление - O(Log N)
Удаление - O(Log N)
[todo]