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

Материал из Викиконспекты
Перейти к: навигация, поиск
(→‎Удаление вершины)
Строка 44: Строка 44:
 
Для балансировки АА-дерева нужны следующие две операции:
 
Для балансировки АА-дерева нужны следующие две операции:
  
−
1.'''Skew(T)''' {{---}} устранение левого горизонтального ребра.
+
1.'''<tex>\mathrm{Skew(T)}</tex>''' {{---}} устранение левого горизонтального ребра.
  
 
  '''function''' skew(T)
 
  '''function''' skew(T)
−
     '''if''' T == NULL '''then'''
+
     '''if''' T == <tex>\varnothing</tex>
−
         '''return''' NULL
+
         '''return''' <tex>\varnothing</tex>
−
     '''else''' '''if''' left(T) == NULL '''then'''
+
     '''else''' '''if''' T.left == <tex>\varnothing</tex>
 
         '''return''' T
 
         '''return''' T
−
     '''else''' '''if''' level(left(T)) == level(T) '''then'''
+
     '''else''' '''if''' T.left.level == T.level '''then'''
−
         <font color=green> //Меняем указатель горизонтального левого ребра</font>
+
         <font color=green> // Меняем указатель горизонтального левого ребра</font>
−
         L = left(T)
+
         L = T.left
−
         left(T) := right(L)
+
         T.left := L.right
−
         right(L) := T
+
         L.right := T
 
         '''return''' L
 
         '''return''' L
 
     '''else'''
 
     '''else'''
 
         '''return''' T
 
         '''return''' T
−
    '''end''' '''if'''
 
−
'''end''' '''function'''
 
  
 
[[Файл: Skew.png]]
 
[[Файл: Skew.png]]
  
−
2.'''Split(T)''' {{---}} устранение двух последовательных правых горизонтальных ребер.
+
2.'''<tex>\mathrm{Split(T)}</tex>''' {{---}} устранение двух последовательных правых горизонтальных ребер.
  
 
  '''function''' split(T)
 
  '''function''' split(T)
−
     '''if''' nil(T) '''then'''
+
     '''if''' T == <tex>\varnothing</tex>
−
         '''return''' Nil
+
         '''return''' <tex>\varnothing</tex>
−
     '''else''' '''if''' nil(right(T)) '''or'''  nil(right(right(T))) '''then'''
+
     '''else''' '''if''' T.right == <tex>\varnothing</tex> '''or'''  T.right.right == <tex>\varnothing</tex>
 
         '''return''' T
 
         '''return''' T
−
     '''else''' '''if''' level(T) == level(right(right(T))) '''then'''
+
     '''else''' '''if''' T.level == T.right.right.level
−
         <font color=green> //Существует два правых горизонтальных ребра. Берем центральную вершину, "поднимаем" ее и возвращаем указатель на нее</font>
+
         <font color=green> // Существует два правых горизонтальных ребра. Берем центральную вершину, "поднимаем" ее и возвращаем указатель на нее</font>
−
         R = right(T)
+
         R = T.right
−
         right(T) := left(R)
+
         T.right := R.left
−
         left(R) := T
+
         R.left := T
−
         level(R) := level(R) + 1
+
         R.level := R.level + 1
 
         '''return''' R
 
         '''return''' R
 
     '''else'''
 
     '''else'''
 
         '''return''' T
 
         '''return''' T
−
    '''end''' '''if'''
 
−
'''end function'''
 
  
 
[[Файл: Split_rb.png]]
 
[[Файл: Split_rb.png]]
Строка 87: Строка 83:
 
== Операции ==
 
== Операции ==
 
=== Вставка элемента ===
 
=== Вставка элемента ===
−
Рекурсивная реализация. Спускаемся от корня вниз по дереву, сравнивая ключи; вставляем новую вершину; выходя из рекурсии и выполняем балансировку: skew и split для каждой вершины.
+
Рекурсивная реализация. Спускаемся от корня вниз по дереву, сравнивая ключи; вставляем новую вершину; выходя из рекурсии и выполняем балансировку: <tex>\mathrm{skew}</tex> и <tex>\mathrm{split}</tex> для каждой вершины.
  
 
  '''function''' insert(X, T)
 
  '''function''' insert(X, T)
−
     <font color=green>//X - вставляемое значение, Т - корень дерева, в который вставляется вершина</font>
+
     <font color=green>// X - вставляемое значение, Т - корень дерева, в который вставляется вершина</font>
−
+
     '''if''' T == <tex>\varnothing</tex>
−
     '''if''' nil(T) '''then'''
 
 
         Create a new leaf node with X.
 
         Create a new leaf node with X.
−
         '''return''' node(X, 1, Nil, Nil)
+
         '''return''' node(X, 1, <tex>\varnothing</tex>, <tex>\varnothing</tex>)
−
     '''else if''' X < value(T) '''then'''
+
     '''else if''' X < T.value
−
         left(T) := insert(X, left(T))
+
         T.left := insert(X, T.left)
−
     '''else if''' X > value(T) '''then'''
+
     '''else if''' X > T.value
−
         right(T) := insert(X, right(T))
+
         T.right := insert(X, T.right)
−
    '''end if'''
+
     <font color=green>// Случай X == value(T) не определен. Т.е. вставка не будет иметь никакого эффекта,
−
     <font color=green>//Случай X == value(T) не определен. Т.е. вставка не будет иметь никакого эффекта, возможны различные варианты обработки, в зависимости от решаемой задачи</font>
+
    возможны различные варианты обработки, в зависимости от решаемой задачи</font>
−
 
 
     T := skew(T)
 
     T := skew(T)
 
     T := split(T)
 
     T := split(T)
−
 
 
     '''return''' T
 
     '''return''' T
−
'''end function'''
 
  
 
Пример вставки нового элемента (на рис. уровни разделены горизонтальными линиями):
 
Пример вставки нового элемента (на рис. уровни разделены горизонтальными линиями):
Строка 116: Строка 108:
  
 
Чтобы сохранять баланс дерева необходимо делать skew, split и корректировку уровня для каждой вершины.
 
Чтобы сохранять баланс дерева необходимо делать skew, split и корректировку уровня для каждой вершины.
 +
 +
'''function''' decrease_level(T)
 +
    should_be = min(T.left.level, T.right.level) + 1
 +
    '''if''' should_be < T.level
 +
        T.level := should_be
 +
        '''if''' should_be < T.right.level
 +
            T.right.level := should_be
 +
    '''return''' T
  
 
  '''function''' delete(X, T)
 
  '''function''' delete(X, T)
−
     <font color=green>//X - удаляемый элемент, Т - корень дерева, из которого он должен быть удален</font>
+
     <font color=green>// X - удаляемый элемент, Т - корень дерева, из которого он должен быть удален</font>
−
   
+
     '''if''' T == <tex>\varnothing</tex>
−
     '''if''' nil(T) '''then'''
 
 
         '''return''' T
 
         '''return''' T
−
     '''else if''' X > value(T) '''then'''
+
     '''else if''' X > T.value
−
         right(T) := delete(X, right(T))
+
         T.right := delete(X, T.right)
−
     '''else if''' X < value(T) '''then'''
+
     '''else if''' X < T.value
−
         left(T) := delete(X, left(T))
+
         T.left := delete(X, T.left)
 
     '''else'''
 
     '''else'''
 
         '''if''' leaf(T) '''then'''
 
         '''if''' leaf(T) '''then'''
−
             '''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(value(L), 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>
−
   
 
−
     <font color=green>//Сбалансируем дерево. Если необходимо, уменьшим поля "уровень" у вершин на данном уровне, и затем skew и split все вершины на новом уровне</font>
 
 
     T := decrease_level(T)
 
     T := decrease_level(T)
 
     T := skew(T)
 
     T := skew(T)
−
     right(T) := skew(right(T))
+
     T.right := skew(T.right)
−
     '''if not''' nil(right(T))
+
     '''if not''' nil(T.right)
−
         right(right(T)) := skew(right(right(T)))
+
         right(T.right) := skew(T.right.right)
 
     '''end if'''
 
     '''end if'''
 
     T := split(T)
 
     T := split(T)
−
     right(T) := split(right(T))
+
     T.right := split(T.right)
−
    '''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
 
     '''return''' T
−
'''end function'''
 
  
 
Пример удаления вершины (на рис. уровни разделены горизонтальными линиями):
 
Пример удаления вершины (на рис. уровни разделены горизонтальными линиями):

Версия 01:08, 23 декабря 2016

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

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


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


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

Exaa.PNG

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

Exaa2.PNG

Свойства

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

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

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

Rb3.png

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

Rb2.png

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

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


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


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

1.[math]\mathrm{Skew(T)}[/math] — устранение левого горизонтального ребра. 

function skew(T)
   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

Skew.png

2.[math]\mathrm{Split(T)}[/math] — устранение двух последовательных правых горизонтальных ребер. 

function split(T)
   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

Split rb.png

Операции

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

Рекурсивная реализация. Спускаемся от корня вниз по дереву, сравнивая ключи; вставляем новую вершину; выходя из рекурсии и выполняем балансировку: [math]\mathrm{skew}[/math] и [math]\mathrm{split}[/math] для каждой вершины. 

function insert(X, T)
   // 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

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

Ex insert.png

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

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

Чтобы сохранять баланс дерева необходимо делать skew, split и корректировку уровня для каждой вершины. 

function decrease_level(T)
   should_be = min(T.left.level, T.right.level) + 1
   if should_be < T.level
       T.level := should_be
       if should_be < T.right.level
           T.right.level := should_be
   return T

function delete(X, T)
   // 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 := decrease_level(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

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

Exdelete.png

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

Скорость работы AA-дерева эквивалентна скорости работы красно-черного дерева. В среднем более простые алгоритмы на AA-дерева выполняются быстрее, но в красно-черном дереве делается меньше поворотов, что уравновешивает асимптотику.

См. также


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

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