Бинарные деревья

Бинарное дерево представляет собой структуру, в которой каждый узел (или вершина) имеет не более двух узлов-потомков и в точности одного родителя. Самый верхний узел дерева является единственным узлом без родителей; он называется корневым узлом, или корнем.

Бинарное дерево с N узлами имеет не меньше ⌊log₂N + 1⌋ уровней (при максимально плотной упаковке узлов). Например, у полного бинарного дерева с 15 узлами один корень, два узла на втором уровне, четыре узла на третьем уровне и восемь узлов на четвертом уровне; наше равенство также даёт ⌊log₂15⌋ + 1 = ⌊3,9⌋ + 1 = 4 уровня. Добавление еще одного узла к дереву приведет к появлению нового уровня, и их число станет равным ⌊log₂16⌋ + 1 = ⌊4⌋ + 1 = 5. В самом большом бинарном дереве с N узлами N уровней: у каждого узла этого дерева в точности один потомок (и само дерево представляет собой список).

Если уровни дерева занумеровать, считая, что корень лежит на уровне 1, то на уровне с номером k лежит не более чем 2^{k - 1} узла. У полного бинарного дерева с j уровнями (занумерованными от 1 до j) все листья (узлы без потомков) лежат на уровне с номером j, и у каждого узла на уровня с первого по j - 1 в точности два непосредственных потомка. В полном бинарном дереве с j уровнями 2^j - 1 узел.