АА-дерево

TL;DR

АА-дерево (AA tree, дерево Андерссона) — это двоичное дерево поиска, в котором вместо цвета узла, как в красно-чёрном дереве, хранится целое число — уровень. Дерево устроено так, что проигрывает в структуре 2-3-дереву: горизонтальная (правого наклона) связь кодирует 3-узел. Вся балансировка сводится к двум операциям — skew и split, — поэтому код выходит заметно короче, чем у КЧ-дерева. Все операции поиска, вставки и удаления выполняются за [math]\displaystyle{ O(\log n) }[/math] в худшем случае, без рандомизации.

Свойство	Значение
Класс	Двоичное дерево поиска (binary search tree, BST) с балансировкой
Другое название	Дерево Андерссона (Arne Andersson tree), «AA» — инициалы автора
Изобретение	Арне Андерссон (Arne Andersson), 1993, WADS '93 [1]
Основа	Вариант красно-чёрного дерева, моделирующий 2-3-дерево (красные связи только справа)
Поиск (худший / средний)	[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(\log n) }[/math]; [math]\displaystyle{ O(\log n) }[/math] поворотов по пути вверх
Обход по возрастанию	[math]\displaystyle{ O(n) }[/math]
Память	[math]\displaystyle{ O(n) }[/math]; целое «уровень» на узел (до [math]\displaystyle{ \lceil\log_2\log_2(n{+}1)\rceil }[/math] бит, на практике 1 байт)
Упорядоченность	Да; итерация даёт ключи по возрастанию
Детерминированность	Да; рандомизация не требуется
Альтернативы	Красно-чёрное дерево, АВЛ-дерево, 2-3-дерево, декартово дерево (treap), B-дерево, хеш-таблица
Где встречается	Открытые реализации (C, Java, Scala), учебные курсы по структурам данных, расширяемые деревья (interval / order-statistic)

Определения

АА-дерево — двоичное дерево поиска, каждому узлу [math]\displaystyle{ x }[/math] которого сопоставлено натуральное число [math]\displaystyle{ \mathrm{level}(x) }[/math] (уровень), а на уровни наложены пять инвариантов. Для внешнего узла NIL полагаем [math]\displaystyle{ \mathrm{level}(\text{NIL}) = 0 }[/math].

Инварианты АА-дерева.

Уровень каждого листа равен единице: если у узла нет детей, то [math]\displaystyle{ \mathrm{level}(x) = 1 }[/math].
Уровень левого ребёнка ровно на единицу меньше уровня родителя: [math]\displaystyle{ \mathrm{level}(\text{left}) = \mathrm{level}(x) - 1 }[/math].
Уровень правого ребёнка равен уровню родителя или на единицу меньше: [math]\displaystyle{ \mathrm{level}(\text{right}) \in \{\mathrm{level}(x)-1,\ \mathrm{level}(x)\} }[/math].
Уровень правого внука строго меньше уровня деда: [math]\displaystyle{ \mathrm{level}(\text{right}[\text{right}]) \lt \mathrm{level}(x) }[/math].
Любой узел уровня больше единицы имеет двух детей.

Алгоритмы балансировки поддерживают дополнительное свойство, эквивалентное «отсутствию пропусков уровней»: у любого узла с детьми [math]\displaystyle{ \mathrm{level}(x) = \min(\mathrm{level}(\text{left}), \mathrm{level}(\text{right})) + 1 }[/math] (его обеспечивают Decrease-Level и Split). Отсюда, в частности, правый ребёнок узла уровня [math]\displaystyle{ L }[/math] имеет уровень не меньше [math]\displaystyle{ L-1 }[/math]; это используется в разделе «Корректность и оценка сложности».

Горизонтальная связь (horizontal link) — ребро, у которого уровень ребёнка равен уровню родителя. По инвариантам 2 и 3 горизонтальной может быть только правая связь (у левого ребёнка уровень строго меньше). Горизонтальная связь аналогична красному ребру в КЧ-дереве. Горизонтальная связь и её нижний узел вместе кодируют один 3-узел 2-3-дерева [1][3].

Уровень (level) узла — величина, обратная «высоте» 2-3-дерева: листья имеют уровень 1, и уровень растёт вверх к корню. Уровень не равен высоте поддерева в смысле числа рёбер, но связан с ней: чем выше уровень, тем больше узлов обязано быть в поддереве (см. «Корректность и оценка сложности»).

Обозначения. [math]\displaystyle{ n }[/math] — число хранимых ключей; [math]\displaystyle{ h }[/math] — высота дерева (число рёбер на самом длинном пути от корня до листа); [math]\displaystyle{ L }[/math] — уровень корня. [math]\displaystyle{ \log }[/math] всюду означает логарифм по основанию 2. Для узла [math]\displaystyle{ x }[/math] запись [math]\displaystyle{ \text{key}[x] }[/math] обозначает ключ, [math]\displaystyle{ \text{left}[x] }[/math], [math]\displaystyle{ \text{right}[x] }[/math] — детей. Поддерживается BST-свойство: для любого узла [math]\displaystyle{ x }[/math] все ключи левого поддерева меньше [math]\displaystyle{ \text{key}[x] }[/math], а правого — больше.

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

Красно-чёрное дерево — стандарт для упорядоченных контейнеров, но его балансировка громоздка: вставка разбирает три случая, удаление — четыре, а с учётом зеркальной симметрии число «форм» доходит до семи [2]. Каждый случай нужно реализовать и не перепутать порядок обработки — именно здесь чаще всего возникают ошибки.

Андерссон заметил, что если запретить левые красные рёбра и оставить только правые, то структура перестаёт кодировать 2-3-4-дерево и начинает кодировать более простое 2-3-дерево [1]. В 2-3-дереве у каждого внутреннего узла 2 или 3 ребёнка, а не 2–4, поэтому форм для разбора остаётся всего две. Их и реализуют операции skew и split:

skew убирает левую горизонтальную связь одним правым поворотом;
split убирает две подряд идущие правые горизонтальные связи левым поворотом с повышением уровня.

Ключевая идея: не разбирать геометрию «дядьёв и племянников», как в КЧ-дереве, а выполнять эти две нормализующие операции на каждом узле пути — они сами ничего не делают, если нарушения нет. Балансировка становится почти механической, а доказательство корректности — коротким.

Устройство

Узел АА-дерева хранит:

ключ (key);
целое level (начинается с 1 у листа);
указатели left и right (при необходимости — parent для итеративной реализации).

Внешние ссылки ведут в NIL с уровнем 0 либо просто равны nullptr.

Дерево удовлетворяет пяти инвариантам из раздела «Определения». Инвариант 2 делает «левый наклон» строго регулярным: спускаясь по левым рёбрам, мы на каждом шаге теряем один уровень. Инвариант 3 разрешает правому ребёнку оставаться на том же уровне — это и есть горизонтальная связь. Инвариант 4 запрещает две горизонтальные связи подряд, а инвариант 5 гарантирует, что «висячих» узлов высокого уровня нет.

Отсюда — картина, показанная на рис. 1: последовательность «блоков» вида «чёрная вершина плюс необязательная правая горизонтальная связь». Каждый такой блок — один узел 2-3-дерева: либо 2-узел (одна вершина), либо 3-узел (вершина и её правый горизонтальный ребёнок).

Рис. 1. Слева АА-дерево: в каждом узле указан уровень; горизонтальная связь [math]\displaystyle{ 40 \to 60 }[/math] соединяет узлы уровня 2. Справа то же дерево как 2-3-дерево: связь [math]\displaystyle{ 40 \to 60 }[/math] кодирует 3-узел [math]\displaystyle{ \{40, 60\} }[/math] с тремя детьми [math]\displaystyle{ 20, 50, 70 }[/math].

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

Операция: skew (устранение левой горизонтальной связи)

Идея. Если левый ребёнок узла имеет тот же уровень, что и сам узел, значит, появилась запрещённая левая горизонтальная связь. Один правый поворот переводит её в разрешённую правую.

Пошаговое описание (рис. 2).

Пусть [math]\displaystyle{ L \leftarrow \text{left}[T] }[/math].
Перевесить правое поддерево [math]\displaystyle{ L }[/math] (узел [math]\displaystyle{ \beta }[/math]) левым ребёнком [math]\displaystyle{ T }[/math]: [math]\displaystyle{ \text{left}[T] \leftarrow \text{right}[L] }[/math].
Сделать [math]\displaystyle{ T }[/math] правым ребёнком [math]\displaystyle{ L }[/math]: [math]\displaystyle{ \text{right}[L] \leftarrow T }[/math].
Вернуть [math]\displaystyle{ L }[/math] как новый корень поддерева.

Инвариант. Порядок ключей сохраняется; если горизонтальной левой связи не было, операция ничего не меняет.

Псевдокод.

Алгоритм Skew(T)
Вход:  T — корень поддерева АА-дерева (или NIL)
Выход: корень поддерева без левой горизонтальной связи
Инвариант: BST-порядок сохранён; изменяются только связи T и left[T]

1  if T = NIL
2      return NIL
3  if left[T] ≠ NIL and level[left[T]] = level[T]
4      L ← left[T]
5      left[T] ← right[L]
6      right[L] ← T
7      return L
8  return T

Сложность: O(1) времени и памяти.

Корректность: после строк 4–6 выполняется порядок α < L < β < T < γ, где α = left[L], β = right[L], γ = right[T]; горизонтальной остаётся связь L → T.

Разбор примера. В дереве после вставок [math]\displaystyle{ 1,2,3 }[/math] (см. «Трассировка примера») левой горизонтальной связи нет. Появляется она, например, при удалении: уменьшив уровень узла, можно получить левого ребёнка того же уровня. Пусть поддерево — T(ур.2) с левым ребёнком L(ур.2). После Skew корнем становится L, а T — его правым ребёнком; левая горизонтальная связь превратилась в правую.

Крайние случаи. T = NIL или отсутствие левого ребёнка — возврат без изменений. Совпадение уровней ровно на единицу недопустимо: skew срабатывает только при [math]\displaystyle{ \mathrm{level}(\text{left}) = \mathrm{level}(T) }[/math].

Рис. 2. skew(T): когда левый ребёнок [math]\displaystyle{ B }[/math] имеет тот же уровень, что и [math]\displaystyle{ A }[/math], правый поворот поднимает [math]\displaystyle{ B }[/math]; левая горизонтальная связь становится правой.

Операция: split (устранение двух правых горизонтальных связей)

Идея. Если у узла правый ребёнок и правый внук имеют тот же уровень, что и сам узел, то стоят две горизонтальные связи подряд. Левый поворот поднимает средний узел и увеличивает его уровень на единицу; три узла уровня [math]\displaystyle{ k }[/math] превращаются в «домик» с корнем уровня [math]\displaystyle{ k+1 }[/math].

Пошаговое описание (рис. 3).

Если правого ребёнка или правого внука нет — вернуть [math]\displaystyle{ T }[/math] без изменений.
Пусть [math]\displaystyle{ R \leftarrow \text{right}[T] }[/math].
Перевесить левое поддерево [math]\displaystyle{ R }[/math] (узел [math]\displaystyle{ \delta }[/math]) правым ребёнком [math]\displaystyle{ T }[/math]: [math]\displaystyle{ \text{right}[T] \leftarrow \text{left}[R] }[/math].
Сделать [math]\displaystyle{ T }[/math] левым ребёнком [math]\displaystyle{ R }[/math]: [math]\displaystyle{ \text{left}[R] \leftarrow T }[/math].
Увеличить уровень: [math]\displaystyle{ \mathrm{level}[R] \leftarrow \mathrm{level}[R] + 1 }[/math].
Вернуть [math]\displaystyle{ R }[/math].

Инвариант. Порядок ключей сохраняется; если двух горизонтальных связей подряд не было, операция ничего не меняет.

Псевдокод.

Алгоритм Split(T)
Вход:  T — корень поддерева; допускаются две подряд правые горизонтальные связи
Выход: корень поддерева без двух подряд идущих правых горизонтальных связей
Инвариант: средний узел цепочки поднимается на уровень выше

1  if T = NIL or right[T] = NIL or right[right[T]] = NIL
2      return T
3  if level[T] = level[right[right[T]]]
4      R ← right[T]
5      right[T] ← left[R]
6      left[R] ← T
7      level[R] ← level[R] + 1
8      return R
9  return T

Сложность: O(1) времени и памяти.

Корректность: после строк 4–6 порядок α < T < δ < R < ε < C < ζ сохранён, где δ = left[R], а ε, ζ — поддеревья вершины C = right[R].

Разбор примера. Вставляем в пустое дерево ключи [math]\displaystyle{ 1, 2, 3 }[/math]. После вставки [math]\displaystyle{ 3 }[/math] образуется цепочка [math]\displaystyle{ 1 \to 2 \to 3 }[/math] с двумя правыми горизонтальными связями. Вызов Split(1) поднимает узел [math]\displaystyle{ 2 }[/math] до уровня 2 и делает его корнем; [math]\displaystyle{ 1 }[/math] и [math]\displaystyle{ 3 }[/math] становятся его детьми уровня 1. Дерево становится сбалансированным (рис. 4, панель «1, 2, 3»).

Крайние случаи. Если правого внука нет, условие строки 3 ложно и split возвращает [math]\displaystyle{ T }[/math]; именно поэтому split безопасно вызывать на каждом узле. Уровень повышается только здесь — это единственное место, где дерево «растёт вверх» после вставки.

Рис. 3. split(T): при двух правых горизонтальных связях левый поворот поднимает средний узел [math]\displaystyle{ B }[/math] на уровень выше; [math]\displaystyle{ A }[/math] и [math]\displaystyle{ C }[/math] становятся его детьми.

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

Идея. Сначала действовать как в обычном BST, добавив лист уровня 1. Затем на обратном пути вверх на каждом узле сначала выполнить skew, потом split. Две операции сами восстанавливают все инварианты, если вызывать их безусловно.

Пошаговое описание.

Спуститься от корня по BST-правилу; если узел пуст — создать лист уровня 1.
Дубликат: вернуть узел без изменений.
На каждом узле пути вверх: [math]\displaystyle{ T \leftarrow \text{Skew}(T) }[/math].
На каждом узле пути вверх: [math]\displaystyle{ T \leftarrow \text{Split}(T) }[/math].

Инвариант. После обработки поддерева с корнем [math]\displaystyle{ x }[/math] это поддерево снова удовлетворяет инвариантам 1–5.

Псевдокод.

Алгоритм AA-Insert(T, key)
Вход:  T — корень дерева (или NIL); key — вставляемый ключ
Выход: корень дерева с ключом key; дубликат игнорируется
Инвариант: на обратном пути каждый узел сначала проходит Skew, затем Split

1  if T = NIL
2      return новый узел(key, level = 1)
3  if key < key[T]
4      left[T] ← AA-Insert(left[T], key)
5  else if key > key[T]
6      right[T] ← AA-Insert(right[T], key)
7  else
8      return T
9  T ← Skew(T)
10 T ← Split(T)
11 return T

Сложность: O(log n) времени; O(log n) стека при рекурсии либо O(1) дополнительной памяти при итеративной реализации. Число поворотов — O(log n).

Корректность: см. «Корректность и оценка сложности» (инвариант-аргумент).

Разбор примера. Полная трассировка вставки [math]\displaystyle{ 1,2,3,4,5,6,7 }[/math] — в разделе «Трассировка примера» и на рис. 4. После каждой вставки skew устраняет возможную левую горизонтальную связь, а split — две правые; наиболее интересен шаг с ключом 7, где split срабатывает дважды подряд (сначала на узле 5, затем на узле 2) и корнем становится узел 4 уровня 3.

Крайние случаи. Вставка в пустое дерево даёт один лист уровня 1. Вставка дубликата не меняет дерево (можно завести счётчик для мультимножества). Если вставка происходит только в левое поддерево, split может вовсе не сработать, а skew — сработать один раз.

Рис. 4. Четыре состояния при вставке ключей [math]\displaystyle{ 1..7 }[/math]: split срабатывает над узлом 1 (после 3), над узлом 3 (после 5) и дважды после 7 (над узлами 5 и 2). Итоговое дерево идеально сбалансировано, корень 4 имеет уровень 3.

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

Идея. Свести удаление внутреннего узла к удалению листа, обменяв ключ с преемником. После удаления уровень узлов на пути вверх мог «просесть», поэтому сначала понижаем уровни (Decrease-Level), а затем нормализуем уровень операциями skew и split — уже не только над самим узлом, но и над его правым ребёнком (и правым внуком).

Пошаговое описание.

Найти узел по BST-правилу.
Если это лист — вернуть NIL. Если у узла есть только правый ребёнок (левый невозможен по инвариантам) — вернуть этого ребёнка.
Если у узла два ребёнка — найти преемника [math]\displaystyle{ S }[/math] (вправо один раз, затем влево до конца), скопировать его ключ в узел, рекурсивно удалить [math]\displaystyle{ S }[/math] из правого поддерева.
На пути вверх: [math]\displaystyle{ T \leftarrow \text{Decrease-Level}(T) }[/math].
[math]\displaystyle{ T \leftarrow \text{Skew}(T) }[/math]; [math]\displaystyle{ \text{right}[T] \leftarrow \text{Skew}(\text{right}[T]) }[/math]; при наличии правого внука [math]\displaystyle{ \text{right}[\text{right}[T]] \leftarrow \text{Skew}(\text{right}[\text{right}[T]]) }[/math].
[math]\displaystyle{ T \leftarrow \text{Split}(T) }[/math]; [math]\displaystyle{ \text{right}[T] \leftarrow \text{Split}(\text{right}[T]) }[/math].

Инвариант. После Decrease-Level уровень каждого узла равен [math]\displaystyle{ \min(\mathrm{level}(\text{left}), \mathrm{level}(\text{right})) + 1 }[/math], поэтому «пропусков уровней» нет; дальнейшие skew/split восстанавливают инварианты 2–5.

Псевдокод.

Алгоритм Decrease-Level(T)
Вход:  T — узел, чьи дети могли «просесть» после удаления
Выход: T с уменьшенным при необходимости уровнем
Инвариант: level[T] ≤ min(level[left[T]], level[right[T]]) + 1

1  should_be ← min(level[left[T]], level[right[T]]) + 1    # level[NIL] = 0
2  if should_be < level[T]
3      level[T] ← should_be
4      if right[T] ≠ NIL and should_be < level[right[T]]
5          level[right[T]] ← should_be
6  return T

Алгоритм AA-Delete(T, key)
Вход:  T — корень дерева (или NIL); key — удаляемый ключ
Выход: корень дерева без ключа key; инварианты восстановлены
Инвариант: на обратном пути выполняется Decrease-Level, затем Skew и Split

1  if T = NIL
2      return NIL
3  if key < key[T]
4      left[T] ← AA-Delete(left[T], key)
5  else if key > key[T]
6      right[T] ← AA-Delete(right[T], key)
7  else
8      if left[T] = NIL and right[T] = NIL
9          return NIL
10     else if left[T] = NIL
11         return right[T]                     # единственный ребёнок — правый
12     else
13         S ← Successor(T)                    # вправо один раз, затем влево до конца
14         key[T] ← key[S]
15         right[T] ← AA-Delete(right[T], key[S])
16 T ← Decrease-Level(T)
17 T ← Skew(T)
18 right[T] ← Skew(right[T])
19 if right[T] ≠ NIL and right[right[T]] ≠ NIL
20     right[right[T]] ← Skew(right[right[T]])
21 T ← Split(T)
22 right[T] ← Split(right[T])
23 return T

Сложность: O(log n) времени; O(log n) стека или O(1) дополнительной памяти.

Корректность: Decrease-Level убирает пропуски уровней, Skew и Split восстанавливают инварианты 2–5; см. «Корректность и оценка сложности».

Разбор примера. Удалим лист 7 из идеального дерева с корнем 4 (см. «Трассировка примера», рис. 5). Узел 6 лишается правого ребёнка; Decrease-Level(6) понижает его до уровня 1, затем Skew(6) поднимает узел 5. При подъёме узел 4 тоже становится уровня 2, а Skew(4) поднимает узел 2 в корень. Итоговое дерево: корень 2, справа 4 с детьми 3 и 5, у 5 правый горизонтальный ребёнок 6.

Крайние случаи. Удаление единственного узла даёт пустое дерево. У узла с двумя детьми важно искать именно преемника и не забыть, что после копирования ключа рекурсивное удаление идёт из правого поддерева. Если после Decrease-Level узел стал уровня 1 и у него один правый ребёнок — split не сработает, а skew может сработать на правом ребёнке.

Рис. 5. Удаление листа 7: Decrease-Level понижает узел 6, skew поднимает 5; при подъёме узел 4 понижается до уровня 2 и skew поднимает 2 в корень.

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

Идея. Поиск в АА-дереве ничем не отличается от поиска в обычном BST: балансировка лишь гарантирует, что высота невелика.

Алгоритм AA-Search(T, key)
Вход:  T — корень; key — искомый ключ
Выход: узел с ключом key либо NIL
Инвариант: если key присутствует, он лежит в поддереве с корнем T

1  while T ≠ NIL
2      if key < key[T]
3          T ← left[T]
4      else if key > key[T]
5          T ← right[T]
6      else
7          return T
8  return NIL

Сложность: O(log n) времени, O(1) памяти.

Операция: минимум, максимум, преемник

Минимум — спуск по левым ссылкам до NIL, максимум — по правым. Преемник узла при наличии правого поддерева — минимум правого поддерева; иначе — подъём по родителям до первого поворота влево. Все три операции — [math]\displaystyle{ O(\log n) }[/math].

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

Ниже — компактная реализация АА-дерева (рекурсивные вставка и удаление). Она следует псевдокоду выше; в конце блока — тест на краевых случаях. Индексация не нужна, узлы хранятся в куче.

#include <algorithm>
#include <cassert>
#include <iostream>
#include <vector>

struct Node {
    int key;
    int level;
    Node* left;
    Node* right;
    explicit Node(int k) : key(k), level(1), left(nullptr), right(nullptr) {}
};

class AATree {
    Node* root_ = nullptr;

    static int lvl(Node* t) { return t ? t->level : 0; }

    static Node* skew(Node* t) {
        if (!t) return nullptr;
        if (t->left && t->left->level == t->level) {
            Node* l = t->left;
            t->left = l->right;
            l->right = t;
            return l;
        }
        return t;
    }

    static Node* split(Node* t) {
        if (!t) return nullptr;
        if (t->right && t->right->right && t->right->right->level == t->level) {
            Node* r = t->right;
            t->right = r->left;
            r->left = t;
            r->level += 1;
            return r;
        }
        return t;
    }

    static Node* insert(Node* t, int key) {
        if (!t) return new Node(key);
        if (key < t->key) t->left = insert(t->left, key);
        else if (key > t->key) t->right = insert(t->right, key);
        else return t;                       // дубликат игнорируем
        t = skew(t);
        t = split(t);
        return t;
    }

    static Node* decrease_level(Node* t) {
        int should_be = std::min(lvl(t->left), lvl(t->right)) + 1;
        if (should_be < t->level) {
            t->level = should_be;
            if (t->right && should_be < t->right->level) t->right->level = should_be;
        }
        return t;
    }

    static Node* erase(Node* t, int key) {
        if (!t) return nullptr;
        if (key < t->key) t->left = erase(t->left, key);
        else if (key > t->key) t->right = erase(t->right, key);
        else {
            if (!t->left && !t->right) { delete t; return nullptr; }
            if (!t->left) { Node* r = t->right; delete t; return r; }
            Node* s = t->right;              // преемник
            while (s->left) s = s->left;
            t->key = s->key;
            t->right = erase(t->right, s->key);
        }
        t = decrease_level(t);
        t = skew(t);
        t->right = skew(t->right);
        if (t->right && t->right->right) t->right->right = skew(t->right->right);
        t = split(t);
        t->right = split(t->right);
        return t;
    }

    static void inorder(Node* t, std::vector<int>& out) {
        if (!t) return;
        inorder(t->left, out);
        out.push_back(t->key);
        inorder(t->right, out);
    }

    static void destroy(Node* t) {
        if (!t) return;
        destroy(t->left);
        destroy(t->right);
        delete t;
    }

public:
    ~AATree() { destroy(root_); }
    void insert(int k) { root_ = insert(root_, k); }
    void erase(int k) { root_ = erase(root_, k); }
    std::vector<int> keys() const {
        std::vector<int> out;
        inorder(root_, out);
        return out;
    }
};

int main() {
    AATree t;
    for (int i = 1; i <= 7; ++i) t.insert(i);
    assert((t.keys() == std::vector<int>{1, 2, 3, 4, 5, 6, 7}));
    t.insert(4);                              // дубликат
    assert(t.keys().size() == 7);
    t.erase(7);                               // лист
    assert((t.keys() == std::vector<int>{1, 2, 3, 4, 5, 6}));
    t.erase(4);                               // узел с двумя детьми
    assert((t.keys() == std::vector<int>{1, 2, 3, 5, 6}));
    std::cout << "AA tree OK" << std::endl;
    return 0;
}

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

Операция	Худший случай	Средний случай	Амортизированная	Память	Поворотов
Поиск	[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]	[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]	[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(n) }[/math]	[math]\displaystyle{ O(n) }[/math]	[math]\displaystyle{ O(n) }[/math]	[math]\displaystyle{ O(\log n) }[/math] стека	0
Память структуры	[math]\displaystyle{ O(n) }[/math]	[math]\displaystyle{ O(n) }[/math]	[math]\displaystyle{ O(n) }[/math]	указатели + уровень	0

Примечание. Оценки худшего случая детерминированы и не зависят от порядка вставок. Как и у КЧ-дерева, оценки константны по числу видов выполняемых действий, но число поворотов при записи — [math]\displaystyle{ O(\log n) }[/math], а не [math]\displaystyle{ O(1) }[/math]: АА-дерево «выравнивается» жаднее и делает больше поворотов, компенсируя это простотой кода [4].

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

Вставим в пустое дерево ключи [math]\displaystyle{ 1,2,3,4,5,6,7 }[/math] (соответствует рис. 4). В скобках — уровень узла.

Шаг	Вставили	Состояние (по возрастанию, с уровнями)	Действие нормализации
0	—	пусто	—
1	1	1(1)	лист уровня 1
2	2	1(1)→2(1)	одна правая горизонтальная связь, `split` не нужен
3	3	2(2); 1(1), 3(1)	`Split(1)` поднял узел 2 до уровня 2
4	4	2(2); 1(1), 3(1)→4(1)	`split` не срабатывает
5	5	2(2); 1(1), 4(2); 3(1), 5(1)	`Split(3)` поднял узел 4 до уровня 2
6	6	2(2); 1(1), 4(2); 3(1), 5(1)→6(1)	`split` не срабатывает
7	7	4(3); 2(2){1,3}, 6(2){5,7}	`Split(5)` поднял 6; `Split(2)` поднял 4 в корень

Обозначение: a(ур.) — ключ и уровень; → — правая связь. После шага 7 дерево идеально сбалансировано: все листья на глубине 2, корень (4) имеет уровень 3.

Для удаления рассмотрим то же дерево и удалим ключ 7 (рис. 5):

Шаг	Действие	Результат
0	дерево	4(3); 2(2){1,3}, 6(2){5,7}
1	удалить лист 7	узел 6 остаётся без правого ребёнка
2	`Decrease-Level(6)`	6 понижается до уровня 1
3	`Skew(6)`	5 становится корнем поддерева, 6 — его правым ребёнком
4	`Decrease-Level(4)`	4 понижается до уровня 2
5	`Skew(4)`	2 поднимается в корень, 4 становится его правым ребёнком
6	итог	2(2); 1(1), 4(2); 3(1), 5(1)→6(1)

Проверка инвариантов после каждого шага подтверждает корректность.

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

Лемма 1 (минимум узлов на уровне). Поддерево с корнем уровня [math]\displaystyle{ L }[/math] содержит не менее [math]\displaystyle{ 2^{L} - 1 }[/math] узлов.

Доказательство. Индукция по [math]\displaystyle{ L }[/math]. База: [math]\displaystyle{ L = 1 }[/math] — лист, [math]\displaystyle{ 1 = 2^1 - 1 }[/math]. Шаг: узел уровня [math]\displaystyle{ L \gt 1 }[/math] по инварианту 5 имеет двух детей. Левый ребёнок по инварианту 2 имеет уровень [math]\displaystyle{ L - 1 }[/math]. Правый ребёнок по свойству «нет пропусков уровней» имеет уровень не меньше [math]\displaystyle{ L - 1 }[/math] (иначе [math]\displaystyle{ \min(\text{детей}) + 1 \ne L }[/math]). Значит, оба поддерева содержат не менее [math]\displaystyle{ N(L-1) = 2^{L-1} - 1 }[/math] узлов каждое. Тогда

[math]\displaystyle{ N(L) \ge 1 + 2\,(2^{L-1} - 1) = 2^{L} - 1. \qquad \blacksquare }[/math]

Лемма 2 (высота). Высота [math]\displaystyle{ h }[/math] АА-дерева с [math]\displaystyle{ n }[/math] узлами удовлетворяет [math]\displaystyle{ h \le 2\log_2(n+1) }[/math].

Доказательство. Пусть [math]\displaystyle{ L }[/math] — уровень корня. По лемме 1 [math]\displaystyle{ n \ge 2^L - 1 }[/math], откуда [math]\displaystyle{ L \le \log_2(n+1) }[/math]. Рассмотрим путь от корня до листа. Каждое «негоризонтальное» ребро уменьшает уровень ровно на 1 (левый ребёнок всегда, правый — когда его уровень меньше), а «горизонтальное» правое ребро уровень сохраняет. По инварианту 4 и 5 горизонтальные рёбра не идут подряд и между двумя понижениями уровня стоит не более одного горизонтального ребра. Понижений уровня ровно [math]\displaystyle{ L - 1 }[/math], поэтому рёбер на пути не больше [math]\displaystyle{ 2(L-1) }[/math]. Следовательно,

[math]\displaystyle{ h \le 2(L-1) \le 2\log_2(n+1). \qquad \blacksquare }[/math]

Вывод по сложности. Поиск, минимум/максимум и преемник выполняют не более [math]\displaystyle{ h+1 = O(\log n) }[/math] шагов. Вставка и удаление проходят путь длины [math]\displaystyle{ O(\log n) }[/math], выполняя [math]\displaystyle{ O(1) }[/math] работы на уровне (skew/split), значит, [math]\displaystyle{ O(\log n) }[/math] времени и [math]\displaystyle{ O(\log n) }[/math] поворотов. Рекурсивные реализации тратят [math]\displaystyle{ O(\log n) }[/math] памяти стека; итеративные (с обходом и перестройкой пути) — [math]\displaystyle{ O(1) }[/math] дополнительной памяти.

Инвариант-аргумент для вставки. Новый лист имеет уровень 1 и не нарушает инварианты 2–5 (у него нет детей). Единственное возможное нарушение после рекурсивного возврата — левая горизонтальная связь или две правые горизонтальные связи подряд. Skew устраняет первое, Split — второе, повышая уровень среднего узла. Поскольку Split может поднять узел на уровень, соседний с уровнем его родителя, изменения обязаны «всплывать» дальше вверх — именно поэтому skew и split вызываются на каждом узле пути, а не только у листа.

Инвариант-аргумент для удаления. После удаления листа (или замены узла на преемника) поддерево на месте удалённого узла может стать на уровень ниже. Decrease-Level понижает уровни так, что пропусков не остаётся: уровень узла становится [math]\displaystyle{ \min(\text{детей}) + 1 }[/math], а если правый ребёнок «отстал», понижается и он. После этого возможные нарушения — левая горизонтальная связь, две правые подряд, а также обрыв уровня у правого внука; их снимают три вызова Skew и два вызова Split. Дойдя до корня, получаем корректное АА-дерево.

Рис. 6. Поддереву уровня [math]\displaystyle{ L }[/math] нужно не менее [math]\displaystyle{ 2^L - 1 }[/math] узлов, поэтому уровень корня не превосходит [math]\displaystyle{ \log_2(n+1) }[/math]. На пути от корня к листу между двумя понижениями уровня — не более одной горизонтальной связи, откуда [math]\displaystyle{ h \le 2\log_2(n+1) }[/math].

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

Структура	Поиск (худший)	Вставка (худший)	Удаление (худший)	Метаданные на узел	Форм балансировки	Когда выбирать
Несбалансированное BST	[math]\displaystyle{ O(n) }[/math]	[math]\displaystyle{ O(n) }[/math]	[math]\displaystyle{ O(n) }[/math]	нет	—	статические данные, учебные задачи
АА-дерево	[math]\displaystyle{ O(\log n) }[/math]	[math]\displaystyle{ O(\log n) }[/math]	[math]\displaystyle{ O(\log n) }[/math]	целое «уровень»	2 (`skew`, `split`)	когда важны простота и компактность кода
Красно-чёрное дерево	[math]\displaystyle{ O(\log n) }[/math]	[math]\displaystyle{ O(\log n) }[/math]	[math]\displaystyle{ O(\log n) }[/math]	1 бит цвета	3 (вставка) / 4 (удаление), до 7 форм	стандартные упорядоченные контейнеры
АВЛ-дерево	[math]\displaystyle{ O(\log n) }[/math]	[math]\displaystyle{ O(\log n) }[/math]	[math]\displaystyle{ O(\log n) }[/math]	поле баланса/высоты	4 (LL, RR, LR, RL)	частые поиски, редкие записи; строгий баланс
2-3-дерево	[math]\displaystyle{ O(\log n) }[/math]	[math]\displaystyle{ O(\log n) }[/math]	[math]\displaystyle{ O(\log n) }[/math]	ключи в узле	расщепление/слияние узлов	понимание AA-модели, B-деревья
Splay-дерево	до [math]\displaystyle{ O(n) }[/math]	до [math]\displaystyle{ O(n) }[/math]	до [math]\displaystyle{ O(n) }[/math]	нет	zig/zig-zig/zig-zag	«горячие» ключи, амортизированная скорость
Хеш-таблица	[math]\displaystyle{ O(n) }[/math]	[math]\displaystyle{ O(n) }[/math]	[math]\displaystyle{ O(n) }[/math] (средн. [math]\displaystyle{ O(1) }[/math])	слоты/цепочки	нет	порядок не нужен

Рис. 7. AA-дерево разбирает две формы, АВЛ — четыре, КЧ — семь. Метаданные: у AA — целое уровня, у КЧ — бит цвета, у АВЛ — поле баланса. Худшая высота у AA и КЧ совпадает.

Вердикт. Если нужен упорядоченный контейнер «из коробки» и важна гарантия худшего случая — выбирают КЧ-дерево (так сделано в стандартных библиотеках). Если тот же результат нужен малым объёмом и понятным кодом — АА-дерево предпочтительнее: вся балансировка — две функции по пять строк. АВЛ-дерево даёт меньшую высоту и больше поворотов, поэтому уместно там, где преобладают поиски.

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

АА-дерево не входит в стандартные библиотеки основных языков (там доминирует КЧ-дерево), поэтому его применение — это в первую очередь реализации в открытом коде, обучение и расширяемые структуры. Ниже — конкретные примеры и причина выбора [1][2].

Открытые библиотеки на C. Проект tidwall/aatree — однофайловая (single-header) реализация АА-дерева [6], а pem/aatree — компактная C-библиотека упорядоченного дерева на той же основе [7]. Причина выбора — минимальный размер кода балансировки: две функции skew/split вместо десятка случаев КЧ-дерева.
Учебные материалы и курсы. АА-дерево регулярно используется для объяснения связи «сбалансированное BST ↔ многопутевое дерево»: конспект CMSC 420 (University of Maryland), статьи GeeksforGeeks и визуализаторы (например, Gnarley trees) прямо показывают, как горизонтальная связь кодирует 3-узел 2-3-дерева [2]. Причина — прозрачность связи между уровнем и формой дерева.
Эталонные реализации на языках высокого уровня. Библиотека Nayuki включает упорядоченное множество на АА-дереве, отдельно отмечая, что код получается, пожалуй, самым коротким среди всех сбалансированных деревьев [8]; аналогичная реализация есть в Scalacaster (Scala). Причина — компактность и лёгкость сопровождения.
Расширяемые деревья (augmented). На АА-дерево можно навесить дополнительные поля, как на любое BST: размер поддерева — для порядковой статистики (select/rank), максимум правых концов интервалов — для интервального дерева. Простые повороты skew/split упрощают пересчёт агрегатов. Причина — те же гарантии [math]\displaystyle{ O(\log n) }[/math] при меньшем коде, чем у КЧ-дерева.
Встраиваемые и специализированные системы. Там, где важны малый размер кода и отсутствие громоздкой логики перекраски (десятки строк вместо сотен), АА-дерево служит практичной заменой КЧ-дерева. По эмпирическим данным АА-деревья получаются чуть «площе», чем КЧ, что даёт небольшой выигрыш на поиске при более простом коде записи ⚠️ требует проверки [5].

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

1970-е. Появляются многопутевые деревья поиска: симметричные двоичные B-деревья Байера (1972) и красно-чёрные деревья в формулировке Гийбы и Седжвика (1978) [2][3]. Идея кодировать многоключевой узел горизонтальным ребром уже присутствует.
1993. Арне Андерссон публикует статью «Balanced Search Trees Made Simple» на конференции WADS '93 [1]. Он ограничивает красные связи только правыми, получая кодировку 2-3-дерева и сводя всю балансировку к skew и split. Структуру называют «AA tree» по инициалам автора — это общепринятое объяснение названия.
2000-е. АА-дерево становится популярным учебным примером «простого балансирования»; независимо от него Седжвик предлагает лево-ориентированные красно-чёрные деревья (left-leaning red-black trees, 2008) — зеркальную по духу конструкцию с той же целью упрощения [4].
2004. Д. Хегер публикует сравнительное исследование поведения BST, где отмечает, что АА-дерево при более простом коде не проигрывает КЧ-дереву по скорости и получается чуть площе [5] ⚠️ требует проверки.

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

Перепутать порядок skew и split. Во вставке всегда сначала skew, затем split (строки 9–10). Обратный порядок оставляет нарушения.
Запускать split только у листа. Из-за повышения уровня split может «зацепить» родителя, поэтому обе операции вызываются на каждом узле пути вверх, а не один раз.
Забыть Decrease-Level при удалении. Без понижения уровней остаются «пропуски», и дерево перестаёт быть АА-деревом, хотя BST-порядок сохраняется.
Не обработать правого внука. В удалении после Skew(T) и Skew(right[T]) нужен ещё Skew(right[right[T]]); пропуск этой операции нарушает инвариант 4.
Неверный преемник/предшественник. При удалении узла с двумя детьми преемник — это «вправо один раз, затем влево до конца»; путаница с минимумом правого поддерева (это оно и есть) или копирование ключа без последующего удаления даёт дубликат.
Сравнение уровней с NIL. Уровень NIL нужно считать равным 0; если этого не сделать, Decrease-Level при удалении листа вычислит неверный should_be.
Рекурсия и стек. Глубина АА-дерева [math]\displaystyle{ O(\log n) }[/math], поэтому рекурсия безопасна; но при уже нарушенном инварианте дерево может выродиться и переполнить стек — итеративная реализация надёжнее.
Дубликаты. Как и std::set, АА-дерево обычно уникально; для мультимножества нужен счётчик повторов, иначе вставка молча теряет элементы.
Пересчёт агрегатов при поворотах. В расширяемом дереве не забывайте обновлять поля (размер, максимум) в skew и split — иначе запросы порядковой статистики дадут неверный ответ.

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

Проверка инвариантов. По дереву с уровнями за [math]\displaystyle{ O(n) }[/math] проверьте все пять инвариантов. Ограничения: [math]\displaystyle{ n \le 10^6 }[/math]. Подсказка: один обход; для каждого узла сверяйте уровень левого ребёнка ([math]\displaystyle{ = \mathrm{level}-1 }[/math]), уровень правого ([math]\displaystyle{ \le \mathrm{level} }[/math]), уровень правого внука ([math]\displaystyle{ \lt \mathrm{level} }[/math]), наличие двух детей при уровне [math]\displaystyle{ \gt 1 }[/math]. Ответ: [math]\displaystyle{ O(n) }[/math] времени, [math]\displaystyle{ O(\log n) }[/math] стека.
Число поворотов. Докажите, что вставка одного ключа делает [math]\displaystyle{ O(\log n) }[/math] поворотов, и постройте последовательность вставок, где поворотов максимально много. Подсказка: split повышает уровень, из-за чего может сработать на следующем узле вверх.
Переход к 2-3-дереву. По АА-дереву постройте эквивалентное 2-3-дерево и обратно. Подсказка: горизонтальная связь + её родитель = 3-узел. Ответ: обход за [math]\displaystyle{ O(n) }[/math].
Построение за [math]\displaystyle{ O(n) }[/math]. По отсортированному массиву постройте идеальное АА-дерево за [math]\displaystyle{ O(n) }[/math]. Подсказка: рекурсивно делите массив; корню среднего отрезка давайте уровень по рекурсии, листьям — 1.
Порядковая статистика. Добавьте размер поддерева и реализуйте select(k) и rank(key) за [math]\displaystyle{ O(\log n) }[/math]. Подсказка: пересчитывайте размер при skew и split.
Диапазонный запрос. Выведите все ключи из [math]\displaystyle{ [a,b] }[/math] за [math]\displaystyle{ O(\log n + k) }[/math]. Подсказка: рекурсивный обход с отсечением поддеревьев вне диапазона.
Сравнение с КЧ-деревом. Сгенерируйте [math]\displaystyle{ 10^5 }[/math] случайных вставок и удалений и сравните высоты и число поворотов АА- и КЧ-деревьев. Подсказка: средние высоты близки, у АА обычно больше поворотов.
Мультимножество. Расширьте реализацию счётчиком повторов и проверьте, что удаление одного из дубликатов не удаляет узел преждевременно.

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

Двоичное дерево поиска — базовая структура, на которой построено АА-дерево.
Красно-чёрное дерево — более общий родственник; АА — это КЧ с правыми красными связями.
2-3 дерево — многопутевая модель, которую кодирует АА-дерево.
2-3-4 дерево — модель, которую кодирует обычное КЧ-дерево.
АВЛ-дерево — более строгий баланс, больше поворотов, меньше высота.
Splay-дерево — амортизированная альтернатива без хранения уровней.
Декартово дерево — рандомизированное упорядоченное дерево.
B-дерево — страничная балансировка для внешней памяти.
Асимптотическая сложность — нотация [math]\displaystyle{ O }[/math], [math]\displaystyle{ \Omega }[/math], [math]\displaystyle{ \Theta }[/math].
Амортизационный анализ — аппарат для оценок серий операций.

Источники

Andersson A. Balanced Search Trees Made Simple // Algorithms and Data Structures, Third Workshop (WADS '93). Lecture Notes in Computer Science, Vol. 709. — Springer, 1993. — P. 60–71. DOI: 10.1007/3-540-57155-8_236.
Cormen T. H., Leiserson C. E., Rivest R. L., Stein C. Introduction to Algorithms (CLRS). 3rd ed. — MIT Press, 2009. — Гл. 13 «Red-Black Trees», гл. 12 «Binary Search Trees».
Wikipedia: AA tree. URL: https://en.wikipedia.org/wiki/AA_tree.
Sedgewick R., Wayne K. Algorithms. 4th ed. — Addison-Wesley, 2011. — Гл. 3.3 «Balanced Search Trees».
Heger D. A. A Disquisition on the Performance Behavior of Binary Search Tree Data Structures // Upgrade. — 2004. — Vol. 5, No. 5. — P. 67–75.
tidwall/aatree — реализация АА-дерева одним заголовочным файлом на C. URL: https://github.com/tidwall/aatree.
pem/aatree — C-библиотека сбалансированного дерева на основе работы Андерссона. URL: https://github.com/pem/aatree.
Nayuki. AA tree set. URL: https://www.nayuki.io/page/aa-tree-set.

Поиск

Навигация

АА-дерево

Содержание

TL;DR

Определения

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

Устройство

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

Операция: skew (устранение левой горизонтальной связи)

Операция: split (устранение двух правых горизонтальных связей)

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

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

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

Операция: минимум, максимум, преемник

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

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

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

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

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

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

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

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

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

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

Источники