234
правки
Изменения
→link(v, u)
Если <tex>v</tex> - корень, а <tex>u</tex> - вершина в другом дереве, то <tex>link(v, u)</tex> соединяет два дерева добавлением ребра <tex>(v, u)</tex>, причем <tex>u</tex> становится родителем <tex>v</tex>.
'''functiontree''' link(v : '''tree''', u : '''tree'''):
expose(v) <font color=green> //теперь v - корень в splay-дереве пути и не имеет левого ребенка(так как ключ равен глубине в link-cut дереве)</font>
expose(u)
left(v) <tex>\leftarrow</tex> u
<tex>\vartriangle</tex>min(v) <tex>\leftarrow</tex> min{0, <tex>\vartriangle</tex>min(u) + <tex>\vartriangle</tex>w(u), <tex>\vartriangle</tex>min(right(v)) + <tex>\vartriangle</tex>w((right(v)))}
'''return''' v
===cut(v)===
