АВЛ-дерево

АВЛ-Дерево (англ. AVL Tree) — збалансоване бінарне дерево, різниця між висотою лівого та правого піддерева для кожної з вершин якого не більше одиниці. АВЛ-дерево також називають збалансованим за висотою бінарним деревом.

Назва походить від ініціалів винахідників Г. М. Адельсон-Вельский (англ. G.M. Adelson-Velskii) та Е. М. Ландис (англ. E.M. Landis), які описали нову структуру даних в 1962 році.

Показник збалансованості вузла — висота його лівого піддерева мінус висота його правого піддерева (іноді навпаки), вузли з показником збалансованості рівним 1, 0 чи −1 вважаються збалансованими. Вузли з іншими значеннями показника збалансованості вважаються незбалансованими і потребують перебалансування дерева. Показник збалансованості зберігається в кожному вузлі або підраховується з висоти піддерев.

АВЛ-дерева часто порівнюють з червоно-чорними деревами через те, що вони підтримують той самий набір дій і тому, що також витрачають O(log n) часу на базові дії. З того, що АВЛ-дерево більш жорсткіше збалансоване, воно має кращу швидкодію в пошук-містких застосунках. Однак, червоно-чорні дерева мають кращий час вставки і видалення.

Властивості

Найбільша довжина гілок в АВЛ-дереві з $n$ вершинами не перевищує $(3/2) \log n$ (точніша оцінка — $\approx 1.44$).

АВЛ-дерева висоти $h$ мають щонайменше $F_{h+2} - 1$ вершин (де $F_i$ — число Фібоначчі).

АВЛ-дерева мають досить коротку відстань від кореня до звисаючих вершин, що робить їх ефективними для операцій пошуку даних.

Баланс

Див. також: Поворот дерева

В АВЛ-деревах, алгоритм відновлення балансу має такі властивості:

• після вставки нового елементу, операція відновлення балансу може відбутись на будь-якому рівні до кореня, але баланс відновлюється після виконання повороту.
• після видалення елементу, повороти можуть знадобитись для всіх вершин на шляху пошуку.
• Якщо виконують лише операції вставки, або лише видалення, обсяг необхідних змін може досягати O(1).

Джерела інформації

• Евстигнеев В. А. Применение теории графов в программировании. — «Наука», 1985.

Дивіться також

• Червоно-чорне дерево
• Список структур даних