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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 74: Строка 74:
 
     '''else''' '''if''' t.left.level == t.level
 
     '''else''' '''if''' t.left.level == t.level
 
         <font color=green>// Меняем указатель горизонтального левого ребра</font>
 
         <font color=green>// Меняем указатель горизонтального левого ребра</font>
         l = t.left
+
         '''return''' Node(t.left,t.left.level,t.left.left,Node(t,t.level,t.left.right,t.right))
        t.left = l.right
 
        l.right = t
 
        '''return''' l
 
 
     '''else'''
 
     '''else'''
 
         '''return''' t
 
         '''return''' t
Строка 97: Строка 94:
 
     '''else''' '''if''' t.level == t.right.right.level
 
     '''else''' '''if''' t.level == t.right.right.level
 
         <font color=green>// Существует два правых горизонтальных ребра. Берем центральную вершину, «поднимаем» ее и возвращаем указатель на нее</font>
 
         <font color=green>// Существует два правых горизонтальных ребра. Берем центральную вершину, «поднимаем» ее и возвращаем указатель на нее</font>
         r = t.right
+
         '''return''' Node(t.right,t.right.level+1,Node(t,t.level,t.left,t.right.left),t.right.right)
        t.right = r.left
 
        r.left = t
 
        r.level = r.level + 1
 
        '''return''' r
 
 
     '''else'''
 
     '''else'''
 
         '''return''' t
 
         '''return''' t

Версия 23:12, 26 декабря 2016

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

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

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

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

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

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

struct Node:
  V value                  // значение вершины
  Node 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(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 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-дерева эквивалентна скорости работы красно-черного дерева, но так как в реализации вместо цвета обычно хранят «уровень» вершины, дополнительные расходы по памяти достигают байта.

См. также

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