Динамические деревья слейтора тарьяна

Link-Cut Tree

Динамические деревья (англ.dynamic tree) используются в двух областях: потоки и динамические графы. В первом случае динамические деревья позволяют построить эффективные алгоритмы для задачи о поиске максимального потока. В динамическом графе периодически происходят изменения: появляются и исчезают ребра, меняются их веса. Нужно быстро обрабатывать изменения, а также уметь проверять связность, искать диаметр. Динамические деревья являются инструментом, который позволяет легко решать эти задачи. Динамические деревья особенно эффективны, когда нужно работать с большими деревьями и большим количеством запросов link и cut.

Link-cut tree — это структура данных, которая хранит лес деревьев и позволяет выполнять следующие операции:

• [math]\mathrm[/math] — искать минимум на пути от вершины до корня,
• [math]\mathrm[/math] — прибавлять константу на пути от вершины до корня,
• [math]\mathrm[/math] — подвешивать одно дерево на другое,
• [math]\mathrm[/math] — отрезать дерево с корнем в вершине [math]\mathrm[/math] .

Среднее время выполнения каждой операции — [math]O(\log n)[/math] . Эта структура данных была придумана Робертом Тарьяном и Даниелем Слейтером в 1982 году.

Решение задачи в частном случае

Сначала рассмотрим частный случай, в котором все деревья — это пути, и мы хотим уметь:

• [math]\mathrm[/math] и [math]\mathrm[/math] — прибавлять константу и искать минимум на некотором суффиксе (то есть на пути от вершины до корня),
• [math]\mathrm[/math] — разбить один путь на два,
• [math]\mathrm[/math] — подвешивать голову одного пути к хвосту другого.

Если бы не последние две операции, то можно было бы применить дерево отрезков, сложив в него вершины в том порядке в котором они идут в пути. Но непонятно, как сливать или разрезать деревья отрезков. Эту задачу можно решить при помощи декартового дерева по неявному ключу. Также, если использовать какие-нибудь сливаемые деревья, то [math]\mathrm[/math] и [math] \mathrm[/math] реализуются просто. Осталось научиться искать минимум и прибавлять константу на пути. Для этого, как и в деревьях отрезков, будем хранить дополнительные значения в вершинах. В качестве сливаемых деревьев выберем splay-деревья, в которых ключи выбираются равными глубине вершины.

Тогда операции [math]\mathrm[/math] будет соответствовать [math]\mathrm[/math] .

[math]\mathrm[/math] соединяет голову первого пути с хвостом второго. Используем функцию [math]\mathrm[/math] , которая вызовет [math]\mathrm[/math] от хвоста второго пути и сделает первый путь правым ребенком корня [math]\mathrm[/math] , то есть теперь [math]\mathrm[/math] находится ниже, чем [math]\mathrm[/math] .

Чтобы прибавлять заданное число на пути от вершины до корня, будем в каждой вершине хранить величину [math]\Delta w[/math] , которая равна разнице между весом вершины и весом её родителя. Для корня это значение равно весу самого корня. Поэтому вес вершины определятся следующим образом:

[math]w(u) = \displaystyle \sum_v^<> \Delta w(v)[/math] , где [math] v [/math] — все предки вершины [math] u [/math] .

При прибавлении [math]\alpha[/math] на пути от вершины [math]v[/math] до корня, сначала вызывается [math]\mathrm[/math] , после чего в левом поддереве находятся вершины, которые лежат на пути к корню. Затем надо прибавить [math]\alpha[/math] к [math]\Delta w(v)[/math] и, чтобы сохранить веса вершин, которые находятся ниже в пути, вычесть [math]\alpha[/math] от [math]\Delta w(right(v))[/math] .

Для реализации [math]\min[/math] будем хранить минимум уже для всего поддерева. Чтобы искать минимум от вершины [math]v[/math] , надо вызвать [math]\mathrm[/math] и сравнить её вес с минимумом левого поддерева, в котором теперь находятся все вершины пути кроме [math]v[/math] . Определим [math]\Delta \min (v)[/math] таким образом, чтобы сохранялся следующий инвариант: [math]\min (v) = \Delta \min (v) + w(v) [/math] . Пусть [math]l[/math] и [math]r[/math] дети [math]v[/math] , тогда

Link-cut tree

Чтобы обобщить, разобьем дерево на множество непересекающихся путей. Каждое ребро обозначим либо сплошным, либо пунктирным. Все пути в link-cut дереве хранятся в виде splay-деревьев. Корень каждого splay-дерева хранит указатель на вершину-родителя. В дальнейшем будем называть этот указатель [math]pathparent[/math] .

expose(u)

Ключевая операция в link-cut-деревьях — [math]\mathrm[/math] . После её выполнения [math]u[/math] лежит на одном пути с корнем link-cut дерева и при этом становится корнем в splay-дереве получившегося пути. Для этого она поднимается вверх по link-cut дереву, и если какой-нибудь путь пересекает путь от [math]u[/math] до корня, то она его отрезает, разъединяя splay-дерево и делая соответствующее сплошное ребро пунктирным ребром.

function expose(u: tree): splay(u) v [math]=[/math] u while v [math] \ne [/math] root p [math]=[/math] pathparent(v) //получаем указатель на ближайшую вершину пути, пересекающего путь от u до корня splay(p) //теперь в правом поддереве p находятся вершины пути, которые находятся ниже чем p в link-cut-дереве, parent(right(p)) [math]=[/math] null //поэтому правое поддерево p делаем новым путем pathparent(right(p)) [math]=[/math] p right(p) [math]=[/math] v //объединяем оставшийся и построенный пути [math]\vartriangle[/math]w(v) -= [math]\vartriangle[/math]w(p) [math]\vartriangle[/math]min(p) [math]=[/math] min[math]\vartriangle[/math]min(left(p)) + [math]\vartriangle[/math]w(left(p)), [math]\vartriangle[/math]min(right(p)) + [math]\vartriangle[/math]w(right(p))> pathparent(v) [math]=[/math] null v [math]=[/math] p splay(u)

add(v, c)

Чтобы прибавить константу на пути от [math]v[/math] до корня link-cut-дерева вызовем [math]\mathrm[/math] , что построит запрашиваемый путь в виде splay-дерева, в котором [math]v[/math] — корень, и в левом поддереве находятся вершины, которые находятся выше чем [math]v[/math] в link-cut-дереве (то есть все вершины пути без [math]v[/math] ), а в правом — те, что ниже. Тогда прибавим [math]c[/math] к [math]\Delta w(v)[/math] и вычтем константу от правого ребенка [math]v[/math] , чтобы скомпенсировать разницу и сохранить инвариант.

function add(v: tree, c: int): expose(v) [math]\vartriangle[/math]w(v) += c [math]\vartriangle[/math]w(right(v)) -= c

min(v)

Построим splay-дерево для пути и сравним вес корня [math]v[/math] c минимумом в левом поддереве:

function min(v: tree): int expose(v) if [math]\vartriangle[/math]min(left(v)) + [math]\vartriangle[/math]w(left(v)) < [math]\vartriangle[/math]w(v) return [math]\vartriangle[/math]min(left(v)) + [math]\vartriangle[/math]w(left(v)) else return [math]\vartriangle[/math]w(v)

link(v, u)

Если [math]v[/math] — корень, а [math]u[/math] — вершина в другом дереве, то [math]\mathrm[/math] соединяет два дерева добавлением ребра [math](v, u)[/math] , причем [math]v[/math] становится родителем [math]u[/math] .

function link(v: tree, u: tree): tree expose(v) //теперь v — корень в splay-дереве пути и не имеет левого ребенка(так как ключ равен глубине в link-cut дереве) expose(u) [math]\vartriangle[/math]w(u) -= [math]\vartriangle[/math]w(v) //чтобы сделать u родителем v в link-cut дереве 1. делаем путь, содержащий u, левым ребенком v в splay-дереве parent(u) [math]=[/math] v // 2. обновляем [math]\vartriangle[/math]w, [math]\vartriangle[/math]min left(v) [math]=[/math] u [math]\vartriangle[/math]min(v) [math]=[/math] min[math]\vartriangle[/math]min(u) + [math]\vartriangle[/math]w(u), [math]\vartriangle[/math]min(right(v)) + [math]\vartriangle[/math]w((right(v)))> return v

cut(v)

Отрезает дерево с корнем [math]v[/math] . После вызова [math]\mathrm[/math] вершина [math]v[/math] станет корнем splay-дерева, и в правом поддереве будут содержаться все вершины, которые были ниже [math]v[/math] в link-cut дереве, а в левом — те что выше. Обнулив указатель на левого ребенка [math]v[/math] и на родителя в левом поддереве, получим требуемое.

function cut(v: tree): expose(v) [math]\vartriangle[/math]w(left(v)) += [math]\vartriangle[/math]w(v) [math]\vartriangle[/math]min(v) [math]=[/math] min[math]\vartriangle[/math]min(right(v)) + [math]\vartriangle[/math]w(right(v))> parent(left(v)) [math]=[/math] null left(v) [math]=[/math] null

Оценка времени работы

Назовем ребро из [math]u[/math] в её родителя [math]v[/math] тяжелым, если количество детей [math]u[/math] равное [math]d(u) \gt \dfrac d(v)[/math] .

Операция [math]\mathrm[/math] осуществляется с помощью последовательности преобразований пунктирного ребра в сплошное ребро и другого сплошного ребра в пунктирное ребро. Обозначим количество таких преобразований за [math]M[/math] . Найдем количество преобразований сделанных в течение [math]\mathrm[/math] . Пусть [math]H[/math] — множество всех тяжелых ребер, [math]L[/math] — все легкие ребра, [math]S \rightarrow D[/math] — множество сплошных ребер, преобразованных в пунктирные в течение одного [math]\mathrm[/math] , [math]D \rightarrow S[/math] — множество пунктирных ребер, преобразованных в сплошные.

По лемме, количество легких пунктирных ребер, преобразованных в сплошные, будет не больше, чем [math]\log n[/math] .

Обозначим за [math]F[/math] лес деревьев, в которых каждое ребро либо сплошное, либо пунктирное, a [math]F'[/math] — лес, получившийся из [math]F[/math] после одного вызова [math]\mathrm[/math] . Определим потенциал [math]\Phi _(F) = n — 1 — |\|[/math] , [math]\Delta \Phi _[/math] — увеличение [math]\Phi _[/math] после одной операции [math]\mathrm[/math] .

Пусть [math]s(v)[/math] — количество вершин в поддеревьях [math]v[/math] ( здесь имеется в виду splay-дерево пути, который строится в ходе выполнения [math]\mathrm[/math] ), [math]r(v) = \log s(v)[/math] . По лемме стоимость i-той операции [math]\mathrm[/math] не превосходит [math]1 + 3 \cdot (r(t) — r(v))[/math] . Это приводит к тому, что амортизационная стоимость [math]\mathrm[/math] ограничена следующим значением:

[math]3 \cdot \log n — 3 \cdot \log (s(v)) + M[/math]

Здесь [math]M = O(\log n)[/math] , поэтому амортизационная стоимость [math]\mathrm[/math] равна [math]O(\log n)[/math] .

Применение

LCA

C помощью link-cut-дерева можно найти наименьшего общего предка:

function lca(u: tree, v: tree): tree expose(u) expose(v) return pathparent(splay(u))

Первый вызов [math]\mathrm[/math] построит путь от [math]u[/math] до корня. Второй пересечет этот путь в наименьшем общем предке, поэтому в splay-дереве, которому принадлежит [math]u[/math] , хранится указатель [math]pathparent[/math] на [math]\mathrm[/math] , после [math]\mathrm(u)[/math] он будет находиться в [math]u[/math] .

См. также

Источники информации

Источник

Задача о максимальном потоке сети

Изучение определений и теорем потока сети, определение сводимости некоторых задач о максимальном потоке. Описание алгоритмов локального и кратчайшего увеличения цепей сети. Метод поразрядного сокращения невязок и Динамические деревья Слейтора-Тарьяна.

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

Подобные документы

Шифрование — широко используемый криптографический метод сохранения конфиденциальности информации. Описание схемы шифрования и расшифрования. Структура алгоритмов на основе сети Фейстеля. Скриншоты работающей программы. Скорость работы алгоритмов.

Анализ и практическая реализация использования администрирования и мониторинга сети на предприятии. Процесс создания карты сети в программе LANState. Сетевые программы для сисадминов, программы мониторинга сети. Описание локальной вычислительной сети.

Технология настройки распределённой беспроводной сети в домашних условиях с использованием двух точек беспроводного доступа: выбор оборудования, определение архитектуры сети. Средства безопасности беспроводной сети, процедура ее взлома с протоколом WEP.

Сущность и классификация компьютерных сетей по различным признакам. Топология сети — схема соединения компьютеров в локальные сети. Региональные и корпоративные компьютерные сети. Сети Интернет, понятие WWW и унифицированный указатель ресурса URL.

Принцип деятельности ООО «МАГМА Компьютер». Особенности предметной области. Цели создания компьютерной сети. Разработка конфигурации сети. Выбор сетевых компонентов. Перечень функций пользователей сети. Планирование информационной безопасности сети.

Источник