кції по висоті дерева, що після видалення деякої вершини з дерева і наступного балансування висота дерева зменшується не більше, ніж на 1. База індукції: Для листа очевидно вірно. Крок індукції: Або умова Балансування в корені (після видалення корінь може зміниться) не порушена, тоді висота даного дерева не змінилася, або зменшилася строго менше з піддерев= gt; висота до балансування не змінилася= gt; після зменшиться не більше ніж на 1.
Очевидно, в результаті зазначених дій процедура видалення викликається не більше 3 разів, так як у вершини, що видаляється по 2-му викликом, немає одного з піддерев. Але пошук найближчого щораз вимагає O (N) операцій, звідси видно очевидна оптимізація: пошук найближчої вершини проводиться по краю поддерева. Звідси кількість дій O (log (N)).
Розстановка балансів при видаленні
Як вже говорилося, якщо видаляється вершина - лист, то вона віддаляється, і зворотний обхід дерева походить від батька віддаленого листа. Якщо не лист - їй знаходиться заміна raquo ;, і зворотний обхід дерева походить від батька заміни raquo ;. Безпосередньо після видалення елемента - заміна отримує баланс видаляється вузла.
При зворотному обході: якщо при переході до батьків прийшли зліва - баланс зменшується на 1, якщо ж прийшли праворуч - збільшується на 1.
Це робиться до тих пір, поки при зміні балансу він не стане рівним? 1 або 1 (зверніть увагу на відмінність з вставкою елемента!): в даному випадку така зміна балансу буде гласить про незмінну дельта-висоті піддерев. Повороти відбуваються за тими ж правилами, що і при вставці.
Розстановка балансів при одинарному повороті
Позначимо:
Current - Вузол, баланс якого дорівнює? 2 або 2: тобто той, який потрібно повернути (на схемі - елемент a )
Pivot - Вісь обертання. +2: Лівий син Current а,? 2: правий син Current а (на схемі - елемент b )
Якщо поворот здійснюється при вставці елемента, то баланс Pivot а дорівнює або 1, або? 1. У такому випадку після повороту баланси обох встановлюються рівними 0.
При видаленні все інакше: баланс Pivot а може стати рівним 0 (в цьому легко переконатися).
Наведемо зведену таблицю залежності фінальних балансів від напрямку повороту і вихідного балансу вузла Pivot:
Напрямок поворотаOld Pivot. BalanceNew Current. BalanceNew Pivot. BalanceЛевий або Правий - 1 або + 100Правий0-1 + 1Левий0 + 1-1
Розстановка балансів при подвійному повороті
Pivot і Current - ті ж самі, але додається третій учасник повороту. Позначимо його за Bottom raquo ;: це (при подвійному правому повороті) лівий син Pivot а, а при подвійному лівому - правий син Pivot а.
При даному повороті - Bottom в результаті завжди набуває баланс 0, але від його вихідного балансу залежить розстановка балансів для Pivot і Current.
Наведемо зведену таблицю залежності фінальних балансів від напрямку повороту і вихідного балансу вузла Bottom:
НаправленіеOld Bottom. BalanceNew Current. BalanceNew Pivot. BalanceЛевий або Правий000Правий + 10-1Правий - 1 + 10Левий + 1-10Левий - 10 + 1
Оцінка ефективності
Г.М. Адельсон-Бєльський і Е.М. Ландіс довели теорему, за якою висота АВЛ-дерева з N внутрішніми вершинами укладена між log2 (N + 1) і 1.4404 * log2 (N + 2) - 0.328, тобто висота АВЛ-дерева ніколи не перевищить висоту ідеально збалансованого дерева більше, ніж на 45%. Для великих N має місце оцінка 1.04 * log2 (N). Таким чином, виконання основних операцій 1 - 3 вимагає порядку log2 (N) порівнянь. Експериментально з'ясовано, що одна балансування припадає на кожні дві включення і на кожні п'ять винятків.
1.3 Обходи бінарних дерев
Існує досить багато алгоритмів роботи з деревовидними структурами, в яких часто зустрічається поняття обходу (traversing) дерева або проходу по дереву. При такому методі дослідження дерева кожен вузол відвідується тільки один раз, а повний обхід задає лінійне упорядкування вузлів, що дозволяє спростити алгоритм, так як при цьому можна використовувати поняття наступний вузол. тобто вузол стоїть після даного при обраному порядку обходу.
Існує кілька принципово різних способів обходу дерева:
Обхід в прямому порядку
Кожен вузол відвідується до того, як відвідані його нащадки.
