DS Структуры данных Структура данных
АВЛ-дерево
Также: AVL tree · АВЛ · дерево, сбалансированное по высоте · height-balanced tree · дерево Фибоначчи · Fibonacci tree · LL, RR, LR, RL · двойной поворот
Дерево поиска, которое после каждой вставки и удаления сверяет высоты веток и чинит перекос поворотами. Высота не превышает примерно 1,44·log₂ n, в каком бы порядке ни приходили ключи. На потоке землетрясений, где новый ключ всегда самый большой, а старый уходит слева, видно и цену: поворачивает почти каждая вставка, зато дерево остаётся низким, как идеальное.
29 июля 2025 года произошло землетрясение силой 8,8 — сильнейшее в каталоге USGS за одиннадцать лет, — и за следующую неделю каталог записал сотни толчков силой от 5. Пусть сервис держит под рукой все толчки за последние семь суток в дереве поиска по времени: новый всегда позже всех, а тот, что старше недели, уходит. Для обычного дерева поиска это худший случай: каждый новый ключ ложится правее всех, и дерево растёт палкой — к 4 августа в ней было бы 277 этажей. АВЛ-дерево на тех же событиях не поднималось выше девяти этажей, столько же, сколько у идеального дерева из 277 узлов. Сцена начинается за несколько часов до главного толчка.
Посмотрите на правый край. Новый толчок встаёт листом справа внизу, и почти сразу какой-нибудь узел над ним оказывается перекошен: его правая ветка на два этажа выше левой. Дерево поворачивается — узлы меняют этажи, но порядок слева направо остаётся прежним. За 2025 год поворотом закончились 946 вставок из тысячи. Слева уходят старые толчки, и там перебалансировок вдвое меньше: 481 на тысячу удалений. Переключите дерево на «без балансировки» — та же неделя превратится в диагональ, и каждый поиск самого свежего толчка пройдёт её целиком. На графике внизу оранжевая линия — сколько толчков в окне, то есть высота палки; бирюзовая — высота АВЛ-дерева, и она держится у пунктира идеальной высоты все одиннадцать лет.
Идея
В каждом узле хранится высота его поддерева, и правило одно: у любого узла высоты левой и правой ветки различаются не больше чем на единицу. Вставка и удаление делаются как в обычном дереве поиска, а потом идут от места изменения к корню, пересчитывают высоты и там, где разница стала два, поворачивают. Поворот перевешивает узлы с этажа на этаж, не трогая порядок ключей, и возвращает перекошенному кусту допустимую форму. Этого правила хватает, чтобы высота не превышала примерно 1,44·log₂ n, в каком бы порядке ни приходили ключи.
Что такое поворот, как его записать тремя присваиваниями и как придумали само дерево, рассказано в главе курса о деревьях поиска; там же есть сад, где повороты можно делать руками. Здесь — сколько поворотов стоит каждая операция, почему высота не может вырасти и что происходит при удалении, о котором в учебниках часто пишут одной строкой.
Балансом узла называют разность высот его левой и правой ветки. В АВЛ-дереве он бывает −1, 0 или +1, и вместо высоты можно хранить его — два бита на узел. Высоту хранить проще, а места она в узле с двумя ссылками всё равно почти не занимает; так сделано в листинге ниже.
Четыре перекоса
Пусть после вставки или удаления у узла x левая ветка стала на два этажа выше правой. Назовём левого ребёнка y. Что делать, зависит от того, какая ветка y выше.
| Случай | Что выше всего | Лечение |
|---|---|---|
| LL | левая ветка левого ребёнка (или обе его ветки поровну) | один поворот направо вокруг x |
| LR | правая ветка левого ребёнка | поворот налево вокруг y, потом направо вокруг x |
| RR | правая ветка правого ребёнка (или обе поровну) | один поворот налево вокруг x |
| RL | левая ветка правого ребёнка | поворот направо вокруг y, потом налево вокруг x |
Буквы читаются как путь от перекошенного узла вниз к самой высокой ветке: LL — налево и ещё раз налево. Когда высокая ветка растёт наружу, один поворот поднимает её на этаж, и куст выравнивается. Когда она растёт внутрь — зигзаг, — один поворот только перекладывает перекос на другую сторону: высокая средняя ветка переезжает к x и остаётся такой же высокой. Поэтому сначала зигзаг выпрямляют поворотом вокруг ребёнка, и получается обычный случай LL или RR.
Оговорка «или обе поровну» нужна только при удалении. После вставки у ребёнка перекошенного узла ветки всегда разной высоты — новая ветка выросла и стала выше. А при удалении ребёнок может оказаться ровным, и тогда нужен одиночный поворот. Двойной в этом случае может оставить перекос в два этажа у бывшего ребёнка, и дерево перестанет быть АВЛ-деревом; эта ошибка в самодельных реализациях встречается часто, и одна из задач статьи её ловит.
В сцене с землетрясениями при вставке встречается один-единственный случай — RR: новый ключ больше всех, и высокой всегда становится правая ветка правого ребёнка. Листинг ниже вставляет по порядку 19 073 ключа, столько же, сколько событий в каталоге, и все 19 058 перебалансировок у него — RR.
Вставке хватает одного поворота
Вставка увеличивает высоты на пути от нового листа вверх, и перекос может возникнуть у нескольких узлов этого пути сразу. Чинить, однако, приходится только один.
После вставки в АВЛ-дерево достаточно одной перебалансировки — одиночного или двойного поворота у самого нижнего перекошенного узла. После неё высота его поддерева такая же, какой была до вставки, и выше перекосов не остаётся.
Пусть x — самый нижний узел на пути от нового листа к корню, у которого баланс стал ±2; ниже него все узлы в порядке. Пусть, для определённости, новый ключ ушёл в левую ветку x. Раз разница стала два, до вставки левая ветка была на этаж выше правой: обозначим их высоты h и h − 1, а высоту x — h + 1. После вставки левая ветка выросла до h + 1. Её корень — левый ребёнок y, и он вырос, только если выросла одна из его веток и стала выше другой: у y теперь ветки высот h и h − 1, в каком-то порядке.
Случай LL: выше левая ветка y, назовём её A (высота h); правая B — высоты h − 1; правая ветка x, C, — тоже h − 1. Поворот направо делает y корнем, A остаётся у него слева, а справа встаёт x с ветками B и C. У x теперь обе ветки высоты h − 1, он ровный и имеет высоту h; у y слева A высоты h, справа x высоты h — тоже ровный, высота h + 1.
Случай LR: выше правая ветка y; её корень z, а у z ветки B₁ и B₂, одна высоты h − 1, другая — h − 1 или h − 2. Левая ветка y, A, и правая ветка x, C, — высоты h − 1. Два поворота поднимают z наверх: слева у него y с ветками A и B₁, справа x с ветками B₂ и C. У y и x ветки различаются не больше чем на единицу, и высота каждого — h; z ровный, высота h + 1.
В обоих случаях поддерево снова высоты h + 1, как до вставки. Узлы над ним видят ту же высоту, что и раньше, и их балансы не изменились, а до вставки они были в порядке. Случаи RR и RL зеркальны.
Высота дерева от поворота не меняется, а значит, расти она может только при вставках без поворота. На возрастающих ключах это видно в чистом виде: листинг вставляет числа от 1 до 19 073 и насчитывает 19 058 поворотов. Без поворота обошлись ровно пятнадцать вставок — 1-я, 2-я, 4-я, 8-я и дальше по степеням двойки до 16 384-й, — и каждая из них подняла дерево на этаж: до высоты 15, как у идеального дерева. Почему именно степени двойки, разбирается во второй задаче статьи: дерево, выросшее из ключей по порядку, оказывается двоичной записью числа n, а каждая вставка — прибавлением единицы.
Если ключи приходят вразнобой, поворотов вдвое меньше. Тот же 2025 год, перемешанный, вставляется с 477 перебалансировками на тысячу вставок, и чуть больше половины из них — 563 из 1015 — двойные.
Почему высота — логарифм
Правило говорит только о двух ветках одного узла, а держит высоту всего дерева. Чтобы это увидеть, спросим наоборот: из какого наименьшего числа узлов может состоять АВЛ-дерево высоты h?
АВЛ-дерево из n узлов имеет высоту $h < \log_\varphi(n + 2) + \log_\varphi\sqrt5 - 2 \approx 1{,}4404\,\log_2(n + 2) - 0{,}3277$, где $\varphi = \frac{1 + \sqrt5}{2}$ — золотое сечение.
Обозначим через N(h) наименьшее число узлов в АВЛ-дереве высоты h: N(0) = 0, N(1) = 1. У дерева высоты h ≥ 2 одна ветка корня обязана иметь высоту h − 1, иначе дерево было бы ниже, а другая по правилу — не меньше h − 2. Каждую ветку можно заменить самым худым деревом той же высоты, и правило не нарушится, а узлов станет меньше; и чем ниже ветка, тем меньше в ней может быть узлов. Поэтому у самого худого дерева ветки высот h − 1 и h − 2, обе самые худые: $N(h) = N(h-1) + N(h-2) + 1$.
Прибавим единицу к обеим частям: $N(h) + 1 = \big(N(h-1) + 1\big) + \big(N(h-2) + 1\big)$. Это правило чисел Фибоначчи, а начало $N(0) + 1 = 1 = F_2$, $N(1) + 1 = 2 = F_3$, значит, $N(h) + 1 = F_{h+2}$.
По формуле Бине $F_k = (\varphi^k - \psi^k)/\sqrt5$, где $\psi = \frac{1 - \sqrt5}{2} \approx -0{,}618$, и $|\psi^k| < 1$, поэтому $F_k > (\varphi^k - 1)/\sqrt5$. В дереве из n узлов высоты h узлов не меньше, чем в самом худом: $n + 1 \ge F_{h+2} > (\varphi^{h+2} - 1)/\sqrt5$. Отсюда $\varphi^{h+2} < \sqrt5\,(n + 1) + 1 < \sqrt5\,(n + 2)$, и, логарифмируя по основанию φ, $h + 2 < \log_\varphi(n + 2) + \log_\varphi\sqrt5$. Осталось подставить $1/\log_2\varphi \approx 1{,}4404$ и $\log_\varphi\sqrt5 \approx 1{,}6723$.
Для миллиона ключей это не больше 28 этажей, для миллиарда — не больше 42. В главе курса та же мысль доказана с оценкой попроще, $h \le \log_\varphi(n + 1)$; здесь формула Бине добавляет точности, и граница становится почти достижимой: самые худые деревья — их называют деревьями Фибоначчи — подходят к ней вплотную. Вот они.
Реальные АВЛ-деревья куда ниже предела. Для 277 узлов теорема разрешает 11 этажей, а дерево сцены было высоты 9, как идеальное. Перемешанные 2128 толчков 2025 года выросли в дерево высоты 13 при идеальных 12 и разрешённых 15. Деревья Фибоначчи — редкая порода: чтобы вырастить такое вставками, ключи надо подбирать нарочно.
Удаление: перекос поднимается к корню
Удаляют так же, как в обычном дереве поиска: лист срезают, узел с одной веткой заменяют этой веткой, а у узла с двумя ветками ключ заменяют преемником — самым левым ключом правой ветки — и срезают старый узел преемника. Потом, как и при вставке, идут вверх и пересчитывают высоты. Разница в том, что поворот после удаления часто делает поддерево ниже на этаж. Тогда у родителя укорачивается ветка, и перекошенным может оказаться и он, а потом и узел ещё выше. В сцене выше выберите высоту 8 и нажмите «Удалить самый маленький»: перекос поднимается к корню, и перебалансировок три.
Удаление из АВЛ-дерева высоты h делает не больше ⌊(h − 1)/2⌋ перебалансировок.
Пусть из дерева физически вырезан узел v — сам удаляемый или его преемник. Перебалансировки случаются только на пути от родителя v к корню. Обозначим через H(u) высоту узла u до удаления; все высоты ниже — тоже до удаления. Узел u на этом пути перебалансируется, только если его ветка со стороны v стала ниже, а разница высот достигла двух. Значит, до удаления эта ветка была ниже другой ветки u, и её высота была H(u) − 2.
У самого нижнего перебалансированного узла u₁ в этой ветке лежал v, так что её высота не меньше 1 и H(u₁) ≥ 3. Пусть u и u′ — два перебалансированных узла подряд, u′ выше. Ветка u′ со стороны v содержит u, поэтому её высота не меньше H(u), а с другой стороны она равна H(u′) − 2. Выходит, H(u′) ≥ H(u) + 2: каждая следующая перебалансировка происходит хотя бы на два этажа выше предыдущей. При k перебалансировках верхняя случается в узле высоты не меньше 3 + 2(k − 1) = 2k + 1, а выше высоты дерева узлов нет: 2k + 1 ≤ h.
Деревья Фибоначчи эту границу достигают. Листинг строит их для высот от 1 до 12, удаляет по очереди каждый ключ из свежего дерева и находит худший. Удаление самого маленького ключа всякий раз оказывается среди худших: перебалансировок ровно ⌊(h − 1)/2⌋. Это ровно то, что происходит слева в первой сцене: из окна уходит самый маленький ключ — самое старое событие.
h nodes delete the smallest the worst key 8 54 3 3 9 88 4 4 10 143 4 4 11 232 5 5 12 376 5 5
В среднем, впрочем, каскады редки. За 2025 год окно в семь суток делало 0,481 перебалансировки на удаление, а перемешанный порядок — 0,248. Худший случай логарифмический, но платить его почти не приходится.
Код
Узел хранит ключ, две ссылки и высоту своего поддерева. Вставка и удаление рекурсивны: на обратном пути из рекурсии каждый узел вызывает _rebalance, и подъём к корню получается сам собой — высота дерева не больше нескольких десятков, так что стек не переполнится. Метод check обходит дерево и проверяет порядок ключей, записанные высоты и правило баланса; в задачах такая проверка ловит ошибки, которые иначе проявились бы через тысячу операций. В Go дерево обобщённое, для любого упорядоченного типа ключей (cmp.Ordered), а ключ «время и номер строки» в окне упакован в одно число.
window most nodes max height perfect rebalancings per insert per delete 1 day 166 8 8 0.691 0.385 7 days 277 9 9 0.946 0.481 30 days 471 10 9 0.984 0.496 no window 2128 12 12 0.994 0.000 shuffled 2128 13 12 0.477 0.248
Чем шире окно, тем ближе доля поворачивающих вставок к единице — к тому, что даёт сплошной возрастающий ряд, где без поворота обходятся только вставки, поднимающие высоту. В окне 30 суток дерево однажды поднялось на этаж выше идеального — 10 при идеальных 9: АВЛ-дереву не нужно быть идеальным, ему достаточно правила.
Сколько это стоит
| Операция | Время | Перебалансировок |
|---|---|---|
| поиск, минимум, максимум, ближайший ключ | O(log n): примерно до 1,44·log₂ n сравнений | — |
| вставка | O(log n): спуск и подъём с пересчётом высот | не больше одной |
| удаление | O(log n) | не больше ⌊(h − 1)/2⌋, в среднем меньше одной |
| все ключи из диапазона | O(log n + k) на k найденных | — |
Память — O(n): к ключу и двум ссылкам добавляется высота или баланс. Поворот стоит O(1) — три ссылки и две высоты. Подъём к корню после операции стоит O(log n) даже без поворотов: высоты надо пересчитать на всём пути. Его можно обрывать раньше — как только высота узла не изменилась, выше ничего не поменяется, — но асимптотику это не меняет.
Ради чего всё это, видно на замере. Вставка n ключей: АВЛ-дерево на возрастающих и на случайных ключах и обычное дерево поиска на тех же.
На возрастающих ключах обычное дерево платит за каждую вставку проходом по всей палке: на десяти тысячах ключей в Go это почти в пятьдесят раз дольше, чем у АВЛ-дерева, и разрыв растёт пропорционально n. Миллион возрастающих ключей АВЛ-дерево в Go вставляет меньше чем за треть секунды. На случайных ключах балансировка ничего не выигрывает — обычное дерево и так невысокое — и только тратит. В Go разница невелика, а в Python АВЛ-дерево в 2,5–3,7 раза медленнее: каждый уровень рекурсии, пересчёт высоты и сравнение балансов — это работа интерпретатора. Любопытно, что АВЛ-дерево на возрастающих ключах в Go быстрее, чем на случайных, хотя перебалансировок там вдвое больше: новые ключи всё время идут по одной и той же правой ветке, и её узлы не уходят из кэша процессора.
Где работает
Ядра и системные библиотеки. В OpenZFS — файловой системе, которая пришла из Solaris, — есть общее АВЛ-дерево для кода ядра, файл module/avl/avl.c. Его комментарий объясняет два решения: узел встраивается прямо в структуру пользователя, без отдельного выделения памяти, а вместо рекурсии в узле хранится ссылка на родителя, потому что стек ядра мал. В musl — компактной стандартной библиотеке C — функции tsearch и tdelete, которые стандарт POSIX описывает как работу с деревом поиска, построены на АВЛ-дереве: в узле хранится высота, а перекос проверяется так же, как в листинге. В ядре Windows драйверам доступны готовые «обобщённые таблицы»; по умолчанию они построены на расширяющемся дереве, и документация предупреждает, что такое дерево может стать глубоким и узким, вплоть до прямой линии, и советует для более ровного дерева АВЛ-вариант — RtlInitializeGenericTableAvl.
Против красно-чёрного дерева. Стандартные упорядоченные словари обычно строят на красно-чёрном дереве: оно разрешает перекос побольше и потому поворачивает реже — при вставке не больше двух поворотов, при удалении не больше трёх. АВЛ-дерево ниже и ближе к идеальному, так что поиск в нём делает чуть меньше сравнений, но платит за это поворотами. На одних и тех же данных оба дерева сравниваются в статье о красно-чёрном дереве.
Где ни то ни другое. Если данные лежат на диске, нужно B-дерево: двоичное дерево читало бы по странице на каждый этаж. Если важнее простота и случайность устраивает, есть декартово дерево и список с пропусками. А в Python и Go готового сбалансированного дерева в стандартной библиотеке нет вовсе — для упорядоченных данных там держат отсортированный массив, как рассказано в статье о дереве поиска.
История
АВЛ-дерево — первое дерево поиска, которое гарантирует логарифмическую высоту при любом порядке ключей. Его описали Георгий Адельсон-Вельский и Евгений Ландис в 1962 году в статье «Один алгоритм организации информации» — четыре страницы о дереве, которое после каждой вставки проверяет свою форму и чинит её поворотами, так что поиск и вставка стоят порядка log n шагов при любом порядке ключей. В том же году вышел английский перевод, и название по первым буквам фамилий — AVL — прижилось на всех языках. Кто были авторы и над чем они работали, рассказано в главе курса. В 1970 году появились B-деревья, а в 1972-м Рудольф Байер придумал симметричные двоичные B-деревья, которые позже назвали красно-чёрными: они научились держать равновесие с меньшим числом поворотов.
Задачи
В первой задаче нужно честно реализовать АВЛ-дерево с удалением и сосчитать повороты на потоке событий — по тем самым правилам, что в статье, включая оговорку «или обе поровну». Вторая — о том, почему на возрастающих ключах без поворота обходятся только степени двойки: дерево из ключей 1, 2, …, n нужно описать, не строя его, для n до 10¹⁸.
Повороты на конвейере Загрузка по порядкуДанные: Землетрясения: каталог USGS, общественное достояние