Бинарное дерево — это дерево, в котором все узлы имеют не более двух дочерних элементов.
Строгое/правильное двоичное дерево. В этом виде дерева каждый узел имеет либо 0, либо 2 дочерних элемента.
Полное двоичное дерево:все уровни, кроме последнего (очевидного), полностью заполнены, а все узлы максимально оставлены. Теперь, что вы подразумеваете под «все узлы как можно левее».
Хотя все уровни, кроме уровня 3, полностью заполнены, это не полное бинарное дерево, потому что слева у нас есть 2 свободных места.
При этом все уровни, кроме уровня 3, полностью заполнены. также все узлы максимально оставлены. Итак, это полное бинарное дерево. Максимальное количество узлов на уровне i равно 2^i.
Идеальное бинарное дерево: если все уровни полностью заполнены, то такое дерево называется сбалансированным бинарным деревом.
Максимальное количество узлов в идеальном бинарном дереве высотой h = 2⁰ + 2¹+..+2^h .
Узлы = 2^h+1-1.
Высота бинарного дерева = log(n+1) -1
Общее количество уровней = h+1.
Временная сложность в дереве зависит от высоты дерева. Высота дерева минимальна, когда дерево плотное. Таким образом, максимальная высота может быть n-1 в случае разреженного дерева, а минимальная высота равна журналу (n).
Сбалансированное бинарное дерево: разница между высотой левого и правого поддеревьев для каждого узла не более 1.
Высота дерева определяется как количество ребер на самом длинном пути от корня до конечного узла. Высота пустого дерева равна -1, а дерева с узлом 1 равна 0.
Это дерево сбалансировано, потому что максимальная разница высоты поддерева для любого узла может быть равна 1.
