AA-дерево¶

AA-дерево — это разновидность самобалансирующегося бинарного дерева поиска, в котором для поддержания сбалансированности используется дополнительное поле уровня (level), имитирующее красно-чёрное дерево с упрощёнными правилами балансировки. AA-дерево было предложено Арне Андерссоном в 1993 году как альтернатива красно-чёрным деревьям, отличающаяся меньшим количеством случаев при вставке и удалении узлов.

¶История

AA-дерево было разработано шведским учёным Арне Андерссоном (Arne Andersson) в 1993 году. Основной целью создания было упрощение алгоритмов балансировки по сравнению с красно-чёрными деревьями, которые требуют обработки до шести различных случаев при вставке и удалении. Андерссон предложил ввести понятие уровня узла, который заменяет цвет (красный/чёрный) и позволяет свести все операции к двум базовым поворотам — левому и правому. Впоследствии AA-деревья нашли применение в системах, где важна простота реализации и предсказуемость времени выполнения операций, например, в некоторых реализациях ассоциативных массивов и баз данных.

¶Основные свойства

AA-дерево является бинарным деревом поиска, то есть для каждого узла выполняется условие: все ключи в левом поддереве меньше ключа узла, а все ключи в правом поддереве — больше. Дополнительно вводится понятие уровня (level) узла, который аналогичен чёрной высоте в красно-чёрных деревьях. Уровень листового узла (или NULL) считается равным 0, а уровень внутреннего узла вычисляется по правилам:

• Уровень узла равен уровню его правого потомка плюс один.
• Уровень узла может быть равен уровню левого потомка или на единицу больше.

Эти правила гарантируют, что дерево остаётся приблизительно сбалансированным: высота AA-дерева с n узлами не превышает O(log n).

¶Отличие от красно-чёрных деревьев

В красно-чёрных деревьях балансировка контролируется цветом узлов (красный или чёрный) и набором сложных правил, включающих до трёх поворотов и перекрашиваний. В AA-дереве вместо цвета используется числовой уровень, а все операции сводятся к двум простым процедурам — skew (правый поворот) и split (левый поворот с повышением уровня). Это делает код более компактным и менее подверженным ошибкам.

¶Устройство и операции

Каждый узел AA-дерева содержит ключ, значение (опционально), указатели на левого и правого потомка, а также целочисленный уровень. Основные операции — вставка, удаление и поиск — выполняются рекурсивно с последующей балансировкой.

¶Балансировка: skew и split

Для восстановления инвариантов AA-дерева после вставки или удаления используются две вспомогательные функции:

• Skew (правый поворот): применяется, если уровень левого потомка равен уровню текущего узла. При этом левый потомок становится новым корнем поддерева, а текущий узел — его правым потомком. Уровни узлов не изменяются.
• Split (левый поворот с повышением уровня): применяется, если уровень правого потомка равен уровню текущего узла, а уровень правого потомка этого правого потомка также равен тому же уровню. При этом правый потомок становится новым корнем, его уровень увеличивается на 1, а текущий узел становится его левым потомком.

Эти две операции повторяются рекурсивно при возврате из рекурсии после вставки или удаления, что гарантирует соблюдение всех свойств AA-дерева.

¶Вставка

Вставка нового узла начинается с обычного рекурсивного спуска по дереву поиска. Когда достигается NULL-указатель, создаётся новый узел с уровнем 1. Затем при возврате из рекурсии последовательно вызываются skew и split для каждого узла на пути. Это обеспечивает балансировку за O(log n) времени.

¶Удаление

Удаление узла из AA-дерева сложнее, чем вставка, но всё же проще, чем в красно-чёрных деревьях. Алгоритм:

1. Найти узел с заданным ключом.
2. Если узел является листом (оба потомка NULL), удалить его.
3. Если узел имеет только одного потомка, заменить его этим потомком.
4. Если узел имеет двух потомков, найти минимальный ключ в правом поддереве (или максимальный в левом), скопировать его значение в удаляемый узел, а затем рекурсивно удалить найденный узел-заменитель.
5. После удаления при возврате из рекурсии выполняется балансировка: для каждого узла проверяется, не нарушены ли уровни, и при необходимости применяются skew и split. В некоторых случаях может потребоваться уменьшение уровня узла, если его потомки имеют слишком низкие уровни.

Время выполнения удаления также составляет O(log n).

¶Поиск

Поиск элемента по ключу выполняется стандартным для бинарных деревьев поиска способом: сравнение ключа с корнем, рекурсивный переход в левое или правое поддерево. Благодаря сбалансированности, поиск занимает O(log n) времени.

¶Преимущества и недостатки

¶Преимущества

• Простота реализации: код AA-дерева обычно короче и понятнее, чем код красно-чёрного дерева, особенно для вставки и удаления.
• Меньше случаев: вместо шести вариантов поворотов в красно-чёрных деревьях AA-дерево использует только два.
• Предсказуемость: все операции выполняются за O(log n) в худшем случае.

¶Недостатки

• Несколько более высокая константа: из-за рекурсивных вызовов skew и split на каждом шаге AA-дерево может быть немного медленнее красно-чёрного дерева на практике, хотя асимптотическая сложность та же.
• Меньшая распространённость: AA-деревья менее известны, чем красно-чёрные или AVL-деревья, поэтому для них меньше готовых библиотек и примеров.
• Чувствительность к реализации: ошибки в рекурсивной балансировке могут привести к нарушению инвариантов.

¶Применение

AA-деревья используются в тех же областях, что и другие самобалансирующиеся деревья поиска:

• Реализация ассоциативных массивов (словарей) и множеств в языках программирования.
• Хранение индексов в базах данных (например, в некоторых реализациях B-деревьев или как альтернатива).
• Системы реального времени, где требуется гарантированное время доступа.
• Образовательные проекты для изучения структур данных благодаря простоте.

В России и русскоязычном сообществе AA-деревья изучаются в курсах алгоритмов и структур данных, но редко используются в промышленном программировании по сравнению с красно-чёрными деревьями (например, в std::map в C++).

¶Пример реализации (псевдокод)

Ниже приведён упрощённый псевдокод основных операций AA-дерева:

``` struct Node { key: int left: Node right: Node level: int }

function skew(node): if node.left.level == node.level: left = node.left node.left = left.right left.right = node return left return node

function split(node): if node.right.right.level == node.level: right = node.right node.right = right.left right.left = node right.level += 1 return right return node

function insert(node, key): if node == NULL: return new Node(key, level=1) if key < node.key: node.left = insert(node.left, key) else if key > node.key: node.right = insert(node.right, key) else: return node // ключ уже существует node = skew(node) node = split(node) return node

function delete(node, key): if node == NULL: return NULL if key < node.key: node.left = delete(node.left, key) else if key > node.key: node.right = delete(node.right, key) else: if node.left == NULL and node.right == NULL: return NULL else if node.left == NULL: // найти минимальный в правом поддереве minNode = findMin(node.right) node.key = minNode.key node.right = delete(node.right, minNode.key) else: // аналогично с левым поддеревом maxNode = findMax(node.left) node.key = maxNode.key node.left = delete(node.left, maxNode.key) // балансировка после удаления node = decreaseLevel(node) node = skew(node) node.right = skew(node.right) node.right.right = skew(node.right.right) node = split(node) node.right = split(node.right) return node ```

¶Интересные факты

• Название «AA-дерево» происходит от инициалов автора (Arne Andersson), а не от двойной буквы A.
• В оригинальной статье Андерссона 1993 года предлагалось также обобщение на многопутевые деревья, но классическим вариантом остаётся бинарное.
• AA-дерево иногда называют «сбалансированным деревом с уровнями» (level-linked tree).
• Существует вариант AA-дерева, в котором уровень узла хранится неявно, что позволяет экономить память, но усложняет код.

¶Источники

• Andersson, Arne. «Balanced Search Trees Made Simple». Proceedings of the Workshop on Algorithms and Data Structures, 1993.
• Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. «Алгоритмы: построение и анализ», 3-е издание, глава 13 (красно-чёрные деревья) и дополнительные материалы.
• Sedgewick, Robert. «Algorithms in C++», 3rd edition, раздел о самобалансирующихся деревьях.
• Документация и исходные коды библиотек, реализующих AA-деревья (например, в проектах с открытым исходным кодом).