302
правки
Изменения
Нет описания правки
'''return''' T
'''end function'''
Пример вставки нового элемента:
=== Удаление вершины ===
Рекурсивная реализация. Как и в большинстве сбалансированных бинарных деревьев, удаление внутренней вершины можно заменить на удаление листа, если заменить внутреннюю вершину на ее ближайшего "предшественника" (англ. ''predecessor'') или "преемника" (англ. ''successor''), в зависимости от реализации. "Предшественник" находиться в начале последнего левого ребра, после которого идут все правые ребра. По аналогии, "преемник" может быть найден после одного правого ребра и последовательности левых ребер, пока не будет найден указатель на NULL. В силу свойства всех узлов уровня более чем 1, имеющих двух детей, предшественник или преемник будет на уровне 1, что делает их удаление тривиальным.
Чтобы сохранять баланс дерева необходимо делать 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, balanced, without the value X.
'''if''' nil(T) '''then'''
'''return''' T
'''else if''' X > value(T) '''then'''
right(T) := delete(X, right(T))
'''else if''' X < value(T) '''then'''
left(T) := delete(X, left(T))
'''else'''
If we're a leaf, easy, otherwise reduce to leaf case.
'''if''' leaf(T) '''then'''
'''return''' Nil
'''else''' '''if''' nil(left(T)) '''then'''
L := successor(T)
right(T) := delete(value(L), right(T))
value(T) := value(L)
'''else'''
L := predecessor(T)
left(T) := delete(value(L), left(T))
value(T) := value(L)
'''end if'''
'''end if'''
Rebalance the tree. Decrease the level of all nodes in this level if
necessary, and then skew and split all nodes in the new level.
T := decrease_level(T)
T := skew(T)
right(T) := skew(right(T))
'''if not''' nil(right(T))
right(right(T)) := skew(right(right(T)))
'''end if'''
T := split(T)
right(T) := split(right(T))
'''return''' 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
'''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
'''end function'''
Пример удаления вершины:
