9.4.10. Сбалансированные деревья

(Бинарное) дерево называется подровненным деревом, или АВЛ-деревом (Адель-сон-Вельский и Ландис, 1962), или сбалансированным деревом, если для любого узла высота левого и правого поддеревьев отличается не более чем на 1.

Пример

На рис. 9.13 приведена диаграмма максимально несимметричного сбалансиро­ванного дерева, в котором для всех узлов высота левого поддерева ровно на 1 больше высоты правого поддерева.

ТЕОРЕМА Для подровненного бинарного дерева h < 2 log₂ p.

доказательство

Рассмотрим наиболее несимметричные сбалансированные деревья, скажем, такие, у которых всякое левое поддерево на 1 выше правого. Такие сбалансированные деревья имеют макси­мальную возможную высоту среди всех сбалансированных деревьев с заданным числом вер­шин. Пусть P_h — число вершин в наиболее несимметричном сбалансированном дереве вы­соты h. По построению имеем: р = P_h = P_h-1 + P_h-2 + 1. Непосредственно проверяется, что Р₀ = 1, Р₁ = 2, Р₂= 4. Покажем по индукции, что P_h База: Р₀ = 1, = 1, 1  l;P₁ = 2 =, 2 .

Рис.9.13. Сбалансированное дерево

Пусть P_h  Тогда P_h+l =P_h + P_h-1 + 1 +1=.

Имеем:  P_h = р, следовательно, log₂p и h  21og₂p.

ЗАМЕЧАНИЕ

Известна более точная оценка высоты сбалансированного -дерева: h < 21og₂p.

Сбалансированные деревья уступают выровненным деревьям по скорости поис­ка (менее чем в два раза), однако их преимущество состоит в том, что известны алгоритмы вставки и удаления узлов в сбалансированное дерево, которые сохра­няют сбалансированность и в то же время при перестройке дерева затрагива­ют только конечное число узлов (см., например, [13]). Поэтому в подавляющем большинстве случаев сбалансированное дерево оказывается наилучшим вариантом предста­вления дерева сортировки.