1632
правки
Изменения
м
rollbackEdits.php mass rollback
'''struct''' Node:
'''V''' value <font color="green">// значение вершины</font>
'''NodeV''' level <font color="green">// указатель на предкавысота вершины</font>
'''Node''' left <font color="green">// указатель на левого потомка</font>
'''Node''' right <font color="green">// указатель на правого потомка</font>
'''if''' t == <tex>\varnothing</tex>
'''return''' <tex>\varnothing</tex>
'''else''' '''if''' t.right == <tex>\varnothing</tex> '''or''' t.right.right == <tex>\varnothing</tex>
'''return''' t
<font color=green>// Проверяем, один ли уровень у родителя и внука, т.е. существует ли два последовательных правых горизонтальных ребра</font>
'''else''' '''if''' t.level == t.right.right.level
<font color=green>// Существует два правых горизонтальных ребра. Берем центральную вершину, «поднимаем» ее и возвращаем указатель на нее</font>
'''return''' Node(t.right,t.right.level+1,Node(t,t.level,t.left,t.right.left),t.right.right)
'''else'''
'''return''' t
=== Удаление вершины ===
Как и в большинстве сбалансированных бинарных деревьев, удаление внутренней вершины можно заменить на удаление листа, если заменить внутреннюю вершину на ее ближайшего «предшественника» или «преемника», в зависимости от реализации. «Предшественник» находиться находится в начале последнего левого ребра, после которого идут все правые ребра. По аналогии, «преемник» может быть найден после одного правого ребра и последовательности левых ребер, пока не будет найден указатель на NULL. В силу свойства всех узлов уровня более чем <tex>1</tex>, имеющих двух детей, предшественник или преемник будет на уровне <tex>1</tex>, что делает их удаление тривиальным. Ниже представлена рекурсивная реализация алгоритма.
Будем использовать дополнительную функцию <tex>\mathrm{decreaseLevel}</tex>, она будет обновлять уровень вершины, которую передают в функцию, в зависимости от значения уровня дочерних вершин.
'''else''' '''if''' t.left == <tex>\varnothing</tex>
l = successor(t)
t.right = delete(value(l).valuel, t.right)
t.value = l.value
'''else'''
l := predecessor(t) t.left = delete(l.value, t.left))
t.value = l.value
<font color=green>// Сбалансируем дерево. Если необходимо, уменьшим поля «уровень»
