AA-дерево — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (переименовал AA-tree в AA-дерево: импортозамещение)
м (rollbackEdits.php mass rollback)
 
(не показана 31 промежуточная версия 5 участников)
Строка 1: Строка 1:
−
'''АA-дерево''' (англ. ''AA-Tree'') {{---}} структура данных, представляющая собой сбалансированное [[Дерево поиска, наивная реализация|двоичное дерево поиска]], которое является разновидностью красно-черного дерева с дополнительными ограничениями.  
+
'''АA-дерево''' (англ. ''AA-Tree'') {{---}} структура данных, представляющая собой сбалансированное [[Дерево поиска, наивная реализация|двоичное дерево поиска]], которое является разновидностью [[Красно-черное дерево|красно-черного дерева]] с дополнительными ограничениями.  
  
−
АA-дерево названо по первым буквам имени и фамилии изобретателя, Арне Андерссона, который впервые предложил данную модификацию B-дерева в 1993 году.
+
АA-дерево названо по первым буквам имени и фамилии изобретателя, Арне Андерссона, который впервые предложил данную модификацию [[Красно-черное дерево|красно-черного дерева]] в 1993 году.
 +
 
 +
== Описание дерева ==
 +
=== Структура АА-дерева ===
  
 
{{Определение
 
{{Определение
−
|definition='''Уровень вершины''' (англ. ''Level'') - вертикальная высота соответствующей вершины. Уровень листа равен 1.
+
|definition='''Уровень вершины''' (англ. ''Level'') {{---}} вертикальная высота соответствующей вершины.
 
}}
 
}}
  
 +
Для представления АА-дерева в памяти будем использовать следующую структуру:
 +
'''struct''' Node:
 +
  '''V''' value                  <font color="green">// значение вершины</font>
 +
  '''V''' level              <font color="green">// высота вершины</font>
 +
  '''Node''' left                <font color="green">// указатель на левого потомка</font>
 +
  '''Node''' right              <font color="green">// указатель на правого потомка</font>
 +
  <font color=green>// Конструктор вершины (создаем экземпляр структуры с полученными значениями)</font>
 +
  '''Node''' (value : '''V''', level : '''V''', left : '''Node''', right: '''Node''')
  
−
В отличие от красно-черных деревьев, к одной вершине можно присоединить вершину только того же уровня, только одну и только справа (другими словами, красные вершины могут быть добавлены только в качестве правого ребенка).
+
=== Свойства АА-дерева ===
  
−
== Свойства ==
+
Свойства АА-дерева:
−
*Уровень каждого листа равен 1.
+
*Уровень каждого листа равен <tex>1</tex>.
 
*Уровень каждого левого ребенка ровно на один меньше, чем у его родителя.
 
*Уровень каждого левого ребенка ровно на один меньше, чем у его родителя.
−
*Уровень каждого правого ребенка равен или один меньше, чем у его родителя.
+
*Уровень каждого правого ребенка равен или на один меньше, чем у его родителя.
 
*Уровень каждого правого внука строго меньше, чем у его прародителя.
 
*Уровень каждого правого внука строго меньше, чем у его прародителя.
−
*Каждая вершина с уровнем больше 1 имеет двоих детей.
+
*Каждая вершина с уровнем больше <tex>1</tex> имеет двоих детей.
 +
 
 +
=== Связь с красно-чёрным деревом ===
 +
 
 +
В отличие от красно-черных деревьев, к одной вершине можно присоединить вершину только того же уровня, только одну и только справа (другими словами, красные вершины могут быть добавлены только в качестве правого ребенка). На картинке ниже представлен пример красно-чёрного дерева.
 +
 
 +
[[Файл: Exaa.PNG]]
 +
 
 +
Теперь рассмотрим то же дерево, но с информацией об уровне каждой вершине. Горизонтальные ребра обозначают связи между ребрами одного уровня.
 +
 
 +
[[Файл: Ex10.PNG]]
  
−
Для поддержки баланса красно-черного дерева необходимо обрабатывать 7 различных вариантов расположения вершин:
+
На практике в AA-дереве вместо значения цвета для балансировки дерева в вершине хранится информация только о ее уровне.
 +
 
 +
[[Файл: Exaa2.PNG]]
 +
 
 +
Для поддержки баланса красно-черного дерева необходимо обрабатывать <tex>7</tex> различных вариантов расположения вершин:
  
 
[[Файл: Rb3.png]]
 
[[Файл: Rb3.png]]
  
−
В АА-дереве из-за строгих ограничений необходимо обрабатывать только два вида возможных расположений вершин:
+
В АА-дереве из-за строгих ограничений необходимо обрабатывать только два вида возможных расположений вершин, чтобы проверить соблюдается ли главное правило «одна правая горизонтальная связь». То есть мы должны проверить нет ли левой горизонтальной связи, как на первом рисунке ниже и нет ли двух последовательных правых горизонтальных связей, как на правом рисунке.
  
−
[[Файл: Rb2.png]]
+
[[Файл: Pr1.png]]
  
 
== Балансировка ==
 
== Балансировка ==
  
 
{{Определение
 
{{Определение
−
|definition='''Горизонтальное ребро''' (англ. ''Horizontal edges'') - ребро, соединяющее вершины с одинаковым уровнем.
+
|definition='''Горизонтальное ребро''' (англ. ''Horizontal edges'') {{---}} ребро, соединяющее вершины с одинаковым уровнем.
 
}}
 
}}
  
−
В AA - дереве разрешены правые ребра, не идущие подряд, и запрещены все левые горизонтальные ребра.  
+
В AA-дереве разрешены правые ребра, не идущие подряд, и запрещены все левые горизонтальные ребра.  
−
Эти более жесткие ограничения , аналогичные ограничениям на красно-черных деревьях, приводят к более простой реализации балансировки AA - дерева.
+
Эти более жесткие ограничения , аналогичные ограничениям на красно-черных деревьях, приводят к более простой реализации балансировки AA-дерева.
  
  
 
Для балансировки АА-дерева нужны следующие две операции:
 
Для балансировки АА-дерева нужны следующие две операции:
−
#'''Skew(T)''' {{---}} устранение левого горизонтального ребра.
 
  
−
  '''function''' skew(T)
+
=== Skew ===
−
     '''if''' T == NULL '''then'''
+
 
−
         '''return''' NULL
+
'''<tex>\mathrm{Skew(t)}</tex>''' {{---}} устранение левого горизонтального ребра. Делаем правое вращение, чтобы заменить поддерево, содержащее левую горизонтальную связь, на поддерево, содержащее разрешенную правую горизонтальную связь.
−
     '''else''' '''if''' left(T) == NULL '''then'''
+
 
−
         '''return''' T
+
  '''Node''' skew(t : '''Node''')
−
     '''else''' '''if''' level(left(T)) == level(T) '''then'''
+
     '''if''' t == <tex>\varnothing</tex>
−
         <font color=green> //Меняем указатель горизонтального левого ребра</font>
+
         '''return''' <tex>\varnothing</tex>
−
        L = left(T)
+
     '''else''' '''if''' t.left == <tex>\varnothing</tex>
−
        left(T) := right(L)
+
         '''return''' t
−
        right(L) := T
+
    <font color=green>// Проверяем, есть ли у нас левое горизонтальное ребро</font>
−
         '''return''' L
+
     '''else''' '''if''' t.left.level == t.level
 +
         <font color=green>// Меняем указатель горизонтального левого ребра</font>
 +
         '''return''' Node(t.left, t.left.level, t.left.left, Node(t, t.level, t.left.right, t.right))
 
     '''else'''
 
     '''else'''
−
         '''return''' T
+
         '''return''' t
−
    '''end''' '''if'''
+
 
−
'''end''' '''function'''
+
На рисунке ниже представлен пример работы алгоритма.
  
 
[[Файл: Skew.png]]
 
[[Файл: Skew.png]]
  
−
#'''Split(T)''' {{---}} устранение двух последовательных правых горизонтальных ребер.
+
=== Split ===
  
−
  '''function''' split(T)
+
'''<tex>\mathrm{Split(t)}</tex>''' {{---}} устранение двух последовательных правых горизонтальных ребер. Делаем левое вращение и увеличиваем уровень, чтобы заменить поддерево, содержащее две или более последовательных правильных горизонтальных связи, на вершину, содержащую два поддерева с меньшим уровнем.
−
    '''if''' nil(T) '''then'''
+
 
−
         '''return''' Nil
+
  '''Node''' split(t : '''Node''')
−
     '''else''' '''if''' nil(right(T)) '''or''' nil(right(right(T))) '''then'''
+
    '''if''' t == <tex>\varnothing</tex>
−
         '''return''' T
+
         '''return''' <tex>\varnothing</tex>
−
     '''else''' '''if''' level(T) == level(right(right(T))) '''then'''
+
     '''else''' '''if''' t.right == <tex>\varnothing</tex> '''or''' t.right.right == <tex>\varnothing</tex>
−
         <font color=green> //Существует два правых горизонтальных ребра. Берем центральную вершину, "поднимаем" ее и возвращаем указатель на нее</font>
+
         '''return''' t
−
         R = right(T)
+
    <font color=green>// Проверяем, один ли уровень у родителя и внука, т.е. существует ли два последовательных правых горизонтальных ребра</font>
−
        right(T) := left(R)
+
     '''else''' '''if''' t.level == t.right.right.level
−
        left(R) := T
+
         <font color=green>// Существует два правых горизонтальных ребра. Берем центральную вершину, «поднимаем» ее и возвращаем указатель на нее</font>
−
        level(R) := level(R) + 1
+
         '''return''' Node(t.right, t.right.level + 1, Node(t, t.level, t.left, t.right.left), t.right.right)
−
        '''return''' R
 
 
     '''else'''
 
     '''else'''
−
         '''return''' T
+
         '''return''' t
−
    '''end''' '''if'''
+
 
−
'''end function'''
+
На рисунке ниже представлен пример работы алгоритма.
  
 
[[Файл: Split_rb.png]]
 
[[Файл: Split_rb.png]]
Строка 79: Строка 104:
 
== Операции ==
 
== Операции ==
 
=== Вставка элемента ===
 
=== Вставка элемента ===
−
Рекурсивная реализация. Спускаемся от корня вниз по дереву, сравнивая ключи; вставляем новую вершину; выходя из рекурсии и выполняем балансировку: skew и split для каждой вершины.
+
Вставка нового элемента происходит как в обычном дереве поиска, только на пути вверх необходимо делать ребалансировку, используя <tex>\mathrm{skew}</tex> и <tex>\mathrm{split}</tex>. Ниже представлена рекурсивная реализация алгоритма.
  
−
  '''function''' insert(X, T)
+
  '''Node''' insert(x : '''V''', t : '''Node''')
−
     <font color=green>//X - вставляемое значение, Т - корень дерева, в который вставляется вершина</font>
+
     <font color=green>// x {{---}} вставляемое значение, t {{---}} корень дерева, в который вставляется вершина</font>
−
+
     '''if''' t == <tex>\varnothing</tex>
−
     '''if''' nil(T) '''then'''
+
         '''return''' Node(x, 1, <tex>\varnothing</tex>, <tex>\varnothing</tex>)
−
        Create a new leaf node with X.
+
     '''else if''' x < t.value
−
         '''return''' node(X, 1, Nil, Nil)
+
         t.left = insert(x, t.left)
−
     '''else if''' X < value(T) '''then'''
+
     '''else if''' x > t.value
−
         left(T) := insert(X, left(T))
+
         t.right = insert(x, t.right)
−
     '''else if''' X > value(T) '''then'''
+
     <font color=green>// Случай x == t.value не определен. Т.е. вставка не будет иметь никакого эффекта,
−
         right(T) := insert(X, right(T))
+
    // возможны различные варианты обработки, в зависимости от решаемой задачи</font>
−
    '''end if'''
+
     t = skew(t)
−
     <font color=green>//Случай X == value(T) не определен. Т.е. вставка не будет иметь никакого эффекта, возможны различные варианты обработки, в зависимости от решаемой задачи</font>
+
     t = split(t)
−
+
     '''return''' t
−
     T := skew(T)
 
−
     T := split(T)
 
−
 
−
     '''return''' T
 
−
'''end function'''
 
  
 
Пример вставки нового элемента (на рис. уровни разделены горизонтальными линиями):
 
Пример вставки нового элемента (на рис. уровни разделены горизонтальными линиями):
Строка 105: Строка 125:
  
 
=== Удаление вершины ===
 
=== Удаление вершины ===
−
Рекурсивная реализация. Как и в большинстве сбалансированных бинарных деревьев, удаление внутренней вершины можно заменить на удаление листа, если заменить внутреннюю вершину на ее ближайшего "предшественника" (англ. ''predecessor'') или "преемника" (англ. ''successor''), в зависимости от реализации. "Предшественник" находиться в начале последнего левого ребра, после которого идут все правые ребра. По аналогии, "преемник" может быть найден после одного правого ребра и последовательности левых ребер, пока не будет найден указатель на NULL. В силу свойства всех узлов уровня более чем 1, имеющих двух детей, предшественник или преемник будет на уровне 1, что делает их удаление тривиальным.
+
Как и в большинстве сбалансированных бинарных деревьев, удаление внутренней вершины можно заменить на удаление листа, если заменить внутреннюю вершину на ее ближайшего «предшественника» или «преемника», в зависимости от реализации. «Предшественник» находится в начале последнего левого ребра, после которого идут все правые ребра. По аналогии, «преемник» может быть найден после одного правого ребра и последовательности левых ребер, пока не будет найден указатель на NULL. В силу свойства всех узлов уровня более чем <tex>1</tex>, имеющих двух детей, предшественник или преемник будет на уровне <tex>1</tex>, что делает их удаление тривиальным. Ниже представлена рекурсивная реализация алгоритма.
  
−
Чтобы сохранять баланс дерева необходимо делать skew, split и корректировку уровня для каждой вершины.
+
Будем использовать дополнительную функцию <tex>\mathrm{decreaseLevel}</tex>, она будет обновлять уровень вершины, которую передают в функцию, в зависимости от значения уровня дочерних вершин.
  
−
  '''function''' delete(X, T)
+
  '''Node''' decreaseLevel(t : '''Node''')
−
     <font color=green>//X - удаляемый элемент, Т - корень дерева, из которого он должен быть удален</font>
+
    shouldBe = min(t.left.level, t.right.level) + 1
−
   
+
    '''if''' shouldBe < t.level
−
     '''if''' nil(T) '''then'''
+
        t.level = shouldBe
−
         '''return''' T
+
        '''if''' shouldBe < t.right.level
−
     '''else if''' X > value(T) '''then'''
+
            t.right.level = shouldBe
−
         right(T) := delete(X, right(T))
+
    '''return''' t
−
     '''else if''' X < value(T) '''then'''
+
 
−
         left(T) := delete(X, left(T))
+
Чтобы сохранять баланс дерева необходимо делать <tex>\mathrm{skew}</tex>, <tex>\mathrm{split}</tex> и <tex>\mathrm{decreaseLevel}</tex> для каждой вершины.
 +
 
 +
'''Node''' delete(x : '''V''', t : '''Node''')
 +
     <font color=green>// x {{---}} удаляемый элемент, t {{---}} корень дерева, из которого он должен быть удален</font>
 +
     '''if''' t == <tex>\varnothing</tex>
 +
         '''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'''
 
     '''else'''
−
         '''if''' leaf(T) '''then'''
+
         '''if''' leaf(t)
−
             '''return''' Nil
+
             '''return''' <tex>\varnothing</tex>
−
         '''else''' '''if''' nil(left(T)) '''then'''
+
         '''else''' '''if''' t.left == <tex>\varnothing</tex>
−
             L := successor(T)
+
             l = successor(t)
−
             right(T) := delete(value(L), right(T))
+
             t.right = delete(l.valuel, t.right)
−
             value(T) := value(L)
+
             t.value = l.value
 
         '''else'''
 
         '''else'''
−
             L := predecessor(T)
+
             l = predecessor(t)
−
             left(T) := delete(value(L), left(T))
+
             t.left = delete(l.value, t.left)
−
             value(T) := value(L)
+
             t.value = l.value
−
        '''end if'''
+
     <font color=green>// Сбалансируем дерево. Если необходимо, уменьшим поля «уровень»
−
    '''end if'''
+
    // у вершин на данном уровне, и затем skew и split все вершины на новом уровне</font>
−
   
+
     t = decreaseLevel(t)
−
     <font color=green>//Сбалансируем дерево. Если необходимо, уменьшим поля "уровень" у вершин на данном уровне, и затем skew и split все вершины на новом уровне</font>
+
     t = skew(t)
−
     T := decrease_level(T)
+
     t.right = skew(t.right)
−
     T := skew(T)
+
     '''if''' t.right <tex> \neq\ \varnothing</tex>
−
     right(T) := skew(right(T))
+
         t.right.right = skew(t.right.right)
−
     '''if not''' nil(right(T))
+
     t = split(t)
−
         right(right(T)) := skew(right(right(T)))
+
     t.right = split(t.right)
−
     '''end if'''
+
     '''return''' t
−
    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'''
 
  
 
Пример удаления вершины (на рис. уровни разделены горизонтальными линиями):
 
Пример удаления вершины (на рис. уровни разделены горизонтальными линиями):
Строка 161: Строка 174:
  
 
== Эффективность ==
 
== Эффективность ==
−
Скорость работы AA - дерева эквивалентна скорости работы красно-черного дерева. В среднем более простые алгоритмы на AA - дерева выполняются быстрее, но в красно-черном дереве делается меньше поворотов, что уравновешивает асимптотику.
+
Оценка на высоту деревьев соответствует оценке для красно-черного дерева, <tex>2\cdot \log 2(N)</tex>, так как AA-дерево сохраняет структуру красно-черного дерева. Следовательно все операции происходят за <tex>O(\log N)</tex>, потому что в сбалансированном двоичном дереве поиска почти все операции реализуются за <tex>O(h)</tex>. Скорость работы AA-дерева эквивалентна скорости работы красно-черного дерева, но так как в реализации вместо цвета обычно хранят «уровень» вершины, дополнительные расходы по памяти достигают байта.
  
 
== См. также ==
 
== См. также ==
Строка 169: Строка 182:
 
* [[Декартово дерево]]
 
* [[Декартово дерево]]
 
* [[Красно-черное дерево]]
 
* [[Красно-черное дерево]]
−
 
  
 
== Источники информации ==
 
== Источники информации ==
−
* [http://user.it.uu.se/~arnea/ps/simp.pdf {{---}} Balanced searched trees made simple]
+
* [http://user.it.uu.se/~arnea/ps/simp.pdf Uppsala University {{---}} Balanced searched trees made simple]  
−
* [https://en.wikipedia.org/wiki/AA_tree {{---}} AA - tree]
+
* [https://en.wikipedia.org/wiki/AA_tree Википедия {{---}} AA - tree]
−
* [https://habrahabr.ru/post/110212/ {{---}} AA-Tree или простое бинарное дерево]
+
* [https://habrahabr.ru/post/110212/ Хабрахабр {{---}} AA-Tree или простое бинарное дерево]
−
 
 
−
 
 
  
 
[[Категория:Дискретная математика и алгоритмы]]
 
[[Категория:Дискретная математика и алгоритмы]]
 
[[Категория:Структуры данных]]
 
[[Категория:Структуры данных]]
 
[[Категория:Деревья поиска]]
 
[[Категория:Деревья поиска]]

Текущая версия на 19:36, 4 сентября 2022

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

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

Описание дерева

Структура АА-дерева

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


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

struct Node:
  V value                  // значение вершины
  V level               // высота вершины
  Node left                // указатель на левого потомка
  Node right               // указатель на правого потомка
  // Конструктор вершины (создаем экземпляр структуры с полученными значениями)
  Node (value : V, level : V, left : Node, right: Node)

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

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

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

Связь с красно-чёрным деревом

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

Exaa.PNG

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

Ex10.PNG

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

Exaa2.PNG

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

Rb3.png

В АА-дереве из-за строгих ограничений необходимо обрабатывать только два вида возможных расположений вершин, чтобы проверить соблюдается ли главное правило «одна правая горизонтальная связь». То есть мы должны проверить нет ли левой горизонтальной связи, как на первом рисунке ниже и нет ли двух последовательных правых горизонтальных связей, как на правом рисунке.

Pr1.png

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

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


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


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

Skew

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

Node 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
       // Меняем указатель горизонтального левого ребра
       return Node(t.left, t.left.level, t.left.left, Node(t, t.level, t.left.right, t.right))
   else
       return t

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

Skew.png

Split

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

Node 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
       // Существует два правых горизонтальных ребра. Берем центральную вершину, «поднимаем» ее и возвращаем указатель на нее
       return Node(t.right, t.right.level + 1, Node(t, t.level, t.left, t.right.left), t.right.right)
   else
       return t

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

Split rb.png

Операции

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

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

Node insert(x : V, t : Node)
   // x — вставляемое значение, t — корень дерева, в который вставляется вершина
   if t == [math]\varnothing[/math]
       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 == t.value не определен. Т.е. вставка не будет иметь никакого эффекта,
   // возможны различные варианты обработки, в зависимости от решаемой задачи
   t = skew(t)
   t = split(t)
   return t

Пример вставки нового элемента (на рис. уровни разделены горизонтальными линиями):

Ex insert.png

Удаление вершины

Как и в большинстве сбалансированных бинарных деревьев, удаление внутренней вершины можно заменить на удаление листа, если заменить внутреннюю вершину на ее ближайшего «предшественника» или «преемника», в зависимости от реализации. «Предшественник» находится в начале последнего левого ребра, после которого идут все правые ребра. По аналогии, «преемник» может быть найден после одного правого ребра и последовательности левых ребер, пока не будет найден указатель на NULL. В силу свойства всех узлов уровня более чем [math]1[/math], имеющих двух детей, предшественник или преемник будет на уровне [math]1[/math], что делает их удаление тривиальным. Ниже представлена рекурсивная реализация алгоритма.

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

Node 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 delete(x : V, t : Node)
   // x — удаляемый элемент, t — корень дерева, из которого он должен быть удален
   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)
           return [math]\varnothing[/math]
       else if t.left == [math]\varnothing[/math]
           l = successor(t)
           t.right = delete(l.valuel, 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 t.right [math] \neq\ \varnothing[/math]
       t.right.right = skew(t.right.right)
   t = split(t)
   t.right = split(t.right)
   return t

Пример удаления вершины (на рис. уровни разделены горизонтальными линиями):

Exdelete.png

Эффективность

Оценка на высоту деревьев соответствует оценке для красно-черного дерева, [math]2\cdot \log 2(N)[/math], так как AA-дерево сохраняет структуру красно-черного дерева. Следовательно все операции происходят за [math]O(\log N)[/math], потому что в сбалансированном двоичном дереве поиска почти все операции реализуются за [math]O(h)[/math]. Скорость работы AA-дерева эквивалентна скорости работы красно-черного дерева, но так как в реализации вместо цвета обычно хранят «уровень» вершины, дополнительные расходы по памяти достигают байта.

См. также

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

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=AA-дерево&oldid=85593»