Изменения

В отличие от красно-черных деревьев, к одной вершине можно присоединить вершину только того же уровня, только одну и только справа (другими словами, красные вершины могут быть добавлены только в качестве правого ребенка). На картинке ниже представлен пример === Свойства АА-дерева. [[Файл: Exaa.PNG]] На практике в AA-дереве вместо значения цвета для балансировки дерева в вершине хранится информация о ее уровне. На картинки ниже изображен пример того же дерева, построенного только на основе информации об уровне вершин, горизонтальные ребра обозначают связь вершин одного уровня.===

*Уровень каждого правого ребенка равен или на один меньше, чем у его родителя.

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

[[Файл: Rb2Pr1.png]]

1.=== Skew === '''<tex>\mathrm{Skew(Tt)}</tex>''' {{---}} устранение левого горизонтального ребра. Делаем правое вращение, чтобы заменить поддерево, содержащее левую горизонтальную связь, на поддерево, содержащее разрешенную правую горизонтальную связь.

'''functionNode''' skew(Tt : '''Node''') '''if''' T t == NULL '''then'''<tex>\varnothing</tex> '''return''' NULL<tex>\varnothing</tex> '''else''' '''if''' t.left(T) == NULL '''then'''<tex>\varnothing</tex> '''return''' Tt <font color=green>// Проверяем, есть ли у нас левое горизонтальное ребро</font> '''else''' '''if''' t.left.level(left(T)) == t.level(T) '''then''' <font color=green> //Меняем указатель горизонтального левого ребра</font> L = left(T) left(T) := right(L) right(L) := T '''return''' LNode(t.left, t.left.level, t.left.left, Node(t, t.level, t.left.right, t.right))

'''return''' Tt '''end''' '''if''' '''end''' '''function'''На рисунке ниже представлен пример работы алгоритма.

2.'''=== Split(T)''' {{---}} устранение двух последовательных правых горизонтальных ребер.===

'''<tex>\mathrm{Split(t)}</tex>''' {{---}} устранение двух последовательных правых горизонтальных ребер. Делаем левое вращение и увеличиваем уровень, чтобы заменить поддерево, содержащее две или более последовательных правильных горизонтальных связи, на вершину, содержащую два поддерева с меньшим уровнем.   '''functionNode''' split(T) t : '''ifNode''' nil(T) '''thenif'''t == <tex>\varnothing</tex> '''return''' Nil<tex>\varnothing</tex> '''else''' '''if''' nil(t.right(T)) == <tex>\varnothing</tex> '''or''' nil(t.right(.right(T))) '''then'''== <tex>\varnothing</tex> '''return''' Tt <font color=green>// Проверяем, один ли уровень у родителя и внука, т.е. существует ли два последовательных правых горизонтальных ребра</font> '''else''' '''if''' t.level(T) == level(t.right(.right(T))) '''then'''.level <font color=green> //Существует два правых горизонтальных ребра. Берем центральную вершину, "поднимаем" «поднимаем» ее и возвращаем указатель на нее</font> R = '''return''' Node(t.right(T) , t.right.level + 1, Node(T) := t, t.level, t.left(R) , t.right.left(R) := T level(R) := level(R, t.right.right) + 1 '''return''' R

'''return''' Tt '''end''' '''if''' '''end function'''На рисунке ниже представлен пример работы алгоритма.

Рекурсивная реализация. Спускаемся от корня вниз по деревуВставка нового элемента происходит как в обычном дереве поиска, только на пути вверх необходимо делать ребалансировку, сравнивая ключи; вставляем новую вершину; выходя из рекурсии и выполняем балансировку: используя <tex>\mathrm{skew }</tex> и <tex>\mathrm{split для каждой вершины}</tex>. Ниже представлена рекурсивная реализация алгоритма.

'''functionNode''' insert(Xx : '''V''', Tt : '''Node''') <font color=green>//X x {{- --}} вставляемое значение, Т t {{--- }} корень дерева, в который вставляется вершина</font> '''if''' nil(T) '''then''' Create a new leaf node with X.t == <tex>\varnothing</tex> '''return''' nodeNode(Xx, 1, Nil<tex>\varnothing</tex>, Nil<tex>\varnothing</tex>) '''else if''' X x < t.value(T) '''then''' t.left(T) := insert(Xx, t.left(T)) '''else if''' X x > t.value(T) '''then''' t.right(T) := insert(Xx, t.right(T)) '''end if''' <font color=green>//Случай X x == t.value(T) не определен. Т.е. вставка не будет иметь никакого эффекта, // возможны различные варианты обработки, в зависимости от решаемой задачи</font> T :t = skew(Tt) T :t = split(Tt) '''return''' T '''end function'''t

Рекурсивная реализация. Как и в большинстве сбалансированных бинарных деревьев, удаление внутренней вершины можно заменить на удаление листа, если заменить внутреннюю вершину на ее ближайшего "предшественника" (англ. ''predecessor'') «предшественника» или "преемника" (англ. ''successor'')«преемника», в зависимости от реализации. "Предшественник" находиться «Предшественник» находится в начале последнего левого ребра, после которого идут все правые ребра. По аналогии, "преемник" «преемник» может быть найден после одного правого ребра и последовательности левых ребер, пока не будет найден указатель на NULL. В силу свойства всех узлов уровня более чем <tex>1</tex>, имеющих двух детей, предшественник или преемник будет на уровне <tex>1</tex>, что делает их удаление тривиальным. Ниже представлена рекурсивная реализация алгоритма. Будем использовать дополнительную функцию <tex>\mathrm{decreaseLevel}</tex>, она будет обновлять уровень вершины, которую передают в функцию, в зависимости от значения уровня дочерних вершин.

Чтобы сохранять баланс дерева необходимо делать skew '''Node''' decreaseLevel(t : '''Node''') shouldBe = min(t.left.level, split и корректировку уровня для каждой вершиныt.right.level) + 1 '''if''' shouldBe < t.level t.level = shouldBe '''if''' shouldBe < t.right.level t.right.level = shouldBe '''return''' t

Чтобы сохранять баланс дерева необходимо делать <tex>\mathrm{skew}</tex>, <tex>\mathrm{split}</tex> и <tex>\mathrm{decreaseLevel}</tex> для каждой вершины.  '''functionNode''' delete(Xx : '''V''', Tt : '''Node''') <font color=green>//X x {{--- }} удаляемый элемент, Т t {{-- -}} корень дерева, из которого он должен быть удален</font> '''if''' nil(T) '''then'''t == <tex>\varnothing</tex> '''return''' Tt '''else if''' X x > t.value(T) '''then''' t.right(T) := delete(Xx, t.right(T)) '''else if''' X x < t.value(T) '''then''' t.left(T) := delete(Xx, t.left(T))

'''if''' leaf(Tt) '''then''' '''return''' Nil<tex>\varnothing</tex> '''else''' '''if''' nil(t.left(T)) '''then'''== <tex>\varnothing</tex> L :l = successor(Tt) t.right(T) := delete(value(L)l.valuel, t.right(T)) t.value(T) := l.value(L)

L :l = predecessor(Tt) t.left(T) := delete(l.value(L), t.left(T)) t.value(T) := l.value(L) '''end if''' '''end if''' <font color=green>//Сбалансируем дерево. Если необходимо, уменьшим поля "уровень" «уровень» // у вершин на данном уровне, и затем skew и split все вершины на новом уровне</font> T :t = decrease_leveldecreaseLevel(Tt) T :t = skew(Tt) t.right(T) := skew(t.right(T)) '''if not''' nil(t.right(T))<tex> \neq\ \varnothing</tex> t.right(.right(T)) := skew(t.right(.right(T))) '''end if''' T :t = split(Tt) t.right(T) := split(t.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'''t

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

* [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://habrahabr.ru/post/110212/ Хабрахабр {{---}} AA-Tree или простое бинарное дерево]