АВЛ-дерево: различия между версиями
СВ (обсуждение | вклад) |
СВ (обсуждение | вклад) |
||
| Строка 74: | Строка 74: | ||
\text{BF}(x) = h(\text{left}[x]) - h(\text{right}[x]).</math> | \text{BF}(x) = h(\text{left}[x]) - h(\text{right}[x]).</math> | ||
[[Файл:avl-01-structure.svg| | [[Файл:avl-01-structure.svg|frame|none|700px|Рис. 1. Слева допустимое АВЛ-дерево: у всех узлов <math>|\text{BF}| \le 1</math>. Справа цепочка из трёх узлов: у корня 30 левое поддерево выше правого на 2, <math>\text{BF}(30) = +2</math> — нарушение, требующее поворота.]] | ||
== Операции и алгоритмы == | == Операции и алгоритмы == | ||
Версия 21:40, 7 октября 2026
TL;DR
АВЛ-дерево (AVL tree) — первое в истории сбалансированное двоичное дерево поиска, в котором для каждого узла высоты левого и правого поддеревьев отличаются не более чем на 1. Название — по фамилиям изобретателей, Г. М. Адельсон-Вельского и Е. М. Ландиса (1962). Строгое условие баланса даёт высоту не более [math]\displaystyle{ \approx 1.44\log_2(n+2) }[/math], что даже ниже, чем у красно-чёрного дерева ([math]\displaystyle{ 2\log_2(n+1) }[/math]), и потому поиск в АВЛ-дереве делает меньше сравнений. Плата за строгость — больше поворотов при удалении: вставка требует не более одного поворота, а удаление — до [math]\displaystyle{ O(\log n) }[/math] поворотов. Все операции выполняются за [math]\displaystyle{ O(\log n) }[/math] в худшем случае.
| Свойство | Значение |
|---|---|
| Класс | Двоичное дерево поиска (binary search tree, BST) с балансировкой по высоте |
| Изобретение | Адельсон-Вельский и Ландис, 1962 [3] |
| Поиск (худший / средний) | [math]\displaystyle{ O(\log n) }[/math] / [math]\displaystyle{ O(\log n) }[/math] |
| Вставка (худший) | [math]\displaystyle{ O(\log n) }[/math]; не более 1 поворота (одинарного или двойного) |
| Удаление (худший) | [math]\displaystyle{ O(\log n) }[/math]; до [math]\displaystyle{ O(\log n) }[/math] поворотов |
| Обход в порядке возрастания | [math]\displaystyle{ O(n) }[/math] |
| Высота | [math]\displaystyle{ \le 1.44\log_2(n+2) }[/math]; минимум узлов при высоте [math]\displaystyle{ h }[/math]: [math]\displaystyle{ N(h)=N(h{-}1)+N(h{-}2)+1 }[/math] |
| Память | [math]\displaystyle{ O(n) }[/math]; один счётчик высоты или баланса на узел сверх обычного BST |
| Упорядоченность | Да; итерация даёт ключи по возрастанию |
| Детерминированность | Да; рандомизация не нужна |
| Альтернативы | Красно-чёрное дерево, B-дерево, splay-дерево, декартово дерево, хеш-таблица |
| Где встречается | индексы в оперативной памяти, словари и проверка орфографии, вычислительная геометрия, системы с жёстким пределом времени отклика |
Определения
АВЛ-дерево (AVL tree) — двоичное дерево поиска, в котором для каждого узла [math]\displaystyle{ x }[/math] выполняется условие АВЛ:
[math]\displaystyle{ |\,h(\text{left}[x]) - h(\text{right}[x])\,| \le 1, }[/math]
где [math]\displaystyle{ h }[/math] — высота поддерева. Иначе говоря, высоты левого и правого поддеревьев различаются не более чем на единицу.
Высота узла [math]\displaystyle{ h(x) }[/math] — число рёбер на самом длинном пути от [math]\displaystyle{ x }[/math] вниз до листа. Принята соглашение [math]\displaystyle{ h(\text{NIL}) = -1 }[/math] (высота пустого поддерева), тогда у листа [math]\displaystyle{ h = 0 }[/math]. Высота всего дерева — это [math]\displaystyle{ h(\text{root}) }[/math].
Коэффициент баланса (balance factor, BF) узла [math]\displaystyle{ x }[/math] — величина
[math]\displaystyle{ \text{BF}(x) = h(\text{left}[x]) - h(\text{right}[x]). }[/math]
Условие АВЛ равносильно [math]\displaystyle{ \text{BF}(x) \in \{-1, 0, +1\} }[/math] для всех узлов. Положительный BF означает перевес левого поддерева, отрицательный — правого.
Поворот (rotation) — локальная перестройка связей двух узлов за время [math]\displaystyle{ O(1) }[/math], сохраняющая порядок ключей. Различают одинарные (LL, RR) и двойные (LR, RL) повороты.
Обозначения. [math]\displaystyle{ n }[/math] — число внутренних узлов (ключей). [math]\displaystyle{ \log }[/math] — логарифм по основанию 2. [math]\displaystyle{ \varphi = (1+\sqrt5)/2 \approx 1.618 }[/math] — золотое сечение. Для узла [math]\displaystyle{ x }[/math]: [math]\displaystyle{ \text{left}[x] \lt x \lt \text{right}[x] }[/math]. Дубликаты, как и в других упорядоченных деревьях, либо отклоняются, либо хранятся со счётчиком.
Мотивация и интуиция
Обычное BST деградирует при неудачном порядке вставок. Последовательность [math]\displaystyle{ 1,2,\dots,n }[/math] превращает его в список высоты [math]\displaystyle{ n-1 }[/math]: при [math]\displaystyle{ n=10^6 }[/math] поиск выполняет до миллиона сравнений вместо примерно 20. Противник, знающий алгоритм, может подобрать такой вход намеренно.
Чтобы этого избежать, нужно поддерживать малую высоту после каждой операции. Красно-чёрное дерево делает это «слабо»: разрешает перекос вдвое. АВЛ-дерево выбирает противоположную крайность — жёсткое условие [math]\displaystyle{ |\text{BF}| \le 1 }[/math]. Ключевое наблюдение: при таком условии число узлов растёт экспоненциально с высотой (как [math]\displaystyle{ \varphi^h }[/math]), поэтому высота логарифмична по [math]\displaystyle{ n }[/math] с очень хорошей константой [math]\displaystyle{ 1.44 }[/math]. На практике это означает меньше сравнений при поиске.
Цена строгости проявляется при удалении: удаление уменьшает высоту поддерева, из-за чего условие может нарушиться не только у ближайшего предка, но и выше, вплоть до корня. Поэтому удаление может потребовать [math]\displaystyle{ O(\log n) }[/math] поворотов, тогда как вставка — не более одного. Именно по этой причине контейнеры общего назначения (std::map, TreeMap) предпочитают красно-чёрное дерево, а АВЛ остаётся выбором для читающих нагрузок.
Устройство
АВЛ-дерево — это обычное BST, дополненное двумя элементами:
- Условие баланса [math]\displaystyle{ |\text{BF}(x)| \le 1 }[/math] для каждого узла.
- Данные для контроля баланса — высота поддерева (целое число) в каждом узле. Хранить можно также сам коэффициент баланса, но хранить высоту удобнее и надёжнее: её легко пересчитывать.
Ссылка на родителя не обязательна для рекурсивной реализации, но очень полезна для итеративного подъёма при балансировке; ниже используется именно она.
Высота и коэффициент связаны простыми соотношениями:
[math]\displaystyle{ h(x) = 1 + \max\bigl(h(\text{left}[x]),\, h(\text{right}[x])\bigr), \qquad \text{BF}(x) = h(\text{left}[x]) - h(\text{right}[x]). }[/math]
Операции и алгоритмы
Операция: поворот (rotation)
Идея. Одинарный поворот поднимает более высокого ребёнка на место родителя, перевешивая среднее поддерево. Двойной поворот — это два одинарных подряд и применяется для «зигзага». Поворот сохраняет порядок ключей и меняет высоты только участвующих узлов.
Пошаговое описание (правый поворот вокруг [math]\displaystyle{ x }[/math]).
- Обозначить [math]\displaystyle{ y \leftarrow \text{left}[x] }[/math] (левый ребёнок становится новым корнем поддерева).
- Перевесить правое поддерево [math]\displaystyle{ y }[/math] ([math]\displaystyle{ \text{right}[y] }[/math]) в левого ребёнка [math]\displaystyle{ x }[/math].
- Поднять [math]\displaystyle{ y }[/math] на место [math]\displaystyle{ x }[/math]: переназначить ссылку родителя.
- Сделать [math]\displaystyle{ x }[/math] правым ребёнком [math]\displaystyle{ y }[/math].
- Пересчитать высоты: сначала у [math]\displaystyle{ x }[/math], затем у [math]\displaystyle{ y }[/math] (порядок важен, иначе [math]\displaystyle{ y }[/math] получит устаревшую высоту).
Инвариант. До и после поворота выполнено BST-свойство ([math]\displaystyle{ \text{left} \lt \text{node} \lt \text{right} }[/math]); множество ключей не меняется, высоты всех затронутых узлов корректны.
Псевдокод.
Алгоритм Update-Height(x)
1 h-left ← (left[x] = NIL) ? −1 : height[left[x]]
2 h-right ← (right[x] = NIL) ? −1 : height[right[x]]
3 height[x] ← 1 + max(h-left, h-right)
Алгоритм Balance(x)
1 return height[left[x]] − height[right[x]] # height[NIL] = −1
Алгоритм Right-Rotate(T, x)
Вход: x — узел, у которого left[x] ≠ NIL
Выход: y = left[x] поднят на место x; BST-порядок и высоты восстановлены
Инвариант: ключи множества не меняются, left < node < right сохраняется
1 y ← left[x]
2 left[x] ← right[y]
3 if right[y] ≠ NIL
4 parent[right[y]] ← x
5 parent[y] ← parent[x]
6 if parent[x] = NIL
7 root[T] ← y
8 else if x = right[parent[x]]
9 right[parent[x]] ← y
10 else
11 left[parent[x]] ← y
12 right[y] ← x
13 parent[x] ← y
14 Update-Height(x) # сначала x — он теперь ниже
15 Update-Height(y)
Сложность: O(1) времени и памяти.
Left-Rotate — зеркальная операция.
Четыре случая. Первый узел на пути вверх, где [math]\displaystyle{ |\text{BF}| = 2 }[/math], называется разбалансированным. Его лечат так:
| Случай | Форма (ключи) | Что делают | Итог |
|---|---|---|---|
| LL | [math]\displaystyle{ z \lt y \lt x }[/math] по левому-левому пути | правый поворот вокруг [math]\displaystyle{ z }[/math] | [math]\displaystyle{ y }[/math] — корень |
| RR | правая-правая цепочка | левый поворот вокруг [math]\displaystyle{ z }[/math] | средний — корень |
| LR | [math]\displaystyle{ y \lt x \lt z }[/math] зигзагом | левый вокруг [math]\displaystyle{ y }[/math], затем правый вокруг [math]\displaystyle{ z }[/math] | [math]\displaystyle{ x }[/math] — корень |
| RL | зигзаг в другую сторону | правый вокруг [math]\displaystyle{ y }[/math], затем левый вокруг [math]\displaystyle{ z }[/math] | средний — корень |
Операция: вставка (insert)
Идея. Вставить узел как в обычное BST (новый узел — лист), затем подниматься к корню, пересчитывая высоты. На первом узле с [math]\displaystyle{ |\text{BF}| = 2 }[/math] выполнить соответствующий поворот. После одинарного или двойного поворота высота поддерева возвращается к значению до вставки, поэтому предки уже сбалансированы — достаточно одного поворота.
Пошаговое описание.
- Спуск от корня по сравнению ключей; вставка нового листа [math]\displaystyle{ z }[/math] с высотой 0.
- Подъём от родителя [math]\displaystyle{ z }[/math] к корню.
- На каждом шаге:
Update-Height; еслиBalance(x) > 1— левый перевес (LL или LR); еслиBalance(x) < −1— правый (RR или RL). - LL/LR: если
Balance(left[x]) < 0, сначала левый поворот вокругleft[x], затем правый вокруг [math]\displaystyle{ x }[/math]. - RR/RL: если
Balance(right[x]) > 0, сначала правый поворот вокругright[x], затем левый вокруг [math]\displaystyle{ x }[/math]. - Продолжать подъём (при вставке можно остановиться сразу после первого поворота).
Инвариант. Перед обработкой узла [math]\displaystyle{ x }[/math] все узлы ниже него уже удовлетворяют условию АВЛ, а высоты пересчитаны корректно. При вставке высота не могла вырасти больше чем на 1, поэтому [math]\displaystyle{ |\text{BF}(x)| \le 2 }[/math].
Псевдокод.
Алгоритм AVL-Fixup(T, x)
Вход: x — узел, от которого поднимаемся (обычно родитель вставленного/удалённого)
Выход: для всех узлов выполнено |BF| ≤ 1, высоты пересчитаны
Инвариант: все узлы ниже x уже сбалансированы
1 while x ≠ NIL
2 p ← parent[x] # запомнить ДО возможных поворотов
3 Update-Height(x)
4 if Balance(x) > 1
5 if Balance(left[x]) < 0
6 Left-Rotate(T, left[x]) # случай LR: подготовка
7 Right-Rotate(T, x) # LL или завершение LR
8 else if Balance(x) < −1
9 if Balance(right[x]) > 0
10 Right-Rotate(T, right[x]) # случай RL: подготовка
11 Left-Rotate(T, x) # RR или завершение RL
12 x ← p
Алгоритм AVL-Insert(T, z)
Вход: T — АВЛ-дерево; z — новый узел с key[z], height[z] = 0
Выход: T содержит z, условие АВЛ восстановлено
1 y ← NIL
2 x ← root[T]
3 while x ≠ NIL
4 y ← x
5 if key[z] < key[x]
6 x ← left[x]
7 else if key[x] < key[z]
8 x ← right[x]
9 else
10 return # дубликат: игнорируем
11 parent[z] ← y
12 if y = NIL
13 root[T] ← z
14 else if key[z] < key[y]
15 left[y] ← z
16 else
17 right[y] ← z
18 AVL-Fixup(T, y) # подъём от родителя
Сложность: O(log n) времени, O(1) памяти; не более одного поворота (одинарного или двойного).
Корректность: поворот в узле x восстанавливает |BF(x)| ≤ 1 и возвращает высоту поддерева к прежнему значению, поэтому выше ничего не нарушается.
Разбор на примере. Вставка в пустое дерево ключей [math]\displaystyle{ 10, 20, 30, 40, 50, 25 }[/math] (рис. 4):
- [math]\displaystyle{ 10, 20 }[/math]: высоты растут по цепочке, но [math]\displaystyle{ |\text{BF}| \le 1 }[/math] — поворот не нужен.
- [math]\displaystyle{ 30 }[/math]: [math]\displaystyle{ \text{BF}(10) = -2 }[/math] (случай RR) → левый поворот вокруг 10. Корнем становится 20.
- [math]\displaystyle{ 40 }[/math]: проходит как лист, баланс в норме.
- [math]\displaystyle{ 50 }[/math]: [math]\displaystyle{ \text{BF}(30) = -2 }[/math] (случай RR) → левый поворот вокруг 30, поднимается 40.
- [math]\displaystyle{ 25 }[/math]: [math]\displaystyle{ \text{BF}(20) = -2 }[/math], при этом [math]\displaystyle{ \text{BF}(40) = +1 }[/math] (случай RL) → двойной поворот: правый вокруг 40, затем левый вокруг 20; корнем поддерева становится 30.
Крайние случаи. Вставка в пустое дерево — новый узел сразу корень. Вставка ключа, который уже есть, — отклоняется. Случай, когда перевес уходит в одну сторону цепочкой, немедленно исправляется одинарным поворотом.
Операция: удаление (delete)
Идея. Удалить узел по правилам BST (узел с двумя детьми заменяется преемником), затем подняться к корню, пересчитывая высоты и поворачивая там, где [math]\displaystyle{ |\text{BF}| = 2 }[/math]. В отличие от вставки, поворот уменьшает высоту поддерева, поэтому нарушение может «всплыть» у предков, и балансировку приходится повторять.
Пошаговое описание.
- Найти узел [math]\displaystyle{ z }[/math] с ключом [math]\displaystyle{ k }[/math]. Если его нет — ничего не делать.
- Если у [math]\displaystyle{ z }[/math] два ребёнка, скопировать в [math]\displaystyle{ z }[/math] ключ преемника [math]\displaystyle{ y = \text{Minimum}(\text{right}[z]) }[/math] и физически удалять уже [math]\displaystyle{ y }[/math] (у него не более одного ребёнка).
- Подвесить единственного ребёнка удаляемого узла на место (или
NIL). - Подняться от родителя удалённого узла к корню (
AVL-Fixup). - На разбалансированных узлах выбирать поворот по балансу ребёнка: - левый перевес ([math]\displaystyle{ \text{BF} \gt 1 }[/math]): [math]\displaystyle{ \text{BF}(\text{left}) \lt 0 }[/math] → LR, иначе LL; - правый перевес ([math]\displaystyle{ \text{BF} \lt -1 }[/math]): [math]\displaystyle{ \text{BF}(\text{right}) \gt 0 }[/math] → RL, иначе RR.
- Продолжать подъём до корня (в отличие от вставки, ранняя остановка не гарантирована).
Инвариант. Перед обработкой [math]\displaystyle{ x }[/math] все узлы ниже сбалансированы; высота поддерева [math]\displaystyle{ x }[/math] могла уменьшиться на 1, поэтому [math]\displaystyle{ |\text{BF}(x)| \le 2 }[/math].
Псевдокод.
Алгоритм AVL-Delete(T, k)
Вход: k — удаляемый ключ
Выход: узел с ключом k удалён, условие АВЛ восстановлено
1 z ← поиск узла с ключом k в T
2 if z = NIL
3 return
4 if left[z] ≠ NIL and right[z] ≠ NIL
5 y ← Minimum(right[z]) # преемник
6 key[z] ← key[y] # копируем ключ
7 z ← y # физически удаляем y
8 child ← (left[z] ≠ NIL) ? left[z] : right[z]
9 par ← parent[z]
10 if child ≠ NIL
11 parent[child] ← par
12 if par = NIL
13 root[T] ← child
14 else if z = left[par]
15 left[par] ← child
16 else
17 right[par] ← child
18 удалить узел z; уменьшить число узлов
19 if par ≠ NIL
20 AVL-Fixup(T, par) # может потребоваться много поворотов
Сложность: O(log n) времени, O(1) памяти; поворотов может быть до Θ(log n).
Корректность: AVL-Fixup пересчитывает высоты и восстанавливает |BF| ≤ 1 на каждом уровне, поэтому после подъёма условие АВЛ выполнено для всего дерева.
Крайние случаи. Удаление листа — просто отцепляем. Удаление узла с одним ребёнком — ребёнок занимает место. Удаление корня — новым корнем становится ребёнок или NIL. Если ребёнок разбалансированного узла имеет баланс 0 (ситуация, невозможная при вставке, но возможная при удалении), достаточно одинарного поворота.
Операция: поиск (search)
Идея. Поиск не зависит от баланса: дерево корректно как BST, значит, обычный спуск по сравнениям находит ключ. Малая высота гарантирует число сравнений.
Алгоритм AVL-Search(T, k)
Вход: T — дерево; k — искомый ключ
Выход: узел с ключом k либо NIL
Инвариант: если k есть в дереве, то он лежит в поддереве текущего узла x
1 x ← root[T]
2 while x ≠ NIL and k ≠ key[x]
3 if k < key[x]
4 x ← left[x]
5 else
6 x ← right[x]
7 return x
Сложность: O(log n) времени (высота дерева), O(1) памяти.
Минимум/максимум находятся спуском влево/вправо до NIL; преемник и предшественник — за [math]\displaystyle{ O(\log n) }[/math]; упорядоченный обход — за [math]\displaystyle{ O(n) }[/math].
Реализация структуры на C++
Полная реализация (C++17): итеративная вставка/удаление, ссылки на родителя, хранение высоты. Функция validate() проверяет BST-свойство, условие АВЛ, корректность высот и ссылок на родителей.
#include <iostream>
#include <vector>
#include <cassert>
#include <cstdlib>
#include <algorithm>
template <typename T>
class AVLTree {
struct Node {
T key;
int height;
Node *left, *right, *parent;
explicit Node(const T& k)
: key(k), height(0), left(nullptr), right(nullptr), parent(nullptr) {}
};
Node* root_ = nullptr;
std::size_t count_ = 0;
static int height(Node* n) { return n ? n->height : -1; }
static void update(Node* n) {
n->height = 1 + std::max(height(n->left), height(n->right));
}
static int balanceOf(Node* n) { return height(n->left) - height(n->right); }
void rotateLeft(Node* x) {
Node* y = x->right;
x->right = y->left;
if (y->left) y->left->parent = x;
y->parent = x->parent;
if (!x->parent) root_ = y;
else if (x == x->parent->left) x->parent->left = y;
else x->parent->right = y;
y->left = x;
x->parent = y;
update(x);
update(y);
}
void rotateRight(Node* x) {
Node* y = x->left;
x->left = y->right;
if (y->right) y->right->parent = x;
y->parent = x->parent;
if (!x->parent) root_ = y;
else if (x == x->parent->right) x->parent->right = y;
else x->parent->left = y;
y->right = x;
x->parent = y;
update(x);
update(y);
}
void fixup(Node* x) {
while (x) {
Node* parent = x->parent;
update(x);
if (balanceOf(x) > 1) {
if (balanceOf(x->left) < 0) rotateLeft(x->left);
rotateRight(x);
} else if (balanceOf(x) < -1) {
if (balanceOf(x->right) > 0) rotateRight(x->right);
rotateLeft(x);
}
x = parent;
}
}
Node* find(const T& key) const {
Node* x = root_;
while (x) {
if (key < x->key) x = x->left;
else if (x->key < key) x = x->right;
else return x;
}
return nullptr;
}
static Node* minimum(Node* x) {
while (x->left) x = x->left;
return x;
}
bool check(Node* n, int& h) const {
if (!n) { h = -1; return true; }
int lh, rh;
if (!check(n->left, lh) || !check(n->right, rh)) return false;
if (n->left && n->left->parent != n) return false;
if (n->right && n->right->parent != n) return false;
if (std::abs(lh - rh) > 1) return false; // условие АВЛ
if (n->height != 1 + std::max(lh, rh)) return false;
h = n->height;
return true;
}
void inorder(Node* n, std::vector<T>& out) const {
if (!n) return;
inorder(n->left, out);
out.push_back(n->key);
inorder(n->right, out);
}
void destroy(Node* n) {
if (!n) return;
destroy(n->left);
destroy(n->right);
delete n;
}
public:
AVLTree() = default;
~AVLTree() { destroy(root_); }
AVLTree(const AVLTree&) = delete;
AVLTree& operator=(const AVLTree&) = delete;
void insert(const T& key) {
Node* z = new Node(key);
if (!root_) { root_ = z; ++count_; return; }
Node* cur = root_;
Node* par = nullptr;
while (cur) {
par = cur;
if (key < cur->key) cur = cur->left;
else if (cur->key < key) cur = cur->right;
else { delete z; return; } // дубликат отклоняется
}
z->parent = par;
if (key < par->key) par->left = z;
else par->right = z;
++count_;
fixup(par);
}
bool contains(const T& key) const { return find(key) != nullptr; }
void erase(const T& key) {
Node* z = find(key);
if (!z) return;
if (z->left && z->right) {
Node* y = minimum(z->right); // преемник
z->key = y->key; // копируем ключ
z = y; // физически удаляем y
}
Node* child = z->left ? z->left : z->right;
Node* par = z->parent;
if (child) child->parent = par;
if (!par) root_ = child;
else if (z == par->left) par->left = child;
else par->right = child;
delete z;
--count_;
fixup(par);
}
std::size_t size() const { return count_; }
bool empty() const { return count_ == 0; }
std::vector<T> sorted() const {
std::vector<T> out;
inorder(root_, out);
return out;
}
bool validate() const {
int h;
if (!check(root_, h)) return false;
std::vector<T> v = sorted();
return std::is_sorted(v.begin(), v.end());
}
};
int main() {
AVLTree<int> t;
std::vector<int> vals = {10, 20, 30, 40, 50, 25, 5, 15, 27, 60, 1, 3, 7, 45};
for (int v : vals) t.insert(v);
assert(t.validate() && "нарушение после вставки");
for (int v : vals) assert(t.contains(v));
for (int v : {30, 10, 50, 1, 7, 45}) t.erase(v);
assert(t.validate() && "нарушение после удаления");
assert(!t.contains(30) && !t.contains(45));
std::vector<int> out = t.sorted();
assert(std::is_sorted(out.begin(), out.end()));
for (std::size_t i = 0; i < out.size(); ++i)
std::cout << out[i] << (i + 1 == out.size() ? '\n' : ' ');
return 0;
}
Замечания по реализации.
fixupпродолжает подъём до корня и для вставки, и для удаления. Для вставки можно остановиться после первого поворота — это микрооптимизация; корректность от неё не зависит.- При удалении узла с двумя детьми ключ преемника копируется, а физически удаляется узел с одним ребёнком. Это требует копируемости ключа; для некопируемых типов переносят узел целиком.
- Рекурсивные
check,inorder,destroyбезопасны: высота [math]\displaystyle{ O(\log n) }[/math] гарантирует малую глубину стека. - Копирование контейнера отключено: корректная копия требует клонирования всех узлов и переноса родительских ссылок. При необходимости реализуйте правило трёх/пяти.
Сводная таблица сложности
| Операция | Худший случай | Средний случай | Амортизированная | Память | Поворотов |
|---|---|---|---|---|---|
| Поиск | [math]\displaystyle{ O(\log n) }[/math] | [math]\displaystyle{ O(\log n) }[/math] | [math]\displaystyle{ O(\log n) }[/math] | [math]\displaystyle{ O(1) }[/math] | 0 |
| Вставка | [math]\displaystyle{ O(\log n) }[/math] | [math]\displaystyle{ O(\log n) }[/math] | [math]\displaystyle{ O(\log n) }[/math] | [math]\displaystyle{ O(1) }[/math] | ≤ 1 (одинарный или двойной) |
| Удаление | [math]\displaystyle{ O(\log n) }[/math] | [math]\displaystyle{ O(\log n) }[/math] | [math]\displaystyle{ O(\log n) }[/math] | [math]\displaystyle{ O(1) }[/math] | до [math]\displaystyle{ O(\log n) }[/math] |
| Минимум / максимум | [math]\displaystyle{ O(\log n) }[/math] | — | — | [math]\displaystyle{ O(1) }[/math] | 0 |
| Обход по возрастанию | [math]\displaystyle{ O(n) }[/math] | [math]\displaystyle{ O(n) }[/math] | [math]\displaystyle{ O(n) }[/math] | [math]\displaystyle{ O(\log n) }[/math] стека | 0 |
| Память структуры | [math]\displaystyle{ O(n) }[/math] | — | — | 3 указателя + 1 счётчик высоты на узел | — |
Примечание. Границы худшего случая детерминированы и не зависят от порядка вставок. Главное отличие от красно-чёрного дерева — число поворотов при удалении: у АВЛ это [math]\displaystyle{ O(\log n) }[/math], у КЧ — не более 3. Поэтому АВЛ выгоднее при редких удалениях и частых поисках.
Трассировка примера
Вставим [math]\displaystyle{ 10, 20, 30, 40, 50, 25 }[/math] в пустое дерево. Столбец «Дерево» записан в порядке возрастания.
| Шаг | Ключ | Дерево (по возрастанию) | Балансировка |
|---|---|---|---|
| 1 | 10 | 10 | корень, BF = 0 |
| 2 | 20 | 10 → 20 | BF(10) = −1, поворот не нужен |
| 3 | 30 | 10 → 20 → 30 | BF(10) = −2, случай RR → Left-Rotate(10): корень 20, дети 10 и 30 |
| 4 | 40 | 10, 20, 30, 40 | BF(30) = −1, всё в норме |
| 5 | 50 | 10, 20, 30, 40, 50 | BF(30) = −2, случай RR → Left-Rotate(30): поднимается 40 |
| 6 | 25 | 10, 20, 25, 30, 40, 50 | BF(20) = −2, BF(40) = +1, случай RL → Right-Rotate(40), Left-Rotate(20): корень 30 |
Итоговое дерево шага 6:
30
/ \
20 40
/ / \
10 25 50
Во всех узлах [math]\displaystyle{ |\text{BF}| \le 1 }[/math]: у 20 слева 10, справа пусто (BF = +1); у 40 дети 25 и 50 (BF = 0); у 30 поддеревья равной высоты (BF = 0). Балансировка шага 6 — единственный случай, потребовавший двух поворотов; остальные обошлись одним (или ни одним).
Корректность и оценка сложности
Дерево высоты [math]\displaystyle{ h }[/math] имеет корень и два поддерева. Чтобы минимизировать число узлов, нужно, чтобы одно поддерево имело высоту [math]\displaystyle{ h-1 }[/math], а другое — не менее [math]\displaystyle{ h-2 }[/math] (разность высот не превосходит 1, и одно из поддеревьев обязательно имеет высоту [math]\displaystyle{ h-1 }[/math], иначе высота дерева была бы меньше [math]\displaystyle{ h }[/math]). Минимумы слагаются: [math]\displaystyle{ N(h) = N(h-1) + N(h-2) + 1 }[/math]. База очевидна.
Подстановкой: [math]\displaystyle{ F(h+3) - 1 = (F(h+2)-1) + (F(h+1)-1) + 1 }[/math], что совпадает с рекуррентностью [math]\displaystyle{ F(k) = F(k-1) + F(k-2) }[/math]; базы [math]\displaystyle{ N(0) = F(3)-1 = 1 }[/math] и [math]\displaystyle{ N(1) = F(4)-1 = 2 }[/math] сходятся.
Так как [math]\displaystyle{ n \ge N(h) = F(h+3) - 1 }[/math] и [math]\displaystyle{ F(k) \ge \varphi^{\,k}/\sqrt5 }[/math] (стандартная оценка чисел Фибоначчи через золотое сечение [math]\displaystyle{ \varphi }[/math]), получаем
[math]\displaystyle{ n + 1 \ge \frac{\varphi^{\,h+3}}{\sqrt5} \;\Longrightarrow\; h \le \log_\varphi\!(\sqrt5\,(n+1)) - 3 = \frac{\log_2(\sqrt5\,(n+1))}{\log_2\varphi} - 3 \le 1.44\,\log_2(n+2). }[/math]
Следствия. Поиск, минимум/максимум и поиск преемника выполняют [math]\displaystyle{ O(\log n) }[/math] шагов спуска. Вставка и удаление проходят путь до корня, выполняя [math]\displaystyle{ O(1) }[/math] работы на уровень: [math]\displaystyle{ O(\log n) }[/math] времени и [math]\displaystyle{ O(1) }[/math] дополнительной памяти. При вставке поворот один, потому что он восстанавливает прежнюю высоту поддерева; при удалении поворот уменьшает высоту, поэтому балансировка может подниматься до корня — до [math]\displaystyle{ O(\log n) }[/math] поворотов.
Инвариант-аргумент для поворота. Одинарный поворот в разбалансированном узле [math]\displaystyle{ x }[/math] восстанавливает [math]\displaystyle{ |\text{BF}(x)| \le 1 }[/math]: если левое поддерево было выше на 2, а его ребёнок имел баланс [math]\displaystyle{ \ge 0 }[/math], то после правого поворота высоты детей нового корня различаются не более чем на 1, а общая высота поддерева равна прежней (до вставки). Двойной поворот сначала превращает зигзаг в цепочку, затем выправляет её. В обоих случаях BST-порядок сохраняется, так как переставляются только связи, а среднее поддерево перевешивается, как в псевдокоде.
Сравнение с альтернативами
| Структура | Поиск (худший) | Вставка | Удаление | Поворотов при удалении | Высота | Когда выбирать |
|---|---|---|---|---|---|---|
| Несбалансированное BST | [math]\displaystyle{ O(n) }[/math] | [math]\displaystyle{ O(n) }[/math] | [math]\displaystyle{ O(n) }[/math] | 0 | до [math]\displaystyle{ n-1 }[/math] | статические данные |
| АВЛ-дерево | [math]\displaystyle{ O(\log n) }[/math] | [math]\displaystyle{ O(\log n) }[/math], ≤ 1 поворот | [math]\displaystyle{ O(\log n) }[/math] | до [math]\displaystyle{ O(\log n) }[/math] | [math]\displaystyle{ \le 1.44\log_2(n{+}2) }[/math] | поиск преобладает над записью |
| Красно-чёрное дерево | [math]\displaystyle{ O(\log n) }[/math] | [math]\displaystyle{ O(\log n) }[/math], ≤ 2 поворота | [math]\displaystyle{ O(\log n) }[/math], ≤ 3 поворота | ≤ 3 | [math]\displaystyle{ \le 2\log_2(n{+}1) }[/math] | универсальное; std::map, TreeMap
|
| B-дерево / B⁺-дерево | [math]\displaystyle{ O(\log_t n) }[/math] | [math]\displaystyle{ O(\log_t n) }[/math] | [math]\displaystyle{ O(\log_t n) }[/math] | — | страничная | диск, СУБД |
| Хеш-таблица | [math]\displaystyle{ O(n) }[/math] худший, [math]\displaystyle{ O(1) }[/math] средний | [math]\displaystyle{ O(1) }[/math] средний | [math]\displaystyle{ O(1) }[/math] средний | — | — | порядок не нужен |
Вердикт. АВЛ-дерево даёт меньшую высоту, а значит, меньше обращений к памяти при поиске — это важно для читающих нагрузок. Красно-чёрное дерево при чуть большей высоте делает заметно меньше перестроек при записи, поэтому побеждает в контейнерах общего назначения. Для данных на диске выбирают B-деревья, для неупорядоченного доступа — хеш-таблицы.
Где применяется
- Индексы в оперативной памяти для чтения. Когда запросов «найти» много, а вставок и удалений мало, меньшая высота АВЛ-дерева сокращает среднее число сравнений и обращений к кэшу. Именно поэтому АВЛ выбирают для read-mostly индексов.
- Словари и проверка орфографии. Большие списки слов читаются многократно и почти не меняются; при этом важна гарантия худшего случая [math]\displaystyle{ O(\log n) }[/math] на уровне отдельных букв в разветвлённых структурах предков.
- Вычислительная геометрия. В алгоритмах заметающей прямой (sweep line) статус-структура хранит упорядоченное множество активных отрезков; жёсткая граница высоты удобна для оценки времени и памяти.
- Системы с требованием ограниченного времени отклика. В реальном времени стабильное ограничение на высоту даёт предсказуемое число операций на критическом пути; рандомизированные структуры (treap) тут менее удобны.
- Библиотеки и учебный код. Существуют свободные реализации АВЛ (например, библиотека
libavl, известная в учебной литературе ⚠️ требует проверки точных деталей). Контраст: стандартныеstd::map/std::set(C++),java.util.TreeMapиSortedDictionary(.NET) используют красно-чёрное дерево, поскольку пишущие операции с ним дешевле.
Историческая справка
- 1962. Г. М. Адельсон-Вельский и Е. М. Ландис опубликовали статью «Об одном алгоритме организации информации», где предложили первый сбалансированный по высоте BST [3]. Инициалы авторов дали структуре имя AVL (АВЛ).
- 1970-е. Т. А. Норбс и другие формализовали повороты и правило их выбора; в учебнике Кнута (том 3, §6.2.3 «Balanced trees») АВЛ-деревья изложены в классическом виде [2].
- 1972. Р. Байер ввёл симметричные двоичные B-деревья — идейную основу будущих красно-чёрных деревьев [5].
- 1978. Л. Гийба и Р. Седжвик предложили красно-чёрные деревья как более «пишуще-дружелюбную» альтернативу; с тех пор в контейнерах общего назначения преобладают они [5].
- Название структуры — просто аббревиатура фамилий изобретателей, а не характеристика.
Типичные ошибки и подводные камни
- Перепутать соглашение о высоте. Если принять [math]\displaystyle{ h(\text{лист}) = 1 }[/math], все формулы сдвигаются. Выберите одно: здесь [math]\displaystyle{ h(\text{NIL}) = -1 }[/math], [math]\displaystyle{ h(\text{лист}) = 0 }[/math], и соблюдайте везде.
- Обновлять высоты в неверном порядке. После поворота высоты пересчитывают сначала у опущенного узла [math]\displaystyle{ x }[/math], затем у поднятого [math]\displaystyle{ y }[/math]: иначе [math]\displaystyle{ y }[/math] посчитает себя через устаревшую высоту [math]\displaystyle{ x }[/math].
- Считать, что при удалении хватит одного поворота. Это верно для вставки, но не для удаления: высота поддерева уменьшилась, и нарушение может подняться к корню — до [math]\displaystyle{ O(\log n) }[/math] поворотов.
- Забыть про случай BF ребёнка = 0. При удалении у ребёнка разбалансированного узла баланс может быть 0; тогда достаточно одинарного поворота (знак
>= 0/<= 0в правиле выбора). - Потерять ссылку на родителя при перевешивании среднего поддерева. Средний ребёнок меняет родителя; если этого не сделать,
fixupпойдёт не туда. - Спутать знак BF и сторону поворота. [math]\displaystyle{ \text{BF} \gt 1 }[/math] — перевес левого поддерева, лечится правым поворотом; знаки удобно проверять на маленьком примере.
- Рекурсивный деструктор и сортировка. При корректных инвариантах глубина [math]\displaystyle{ O(\log n) }[/math] безопасна; но если инвариант уже нарушен и дерево выродилось, рекурсия может переполнить стек.
- Путать АВЛ и КЧ по числу поворотов. Утверждение «вставка — один поворот» относится к АВЛ; для красно-чёрного дерева это «не более двух», но зато удаление — «не более трёх».
- Дубликаты. Обычное BST-условие строгое; для мультимножества нужен счётчик повторов в узле, иначе повторные вставки будут молча отброшены.
Задачи для практики
- Проверка АВЛ за [math]\displaystyle{ O(n) }[/math]. Дано двоичное дерево. Проверьте BST-свойство и условие [math]\displaystyle{ |\text{BF}| \le 1 }[/math]. Подсказка: рекурсивно возвращайте высоту и признак корректности. Ответ: один обход, [math]\displaystyle{ O(n) }[/math] времени, [math]\displaystyle{ O(\log n) }[/math] стека.
- Число поворотов при вставке. Докажите, что вставка в АВЛ требует не более одного поворота (одинарного или двойного). Подсказка: поворот возвращает высоту поддерева к прежнему значению.
- Высота vs число узлов. Постройте минимальное АВЛ-дерево высоты [math]\displaystyle{ h = 4 }[/math] и [math]\displaystyle{ h = 5 }[/math]. Сколько в них узлов? Подсказка: рекуррентность [math]\displaystyle{ N(h) = N(h-1)+N(h-2)+1 }[/math]. Ответ: 12 и 20.
- Удаление с балансом 0. Приведите пример, где после удаления баланс ребёнка равен 0, и покажите, что одинарного поворота достаточно.
- Построение за [math]\displaystyle{ O(n) }[/math]. По отсортированному массиву постройте АВЛ-дерево за [math]\displaystyle{ O(n) }[/math]. Подсказка: делите пополам, соединяйте поддеревья.
- Порядковая статистика. Добавьте размер поддерева и реализуйте
select(k)/rank(key)за [math]\displaystyle{ O(\log n) }[/math]. Подсказка: пересчитывайте размер при поворотах. - Диапазонный вывод. Выведите ключи в [math]\displaystyle{ [a,b] }[/math] за [math]\displaystyle{ O(\log n + k) }[/math]. Подсказка: рекурсивный обход с отсечением поддеревьев вне диапазона.
- Сравнение с КЧ. Сгенерируйте 100 000 случайных операций и посчитайте суммарное число поворотов в АВЛ и КЧ. Подсказка: при удалениях АВЛ, как правило, делает больше поворотов.
Связанные темы
- Двоичное дерево поиска — базовая структура, над которой надстроена балансировка.
- Красно-чёрное дерево — менее строгий баланс, меньше поворотов при записи.
- B-дерево — страничная балансировка для дисков.
- 2-3-4 дерево — изоморф красно-чёрному дереву.
- Splay-дерево — амортизированная альтернатива.
- Декартово дерево — рандомизированное упорядоченное дерево.
- Хеш-таблица — альтернатива, когда порядок не нужен.
- Асимптотическая сложность — нотация [math]\displaystyle{ O }[/math], [math]\displaystyle{ \Omega }[/math], [math]\displaystyle{ \Theta }[/math].
Источники
- Cormen T. H., Leiserson C. E., Rivest R. L., Stein C. Introduction to Algorithms (CLRS). 3rd ed. — MIT Press, 2009. — Гл. 12 «Binary Search Trees», гл. 13 «Red-Black Trees» (повороты и сбалансированные деревья).
- Knuth D. E. The Art of Computer Programming. Vol. 3: Sorting and Searching. — Addison-Wesley, 2nd ed., 1998. — §6.2.3 «Balanced Trees».
- Адельсон-Вельский Г. М., Ландис Е. М. Об одном алгоритме организации информации // Доклады АН СССР. — 1962. — Т. 146, № 2. — С. 263–266.
- Sedgewick R., Wayne K. Algorithms. 4th ed. — Addison-Wesley, 2011. — Гл. 3.3 «Balanced Search Trees».
- Guibas L. J., Sedgewick R. A Dichromatic Framework for Balanced Trees // FOCS. — 1978 (проверено); Bayer R. Symmetric Binary B-Trees // Acta Informatica. — 1972. — Vol. 1, No. 4. — P. 290–306.
- Wikipedia: AVL tree. URL: https://en.wikipedia.org/wiki/AVL_tree.