AA-дерево

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

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

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

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

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

Свойства

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

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

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

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

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

Горизонтальное ребро (англ. Horizontal edges) - ребро, соединяющее вершины с одинаковым уровнем.

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

Для балансировки АА-дерева нужны следующие две операции:

1. Skew(T) — устранение левого горизонтального ребра.

function skew is
   input: T, a node representing an AA tree that needs to be rebalanced.
   output: Another node representing the rebalanced AA tree.

   if T == NULL then
       return NULL
   else if left(T) == NULL then
       return T
   else if level(left(T)) == level(T) then
       Swap the pointers of horizontal left links.
       L = left(T)
       left(T) := right(L)
       right(L) := T
       return L
   else
       return T
   end if
end function

1. Split(T) — устранение двух последовательных правых горизонтальных ребер.

function split is
   input: T, a node representing an AA tree that needs to be rebalanced.
   output: Another node representing the rebalanced AA tree.

   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
       We have two horizontal right links.  Take the middle node, elevate it, and return it.
       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 is
   input: X, the value to be inserted, and T, the root of the tree to insert it into.
   output: A balanced version T including X.

   Do the normal binary tree insertion procedure. Set the result of the
   recursive call to the correct child in case a new node was created or the
   root of the subtree changes.
   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
   Note that the case of X == value(T) is unspecified. As given, an insert
   will have no effect. The implementor may desire different behavior.

   Perform skew and then split. The conditionals that determine whether or
   not a rotation will occur or not are inside of the procedures, as given
   above.
   T := skew(T)
   T := split(T)

   return T
end function