302
правки
Изменения
Нет описания правки
[[Файл: Rb2.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(T)}</tex>''' {{---}} устранение левого горизонтального ребра. Делаем правое вращение, чтобы заменить поддерево, содержащее левую горизонтальную связь, на поддерево, содержащее разрешенную правую горизонтальную связь. '''Node''' '''function''' skew(T: '''Node''')
'''if''' T == <tex>\varnothing</tex>
'''return''' <tex>\varnothing</tex>
'''return''' T
'''else''' '''if''' T.left.level == T.level '''then'''
<font color=green> // Меняем указатель горизонтального левого ребра</font>
L = T.left
T.left := L.right L.right := T
'''return''' L
'''else'''
'''return''' T
На рисунке ниже представлен пример работы алгоритма.
[[Файл: Skew.png]]
'''Node''' '''function''' split(T: '''Node''')
'''if''' T == <tex>\varnothing</tex>
'''return''' <tex>\varnothing</tex>
<font color=green> // Существует два правых горизонтальных ребра. Берем центральную вершину, "поднимаем" ее и возвращаем указатель на нее</font>
R = T.right
T.right := R.left R.left := T R.level := R.level + 1
'''return''' R
'''else'''
'''return''' T
На рисунке ниже представлен пример работы алгоритма.
[[Файл: Split_rb.png]]
== Операции ==
=== Вставка элемента ===
'''Node''' '''function''' insert(X: '''V''', T: '''Node''')
<font color=green>// X - вставляемое значение, Т - корень дерева, в который вставляется вершина</font>
'''if''' T == <tex>\varnothing</tex>
'''return''' node(X, 1, <tex>\varnothing</tex>, <tex>\varnothing</tex>)
'''else if''' X < T.value
T.left := insert(X, T.left)
'''else if''' X > T.value
T.right := insert(X, T.right)
<font color=green>// Случай X == value(T) не определен. Т.е. вставка не будет иметь никакого эффекта,
возможны различные варианты обработки, в зависимости от решаемой задачи</font>
T := skew(T) T := split(T)
'''return''' T
=== Удаление вершины ===
'''Node''' '''function''' decrease_leveldecreaseLevel(T: '''Node''') should_be shouldBe = min(T.left.level, T.right.level) + 1 '''if''' should_be shouldBe < T.level T.level := should_beshouldBe '''if''' should_be shouldBe < T.right.level T.right.level := should_beshouldBe
'''return''' T
Чтобы сохранять баланс дерева необходимо делать <tex>\mathrm{skew}</tex>, <tex>\mathrm{split}</tex> и <tex>\mathrm{decreaseLevel}</tex> для каждой вершины. '''Node''' '''function''' delete(X: '''V''', T: '''Node''')
<font color=green>// X - удаляемый элемент, Т - корень дерева, из которого он должен быть удален</font>
'''if''' T == <tex>\varnothing</tex>
'''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) '''then'''
'''return''' <tex>\varnothing</tex>
'''else''' '''if''' T.left == <tex>\varnothing</tex>
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
<font color=green>// Сбалансируем дерево. Если необходимо, уменьшим поля "уровень"
у вершин на данном уровне, и затем skew и split все вершины на новом уровне</font>
T := decrease_leveldecreaseLevel(T) T := skew(T) T.right := skew(T.right)
'''if not''' nil(T.right)
right(T.right) := skew(T.right.right)
'''end if'''
T := split(T) T.right := split(T.right)
'''return''' T
== Эффективность ==
Скорость работы AA-дерева эквивалентна скорости работы красно-черного дерева. В среднем более простые алгоритмы на AA-дерева выполняются быстрее, но в красно-черном дереве делается меньше поворотов, что уравновешивает асимптотику.
== См. также ==
