Производительность АВЛ-дерева

Прежде, чем идти дальше, давайте рассмотрим результат соблюдения этого нового фактора баланса. Утверждением для доказательства станет гарантия, что если дерево имеет фактор сбалансированности -1, 0 или 1, то мы получаем лучшую О-производительность для операций с ключами. Начнём с размышлений о том, как условие баланса изменяет наихудший случай. Есть две возможности, которые следует рассмотреть: перевес дерева влево и вправо. Мы будем изучать деревья высотой 0, 1, 2, и 3, и рисунок 2 иллюстрирует дерево максимально перевешивающее влево согласно новым правилам.

../_images/worstAVL.png

Рисунок 2: Худший случай перевешивающих влево АВЛ-деревьев.

Глядя на общее количество узлов, можно заметить, что для дерева высотой 0 оно равно 1, высотой 1 - \(1+1 = 2\), высотой 2 - \(1+1+2 = 4\), высотой 3 - \(1 + 2 + 4 = 7\). Обобщая, количество узлов для дерева высотой \(h\) (\(N_h\)) равно

\[N_h = 1 + N_{h-1} + N_{h-2}\]

Эта рекуррентность может показаться вам знакомой, поскольку очень похожа на последовательность Фибоначчи. Данный факт можно использовать для вывода формулы высоты АВЛ-дерева с заданным количеством узлов. Напомним, что в последовательности Фибоначчи \(i_{ое}\) число равно

\[\begin{split}F_0 = 0 \\ F_1 = 1 \\ F_i = F_{i-1} + F_{i-2} \text{ for all } i \ge 2\end{split}\]

Важный математический результат заключается в том, что числа Фибоначчи с каждым разом становятся всё больше и больше, а отношение \(F_i / F_{i-1}\) всё ближе и ближе к “золотому сечению” \(\Phi\), определяемому как \(\Phi = \frac{1 + \sqrt{5}}{2}\). Вы можете обратиться к текстам по математике, если хотите посмотреть вывод предыдущего уравнения. Мы же просто используем его для приближённого вычисления \(F_i\) как \(F_i = \Phi^i/\sqrt{5}\). Если переписать уравнение для \(N_h\) с использованием этой аппроксимации, то получится

\[N_h = F_{h+2} - 1, h \ge 1\]

Заменив ссылку на Фибоначчи его аппроксимацией к “золотому сечению”, получим

\[N_h = \frac{\Phi^{h+2}}{\sqrt{5}} - 1\]

Перегруппировав переменные и взяв от обоих частей логарифм по основанию 2, получим следующее решение:

\[\begin{split}\log{N_h+1} = (H+2)\log{\Phi} - \frac{1}{2} \log{5} \\ h = \frac{\log{N_h+1} - 2 \log{\Phi} + \frac{1}{2} \log{5}}{\log{\Phi}} \\ h = 1.44 \log{N_h}\end{split}\]

Это выражение говорит о том, что каждый раз высота АВЛ-дерева равна константе (1.44), умноженной на логарифм высоты дерева. И это отличная новость для поиска по АВЛ-дереву, поскольку ограничивает его \(O(\log{N})\).

Next Section - Реализация АВЛ-дерева