AA-дерево
АA-дерево (англ. AA-Tree) — структура данных, представляющая собой сбалансированное двоичное дерево поиска, которое является разновидностью красно-черного дерева с дополнительными ограничениями.
АA-дерево названо по первым буквам имени и фамилии изобретателя, Арне Андерссона, который впервые предложил данную модификацию красно-черного дерева в 1993 году.
| Определение: |
| Уровень вершины (англ. Level) — вертикальная высота соответствующей вершины. |
В отличие от красно-черных деревьев, к одной вершине можно присоединить вершину только того же уровня, только одну и только справа (другими словами, красные вершины могут быть добавлены только в качестве правого ребенка). На картинке ниже представлен пример АА-дерева.
На практике в AA-дереве вместо значения цвета для балансировки дерева в вершине хранится информация о ее уровне. На картинки ниже изображен пример того же дерева, построенного только на основе информации об уровне вершин, горизонтальные ребра обозначают связь вершин одного уровня.
Содержание
Свойства
Свойства АА-дерева:
- Уровень каждого листа равен .
- Уровень каждого левого ребенка ровно на один меньше, чем у его родителя.
- Уровень каждого правого ребенка равен или один меньше, чем у его родителя.
- Уровень каждого правого внука строго меньше, чем у его прародителя.
- Каждая вершина с уровнем больше имеет двоих детей.
Для поддержки баланса красно-черного дерева необходимо обрабатывать различных вариантов расположения вершин:
В АА-дереве из-за строгих ограничений необходимо обрабатывать только два вида возможных расположений вершин:
Для представления АА-дерева в памяти будем использовать следующую структуру:
struct Node: V value // значение вершины Node left // указатель на левого потомка Node right // указатель на правого потомка Node parent // указатель на предка
Балансировка
| Определение: |
| Горизонтальное ребро (англ. Horizontal edges) — ребро, соединяющее вершины с одинаковым уровнем. |
В AA-дереве разрешены правые ребра, не идущие подряд, и запрещены все левые горизонтальные ребра.
Эти более жесткие ограничения , аналогичные ограничениям на красно-черных деревьях, приводят к более простой реализации балансировки AA-дерева.
Для балансировки АА-дерева нужны следующие две операции:
Skew
— устранение левого горизонтального ребра. Делаем правое вращение, чтобы заменить поддерево, содержащее левую горизонтальную связь, на поддерево, содержащее разрешенную правую горизонтальную связь.
Node function skew(T : Node) if T == return else if T.left == return T else if T.left.level == T.level then // Меняем указатель горизонтального левого ребра L = T.left T.left = L.right L.right = T return L else return T
На рисунке ниже представлен пример работы алгоритма.
Split
— устранение двух последовательных правых горизонтальных ребер. Делаем левое вращение и увеличиваем уровень, чтобы заменить поддерево, содержащее две или более последовательных правильных горизонтальных связи, на вершину, содержащую два поддерева с меньшим уровнем.
Node function 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 function insert(X : V, T : Node) // X - вставляемое значение, Т - корень дерева, в который вставляется вершина if T == Create a new leaf node with X. 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 == value(T) не определен. Т.е. вставка не будет иметь никакого эффекта, возможны различные варианты обработки, в зависимости от решаемой задачи T = skew(T) T = split(T) return T
Пример вставки нового элемента (на рис. уровни разделены горизонтальными линиями):
Удаление вершины
Как и в большинстве сбалансированных бинарных деревьев, удаление внутренней вершины можно заменить на удаление листа, если заменить внутреннюю вершину на ее ближайшего "предшественника" (англ. predecessor) или "преемника" (англ. successor), в зависимости от реализации. "Предшественник" находиться в начале последнего левого ребра, после которого идут все правые ребра. По аналогии, "преемник" может быть найден после одного правого ребра и последовательности левых ребер, пока не будет найден указатель на NULL. В силу свойства всех узлов уровня более чем , имеющих двух детей, предшественник или преемник будет на уровне , что делает их удаление тривиальным. Ниже представлена рекурсивная реализация алгоритма.
Будем использовать дополнительную функцию , она будет обновлять уровень вершины, которую передают в функцию, в зависимости от значения уровня дочерних вершин.
Node function 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 function delete(X : V, T : Node) // X - удаляемый элемент, Т - корень дерева, из которого он должен быть удален 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) then 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 nil(T.right) right(T.right) = skew(T.right.right) end if T = split(T) T.right = split(T.right) return T
Пример удаления вершины (на рис. уровни разделены горизонтальными линиями):
Эффективность
Скорость работы AA-дерева эквивалентна скорости работы красно-черного дерева.
См. также
