234
правки
Изменения
→cut(v)
Δmin(v) = min{0, Δmin(u) + Δw(u), Δmin(right(v)) + Δw((right(v)))}
===cut(v)===
Отрезает дерево с корнем <tex>v</tex>. После вызова <tex>expose(v)</tex> <tex>v</tex> станет корнем splay-дерева, и в правом поддереве будут содержатся все вершины, которые были ниже <tex>v</tex> в представляемом дереве, а в левом - те что выше. Обнулив указатель на левого ребенка <tex>v</tex> и на родителя в левом поддереве, получим требуемое.
cut(v)
expose(v)
Δw(left(v)) += Δw(v)
Δmin(v) = min{0, Δmin(right(v)) + Δw(right(v))}
left(v) = null
parent(left(v)) = null
