AA-дерево

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

АA-дерево названо по первым буквам имени и фамилии изобретателя, Арне Андерссона, который впервые предложил данную модификацию красно-черного дерева в 1993 году.

Определение:

Уровень вершины (англ. Level) — вертикальная высота соответствующей вершины.

В отличие от красно-черных деревьев, к одной вершине можно присоединить вершину только того же уровня, только одну и только справа (другими словами, красные вершины могут быть добавлены только в качестве правого ребенка). На картинке ниже представлен пример АА-дерева.

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

Свойства

Свойства АА-дерева:

• Уровень каждого листа равен [math]1[/math].
• Уровень каждого левого ребенка ровно на один меньше, чем у его родителя.
• Уровень каждого правого ребенка равен или один меньше, чем у его родителя.
• Уровень каждого правого внука строго меньше, чем у его прародителя.
• Каждая вершина с уровнем больше [math]1[/math] имеет двоих детей.

Для поддержки баланса красно-черного дерева необходимо обрабатывать [math]7[/math] различных вариантов расположения вершин:

В АА-дереве из-за строгих ограничений необходимо обрабатывать только два вида возможных расположений вершин:

Балансировка

Определение:

Горизонтальное ребро (англ. 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. В силу свойства всех узлов уровня более чем [math]1[/math], имеющих двух детей, предшественник или преемник будет на уровне [math]1[/math], что делает их удаление тривиальным.

Чтобы сохранять баланс дерева необходимо делать 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-дерева выполняются быстрее, но в красно-черном дереве делается меньше поворотов, что уравновешивает асимптотику.

См. также

• B-дерево
• Splay-дерево
• АВЛ-дерево
• Декартово дерево
• Красно-черное дерево

Источники информации

• Balanced searched trees made simple
• AA - tree
• AA-Tree или простое бинарное дерево