Изменения

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

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

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

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

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

'''functionNode''' skew(Tt : '''Node''') '''if''' T t == <tex>\varnothing</tex>

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

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

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

'''<tex>\mathrm{Split(t)}</tex>''' {{---}} устранение двух последовательных правых горизонтальных ребер. Делаем левое вращение и увеличиваем уровень, чтобы заменить поддерево, содержащее две или более последовательных правильных горизонтальных связи, на вершину, содержащую два поддерева с меньшим уровнем.   '''functionNode''' split(Tt : '''Node''') '''if''' T t == <tex>\varnothing</tex>

'''else''' '''if''' Tt.right == <tex>\varnothing</tex> '''or''' Tt.right.right == <tex>\varnothing</tex> '''return''' Tt <font color=green>// Проверяем, один ли уровень у родителя и внука, т.е. существует ли два последовательных правых горизонтальных ребра</font> '''else''' '''if''' Tt.level == Tt.right.right.level <font color=green> // Существует два правых горизонтальных ребра. Берем центральную вершину, "поднимаем" «поднимаем» ее и возвращаем указатель на нее</font> R = T'''return''' Node(t.right T, t.right := R.level + 1, Node(t, t.level, t.left R, t.right.left := T R), t.level := Rright.level + 1 '''return''' Rright)

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

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

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

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

Чтобы сохранять баланс дерева необходимо делать skewБудем использовать дополнительную функцию <tex>\mathrm{decreaseLevel}</tex>, split и корректировку она будет обновлять уровень вершины, которую передают в функцию, в зависимости от значения уровня для каждой вершиныдочерних вершин.

'''functionNode''' decrease_leveldecreaseLevel(Tt : '''Node''') should_be shouldBe = min(Tt.left.level, Tt.right.level) + 1 '''if''' should_be shouldBe < Tt.level Tt.level := should_beshouldBe '''if''' should_be shouldBe < Tt.right.level Tt.right.level := should_beshouldBe '''return''' Tt

Чтобы сохранять баланс дерева необходимо делать <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''' T t == <tex>\varnothing</tex> '''return''' Tt '''else if''' X x > Tt.value Tt.right := delete(Xx, Tt.right) '''else if''' X x < Tt.value Tt.left := delete(Xx, Tt.left)

'''if''' leaf(Tt) '''then'''

'''else''' '''if''' Tt.left == <tex>\varnothing</tex> L :l = successor(Tt) Tt.right := delete(value(L)l.valuel, Tt.right) Tt.value := Ll.value

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

Оценка на высоту деревьев соответствует оценке для красно-черного дерева, <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 или простое бинарное дерево]