AVL-дерево: как работает балансировка и ротации

AVL-дерево - это бинарное дерево поиска (BST), которое после каждой вставки и удаления автоматически восстанавливает почти-сбалансированную форму. Балансировка опирается на жёсткий инвариант высот и набор из четырёх локальных перестроек - ротаций. В результате поиск, вставка и удаление работают за $O(\log n)$ в худшем случае, без вероятностных допущений и без амортизации.

Исторический контекст: Адельсон-Вельский и Ландис, 1962

AVL - это первая известная сбалансированная структура поиска. В 1962 году советские математики Георгий Максимович Адельсон-Вельский и Евгений Михайлович Ландис в статье «Один алгоритм организации информации» («Доклады АН СССР») предложили хранить в каждом узле BST разницу высот его поддеревьев и поддерживать её в пределах единицы. Аббревиатура AVL сложилась из первых букв фамилий авторов.

До AVL обычное BST в худшем случае вырождалось в список (вставка отсортированной последовательности давала высоту $h = n-1$ и поиск $O(n)$). Идея Адельсона-Вельского и Ландиса - отслеживать локальное нарушение баланса и чинить его минимальной локальной перестройкой - стала родоначальницей целого семейства самобалансирующихся структур: красно-чёрные деревья (1972), splay-деревья (1985), AA-деревья, скип-листы. Большинство современных контейнеров map/set в стандартных библиотеках - потомки этой линии.

AVL-инвариант: balance factor

Пусть для каждого узла $v$ заданы высоты левого и правого поддеревьев $h_L(v)$ и $h_R(v)$. Балансировочный фактор узла определяется как

$bf(v) = h_L(v) - h_R(v).$

AVL-инвариант требует, чтобы для каждого узла дерева выполнялось

$bf(v) \in \{-1,\ 0,\ +1\}.$

Если $bf(v) = -2$ или $bf(v) = +2$, дерево считается разбалансированным и должно быть починено ротацией в этом узле. Высоту пустого поддерева полагают равной $-1$, высоту листа - $0$.

Следствие: высота AVL-дерева логарифмическая

Если обозначить минимальное число узлов в AVL-дереве высоты $h$ через $N(h)$, то рекуррентно

$N(h) = N(h-1) + N(h-2) + 1,\quad N(0)=1,\ N(1)=2.$

Это почти числа Фибоначчи, и решение даёт оценку

$h \le 1.44\,\log_2(n+2) - 0.328.$

Иными словами, высота AVL-дерева не более чем на 44% превышает высоту идеально сбалансированного дерева. На практике AVL ведёт себя ещё ближе к идеалу: для $n = 10^6$ типичная высота - около 22–24 уровней.

Из логарифмической высоты автоматически следует, что поиск, вставка и удаление работают за $O(\log n)$ - каждая операция спускается по одному пути от корня к листу, и на обратном ходу проходит этот же путь ещё раз.

Соберите дерево из последовательности вставок или проверьте, какая ротация нужна после конкретной операции - tool вернёт пошаговое решение с balance factor каждого узла и точкой нарушения инварианта.

Четыре типа ротаций: LL, RR, LR, RL

Все локальные перестройки AVL сводятся к четырём случаям, классифицируемым по «направлению перекоса» узла $A$ с $|bf(A)|=2$ и его ребёнка.

• LL-случай: $bf(A) = +2$ и $bf(A.left) = +1$. Перевес ушёл влево-влево. Чинится одной правой ротацией вокруг $A$.
• RR-случай: $bf(A) = -2$ и $bf(A.right) = -1$. Перевес вправо-вправо. Чинится одной левой ротацией вокруг $A$.
• LR-случай: $bf(A) = +2$ и $bf(A.left) = -1$. «Изломанный» перевес. Сначала левая ротация в $A.left$, затем правая ротация в $A$.
• RL-случай: $bf(A) = -2$ и $bf(A.right) = +1$. Симметричный излом. Сначала правая ротация в $A.right$, затем левая в $A$.

Ротация - это перевешивание ровно трёх ссылок и обновление двух балансировочных факторов. Она сохраняет порядок BST (in-order обход остаётся отсортированным) и уменьшает высоту поддерева на 1, что и устраняет нарушение инварианта.

Алгоритм вставки

Вставка в AVL - это вставка как в обычное BST плюс откат к корню с проверкой и починкой инварианта.

1. Спускаемся от корня по правилу BST: меньшее значение - налево, большее - направо. Дойдя до пустого места, создаём новый лист с $bf = 0$.
2. Возвращаемся к корню, на каждом шаге пересчитывая высоту и $bf$ родителя.
3. Если в каком-то узле $bf$ стал равен $\pm 2$ - определяем тип случая (LL/RR/LR/RL) и делаем ротацию.
4. После одной ротации высота поддерева восстанавливается до исходной - дальнейшие проверки родителей уже не находят нарушений, и откат можно остановить.

Ключевое следствие: при вставке нужна не более одной ротации (одинарной или двойной). Поэтому амортизированная стоимость восстановления баланса - константа на операцию.

Удаление: сложнее, может потребоваться несколько ротаций

Удаление начинается так же, как в BST: ищем узел, и если у него двое детей - заменяем его на симметричного преемника (минимум правого поддерева). После физического удаления листа возвращаемся к корню и проверяем инвариант на каждом уровне.

В отличие от вставки, после удаления одна ротация может не закрыть проблему: ротация уменьшает высоту поддерева, что в свою очередь меняет $bf$ родителя - и тот может стать $\pm 2$. В худшем случае ротации каскадно идут до самого корня, и их число - $O(\log n)$. Тем не менее общая стоимость удаления остаётся $O(\log n)$ - мы делаем не больше работы, чем длина пути.

AVL против красно-чёрных деревьев

Красно-чёрные (RB) деревья - главный конкурент AVL и более популярный в стандартных библиотеках. Сравнение:

• Жёсткость баланса. AVL держит $h \le 1.44 \log_2(n+2)$; RB - до $h \le 2 \log_2(n+1)$. То есть AVL в среднем ниже и быстрее на поиске.
• Стоимость изменений. Вставка/удаление в RB требует не больше 2-3 ротаций в худшем случае. В AVL вставка - не больше одной, удаление - до $O(\log n)$ ротаций.
• Память на узел. AVL хранит $bf$ или высоту (часто 1 байт), RB - 1 бит цвета.
• Когда что выгодно. AVL - когда поиск преобладает над модификациями (БД-индексы, in-memory словари с редкими апдейтами). RB - когда модификации частые и важна предсказуемая стоимость записи (это std::map, TreeMap в Java, ядро Linux для VMA).

Где применяются AVL-деревья

• Индексы баз данных и in-memory словари. Там, где запросов на чтение существенно больше, чем на запись (отчётные системы, поисковые сервисы), низкая высота AVL даёт ощутимый выигрыш.
• Файловые системы. Поиск файлов по имени в директориях с большим числом записей - например, в подсистемах ZFS и в некоторых драйверах NTFS.
• Теоретическая база для других структур. AVL - отправная точка для понимания splay-деревьев, weight-balanced trees, B+-деревьев. В курсах алгоритмов AVL подают первым именно потому, что инвариант чище и проще в анализе, чем у RB.
• Учебные задачи и собеседования. Реализация ротаций, доказательство логарифмической высоты, разбор каскадного удаления - классический материал курса «Алгоритмы и структуры данных».

Типовые учебные задачи

• Построить AVL из последовательности 10, 20, 30, 40, 50 - показать промежуточные ротации.
• Дано дерево; найти все узлы с $bf \ne 0$.
• После какой именно вставки в 30, 20, 10 происходит правая ротация и почему это случай LL.
• В AVL высоты 4 минимальное число узлов - посчитать через $N(h)$.
• Удалить корень в AVL из 7 узлов и показать каскад балансировки.

Частые ошибки

• Путать $bf$ и высоту. Balance factor - это разность высот, а не сама высота. Хранить часто удобнее именно $bf \in \{-1, 0, +1\}$ - два бита на узел.
• Забывать про двойные ротации. Случаи LR и RL нельзя починить одной ротацией: $bf$ узла-промежуточника останется некорректным.
• Считать, что удаление обходится одной ротацией. После удаления ротация может уменьшить высоту поддерева - и тогда нарушение «всплывает» к родителю.
• Не обновлять высоту/$bf$ на обратном ходу. Инвариант починен локально, но если не пересчитать значения у предков - следующая операция увидит ложную картину.
• Сравнивать AVL и RB только по высоте. Низкая высота AVL - преимущество для поиска, но при частых модификациях RB обычно выигрывает за счёт меньшего числа ротаций.

FAQ

Чем AVL-дерево отличается от обычного BST? Обычное BST гарантирует только порядок: левое поддерево меньше, правое больше. Высота при неудачной последовательности вставок может стать $O(n)$, и поиск выродится в линейный. AVL добавляет инвариант $|bf| \le 1$ и автоматическую балансировку через ротации - поэтому высота всегда $O(\log n)$, а операции - $O(\log n)$ в худшем случае.

Сколько ротаций нужно при вставке и при удалении? При вставке - не более одной (одинарной LL/RR или двойной LR/RL): после первой ротации высота поддерева возвращается к прежней, и нарушение не «всплывает» выше. При удалении в худшем случае ротации идут каскадом до самого корня - до $O(\log n)$ штук, но общая сложность операции всё равно $O(\log n)$.

Когда выбирать AVL, а когда красно-чёрные деревья? AVL - если операций поиска намного больше, чем вставок и удалений: индексы, словари с предсобранными данными. Красно-чёрные - если запись частая и нужна более низкая стоимость модификаций: контейнеры std::map/TreeMap, структуры ядра ОС. На очень больших данных и при работе с диском обе структуры обычно уступают B+-деревьям, где узел хранит десятки ключей.

Коротко

AVL-дерево, предложенное Адельсоном-Вельским и Ландисом в 1962 году, - это BST с жёстким инвариантом $|bf(v)| \le 1$, который гарантирует высоту $h \le 1.44 \log_2(n+2)$ и операции за $O(\log n)$ в худшем случае. Балансировка восстанавливается четырьмя типами ротаций - LL, RR, LR и RL - после каждой вставки или удаления. AVL особенно удобно там, где поиск преобладает над записью, и остаётся базовой структурой, через которую в учебниках вводят саму идею самобалансировки.