24
правки
Изменения
м
parent(left(v)) <tex>=</tex> null
Исправлена описка
'''Динамические деревья ''' (англ.''dynamic tree'') используются в двух областях: [[Определение сети, потока|потоки]] и динамические графы.
В первом случае динамические деревья позволяют построить эффективные алгоритмы для задачи о поиске максимального потока.
В динамическом графе периодически происходят изменения: появляются и исчезают ребра, меняются их веса. Изменения нужно Нужно быстро обрабатыватьизменения, а также уметь [[Отношение связности, компоненты связности | проверять связность]], [[Алгоритмы на деревьях|искать диаметр]]. Динамические деревья являются инструментом, который позволяет легко решать эти задачи. Динамические деревья особенно эффективны, когда нужно работать с большими деревьями и большим количеством запросов '''link''' и '''cut'''.
'''Link-cut tree''' {{---}} это структура данных, которая хранит [[Дерево, эквивалентные определения |лес деревьев]] и позволяет выполнять следующие операции:
[[Файл:Path_to_tree.png|250px|thumb|right|Пример построения дерева для пути]]
* '''<tex>\mathrm{add(v, c)}</tex>''' и '''<tex>\mathrm{min(v)}</tex>''' {{---}} прибавлять константу и искать минимум на некотором суффиксе (то есть на пути от вершины до корня), * '''<tex>\mathrm{cut(v)}</tex>''' {{---}} разбить один путь на два,* '''<tex>\mathrm{link(v, u)}</tex>''' {{---}} подвешивать голову одного пути к хвосту другого.
Если бы не последние две операции, то можно было бы применить [[Несогласованные поддеревья. Реализация массового обновления|дерево отрезков]], сложив в него вершины в том порядке в котором они идут в пути. Но непонятно, как сливать или разрезать деревья отрезков. Если Эту задачу можно решить при помощи [[Декартово дерево по неявному ключу|декартового дерева по неявному ключу]]. Также, если использовать какие-нибудь сливаемые деревья, то <tex>\mathrm{link}</tex> и <tex> \mathrm{cut}</tex> реализуются просто. Осталось научиться искать минимум и прибавлять константу на пути. Для этого, как и в деревьях отрезков, будем хранить дополнительные значения в вершинах.
В качестве сливаемых деревьев выберем [[Splay-дерево|splay-деревья]], в которых ключи выбираются равными глубине вершины.
===min(v)===
Построим splay-дерево для пути и сравним минимум вес корня <tex>v</tex> c минимумом в левом поддереве:
'''function''' min(v: '''tree'''): '''int'''
expose(v)
===cut(v)===
Отрезает дерево с корнем <tex>v</tex>. После вызова <tex>\mathrm{expose(v)}</tex> вершина <tex>v</tex> станет корнем splay-дерева, и в правом поддереве будут содержатся содержаться все вершины, которые были ниже <tex>v</tex> в link-cut дереве, а в левом {{---}} те что выше. Обнулив указатель на левого ребенка <tex>v</tex> и на родителя в левом поддереве, получим требуемое.
'''function''' cut(v: '''tree'''):
<tex>\vartriangle</tex>w(left(v)) += <tex>\vartriangle</tex>w(v)
<tex>\vartriangle</tex>min(v) <tex>=</tex> min{0, <tex>\vartriangle</tex>min(right(v)) + <tex>\vartriangle</tex>w(right(v))}
parent(left(v)) <tex>=</tex> null
left(v) <tex>=</tex> null
==Оценка времени работы==
Докажем, что [[Амортизационный анализ|амортизационная стоимость операции]] <tex>\mathrm{expose}</tex> равна <tex>O(\log n)</tex>.
Пусть <tex>s(v)</tex> {{---}} количество вершин в поддеревьях <tex>v</tex> ( здесь имеется в виду splay-дерево пути, котоый который строится в ходе выполнения <tex>\mathrm{expose}</tex>), <tex>r(v) = \log s(v)</tex>. По [[Splay-дерево#Lemma1|лемме]] стоимость ''i''-той операции <tex>\mathrm{splay}</tex> не превосходит <tex>1 + 3 \cdot (r(t) - r(v))</tex>. Это приводит к тому, что амортизационная стоимость <tex>\mathrm{expose}</tex> ограничена следующим значением:
<tex>3 \cdot \log n - 3 \cdot \log (s(v)) + M</tex>
===LCA===
C помощью link-cut-дерева можно найти наименьшего общего предка:
'''treefunction''' lca(u: '''tree''', v: '''tree'''):'''tree'''
expose(u)
expose(v)
==См. также==
*[[Метод двоичного подъема]]*[[Алгоритм Тарьяна поиска LCA за O(1) в оффлайн]]*[[Алгоритм Шибера-Вишкина]]
==Источники информации==
*[http://www.lektorium.tv/lecture/14464 А.С. Станкевич, "Дополнительные главы алгоритмов"]*[https://sites.google.com/site/indy256/algo/link-cut-tree-lca Реализация LCA на link-cut дереве]*[http://www.cs.cmu.edu/~sleator/papers/dynamic-trees.pdf D. Sleator and R. Tarjan, "A Data Structure for Dynamic Trees"]*[http://compgeom.cs.uiuc.edu/~jeffe/teaching/datastructures/2006/notes/07-linkcut.pdf Jeff Erickson. Lecture 7. Link-Cut Trees]*[http://planarity.org/Klein_splay_trees_and_link-cut_trees.pdf Optimization Algorithms for Planar Graphs. Splay trees and link-cut trees]*[http://en.wikipedia.org/wiki/Link/cut_tree Wikipedia {{---}} Link/cut tree]
[[Категория: Дискретная математика Алгоритмы и алгоритмыструктуры данных]]
[[Категория: Задача о наименьшем общем предке]]
