AA-дерево

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

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

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

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

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

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

Свойства

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

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

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

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

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

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

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

Чтобы сохранять баланс дерева необходимо делать 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 или простое бинарное дерево