Редактирование: Rake-Compress деревья

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

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 1: Строка 1:
Задача, которая решается с помощью [[Link-Cut Tree|динамических деревьев]], формулируется следующим образом. Необходимо поддерживать лес деревьев и выполнять на нем следующие операции:
+
Задача, которая решается с помощью '''динамических деревьев''' (англ. ''dynamic tree''), формулируется следующим образом. Необходимо поддерживать лес деревьев и выполнять на нем следующие операции:
* <tex>\mathrm{link(u, v)}</tex> {{---}} добавить ребро <tex>(u, v)</tex>. Вершина <tex>u</tex> должна быть корнем некоторого дерева. Вершины <tex>u</tex> и <tex>v</tex> должны находиться в разных деревьях,
+
* добавить ребро <tex>(u, v)</tex>. Вершина <tex>u</tex> должна быть корнем некоторого дерева. Вершины <tex>u</tex> и <tex>v</tex> должны находиться в разных деревьях,
* <tex>\mathrm{cut(u, v)}</tex> {{---}} удалить ребро <tex>(u, v)</tex>. Ребро <tex>(u, v)</tex> должно присутствовать в графе,
+
* удалить ребро <tex>(u, v)</tex>. Ребро <tex>(u, v)</tex> должно присутствовать в графе,
* <tex>\mathrm{query()}</tex> {{---}} некоторый запрос относительно структуры дерева.
+
* некоторый запрос относительно структуры дерева.
 
+
Примером последней операции может быть запрос "достижима ли вершина <tex>u</tex> из <tex>v</tex>?", "сколько ребер на кратчайшем пути из <tex>u</tex> в <tex>v</tex>?" или "какова сумма номеров вершин, которые находятся в поддереве вершины <tex>u</tex>?". Можно легко реализовать структуру данных, которая будет выполнять данные операции за время <tex>O(n)</tex>, где <tex>n</tex> {{---}} количество вершин в графе. Динамические деревья нужны для того, чтобы обрабатывать запросы более эффективно. В частности, все предложенные операции возможно выполнять за время <tex>O(\log{n})</tex>.
  
 
__TOC__
 
__TOC__
==Идея==
+
==Описание==
===Описание===
+
'''Rake-Compress Tree''' {{---}} структура данных, которая хранит [[Дерево, эквивалентные определения|лес деревьев]] и поддерживает следующие операции:
Пусть дано некоторое дерево <tex>T</tex>, для которого мы хотим выполнять описанные выше операции. Рассмотрим алгоритм '''сжатия дерева''' (англ. ''tree-contraction algorithm''), предложенный Миллером и Райфом. Алгоритм сжимает <tex>T</tex> в одну вершину путем применения операций <tex>\mathrm{Rake}</tex> и <tex>\mathrm{Compress}</tex> в несколько раундов:
 
 
* <tex>\mathrm{Rake}</tex> {{---}} все листья дерева сжимаются к своим родителям,
 
* <tex>\mathrm{Rake}</tex> {{---}} все листья дерева сжимаются к своим родителям,
 
* <tex>\mathrm{Compress}</tex> {{---}} выбирается и объединяется некоторое множество несмежных друг с другом вершин, имеющих ровно одного сына.
 
* <tex>\mathrm{Compress}</tex> {{---}} выбирается и объединяется некоторое множество несмежных друг с другом вершин, имеющих ровно одного сына.
Строка 15: Строка 14:
 
<td>[[Файл:Rctree-compress.png|x180px|thumb|Операция <tex>\mathrm{Compress}</tex>]]</td>
 
<td>[[Файл:Rctree-compress.png|x180px|thumb|Операция <tex>\mathrm{Compress}</tex>]]</td>
 
</tr></table>
 
</tr></table>
 +
Входными данными для алгоритма Rake-Compress является лес корневых деревьев. К нему поочередно применяются операции <tex>\mathrm{Rake}</tex> и <tex>\mathrm{Compress}</tex> до тех пор, пока существует хотя бы одна живая вершина.<br>Во время каждой из этих операций выбирается некоторое множество попарно несмежных вершин, которое сжимается к своим родителям. После каждой операции лес сохраняется в специальном виде, что в дальнейшем дает возможность отвечать на запросы о структуре леса.<br>
 +
Современная реализация Rake-Compress деревьев была предложена Р. А. Тарьяном и Р. Ф. Вернеком.
  
Сжатие дерева требует линейного времени и логарифмическое число раундов.<br>
+
Рассмотрим, как изменяется количество вершин в дереве после применения к нему операций <tex>\mathrm{Rake}</tex> и <tex>\mathrm{Compress}</tex>. Разобьём все вершины дерева на три группы: входящая степень которых равна нулю, одному и больше одного. Обозначим их количество за <tex>T_0, T_1</tex> и <tex>T_2</tex> соответственно.  
Для выбора вершин, которые будут удалены во время операции <tex>\mathrm{Compress}</tex>, применяется следующий метод: для каждой вершины генерируется рандомный бит и вершина добавляется в множество удаляемых только в том случае, когда она имеет одного ребёнка, бит для неё равен <tex>0</tex>, а для родителя и ребёнка равен <tex>1</tex>.<br>
 
Рассмотрим, как изменяется количество вершин в дереве после применения к нему операций <tex>\mathrm{Rake}</tex> и <tex>\mathrm{Compress}</tex>.<br>Разобьём все вершины дерева на три группы:  
 
* <tex>T_0</tex> {{---}} входящая степень равна нулю,
 
* <tex>T_1</tex> {{---}} входящая степень равна одному,
 
* <tex>T_2</tex> {{---}} входящая степень больше одного.
 
 
 
 
{{Лемма
 
{{Лемма
 
|about=1
 
|about=1
 
|statement=<tex>T_2 \leqslant T_0 - 1</tex>.
 
|statement=<tex>T_2 \leqslant T_0 - 1</tex>.
|proof=
+
|proof=Докажем по индукции по высоте дерева.<br>Для дерева из одной вершины утверждение верно.<br>Пусть утверждение доказано для деревьев высоты меньше <tex>h</tex>. Докажем для дерева высоты ровно <tex>h</tex>. Рассмотрим степень корня. Если корень имеет ровно одного ребенка, то переходим к случаю дерева высоты <tex>h - 1</tex>. Если у дерева несколько поддеревьев, то имеем:<br><tex>T_2 = 1 + \Sigma_{u \in children(root)}T_2(u) \leqslant 1 + \Sigma_{u \in children(root)}(T_0(u) - 1)</tex>&nbsp;&nbsp;<tex> \leqslant -1 + \Sigma_{u \in children}T_0(u) \leqslant -1 + T_0 = T_0 - 1</tex>.
Докажем по индукции по высоте дерева.<br>
+
Заметим, что для леса деревьев лемма также справедлива.
* '''База
 
*: Для дерева из одной вершины утверждение верно.
 
* '''Переход
 
*: Пусть утверждение доказано для деревьев высоты меньше <tex>h</tex>. Докажем для дерева высоты ровно <tex>h</tex>. Рассмотрим степень корня:<br>
 
*:: Если корень имеет ровно одного ребенка, то переходим к случаю дерева высоты <tex>h - 1</tex>.<br>Если у дерева несколько поддеревьев, то имеем:<br><tex>T_2 = 1 + \sum\limits_{u \in *: children(root)}T_2(u) \leqslant 1 + \sum\limits_{u \in children(root)}(T_0(u) - 1)</tex>&nbsp;&nbsp;<tex> \leqslant -1 + \sum\limits_{u \in children}T_0(u) \leqslant -1 + T_0 = T_0 - 1</tex>.
 
 
}}
 
}}
Заметим, что для леса деревьев лемма также справедлива.
+
 
  
 
{{Лемма
 
{{Лемма
 
|about=2
 
|about=2
|statement=После применения операций <tex>\mathrm{Rake}</tex> и <tex>\mathrm{Compress}</tex> к лесу, математическое ожидание количества вершин в нём не превосходит <tex>\dfrac{7}{8}</tex> от их исходного числа.
+
|statement=После применения операций <tex>\mathrm{Rake}</tex> и <tex>\mathrm{Compress}</tex> к лесу, математическое ожидание количества вершин в нём не превосходит <tex>\frac{7}{8}</tex> от их исходного числа.
|proof=Все листья будут удалены после операции <tex>\mathrm{Rake}</tex>, а каждая вершина, у которой ровно один сын, будет удалена с вероятностью <tex>\dfrac{1}{8}</tex> после операции <tex>\mathrm{Compress}</tex> (так как мы рассматриваем три бита при выборе вершин и добавляем вершину в множество удаляемых только когда эти биты для родителя, вершины и ребёнка соответственно равны <tex>1</tex>, <tex>0</tex> и <tex>1</tex>).<br>
+
|proof=Математическое ожидание количества удаленных вершин <tex>\mathrm{deleted} = T_0 + \frac{T_1}{8}</tex> (так как все листья будут удалены после операции <tex>\mathrm{Rake}</tex>, а каждая вершина, у которой ровно один сын, будет удалена с вероятностью <tex>1</tex> после операции <tex>\mathrm{Compress}</tex>). Из предыдущей леммы получаем:<br>
Таким образом математическое ожидание количества удаленных вершин <tex>\mathrm{deleted} = T_0 + \dfrac{T_1}{8}</tex>. Из предыдущей леммы получаем:<br>
+
<tex>\mathrm{deleted} = \frac{1}{2} (T_0 + T_2) + \frac{1}{8} T_1 \geqslant \frac{1}{8} (T_0 + T_1 + T_2)</tex>.
<tex>\mathrm{deleted} = \dfrac{1}{2} (T_0 + T_2) + \dfrac{1}{8} T_1 \geqslant \dfrac{1}{8} (T_0 + T_1 + T_2)</tex>.
 
 
}}
 
}}
  
Строка 49: Строка 38:
 
}}
 
}}
  
Для конкретного применения можно предположить, что рёбра дерева имеют вес, а вершины имеют метки.
+
==Построение==
 
 
===Пример операций===
 
В качестве примера сжатия дерева рассмотрим следующее взвешенное дерево:
 
[[Файл:RC_graph_example.png|400px|center|thumb|Исходное дерево <tex>T</tex>.]]
 
 
 
[[Файл:RC_graph_contraction.png|350px|right|thumb|Алгоритм сжатия дерева <tex>T</tex>.]]
 
На каждом раунде сжатия (перечислены сверху вниз) удаляется множество вершин с использованием операций <tex>\mathrm{Rake}</tex> и <tex>\mathrm{Compress}</tex>:
 
* Операция <tex>\mathrm{Rake}</tex> удаляет лист и ребро, смежное с ним, сохраняя в соседях данные: метку удалённой вершины, вес удалённого ребра и данные о сжатых на предыдущих раундах вершинах.
 
* Операция <tex>\mathrm{Compress}</tex> удаляет вершины, имеющие ровно одного сына, и смежные им рёбра. Например, для вершины <tex>v</tex> c сыном <tex>w</tex> и родителем <tex>u</tex> будут удалены рёбра <tex>(u, v)</tex> и <tex>(v, w)</tex>. После этого добавляется ребро <tex>(u, w)</tex>, а данные вершины <tex>v</tex> и удалённых рёбер (метка удалённой вершины, сохранённые данные и веса удалённых рёбер) сохраняются в соседние вершины.
 
 
 
Например, для приведённого дерева на первом раунде сжатия применяется операция <tex>\mathrm{Rake}</tex> для вершин <tex>a</tex>, <tex>d</tex>, <tex>n</tex>, <tex>k</tex> и операция <tex>\mathrm{Compress}</tex> для <tex>g</tex> и <tex>i</tex>.<br><br>
 
Сжатие может быть рассмотрено как рекурсивная кластеризация дерева в один '''кластер''' (англ. ''cluster''). Изначально вершины и рёбра составляют базовый кластер. Операции <tex>\mathrm{Rake}</tex> и <tex>\mathrm{Compress}</tex> формируют большие кластеры из нескольких меньших кластеров.<br><br>На иллюстрации примера все кластеры (кроме базового) обозначены зелёными лепестками. Каждый кластер помечен заглавной буквой метки вершины, входящей в него. Например, кластер <tex>A</tex>, полученный после сжатия вершины <tex>a</tex> содержит вершины <tex>a</tex>, <tex>b</tex> и ребро <tex>(a, b)</tex>; сжатая вершина <tex>g</tex> создает кластер <tex>G</tex>, содержащий эту вершину и рёбра <tex>(f, g)</tex> и <tex>(g, h)</tex>. Во втором раунде, после сжатия вершины <tex>b</tex> создается кластер <tex>B</tex>, содержащий кластер <tex>A</tex> и ребро <tex>(b, c)</tex>.<br>Представление сжатого дерева в виде кластеров:
 
[[Файл:RC_graph_clusters.png|400px|left|thumb|Кластеризованное дерево <tex>T</tex>.]]
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Определим кластер как поддерево исходного дерева, порожденное множеством вершин.
 
 
 
Для кластера <tex>C</tex> скажем, что вершина <tex>v</tex> из <tex>C</tex> называется '''граничной вершиной''', если <tex>v</tex> смежная с вершинами не из <tex>C</tex>. '''Граница кластера''' {{---}} множество граничных вершин кластера, а '''степень кластера''' {{---}} количество граничных вершин кластера.
 
 
 
Например, для рассматриваемого дерева кластер <tex>A</tex> имеет границу <tex>\{b\}</tex> и степень <tex>1</tex>, а кластер <tex>G</tex> имеет границу <tex>\{f, g\}</tex> и степень <tex>2</tex>. При сжатии дерева все кластеры, кроме последнего, имеют степени <tex>1</tex> и <tex>2</tex>. Свойством алгоритмом сжатия является то, что:
 
* операции <tex>\mathrm{Rake}</tex> создают кластеры со степенью <tex>1</tex>,
 
* операции <tex>\mathrm{Compress}</tex> создают кластеры со степенью <tex>2</tex>,
 
* финальный кластер имеет степень <tex>0</tex>.
 
 
 
Процесс сжатия исходного дерева может быть представлен в виде нового дерева, называемого <tex>\mathrm{RC-tree}</tex>.<br>Пример такого дерева для рассматриваемого исходного дерева:
 
[[Файл:RC_graph_tree.png|500px|center|thumb|RC-tree для дерева <tex>T</tex>.]]
 
 
 
 
 
Поскольку матожидание количества раундов {{---}} логарифм, то такое дерево будет сбалансированным.<br>
 
<tex>\mathrm{RC}</tex> дерево можно использовать для ответа на динамические запросы для статического дерева. Для этого в <tex>\mathrm{RC}</tex> дереве сохраним требуемую информацию (необходимо модифицировать для пересчёта информации операции <tex>\mathrm{Rake}</tex> и <tex>\mathrm{Compress}</tex>) и используем обход для ответа на запросы. Поскольку дерево с большой вероятностью является сбалансированным, обход дерева также можно осуществить за логарифм.<br>
 
Для динамических деревьев, например, если доступны операции добавления/удаления ребра (операции <tex>\mathrm{link}</tex> и <tex>\mathrm{cut}</tex>), нужно эффективно перестраивать отдельные кластеры, пересчитывая данные. Для этого можно обновлять данные начиная с листа дерева, соответствующего обновляемой вершине в исходном дереве, и подниматься вверх.
 
 
 
==Реализация==
 
===Хранение===
 
 
Для того, чтобы отвечать на запросы относительно структуры леса необходимо сохранить информацию о том, как происходил процесс сжатия леса. Для этого будем хранить таблицу, в каждой строке которой записана информация о структуре леса после выполнения операций. Каждая клетка таблицы будет хранить информацию о вершине после выполнения операций <tex>\mathrm{Rake}</tex> и <tex>\mathrm{Compress}</tex>. Из информации будем сохранять родителя вершины, множество детей и метку, сжата ли вершина.<br>
 
Для того, чтобы отвечать на запросы относительно структуры леса необходимо сохранить информацию о том, как происходил процесс сжатия леса. Для этого будем хранить таблицу, в каждой строке которой записана информация о структуре леса после выполнения операций. Каждая клетка таблицы будет хранить информацию о вершине после выполнения операций <tex>\mathrm{Rake}</tex> и <tex>\mathrm{Compress}</tex>. Из информации будем сохранять родителя вершины, множество детей и метку, сжата ли вершина.<br>
 
Пример таблицы для следующей последовательности операций:
 
Пример таблицы для следующей последовательности операций:
Строка 148: Строка 80:
 
|}
 
|}
 
<br><br>
 
<br><br>
Для того, чтобы выбирать множество вершин для применения операции <tex>\mathrm{Compress}</tex> будем использовать следующий метод: для каждой вершины с помощью генератора псевдослучайных чисел выберем случайный бит. Вершина добавляется в множество, если у нее ровно один ребенок, она не является корнем и биты, которые были сгенерированы для нее, ребенка и родителя равны <tex>0</tex>, <tex>1</tex> и <tex>1</tex> соответственно.
+
Для того, чтобы выбирать множество вершин для применения операции <tex>\mathrm{Compress}</tex> будем использовать следующий метод: для каждой вершины с помощью генератора псевдослучайных чисел выберем случайный бит. Вершина добавляется в множество, если у нее ровно один ребенок, она не является корнем и биты, которые были сгенерированы для нее, ребенка и родителя равны 0, 1 и 1 соответственно.
  
Рассмотрим более подробно, как необходимо хранить клетки таблицы <tex>\mathrm{Rake-Compress}</tex> дерева. Для вершины необходимо сохранить ее родителя, а также множество детей. Для того, чтобы обрабатывать каждую клетку таблицы за <tex>O(\log{n})</tex>, нужно производить операции с множеством детей за <tex>O(1)</tex>. <br><br>Рассмотрим, в каких случаях можно сжать вершину:
+
Рассмотрим более подробно, как необходимо хранить клетки таблицы Rake-Compress дерева. Для вершины необходимо сохранить ее родителя, а также множество детей. Для того, чтобы обрабатывать каждую клетку таблицы за <tex>O(\log{n})</tex>, нужно производить операции с множеством детей за <tex>O(1)</tex>. <br><br>На самом деле, множество детей хранится для того, чтобы определять, можно ли сжать вершину. Если детей у вершины больше одного, то ее точно нельзя сжать. Если у неё нет детей, то ее можно сжать только во время операции <tex>\mathrm{Rake}</tex>. Чтобы определить можно ли применить операцию <tex>\mathrm{Compress}</tex> к вершине, в том случае, когда у нее один ребёнок, нужно узнать, как бит был сгенерирован на текущей итерации для ребёнка. Для этого необходимо знать номер вершины-ребёнка. Значит, необходимо уметь определять, кто находится в множестве только в том случае, если в нём не более одного элемента. Поэтому, всю информацию о множестве можно хранить с помощью двух величин {{---}} хранить количество элементов в множестве и сумму их номеров.<br><br>
* если детей у вершины больше одного, то ее точно нельзя сжать,
 
* если у неё нет детей, то ее можно сжать только во время операции <tex>\mathrm{Rake}</tex>
 
* если у вершины один ребёнок, то её возможно сжать во время операции <tex>\mathrm{Compress}</tex>.  
 
Чтобы определить, можно ли применить операцию <tex>\mathrm{Compress}</tex> к вершине, в том случае, когда у нее один ребёнок, нужно узнать, какой бит был сгенерирован на текущей итерации для ребёнка (один из трёх битов, генерируемых при операции <tex>\mathrm{Compress}</tex>). Для этого необходимо знать номер вершины-ребёнка. Значит, нам нужно определять, какие элементы находятся в множестве детей только в том случае, когда размер множества равен <tex>1</tex>. Поэтому, всю информацию о множестве можно хранить с помощью двух величин {{---}} хранить количество элементов в множестве и сумму их номеров. Поддерживая сумму номеров детей и их количество, можно эффективно узнавать номер вершины-ребёнка, когда это необходимо. Данная оптимизация позволяет за <tex>O(1)</tex> получать номер ребёнка и за <tex>O(1)</tex> обновлять множество детей.<br><br>
 
 
Если вершина является корнем, то в качестве ее родителя будем хранить ее номер. Кроме того необходимо хранить изменения, которые произойдут с клеткой при переходе к следующему слою: будем хранить, кто должен стать новым родителем, на сколько изменится количество детей, а также как изменится сумма их номеров. Все это необходимо для того, чтобы обрабатывать каждую изменившуюся клетку за <tex>O(1)</tex>.<br>
 
Если вершина является корнем, то в качестве ее родителя будем хранить ее номер. Кроме того необходимо хранить изменения, которые произойдут с клеткой при переходе к следующему слою: будем хранить, кто должен стать новым родителем, на сколько изменится количество детей, а также как изменится сумма их номеров. Все это необходимо для того, чтобы обрабатывать каждую изменившуюся клетку за <tex>O(1)</tex>.<br>
 
 
Псевдокод хранения клетки таблицы:
 
Псевдокод хранения клетки таблицы:
* <tex>\mathrm{id}</tex> {{---}} номер вершины,
 
* <tex>\mathrm{parent}</tex> {{---}} родитель вершины,
 
* <tex>\mathrm{cntChild}</tex> {{---}} количество детей вершины,
 
* <tex>\mathrm{sumChild}</tex> {{---}} сумма номеров детей,
 
* <tex>\mathrm{newParent}</tex> {{---}} новый родитель вершины после изменений,
 
* <tex>\mathrm{diffCntChild}</tex> и <tex>\mathrm{diffSumChild}</tex> {{---}} изменения, произведенные с полями <tex>\mathrm{cntChild}</tex> и <tex>\mathrm{sumChild}</tex> соответственно.
 
 
 
  '''struct''' Cell''':'''
 
  '''struct''' Cell''':'''
 
     '''int''' id, parent, cntChild, sumChild
 
     '''int''' id, parent, cntChild, sumChild
Строка 175: Строка 95:
 
         diffCntChild = diffSumChild = 0
 
         diffCntChild = diffSumChild = 0
 
      
 
      
     '''func''' addChild(v: '''int''')''':'''
+
     '''func''' addChild(v)''':'''
 
         diffCntChild++
 
         diffCntChild++
 
         diffSumChild += v
 
         diffSumChild += v
 
    
 
    
     '''func''' removeChild(v: '''int''')''':'''
+
     '''func''' removeChild(v)''':'''
 
         diffCntChild--
 
         diffCntChild--
 
         diffSumChild -= v
 
         diffSumChild -= v
  
Для хранения <tex>\mathrm{Rake-Compress}</tex> дерева будем использовать следующие данные:
+
Для хранения Rake-Compress дерева будем использовать следующие данные:
 
* <tex>\mathrm{cells[]}</tex> {{---}} список клеток, которые ей соответствуют, для каждой вершины,
 
* <tex>\mathrm{cells[]}</tex> {{---}} список клеток, которые ей соответствуют, для каждой вершины,
 
* <tex>\mathrm{rand}</tex> {{---}} генератор псевдослучайных чисел,
 
* <tex>\mathrm{rand}</tex> {{---}} генератор псевдослучайных чисел,
Строка 190: Строка 110:
  
 
  '''struct''' RCTree(n: '''int''')''':'''
 
  '''struct''' RCTree(n: '''int''')''':'''
     '''RndGen''' rand = RandBitsGenerator()
+
     rand = RandBitsGenerator()
     '''int''' time = 0
+
     time = 0
 
     '''for''' i = 0 '''to''' n
 
     '''for''' i = 0 '''to''' n
 
         lastUpdateTime[i] = 0
 
         lastUpdateTime[i] = 0
 
         cells[i] = []
 
         cells[i] = []
  
Кроме запросов о структуре леса, <tex>\mathrm{Rake-Compress}</tex> деревья можно использовать для подсчета значений некоторых функций. Например, каждой вершине можно сопоставить некоторое значение и узнавать, чему равна сумма значений всех вершин, которые находятся в поддереве.
+
Рассмотрим, как работает алгоритм построения Rake-Compress дерева. Будем строить таблицу по строкам. В каждый момент будем хранить множество вершин, которые еще не были сжаты, и перестраивать следующий слой. Также будем делать операции <tex>\mathrm{Rake}</tex> и <tex>\mathrm{Compress}</tex> одновременно. Чтобы определить, нужно ли сжимать вершину, воспользуемся следующим алгоритмом:
Для этого в клетках таблицы <tex>\mathrm{Rake-Compress}</tex> дерева необходимо хранить не только состояние вершины, но и значение функции, посчитанной на части дерева, которое уже было сжато в вершину. Если функция является аддитивной, то ее пересчет аналогичен пересчету множества детей вершины. Так, если некоторая вершина сжимается к родителю, то в соответствующей родителю клетке необходимо обновить значение функции. При добавлении и удалении ребер необходимо в изменившихся клетках пересчитывать значение функции.
 
 
 
===Построение===
 
Рассмотрим, как работает алгоритм построения <tex>\mathrm{Rake-Compress}</tex> дерева. Будем строить таблицу по строкам. В каждый момент будем хранить множество вершин, которые еще не были сжаты, и перестраивать следующий слой. Также будем делать операции <tex>\mathrm{Rake}</tex> и <tex>\mathrm{Compress}</tex> одновременно. Чтобы определить, нужно ли сжимать вершину, воспользуемся следующим алгоритмом:
 
 
  '''bool''' shouldRemoveVertex(c: '''Cell''', rand, layer: '''int''')''':'''
 
  '''bool''' shouldRemoveVertex(c: '''Cell''', rand, layer: '''int''')''':'''
 
     '''if''' c.cntChild == 0
 
     '''if''' c.cntChild == 0
Строка 213: Строка 129:
  
 
Таким образом, алгоритм построения дерева выглядит следующим образом:
 
Таким образом, алгоритм построения дерева выглядит следующим образом:
  '''func''' build(parent: '''int[n]''')''':'''
+
  '''func''' build(parent: '''int[]''')''':'''
 
     alive = <tex>\{0 \dots n - 1\}</tex>
 
     alive = <tex>\{0 \dots n - 1\}</tex>
     '''int''' layer = 0
+
     layer = 0
     '''for''' i = 0 '''to''' n                                             <font color="green">// заполним таблицу вершинами изначального дерева</font>
+
     '''for''' i = 0 '''to''' n
 
         cells[i].add(Cell(parent[i]))
 
         cells[i].add(Cell(parent[i]))
 
     '''while''' <tex>\mathrm{alive} \neq \emptyset</tex>
 
     '''while''' <tex>\mathrm{alive} \neq \emptyset</tex>
 
         nextAlive = <tex>\emptyset</tex>
 
         nextAlive = <tex>\emptyset</tex>
 
         '''for''' <tex>v \in \mathrm{alive}</tex>
 
         '''for''' <tex>v \in \mathrm{alive}</tex>
             '''Cell''' c = getCellForVertex(v)                       <font color="green">// получить клетку таблицы, соответствующую вершине</font>
+
             c = getCellForVertex(v)
 
             '''if''' shouldRemoveVertex(c, rand, layer)
 
             '''if''' shouldRemoveVertex(c, rand, layer)
                 '''if''' c.cntChild == 1
+
                 '''if'' c.cntChild == 1
 
                     getCellForVertex(c.sumChild).newParent = c.parent
 
                     getCellForVertex(c.sumChild).newParent = c.parent
 
                     getCellForVertex(c.parent).addChild(c.sumChild)
 
                     getCellForVertex(c.parent).addChild(c.sumChild)
Строка 232: Строка 148:
 
         alive = nextAlive
 
         alive = nextAlive
 
         '''for''' <tex>v \in \mathrm{alive}</tex>
 
         '''for''' <tex>v \in \mathrm{alive}</tex>
             '''Cell''' newCell = getCellForVertex(v).clone().applyChanges()
+
             newCell = getCellForVertex(v).clone().appleChanges()
 
             cells[v].add(newCell)
 
             cells[v].add(newCell)
 
         layer++
 
         layer++
===Операции удаления и добавления ребра===
 
Как только некоторая вершина помечается как изменившаяся, отменим её действие на таблицу:
 
# Найдем момент времени, когда вершина сжимается к родителю.
 
# Рассмотрим, какие вершины поменяются при сжатии данной: это ее родитель (если он есть), а также сын (если он есть). Для каждой из этих вершин поменяем значения изменений, которые необходимо применить к состоянию.
 
# Пометим, что эти вершины поменялись на этом слое. Для этого на каждом слое будем хранить список вершин, которые на нем поменялись. А перед тем как обрабатывать очередной слой будем добавлять в множество изменившихся вершин вершины из соответствующего списка.
 
# Кроме удаления эффекта от изменившихся вершин также необходимо и добавить правильный эффект. Для этого будем для каждой из изменившихся вершин определять, как ее состояние меняется при переходе к следующему слою. Если вершина сжимается к ее родителю, то пометим родителя и ребенка (если он есть) и поменяем изменение, которое хранится в соответствующих клетках. А для пересчета состояния клеток воспользуемся значениями изменений, которые сохранены в клетках.<br>
 
Рассмотрим, что происходит с таблицей при изменении одного ребра. Основная идея заключается в том, чтобы научится пересчитывать все изменения таблицы за время пропорциональное их количеству. Для этого будем эффективно поддерживать множество изменившихся клеток. В момент, когда вершина помечается, как изменившаяся, найдем, как она влияет на таблицу и отменим это влияние. <br>Для начала необходимо найти момент времени, когда вершина сжимается. В этот момент она влияет на не более чем две вершины. Изменим значения <tex>\mathrm{cntChild}</tex>, <tex>\mathrm{sumChild}</tex> и <tex>\mathrm{newParent}</tex> нужным образом. Также необходимо добавить эти вершины в множество изменившихся (в момент, когда будет обработан соответствующий слой). Поэтому, для каждого слоя еще будем хранить список вершин, которые должны быть помечены перед обработкой слоя.<br>Алгоритм обновления дерева:
 
'''func''' changeTree(<tex>(u, v)</tex>: '''Edge''')''':'''
 
    time = time + 1
 
    affected = <tex>\emptyset</tex>
 
    markAffected(u)                    <font color="green">// пусть из дерева было удалено ребро <tex>(u, v)</tex></font>
 
    markAffected(v)
 
    cells[u].parent = u
 
    cells[v].cntChild--
 
    cells[v].sumChild -= u
 
    '''int''' layer = 0
 
    '''while''' <tex>\mathrm{affected} \neq \emptyset</tex>
 
        '''for''' <tex>v \in \mathrm{affectedOnLayer}</tex>
 
            markAffected(v)
 
        '''for''' <tex>v \in \mathrm{affected}</tex>
 
            '''Cell''' c = getCellForVertex(v)
 
            '''if''' shouldRemoveVertex(v)
 
                cells[v].size = layer + 1
 
                '''if''' c.cntChild == 1
 
                    getCellForVertex(c.sumChild).newParent = c.parent
 
                    getCellForVertex(c.parent).addChild(c.sumChild)
 
                    markAffected(c.sumChild)
 
                '''if''' c.parent <tex>\neq</tex> v
 
                    getCellForVertex(c.parent).removeChild(v)
 
                    markAffected(c.parent)
 
                affected.remove(v)
 
        '''for''' <tex>v \in \mathrm{affected}</tex>
 
            '''Cell''' newCell = getCellForVertex(v).clone().applyChanges()
 
            cells[v][layer + 1] = newCell
 
        layer++
 
 
'''func''' markAffected(v: '''int''')''':'''              <font color="green">// пометить вершину как изменившуюся</font>
 
    '''if''' lastUpdateTime[v] == time
 
        '''return'''                            <font color="green">// вершина уже помечена</font>
 
    lastUpdateTime[v] = time
 
    affected.add(v)
 
    removeEffectOfVertex(v)
 
 
'''func''' removeEffectOfVertex(v: '''int''')''':'''      <font color="green">// удалить отметку о том, что вершина была помечена изменившийся</font>
 
    '''int''' layer = cells[v].size
 
    '''Cell''' c = cells[v][layer]
 
    '''if''' c.parent == v
 
        '''return'''
 
    cells[c].parent.removeChild(v)
 
    '''if''' c.cntChild == 1
 
        cells[c.parent].addChild(c.sumChild)
 
        cells[c.sumChild].newParent = v
 
  
==Сравнение с Link-Cut Tree==
+
==Возможность параллельного построения==
Для Link-Cut деревьев (основанных на [[Splay-дерево|splay-деревьях]]), как и для <tex>\mathrm{Rake-Compress}</tex> деревьев, время работы операций <tex>\mathrm{link}</tex> и <tex>\mathrm{cut}</tex> {{---}} <tex>O(\log{n})</tex>. В реальности <tex>\mathrm{RC}</tex> деревья оказываются медленнее, чем <tex>\mathrm{LC}</tex> деревья. <br>
+
Операции <tex>\mathrm{Rake}</tex> и <tex>\mathrm{Compress}</tex> можно выполнять параллельно для всех вершин. Если предположить, что множество детей можно пересчитывать за <tex>O(1)</tex>, то Rake-Compress дерево можно построить за <tex>O(\log{n})</tex> в модели PRAM в случае наличия <tex>\Omega(n)</tex> процессоров.
Отличительной особенностью <tex>\mathrm{RC}</tex> деревьев является возможность параллельного построения: операции <tex>\mathrm{Rake}</tex> и <tex>\mathrm{Compress}</tex> можно выполнять параллельно для всех вершин. Если предположить, что множество детей можно пересчитывать за <tex>O(1)</tex>, то <tex>\mathrm{Rake-Compress}</tex> дерево можно построить за <tex>O(\log{n})</tex> в модели PRAM<ref>[https://en.wikipedia.org/wiki/Parallel_random-access_machine Wikipedia {{---}} Parallel random-access machine]</ref> в случае наличия <tex>\Omega(n)</tex> процессоров.<br>
+
 
Кроме этого, <tex>\mathrm{Rake-Compress}</tex> деревья могут оказаться полезными, если необходимо пересчитывать значения не на путях, а на поддеревьях.
+
==Пример выполнения операций==
 +
 
 +
==Применения==
 +
* Задача [[Остовные_деревья:_определения,_лемма_о_безопасном_ребре|MST]] online: дан граф <tex>G</tex> из <tex>n</tex> вершин, в который добавляются новые рёбра. Необходимо поддерживать минимальный остовный лес для данного графа,
 +
* Задача о максимальном потоке: в помощью динамических деревьев можно улучшить ассимптотику [[Схема_алгоритма_Диница|алгоритма Диница]] с <tex>O(V^2 E)</tex> до <tex>O(VE \log{V})</tex>.  
  
 
==См. также==
 
==См. также==
 
* [[Link-Cut Tree]]
 
* [[Link-Cut Tree]]
 
==Примечания==
 
<references/>
 
  
 
==Источники информации==
 
==Источники информации==
 
* [https://en.wikipedia.org/wiki/Parallel_Tree_Contraction Wikipedia {{---}} Parallel Tree Contraction]
 
* [https://en.wikipedia.org/wiki/Parallel_Tree_Contraction Wikipedia {{---}} Parallel Tree Contraction]
 
* [https://github.com/BorysMinaiev/bachelor/blob/master/thesis_v2.pdf Б. Ю. Минаев {{---}} Реализация динамических Rake-Compress деревьев в случае отсутствия ограничения на степени вершин]
 
* [https://github.com/BorysMinaiev/bachelor/blob/master/thesis_v2.pdf Б. Ю. Минаев {{---}} Реализация динамических Rake-Compress деревьев в случае отсутствия ограничения на степени вершин]
* [http://www.cs.cmu.edu/~jvittes/rc-trees Acar, Blelloch, and Vittes {{---}} RC-Tree implementation]
+
* G. L. Miller, J. H. Reif {{---}} Parallel Tree Contraction
* [http://www.cs.princeton.edu/~rwerneck/papers/Wer06-dissertation.pdf R. Werneck {{---}} Design and Analysis of Data Structures for Dynamic Trees]
+
* R. Werneck {{---}} Design and Analysis of Data Structures for Dynamic Trees
* G. L. Miller, J. H. Reif {{---}} Parallel Tree Contraction, Journal of Advances in Computer Research Volume 5, 1989
 
* Umit A. Acar, Guy E. Blelloch, Jorge L. Vittes {{---}} An Experimental Analysis of Change Propagation in Dynamic Trees, 1-2005
 
  
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Задача о наименьшем общем предке]]
 

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)

Шаблоны, используемые на этой странице: