188
правок
Изменения
Нет описания правки
__TOC__
==Описание==
* <tex>\mathrm{Rake}</tex> {{---}} все листья дерева сжимаются к своим родителям,
* <tex>\mathrm{Compress}</tex> {{---}} выбирается и объединяется некоторое множество несмежных друг с другом вершин, имеющих ровно одного сына.
|about=1
|statement=<tex>T_2 \leqslant T_0 - 1</tex>.
|proof=Докажем по индукции по высоте дерева.<br>Для дерева из одной вершины утверждение верно.<br>Пусть утверждение доказано для деревьев высоты меньше <tex>h</tex>. Докажем для дерева высоты ровно <tex>h</tex>. Рассмотрим степень корня. Если корень имеет ровно одного ребенка, то переходим к случаю дерева высоты <tex>h - 1</tex>. Если у дерева несколько поддеревьев, то имеем:<br><tex>T_2 = 1 + \Sigma_sum\limits_{u \in children(root)}T_2(u) \leqslant 1 + \Sigma_sum\limits_{u \in children(root)}(T_0(u) - 1)</tex> <tex> \leqslant -1 + \Sigma_sum\limits_{u \in children}T_0(u) \leqslant -1 + T_0 = T_0 - 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>На самом деле, множество детей хранится для того, чтобы определять, можно ли сжать вершину. Если детей у вершины больше одного, то ее точно нельзя сжать. Если у неё нет детей, то ее можно сжать только во время операции <tex>\mathrm{Rake}</tex>. Чтобы определить можно ли применить операцию <tex>\mathrm{Compress}</tex> к вершине, в том случае, когда у нее один ребёнок, нужно узнать, как бит был сгенерирован на текущей итерации для ребёнка. Для этого необходимо знать номер вершины-ребёнка. Значит, необходимо уметь определять, кто находится в множестве только в том случае, если в нём не более одного элемента. Поэтому, всю информацию о множестве можно хранить с помощью двух величин {{---}} хранить количество элементов в множестве и сумму их номеров.<br><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''':'''
'''int''' id, parent, cntChild, sumChild
diffSumChild -= v
Для хранения <tex>\mathrm{Rake-Compress }</tex> дерева будем использовать следующие данные:
* <tex>\mathrm{cells[]}</tex> {{---}} список клеток, которые ей соответствуют, для каждой вершины,
* <tex>\mathrm{rand}</tex> {{---}} генератор псевдослучайных чисел,
cells[i] = []
Кроме запросов о структуре леса, <tex>\mathrm{Rake-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''')''':'''
'''if''' c.cntChild == 0
Таким образом, алгоритм построения дерева выглядит следующим образом:
'''func''' build(parent: '''int[]''')''':'''
n = parent.size
alive = <tex>\{0 \dots n - 1\}</tex>
layer = 0
==Возможность параллельного построения==
Операции <tex>\mathrm{Rake}</tex> и <tex>\mathrm{Compress}</tex> можно выполнять параллельно для всех вершин. Если предположить, что множество детей можно пересчитывать за <tex>O(1)</tex>, то <tex>\mathrm{Rake-Compress }</tex> дерево можно построить за <tex>O(\log{n})</tex> в модели PRAM в случае наличия <tex>\Omega(n)</tex> процессоров. ==Применения==* Задача [[Остовные_деревья:_определения,_лемма_о_безопасном_ребре|MST]] online: дан граф <tex>G</tex> из <tex>n</tex> вершин, в который добавляются новые рёбра. Необходимо поддерживать минимальный остовный лес для данного графа,* Задача о максимальном потоке: в помощью динамических деревьев можно улучшить ассимптотику [[Схема_алгоритма_Диница|алгоритма Диница]] с <tex>O(V^2 E)</tex> до <tex>O(VE \log{V})</tex>.
==См. также==
==Источники информации==
* [https://en.wikipedia.org/wiki/Parallel_Tree_Contraction Wikipedia {{---}} Parallel Tree Contraction]
* [https://github.com/BorysMinaiev/bachelor/blob/master/thesis_v2.pdf Б. Ю. Минаев {{---}} Реализация динамических <tex>\mathrm{Rake-Compress }</tex> деревьев в случае отсутствия ограничения на степени вершин]* G[http://www. Lcs. Miller, Jprinceton. Hedu/~rwerneck/papers/Wer06-dissertation. Reif {{---}} Parallel Tree Contraction* pdf 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
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Задача о наименьшем общем предке]]
