AA-дерево
АA-дерево (англ. AA-Tree) — структура данных, представляющая собой сбалансированное двоичное дерево поиска, которое является разновидностью красно-черного дерева с дополнительными ограничениями.
АA-дерево названо по первым буквам имени и фамилии изобретателя, Арне Андерссона, который впервые предложил данную модификацию красно-черного дерева в 1993 году.
Свойства
| Определение: |
| Уровень вершины (англ. Level) — вертикальная высота соответствующей вершины. |
В отличие от красно-черных деревьев, к одной вершине можно присоединить вершину только того же уровня, только одну и только справа (другими словами, красные вершины могут быть добавлены только в качестве правого ребенка). На картинке ниже представлен пример красно-чёрного дерева.
Теперь рассмотрим то же дерево, но с информацией об уровне каждой вершине. Горизонтальные ребра обозначают связи между ребрами одного уровня.
На практике в AA-дереве вместо значения цвета для балансировки дерева в вершине хранится информация только о ее уровне.
Свойства АА-дерева:
- Уровень каждого листа равен .
- Уровень каждого левого ребенка ровно на один меньше, чем у его родителя.
- Уровень каждого правого ребенка равен или на один меньше, чем у его родителя.
- Уровень каждого правого внука строго меньше, чем у его прародителя.
- Каждая вершина с уровнем больше имеет двоих детей.
Для поддержки баланса красно-черного дерева необходимо обрабатывать различных вариантов расположения вершин:
В АА-дереве из-за строгих ограничений необходимо обрабатывать только два вида возможных расположений вершин (получающиеся из соответствующего правила: «одна правая одноуровневая связь (горизонтальное ребро)»: это устранение левой связи на одном уровне и устранение двух правых связей на одном уровне):
Для представления АА-дерева в памяти будем использовать следующую структуру:
struct Node: V value // значение вершины Node level // указатель на предка Node left // указатель на левого потомка Node right // указатель на правого потомка // Конструктор вершины (создаем экземпляр структуры с полученными значениями) Node (value : V, level : V, left : Node, right: Node)
Балансировка
| Определение: |
| Горизонтальное ребро (англ. Horizontal edges) — ребро, соединяющее вершины с одинаковым уровнем. |
В AA-дереве разрешены правые ребра, не идущие подряд, и запрещены все левые горизонтальные ребра.
Эти более жесткие ограничения , аналогичные ограничениям на красно-черных деревьях, приводят к более простой реализации балансировки AA-дерева.
Для балансировки АА-дерева нужны следующие две операции:
Skew
— устранение левого горизонтального ребра. Делаем правое вращение, чтобы заменить поддерево, содержащее левую горизонтальную связь, на поддерево, содержащее разрешенную правую горизонтальную связь.
Node skew(t : Node) if t == return else if t.left == return t else if t.left.level == t.level // Меняем указатель горизонтального левого ребра l = t.left t.left = l.right l.right = t return l else return t
На рисунке ниже представлен пример работы алгоритма.
Split
— устранение двух последовательных правых горизонтальных ребер. Делаем левое вращение и увеличиваем уровень, чтобы заменить поддерево, содержащее две или более последовательных правильных горизонтальных связи, на вершину, содержащую два поддерева с меньшим уровнем.
Node split(t : Node) if t == return else if t.right == or t.right.right == return t else if t.level == t.right.right.level // Существует два правых горизонтальных ребра. Берем центральную вершину, «поднимаем» ее и возвращаем указатель на нее r = t.right t.right = r.left r.left = t r.level = r.level + 1 return r else return t
На рисунке ниже представлен пример работы алгоритма.
Операции
Вставка элемента
Вставка нового элемента происходит как в обычном дереве поиска, только на пути вверх необходимо делать ребалансировку, используя и . Ниже представлена рекурсивная реализация алгоритма.
Node insert(x : V, t : Node) // x — вставляемое значение, t — корень дерева, в который вставляется вершина if t == return Node(x, 1, , ) else if x < t.value t.left = insert(x, t.left) else if x > t.value t.right = insert(x, t.right) // Случай x == t.value не определен. Т.е. вставка не будет иметь никакого эффекта, возможны различные варианты обработки, в зависимости от решаемой задачи t = skew(t) t = split(t) return t
Пример вставки нового элемента (на рис. уровни разделены горизонтальными линиями):
Удаление вершины
Как и в большинстве сбалансированных бинарных деревьев, удаление внутренней вершины можно заменить на удаление листа, если заменить внутреннюю вершину на ее ближайшего «предшественника» или «преемника», в зависимости от реализации. «Предшественник» находиться в начале последнего левого ребра, после которого идут все правые ребра. По аналогии, «преемник» может быть найден после одного правого ребра и последовательности левых ребер, пока не будет найден указатель на NULL. В силу свойства всех узлов уровня более чем , имеющих двух детей, предшественник или преемник будет на уровне , что делает их удаление тривиальным. Ниже представлена рекурсивная реализация алгоритма.
Будем использовать дополнительную функцию , она будет обновлять уровень вершины, которую передают в функцию, в зависимости от значения уровня дочерних вершин.
Node decreaseLevel(t : Node)
shouldBe = min(t.left.level, t.right.level) + 1
if shouldBe < t.level
t.level = shouldBe
if shouldBe < t.right.level
t.right.level = shouldBe
return t
Чтобы сохранять баланс дерева необходимо делать , и для каждой вершины.
Node delete(x : V, t : Node) // x — удаляемый элемент, t — корень дерева, из которого он должен быть удален if t == return t else if x > t.value t.right = delete(x, t.right) else if x < t.value t.left = delete(x, t.left) else if leaf(t) return else if t.left == l = successor(t) t.right = delete(value(l), t.right) t.value = l.value else l := predecessor(t) t.left = delete(l.value, t.left)) t.value = l.value // Сбалансируем дерево. Если необходимо, уменьшим поля "уровень" у вершин на данном уровне, и затем skew и split все вершины на новом уровне t = decreaseLevel(t) t = skew(t) t.right = skew(t.right) if not t.right == t.right.right = skew(t.right.right) t = split(t) t.right = split(t.right) return t
Пример удаления вершины (на рис. уровни разделены горизонтальными линиями):
Эффективность
Оценка на высоту деревьев соответствует оценке для красно-черного дерева, , так как AA-дерево сохраняет структуру красно-черного дерева. Следовательно все операции происходят за , потому что в сбалансированном двоичном дереве поиска почти все операции реализуются за . Скорость работы AA-дерева эквивалентна скорости работы красно-черного дерева, но так как в реализации вместо цвета обычно хранят «уровень» вершины, overhead по памяти достигает байта.
