AABB-дерево¶

AABB-дерево — это структура данных, разновидность сбалансированного бинарного дерева поиска, в которой для поддержания баланса используются не цвета узлов (как в красно-чёрных деревьях), а числовые уровни (ранги), присваиваемые каждому узлу. AABB-дерево является упрощённой версией красно-чёрного дерева, где все операции балансировки сводятся к двум видам поворотов и переопределению уровней, что облегчает реализацию и доказательство корректности. Название происходит от первых букв фамилий авторов — Арне Андерссона (Arne Andersson) и Рудольфа Байера (Rudolf Bayer), хотя сам термин «AABB» не является официальным; чаще структура называется AA-деревом (AA tree) в честь Андерссона, который предложил её в 1993 году.

¶История

AA-дерево было впервые описано шведским учёным Арне Андерссоном в 1993 году в статье «Balanced Search Trees Made Simple». Андерссон ставил целью создать сбалансированное дерево поиска, которое было бы проще в реализации, чем красно-чёрное дерево, при сохранении гарантированной логарифмической высоты. В отличие от красно-чёрных деревьев, где для балансировки используются три типа операций (повороты и перекрашивания), AA-дерево обходится двумя операциями — правым и левым поворотом, а также специальной операцией «расщепления» (split) и «перекоса» (skew). Название «AA» происходит от инициалов автора, хотя иногда ошибочно расшифровывается как «A-symmetric binary tree» или «Arne Andersson’s binary tree». В русскоязычной литературе иногда используется термин «AABB-дерево» для обозначения модификаций, где уровни кодируются двумя битами, но это нестандартное название.

¶Основные принципы

¶Уровни (ранги)

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

• Если узел является листом, его уровень равен 1.
• Если узел имеет потомков, его уровень равен минимальному уровню потомка плюс 1, но с дополнительными ограничениями, обеспечивающими баланс.

Формально, уровень узла x — это количество шагов до ближайшего листа, если двигаться только по левым или правым связям, но с учётом правил балансировки.

¶Инварианты AA-дерева

AA-дерево поддерживает два основных инварианта (свойства), которые гарантируют его сбалансированность:

1. Горизонтальные связи (horizontal links) — правый потомок узла может иметь тот же уровень, что и сам узел. Такая связь называется «горизонтальной». Левый потомок никогда не может иметь тот же уровень, что и родитель (иначе дерево считается «перекошенным» — skewed).
2. Отсутствие двух последовательных горизонтальных связей — не может быть ситуации, когда узел имеет правого потомка того же уровня, а у этого потомка — своего правого потомка того же уровня (то есть не допускается «двойная горизонтальная связь»). Это свойство называется «отсутствие расщепления» (no split).

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

¶Операции

¶Поиск

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

¶Вставка

Вставка нового узла в AA-дерево состоит из двух этапов:

1. Стандартная вставка — узел добавляется как лист с уровнем 1.
2. Восстановление инвариантов — после вставки дерево может нарушить свойства, поэтому выполняется два вида корректирующих операций, которые применяются рекурсивно от места вставки к корню:

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

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

¶Удаление

Удаление узла из AA-дерева сложнее вставки, но также основано на тех же принципах. Сначала выполняется стандартное удаление из бинарного дерева поиска (замена удаляемого узла на его преемника или предшественника, если он имеет двух потомков). Затем, начиная с уровня, на котором произошло удаление, выполняется восстановление инвариантов с помощью skew и split, но с дополнительной проверкой: если уровень узла стал больше, чем уровень его потомков, или если узел имеет два потомка с уровнем, равным его собственному, то уровень узла уменьшается на 1, и затем применяются skew и split. Удаление также выполняется за O(log n).

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

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

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

¶Недостатки

• Скорость — из-за необходимости выполнять две операции (skew и split) при каждой вставке и удалении, AA-деревья могут быть немного медленнее, чем красно-чёрные деревья, в среднем на 10-20% (по данным некоторых тестов).
• Ограниченная распространённость — AA-деревья менее известны, чем красно-чёрные или AVL-деревья, поэтому для них меньше готовых библиотек и учебных материалов.
• Чувствительность к порядку вставки — как и все бинарные деревья, AA-дерево может деградировать при вставке отсортированных данных, но балансировка предотвращает вырождение в линейный список.

¶Применение

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

• Реализация ассоциативных массивов (словарей) в языках программирования, где требуется быстрый доступ по ключу.
• Базы данных — для индексации данных (например, в некоторых СУБД для in-memory таблиц).
• Файловые системы — для организации каталогов и метаданных.
• Компиляторы — для хранения таблиц символов и синтаксических деревьев.
• Игровые движки — для пространственного разделения объектов (например, в AABB-деревьях для коллизий, но это другая структура — Axis-Aligned Bounding Box tree).

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

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

Ниже приведён упрощённый псевдокод операций skew и split на языке, подобном C:

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

Node skew(Node t) { if (t == NULL) return NULL; if (t->left != NULL && t->left->level == t->level) { // Правый поворот Node* L = t->left; t->left = L->right; L->right = t; return L; } return t; }

Node split(Node t) { if (t == NULL) return NULL; if (t->right != NULL && t->right->right != NULL && t->right->level == t->level && t->right->right->level == t->level) { // Левый поворот Node* R = t->right; t->right = R->left; R->left = t; R->level++; return R; } return t; } ```

Вставка с использованием этих операций:

`` Node insert(Node t, int key) { if (t == NULL) return new Node(key, 1); 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; } ``

¶Сравнение с другими сбалансированными деревьями

AA-деревья уступают по скорости красно-чёрным и AVL-деревьям, но выигрывают в простоте кода. В ситуациях, где важна лёгкость сопровождения и отладки, они могут быть предпочтительнее.

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

• Арне Андерссон, создатель AA-дерева, также известен своими работами по сжатию данных и структурам данных для строк (например, Patricia trie).
• В оригинальной статье Андерссона дерево называлось «AA tree» (Arne Andersson tree), но позже появилось название «AABB tree» как шутливое расширение, подразумевающее, что уровни кодируются двумя битами (A и B), хотя это не является стандартом.
• AA-деревья иногда путают с AABB-деревьями (Axis-Aligned Bounding Box tree), используемыми в компьютерной графике для обнаружения коллизий, но это совершенно разные структуры.
• В некоторых реализациях AA-дерева уровень хранится не как отдельное поле, а кодируется в младших битах указателей на потомков, что экономит память, но усложняет код.

¶Источники

• Andersson, Arne. «Balanced Search Trees Made Simple». Proceedings of the 1993 Workshop on Algorithms and Data Structures, 1993, pp. 60–71.
• Cormen, Thomas H. et al. «Introduction to Algorithms». 3rd ed., MIT Press, 2009, Chapter 13 (Red-Black Trees) — для сравнения с AA-деревьями.
• Sedgewick, Robert. «Algorithms in C++». Addison-Wesley, 1998 — содержит раздел о AA-деревьях.
• Статья «AA tree» в англоязычной Википедии (версия от 2023 года) — для проверки фактов и дополнительных ссылок.