9.4.9. Выровненные деревья

Ордерево называется выровненным, если все узлы, степень которых меньше 2, располагаются на одном или двух последних уровнях. Выровненное дерево имеет наименьшую возможную для данного р высоту h.

Пример

На рис. 9.12 приведены диаграммы выровненного (слева) и невыровненного (справа) деревьев.

Рис. 9.12. Выровненное (слева) и невыровненное деревья

ЛЕММА .

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

Индукция по k. База: k = 0  2⁰ = 1, 2¹ - 1 = 1, 1 = 1. Пусть, тогда

ТЕОРЕМА Для выровненного бинарного дерева log₂(p + 1) - 1  h < log₂(p + 1).

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

На i-м уровне может быть самое большее 2ⁱ вершин, следовательно,

По лемме имеем: 2^h—1 < р  2^h+1 - 1и 2^h <p+l  2^h+1. Логарифмируя, имеем: h< log₂(p +1) & h +1log₂(p +1). Следовательно log₂(p +1) – 1  h < log₂(p +1).

ЗАМЕЧАНИЕ

Выровненные деревья дают наибольший возможный эффект при поиске. Однако извест­но, что вставка/удаление может потребовать полной перестройки всего дерева и, таким образом, трудоемкость операции в худшем случае составит О(р).