АВЛ-дерево: различия между версиями

Версия 00:28, 9 октября 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]

Рис. 1. Слева допустимое АВЛ-дерево: у всех узлов [math]\displaystyle{ |\text{BF}| \le 1 }[/math]. Справа цепочка из трёх узлов: у корня 30 левое поддерево выше правого на 2, [math]\displaystyle{ \text{BF}(30) = +2 }[/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 — зеркальная операция.

Рис. 2. Случай LL (левая цепочка) выправляется правым поворотом, случай RR (правая цепочка) — левым. Средний по ключу узел становится корнем, у всех узлов BF возвращается к 0.

Четыре случая. Первый узел на пути вверх, где [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]	средний — корень

Рис. 3. Случаи LR и RL — «зигзаги». Их выправляют два поворота подряд; медиана по ключу становится корнем поддерева.

Операция: вставка (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.

Рис. 4. Состояния после балансировки при вставке [math]\displaystyle{ 10, 20, 30, 40, 50, 25 }[/math]. Видны случай RR (панели 2–3) и случай RL с двойным поворотом (панель 4).

Крайние случаи. Вставка в пустое дерево — новый узел сразу корень. Вставка ключа, который уже есть, — отклоняется. Случай, когда перевес уходит в одну сторону цепочкой, немедленно исправляется одинарным поворотом.

Операция: удаление (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 (ситуация, невозможная при вставке, но возможная при удалении), достаточно одинарного поворота.

Рис. 5. Слева — правило выбора поворота по балансу ребёнка. Справа — почему после поворота нужно продолжать вверх: высота поддерева уменьшилась, и баланс предка мог снова нарушиться.

Операция: поиск (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{ N(h) }[/math] минимальное число узлов АВЛ-дерева высоты [math]\displaystyle{ h }[/math]. Тогда [math]\displaystyle{ N(0) = 1, \quad N(1) = 2, \quad N(h) = N(h-1) + N(h-2) + 1. }[/math]

Доказательство:

Дерево высоты [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{ \blacksquare }[/math]

Лемма (связь с числами Фибоначчи):

[math]\displaystyle{ N(h) = F(h+3) - 1 }[/math], где [math]\displaystyle{ F_1 = F_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{ \blacksquare }[/math]

Теорема (оценка высоты):

Высота АВЛ-дерева с [math]\displaystyle{ n }[/math] узлами удовлетворяет [math]\displaystyle{ h \le 1.44\,\log_2(n+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{ \blacksquare }[/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-порядок сохраняется, так как переставляются только связи, а среднее поддерево перевешивается, как в псевдокоде.

Рис. 6. Минимальные АВЛ-деревья высот 0–3 содержат [math]\displaystyle{ 1, 2, 4, 7 }[/math] узлов. Рост числа узлов как степень [math]\displaystyle{ \varphi }[/math] даёт оценку [math]\displaystyle{ h \le 1.44\log_2(n+2) }[/math].

Сравнение с альтернативами

Структура	Поиск (худший)	Вставка	Удаление	Поворотов при удалении	Высота	Когда выбирать
Несбалансированное 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] средний	—	—	порядок не нужен

Рис. 7. Худшая высота при [math]\displaystyle{ n = 10^6 }[/math]: АВЛ [math]\displaystyle{ \le 29 }[/math], красно-чёрное [math]\displaystyle{ \le 40 }[/math], B-дерево с [math]\displaystyle{ t=32 }[/math] — около 4, вырожденное BST — до [math]\displaystyle{ 10^6 }[/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.

@@ Строка 664: / Строка 664: @@
 # Wikipedia: AVL tree. URL: https://en.wikipedia.org/wiki/AVL_tree.
-[[Category:Алгоритмы и структуры данных | Деревья поиска]]
+[[Category:Алгоритмы и структуры данных]]
+[[Category:Деревья поиска]]

Поиск

Навигация

АВЛ-дерево: различия между версиями

Версия 00:28, 9 октября 2026

Содержание

TL;DR

Определения

Мотивация и интуиция

Устройство

Операции и алгоритмы

Операция: поворот (rotation)

Операция: вставка (insert)

Операция: удаление (delete)

Операция: поиск (search)

Реализация структуры на C++

Сводная таблица сложности

Трассировка примера

Корректность и оценка сложности

Сравнение с альтернативами

Где применяется

Историческая справка

Типичные ошибки и подводные камни

Задачи для практики

Связанные темы

Источники