AA-дерево

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

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

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

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

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

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

Свойства

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

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

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

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

Для представления АА-дерева в памяти будем использовать следующую структуру:

struct Node:
  V value                  // значение вершины
  Node left                // указатель на левого потомка
  Node right               // указатель на правого потомка
  Node parent              // указатель на предка

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

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

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

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

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

Skew

[math]\mathrm{Skew(T)}[/math] — устранение левого горизонтального ребра. Делаем правое вращение, чтобы заменить поддерево, содержащее левую горизонтальную связь, на поддерево, содержащее разрешенную правую горизонтальную связь.

Node function skew(T : Node)
   if T == [math]\varnothing[/math]
       return [math]\varnothing[/math]
   else if T.left == [math]\varnothing[/math]
       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

[math]\mathrm{Split(T)}[/math] — устранение двух последовательных правых горизонтальных ребер. Делаем левое вращение и увеличиваем уровень, чтобы заменить поддерево, содержащее две или более последовательных правильных горизонтальных связи, на вершину, содержащую два поддерева с меньшим уровнем.

Node function split(T : Node)
   if T == [math]\varnothing[/math]
       return [math]\varnothing[/math]
   else if T.right == [math]\varnothing[/math] or  T.right.right == [math]\varnothing[/math]
       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

На рисунке ниже представлен пример работы алгоритма.

Операции

Вставка элемента

Вставка нового элемента происходит как в обычном дереве поиска, только на пути вверх необходимо делать ребалансировку, используя [math]\mathrm{skew}[/math] и [math]\mathrm{split}[/math]. Ниже представлена рекурсивная реализация алгоритма.

Node function insert(X : V, T : Node)
   // X - вставляемое значение, Т - корень дерева, в который вставляется вершина
   if T == [math]\varnothing[/math]
       Create a new leaf node with X.
       return node(X, 1, [math]\varnothing[/math], [math]\varnothing[/math])
   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. В силу свойства всех узлов уровня более чем [math]1[/math], имеющих двух детей, предшественник или преемник будет на уровне [math]1[/math], что делает их удаление тривиальным. Ниже представлена рекурсивная реализация алгоритма.

Будем использовать дополнительную функцию [math]\mathrm{decreaseLevel}[/math], она будет обновлять уровень вершины, которую передают в функцию, в зависимости от значения уровня дочерних вершин.

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

Чтобы сохранять баланс дерева необходимо делать [math]\mathrm{skew}[/math], [math]\mathrm{split}[/math] и [math]\mathrm{decreaseLevel}[/math] для каждой вершины.

Node function delete(X : V, T : Node)
   // X - удаляемый элемент, Т - корень дерева, из которого он должен быть удален
   if T == [math]\varnothing[/math]
       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 [math]\varnothing[/math]
       else if T.left == [math]\varnothing[/math]
           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-дерева эквивалентна скорости работы красно-черного дерева.

См. также

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

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

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