302
правки
Изменения
Нет описания правки
АA-дерево названо по первым буквам имени и фамилии изобретателя, Арне Андерссона, который впервые предложил данную модификацию [[Красно-черное дерево|красно-черного дерева]] в 1993 году.
== Свойства ==
{{Определение
[[Файл: Exaa2.PNG]]
Свойства АА-дерева:
*Уровень каждого листа равен <tex>1</tex>.
*Уровень каждого левого ребенка ровно на один меньше, чем у его родителя.
*Уровень каждого правого ребенка равен или на один меньше, чем у его родителя.
*Уровень каждого правого внука строго меньше, чем у его прародителя.
*Каждая вершина с уровнем больше <tex>1</tex> имеет двоих детей.
'''struct''' Node:
'''V''' value <font color="green">// значение вершины</font>
'''Node''' level <font color="green">// указатель на предка</font>
'''Node''' left <font color="green">// указатель на левого потомка</font>
'''Node''' right <font color="green">// указатель на правого потомка</font>
== Балансировка ==
=== Skew ===
'''<tex>\mathrm{Skew(Tt)}</tex>''' {{---}} устранение левого горизонтального ребра. Делаем правое вращение, чтобы заменить поддерево, содержащее левую горизонтальную связь, на поддерево, содержащее разрешенную правую горизонтальную связь.
'''Node''' '''function''' skew(T t : '''Node''') '''if''' T t == <tex>\varnothing</tex>
'''return''' <tex>\varnothing</tex>
'''else''' '''if''' Tt.left == <tex>\varnothing</tex> '''return''' Tt '''else''' '''if''' Tt.left.level == Tt.level '''then'''
<font color=green>// Меняем указатель горизонтального левого ребра</font>
'''else'''
'''return''' Tt
На рисунке ниже представлен пример работы алгоритма.
=== Split ===
'''<tex>\mathrm{Split(Tt)}</tex>''' {{---}} устранение двух последовательных правых горизонтальных ребер. Делаем левое вращение и увеличиваем уровень, чтобы заменить поддерево, содержащее две или более последовательных правильных горизонтальных связи, на вершину, содержащую два поддерева с меньшим уровнем.
'''Node''' '''function''' split(T t : '''Node''') '''if''' T t == <tex>\varnothing</tex>
'''return''' <tex>\varnothing</tex>
'''else''' '''if''' Tt.right == <tex>\varnothing</tex> '''or''' Tt.right.right == <tex>\varnothing</tex> '''return''' Tt '''else''' '''if''' Tt.level == Tt.right.right.level
<font color=green> // Существует два правых горизонтальных ребра. Берем центральную вершину, "поднимаем" ее и возвращаем указатель на нее</font>
'''else'''
'''return''' Tt
На рисунке ниже представлен пример работы алгоритма.
Вставка нового элемента происходит как в обычном дереве поиска, только на пути вверх необходимо делать ребалансировку, используя <tex>\mathrm{skew}</tex> и <tex>\mathrm{split}</tex>. Ниже представлена рекурсивная реализация алгоритма.
'''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>
Пример вставки нового элемента (на рис. уровни разделены горизонтальными линиями):
=== Удаление вершины ===
Как и в большинстве сбалансированных бинарных деревьев, удаление внутренней вершины можно заменить на удаление листа, если заменить внутреннюю вершину на ее ближайшего "предшественника" (англ. ''predecessor'') «предшественника» или "преемника" (англ. ''successor'')«преемника», в зависимости от реализации. "Предшественник" «Предшественник» находиться в начале последнего левого ребра, после которого идут все правые ребра. По аналогии, "преемник" «преемник» может быть найден после одного правого ребра и последовательности левых ребер, пока не будет найден указатель на NULL. В силу свойства всех узлов уровня более чем <tex>1</tex>, имеющих двух детей, предшественник или преемник будет на уровне <tex>1</tex>, что делает их удаление тривиальным. Ниже представлена рекурсивная реализация алгоритма.
Будем использовать дополнительную функцию <tex>\mathrm{decreaseLevel}</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
Чтобы сохранять баланс дерева необходимо делать <tex>\mathrm{skew}</tex>, <tex>\mathrm{split}</tex> и <tex>\mathrm{decreaseLevel}</tex> для каждой вершины.
'''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)
'''else'''
'''if''' leaf(Tt) '''then'''
'''return''' <tex>\varnothing</tex>
'''else''' '''if''' Tt.left == <tex>\varnothing</tex> L l = successor(Tt) Tt.right = delete(value(Ll), Tt.right) Tt.value = Ll.value
'''else'''
<font color=green>// Сбалансируем дерево. Если необходимо, уменьшим поля "уровень"
у вершин на данном уровне, и затем skew и split все вершины на новом уровне</font>
'''end if'''
Пример удаления вершины (на рис. уровни разделены горизонтальными линиями):
* [[Декартово дерево]]
* [[Красно-черное дерево]]
== Источники информации ==
* [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 или простое бинарное дерево]
[[Категория:Дискретная математика и алгоритмы]]
[[Категория:Структуры данных]]
[[Категория:Деревья поиска]]
