302
правки
Изменения
Нет описания правки
#'''Skew(T)''' {{---}} устранение левого горизонтального ребра.
'''if''' T == NULL '''then'''
'''return''' NULL
'''return''' T
'''else''' '''if''' level(left(T)) == level(T) '''then'''
L = left(T)
left(T) := right(L)
'''end''' '''function'''
[[Файл: Skew.png]]
#'''Split(T)''' {{---}} устранение двух последовательных правых горизонтальных ребер.
'''if''' nil(T) '''then'''
'''return''' Nil
'''return''' T
'''else''' '''if''' level(T) == level(right(right(T))) '''then'''
R = right(T)
right(T) := left(R)
'''end''' '''if'''
'''end function'''
[[Файл: Split_rb.png]]
== Операции ==
Рекурсивная реализация. Спускаемся от корня вниз по дереву, сравнивая ключи; вставляем новую вершину; выходя из рекурсии и выполняем балансировку: skew и split для каждой вершины.
'''function''' insert '''is''' '''input''': (X, the value to be inserted, and T, the root of the tree to insert it into.) '''output''': A balanced version T including <font color=green>//X.- вставляемое значение, Т - корень дерева, в который вставляется вершина</font>
'''if''' nil(T) '''then'''
Create a new leaf node with X.
right(T) := insert(X, right(T))
'''end if'''
T := skew(T)
T := split(T)
Чтобы сохранять баланс дерева необходимо делать skew, split и корректировку уровня для каждой вершины.
'''function''' delete '''is''' '''input''': (X, the value to delete, and T, the root of the tree from which it should be deleted.) '''output''': T<font color=green>//X - удаляемый элемент, balancedТ - корень дерева, without the value X.из которого он должен быть удален</font>
'''if''' nil(T) '''then'''
left(T) := delete(X, left(T))
'''else'''
'''if''' leaf(T) '''then'''
'''return''' Nil
'''end if'''
'''end if'''
T := decrease_level(T)
T := skew(T)
'''end function'''
'''function''' decrease_level '''is''' '''input''': (T, a tree for which we want to remove links that skip levels. '''output''': T with its level decreased.)
should_be = min(level(left(T)), level(right(T))) + 1
== Эффективность ==
Скорость работы AA - дерева эквивалентна скорости работы красно-черного дерева. В среднем более простые алгоритмы на AA - дерева выполняются быстрее, но в красно-черном дереве делается меньше поворотов, что уравновешивает асимптотику.
== См. также ==
* [[B-дерево]]
* [[Splay-дерево]]
* [[АВЛ-дерево]]
* [[Декартово дерево]]
* [[Красно-черное дерево]]
== Источники информации ==
* [http://user.it.uu.se/~arnea/ps/simp.pdf {{---}} Balanced searched trees made simple]
* [https://en.wikipedia.org/wiki/AA_tree {{---}} AA - tree]
* [https://habrahabr.ru/post/110212/ {{---}} AA-Tree или простое бинарное дерево]
[[Категория:Дискретная математика и алгоритмы]]
[[Категория:Структуры данных]]
[[Категория:Деревья поиска]]
