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>.
'''link(v, u)'''
expose(v) <font color=green> //теперь v - корень в splay-дереве пути и не имеет левого ребенка(так как ключ равен глубине в link-cut дереве)</font>
expose(u)
Δw(u) -= Δw(v) <font color=green>//чтобы сделать u родителем v в link-cut дереве 1. делаем путь, содержащий u, левым ребенком v в splay-дереве</font>
parent(u) = <- v <font color=green>// 2. обновляем Δw, Δmin</font> left(v) = <- u Δmin(v) = <- min{0, Δmin(u) + Δw(u), Δmin(right(v)) + Δw((right(v)))}
===cut(v)===
