Изменения

Перейти к: навигация, поиск

Link-Cut Tree

185 байт добавлено, 21:33, 10 июня 2014
→‎cut(v)
Отрезает дерево с корнем <tex>v</tex>. После вызова <tex>expose(v) \ v</tex> станет корнем splay-дерева, и в правом поддереве будут содержатся все вершины, которые были ниже <tex>v</tex> в link-cut дереве, а в левом - те что выше. Обнулив указатель на левого ребенка <tex>v</tex> и на родителя в левом поддереве, получим требуемое.
'''function'''cut(v): '''tree'''):
expose(v)
Δw<tex>\vartriangle</tex>w(left(v)) += Δw<tex>\vartriangle</tex>w(v) Δmin<tex>\vartriangle</tex>min(v) <- tex>\leftarrow</tex> min{0, Δmin<tex>\vartriangle</tex>min(right(v)) + Δw<tex>\vartriangle</tex>w(right(v))} left(v) <- tex>\leftarrow</tex> null parent(left(v)) <- tex>\leftarrow</tex> null
==Оценка времени работы==
Lena
234
правки
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Служебная:Сравнение_версий/38373»

Навигация