Rake-Compress деревья

Материал из Викиконспекты
Перейти к: навигация, поиск

Задача, которая решается с помощью динамических деревьев (англ. dynamic tree), формулируется следующим образом. Необходимо поддерживать лес деревьев и выполнять на нем следующие операции:

  • добавить ребро [math](u, v)[/math]. Вершина [math]u[/math] должна быть корнем некоторого дерева. Вершины [math]u[/math] и [math]v[/math] должны находиться в разных деревьях,
  • удалить ребро [math](u, v)[/math]. Ребро [math](u, v)[/math] должно присутствовать в графе,
  • некоторый запрос относительно структуры дерева.

Примером последней операции может быть запрос "достижима ли вершина [math]u[/math] из [math]v[/math]?", "сколько ребер на кратчайшем пути из [math]u[/math] в [math]v[/math]?" или "какова сумма номеров вершин, которые находятся в поддереве вершины [math]u[/math]?". Можно легко реализовать структуру данных, которая будет выполнять данные операции за время [math]O(n)[/math], где [math]n[/math] — количество вершин в графе. Динамические деревья нужны для того, чтобы обрабатывать запросы более эффективно. В частности, все предложенные операции возможно выполнять за время [math]O(\log{n})[/math].

Описание

Rake-Compress Tree — структура данных, которая хранит лес деревьев и поддерживает следующие операции:

  • [math]\mathrm{Rake}[/math] — все листья дерева сжимаются к своим родителям,
  • [math]\mathrm{Compress}[/math] — выбирается и объединяется некоторое множество несмежных друг с другом вершин, имеющих ровно одного сына.
Операция [math]\mathrm{Rake}[/math]
Операция [math]\mathrm{Compress}[/math]

Входными данными для алгоритма Rake-Compress является лес корневых деревьев. К нему поочередно применяются операции [math]\mathrm{Rake}[/math] и [math]\mathrm{Compress}[/math] до тех пор, пока существует хотя бы одна живая вершина.
Во время каждой из этих операций выбирается некоторое множество попарно несмежных вершин, которое сжимается к своим родителям. После каждой операции лес сохраняется в специальном виде, что в дальнейшем дает возможность отвечать на запросы о структуре леса.
Современная реализация Rake-Compress деревьев была предложена Р. А. Тарьяном и Р. Ф. Вернеком.

Рассмотрим, как изменяется количество вершин в дереве после применения к нему операций [math]\mathrm{Rake}[/math] и [math]\mathrm{Compress}[/math]. Разобьём все вершины дерева на три группы: входящая степень которых равна нулю, одному и больше одного. Обозначим их количество за [math]T_0, T_1[/math] и [math]T_2[/math] соответственно.

Лемма (1):
[math]T_2 \leqslant T_0 - 1[/math].
Доказательство:
[math]\triangleright[/math]

Докажем по индукции по высоте дерева.
Для дерева из одной вершины утверждение верно.
Пусть утверждение доказано для деревьев высоты меньше [math]h[/math]. Докажем для дерева высоты ровно [math]h[/math]. Рассмотрим степень корня. Если корень имеет ровно одного ребенка, то переходим к случаю дерева высоты [math]h - 1[/math]. Если у дерева несколько поддеревьев, то имеем:
[math]T_2 = 1 + \Sigma_{u \in children(root)}T_2(u) \leqslant 1 + \Sigma_{u \in children(root)}(T_0(u) - 1)[/math]  [math] \leqslant -1 + \Sigma_{u \in children}T_0(u) \leqslant -1 + T_0 = T_0 - 1[/math].

Заметим, что для леса деревьев лемма также справедлива.
[math]\triangleleft[/math]


Лемма (2):
После применения операций [math]\mathrm{Rake}[/math] и [math]\mathrm{Compress}[/math] к лесу, математическое ожидание количества вершин в нём не превосходит [math]\frac{7}{8}[/math] от их исходного числа.
Доказательство:
[math]\triangleright[/math]

Математическое ожидание количества удаленных вершин [math]\mathrm{deleted} = T_0 + \frac{T_1}{8}[/math] (так как все листья будут удалены после операции [math]\mathrm{Rake}[/math], а каждая вершина, у которой ровно один сын, будет удалена с вероятностью [math]1[/math] после операции [math]\mathrm{Compress}[/math]). Из предыдущей леммы получаем:

[math]\mathrm{deleted} = \frac{1}{2} (T_0 + T_2) + \frac{1}{8} T_1 \geqslant \frac{1}{8} (T_0 + T_1 + T_2)[/math].
[math]\triangleleft[/math]
Теорема:
Математическое ожидание количества операций [math]\mathrm{Rake}[/math] и [math]\mathrm{Compress}[/math], которые будут выполнены до полного сжатия дерева, равно [math]O(\log{n})[/math], где [math]n[/math] — общее количество вершин.
Доказательство:
[math]\triangleright[/math]
Из леммы 2 известно, что после каждой итерации применения операций [math]\mathrm{Rake}[/math] и [math]\mathrm{Compress}[/math] число вершин в среднем уменьшается в константное число раз. Значит, количество итераций в среднем ограничено [math]O(\log{n})[/math].
[math]\triangleleft[/math]

Построение

Для того, чтобы отвечать на запросы относительно структуры леса необходимо сохранить информацию о том, как происходил процесс сжатия леса. Для этого будем хранить таблицу, в каждой строке которой записана информация о структуре леса после выполнения операций. Каждая клетка таблицы будет хранить информацию о вершине после выполнения операций [math]\mathrm{Rake}[/math] и [math]\mathrm{Compress}[/math]. Из информации будем сохранять родителя вершины, множество детей и метку, сжата ли вершина.
Пример таблицы для следующей последовательности операций:

Пример выполнения операций.
Шаг Операция [math]1[/math] [math]2[/math] [math]3[/math] [math]4[/math]
4 [math]\mathrm{Rake}[/math] Родитель: —
Дети: [math]\emptyset[/math]
3 [math]\mathrm{Compress}[/math] Родитель: —
Дети: [math]\{3\}[/math]
Родитель: [math]1[/math]
Дети: [math]\emptyset[/math]
2 [math]\mathrm{Rake}[/math] Родитель: —
Дети: [math]\{2\}[/math]
Родитель: [math]1[/math]
Дети: [math]\{3\}[/math]
Родитель: [math]2[/math]
Дети: [math]\emptyset[/math]
1 Родитель: —
Дети: [math]\{2\}[/math]
Родитель: [math]1[/math]
Дети: [math]\{3\}[/math]
Родитель: [math]2[/math]
Дети: [math]\{4\}[/math]
Родитель: [math]3[/math]
Дети: [math]\emptyset[/math]

Возможность параллельного построения

Операции [math]\mathrm{Rake}[/math] и [math]\mathrm{Compress}[/math] можно выполнять параллельно для всех вершин. Если предположить, что множество детей можно пересчитывать за [math]O(1)[/math], то Rake-Compress дерево можно построить за [math]O(\log{n})[/math] в модели PRAM в случае наличия [math]\Omega(n)[/math] процессоров.

Пример выполнения операций

Применения

  • Задача MST online: дан граф [math]G[/math] из [math]n[/math] вершин, в который добавляются новые рёбра. Необходимо поддерживать минимальный остовный лес для данного графа,
  • Задача о максимальном потоке: в помощью динамических деревьев можно улучшить ассимптотику алгоритма Диница с [math]O(V^2 E)[/math] до [math]O(VE \log{V})[/math].

См. также

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