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