302
правки
Изменения
Нет описания правки
== Балансировка ==
{{Определение|definition='''Горизонтальное ребро''' (англ. ''Horizontal edges'') - ребро, соединяющее вершины с одинаковым уровнем.}} В AA - дереве разрешены правые ребра, не идущие подряд, и запрещены все левые горизонтальные ребра. Эти более жесткие ограничения , аналогичные ограничениям на красно-черных деревьях, приводят к более простой реализации балансировки AA - дерева. Для балансировки АА-дерева нужно нужны следующие две операции:#'''Skew(pT)''' {{---}} устранение левого горизонтального ребра, соединяющего вершину ''p'' с вершиной того же уровня, что у ''p''.
[[Файл: Skew.png]]
#'''Split(pT)''' {{---}} устранение двух последовательных правых горизонтальных ребер, которые соединяют вершины с одним уровнем.
[[Файл: Split_rb.png]]
'''end''' '''if'''
'''end function'''
== Операции ==
=== Вставка элемента ===
Рекурсивная реализация. Спускаемся от корня вниз по дереву, сравнивая ключи; вставляем новую вершину; выходим из рекурсии и выполняем балансировку: 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 X.
Do the normal binary tree insertion procedure. Set the result of the
recursive call to the correct child in case a new node was created or the
root of the subtree changes.
'''if''' nil(T) '''then'''
Create a new leaf node with X.
'''return''' node(X, 1, Nil, Nil)
'''else if''' X < value(T) '''then'''
left(T) := insert(X, left(T))
'''else if''' X > value(T) '''then'''
right(T) := insert(X, right(T))
'''end if'''
Note that the case of X == value(T) is unspecified. As given, an insert
will have no effect. The implementor may desire different behavior.
Perform skew and then split. The conditionals that determine whether or
not a rotation will occur or not are inside of the procedures, as given
above.
T := skew(T)
T := split(T)
'''return''' T
'''end function'''
=== Удаление вершины ===
