Изменения

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

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

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

[[Файл: Rb2Pr1.png]] Для представления АА-дерева в памяти будем использовать следующую структуру: '''struct''' Node: '''V''' value <font color="green">// значение вершины</font> '''Node''' left <font color="green">// указатель на левого потомка</font> '''Node''' right <font color="green">// указатель на правого потомка</font> '''Node''' parent <font color="green">// указатель на предка</font>

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

'''Node''' '''function''' skew(T t : '''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'''

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

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

'''Node''' '''function''' split(T t : '''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

'''Node''' '''function''' insert(X x : '''V''', T t : '''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>, что делает их удаление тривиальным. Ниже представлена рекурсивная реализация алгоритма.

'''Node''' '''function''' decreaseLevel(T t : '''Node''') shouldBe = min(Tt.left.level, Tt.right.level) + 1 '''if''' shouldBe < Tt.level Tt.level = shouldBe '''if''' shouldBe < Tt.right.level Tt.right.level = shouldBe '''return''' Tt

'''Node''' '''function''' delete(X x : '''V''', T t : '''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 = decreaseLevel(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-дерева эквивалентна скорости работы красно-черного дерева, но так как в реализации вместо цвета обычно хранят «уровень» вершины, дополнительные расходы по памяти достигают байта.

* [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 или простое бинарное дерево]