234
правки
Изменения
→expose(u)
'''function''' expose(u : '''tree'''):
splay(u)
v <- tex>\leftarrow</tex> u '''while (''' v != root) p <- tex>\leftarrow</tex> pathparent(v) <font color=green>//получаем указатель на ближайшую вершину пути, пересекающего путь от u до корня</font>
splay(p) <font color=green>//теперь в правом поддереве p находятся вершины пути, которые находятся ниже чем p в link-cut-дереве,</font>
parent(right(p)) <- tex>\leftarrow</tex> null <font color=green>//поэтому правое поддерево p делаем новым путем</font> pathparent(right(p)) <- tex>\leftarrow</tex> p right(p) <- tex>\leftarrow</tex> v <font color=green>//объединяем оставшийся и построенный пути</font> Δw<tex>\vartriangle</tex>w(v) -= Δw<tex>\vartriangle</tex>w(p) Δmin<tex>\vartriangle</tex>min(p) <- tex>\leftarrow</tex> min{0, Δmin<tex>\vartriangle</tex>min(left(p)) + Δw<tex>\vartriangle</tex>w(left(p)), Δmin<tex>\vartriangle</tex>min(right(p)) + Δw<tex>\vartriangle</tex>w(right(p))} pathparent(v) <- tex>\leftarrow</tex> null v <- tex>\leftarrow</tex> p
splay(u)
