302
правки
Изменения
Нет описания правки
Для балансировки АА-дерева нужны следующие две операции:
1.'''<tex>\mathrm{Skew(T)}</tex>''' {{---}} устранение левого горизонтального ребра.
'''function''' skew(T)
'''if''' T == NULL '''then'''<tex>\varnothing</tex> '''return''' NULL<tex>\varnothing</tex> '''else''' '''if''' T.left(T) == NULL '''then'''<tex>\varnothing</tex>
'''return''' T
'''else''' '''if''' T.left.level(left(T)) == T.level(T) '''then''' <font color=green> //Меняем указатель горизонтального левого ребра</font> L = T.left(T) T.left(T) := L.right(L) L.right(L) := T
'''return''' L
'''else'''
'''return''' T
[[Файл: Skew.png]]
2.'''<tex>\mathrm{Split(T)}</tex>''' {{---}} устранение двух последовательных правых горизонтальных ребер.
'''function''' split(T)
'''if''' nil(T) '''then'''== <tex>\varnothing</tex> '''return''' Nil<tex>\varnothing</tex> '''else''' '''if''' nil(T.right(T)) == <tex>\varnothing</tex> '''or''' nil(T.right(.right(T))) '''then'''== <tex>\varnothing</tex>
'''return''' T
'''else''' '''if''' T.level(T) == level(T.right(.right(T))) '''then'''.level <font color=green> //Существует два правых горизонтальных ребра. Берем центральную вершину, "поднимаем" ее и возвращаем указатель на нее</font> R = T.right(T) T.right(T) := R.left(R) R.left(R) := T R.level(R) := R.level(R) + 1
'''return''' R
'''else'''
'''return''' T
[[Файл: Split_rb.png]]
== Операции ==
=== Вставка элемента ===
Рекурсивная реализация. Спускаемся от корня вниз по дереву, сравнивая ключи; вставляем новую вершину; выходя из рекурсии и выполняем балансировку: <tex>\mathrm{skew }</tex> и <tex>\mathrm{split }</tex> для каждой вершины.
'''function''' insert(X, T)
<font color=green>//X - вставляемое значение, Т - корень дерева, в который вставляется вершина</font> '''if''' nil(T) '''then'''== <tex>\varnothing</tex>
Create a new leaf node with X.
'''return''' node(X, 1, Nil<tex>\varnothing</tex>, Nil<tex>\varnothing</tex>) '''else if''' X < T.value(T) '''then''' T.left(T) := insert(X, T.left(T)) '''else if''' X > T.value(T) '''then''' T.right(T) := insert(X, T.right(T)) '''end if''' <font color=green>//Случай X == value(T) не определен. Т.е. вставка не будет иметь никакого эффекта, возможны различные варианты обработки, в зависимости от решаемой задачи</font>
T := skew(T)
T := split(T)
'''return''' T
Пример вставки нового элемента (на рис. уровни разделены горизонтальными линиями):
Чтобы сохранять баланс дерева необходимо делать skew, split и корректировку уровня для каждой вершины.
'''function''' decrease_level(T)
should_be = min(T.left.level, T.right.level) + 1
'''if''' should_be < T.level
T.level := should_be
'''if''' should_be < T.right.level
T.right.level := should_be
'''return''' T
'''function''' delete(X, T)
<font color=green>//X - удаляемый элемент, Т - корень дерева, из которого он должен быть удален</font> '''if''' nil(T) '''then'''== <tex>\varnothing</tex>
'''return''' T
'''else if''' X > T.value(T) '''then''' T.right(T) := delete(X, T.right(T)) '''else if''' X < T.value(T) '''then''' T.left(T) := delete(X, T.left(T))
'''else'''
'''if''' leaf(T) '''then'''
'''return''' Nil<tex>\varnothing</tex> '''else''' '''if''' nil(T.left(T)) '''then'''== <tex>\varnothing</tex>
L := successor(T)
T.right(T) := delete(value(L), T.right(T)) T.value(T) := L.value(L)
'''else'''
L := predecessor(T)
T.left(T) := delete(L.value(L), T.left(T)) T.value(T) := L.value(L) '''end if''' '''end if''' <font color=green>//Сбалансируем дерево. Если необходимо, уменьшим поля "уровень" у вершин на данном уровне, и затем skew и split все вершины на новом уровне</font>
T := decrease_level(T)
T := skew(T)
T.right(T) := skew(T.right(T)) '''if not''' nil(T.right(T)) right(T.right(T)) := skew(T.right(.right(T)))
'''end if'''
T := split(T)
T.right(T) := split(right(T)) '''return''' T '''end function''' '''function''' decrease_level(T) should_be = min(level(left(T)), level(right(T))) + 1 '''if''' should_be < level(T) '''then''' level(T) := should_be '''if''' should_be < level(.right(T)) '''then''' level(right(T)) := should_be '''end if''' '''end if'''
'''return''' T
Пример удаления вершины (на рис. уровни разделены горизонтальными линиями):
