188
правок
Изменения
Нет описания правки
[[Файл: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>
Сжатие может быть рассмотрено как рекурсивная кластеризация дерева в один '''кластер'''. Изначально вершины и рёбра составляют базовый кластер. Операции <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>.]]
Определим кластер как поддерево исходного дерева, порожденное множеством вершин.
{{Определение
|definition=Для кластера <tex>C</tex> скажем, что вершина <tex>v</tex> из <tex>C</tex> называется '''граничной вершиной''', если <tex>v</tex> смежная с вершинами не из <tex>C</tex>.
}}
{{Определение
|definition='''Граница кластера''' {{---}} множество граничных вершин кластера. }}{{Определение|definition='''Степень кластера''' {{---}} количество граничных вершин кластера.
}}
diffCntChild = diffSumChild = 0
'''func''' addChild(v: '''int''')''':'''
diffCntChild++
diffSumChild += v
'''func''' removeChild(v: '''int''')''':'''
diffCntChild--
diffSumChild -= v
'''struct''' RCTree(n: '''int''')''':'''
'''RndGen''' rand = RandBitsGenerator() '''int''' time = 0
'''for''' i = 0 '''to''' n
lastUpdateTime[i] = 0
Таким образом, алгоритм построения дерева выглядит следующим образом:
'''func''' build(parent: '''int[n]''')''':''' n = parent.size
alive = <tex>\{0 \dots n - 1\}</tex>
'''int''' layer = 0 '''for''' i = 0 '''to''' n <font color="green">// заполним таблицу вершинами изначального дерева</font>
cells[i].add(Cell(parent[i]))
'''while''' <tex>\mathrm{alive} \neq \emptyset</tex>
nextAlive = <tex>\emptyset</tex>
'''for''' <tex>v \in \mathrm{alive}</tex>
'''Cell''' c = getCellForVertex(v) <font color="green">// получить клетку таблицы, соответствующую вершине</font>
'''if''' shouldRemoveVertex(c, rand, layer)
'''if''' c.cntChild == 1
alive = nextAlive
'''for''' <tex>v \in \mathrm{alive}</tex>
'''Cell''' newCell = getCellForVertex(v).clone().applyChanges()
cells[v].add(newCell)
layer++
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
affected.remove(v)
'''for''' <tex>v \in \mathrm{affected}</tex>
'''Cell''' newCell = getCellForVertex(v).clone().applyChanges()
cells[v][layer + 1] = newCell
layer++
'''func''' removeEffectOfVertex(v: '''int''')''':''' <font color="green">// удалить отметку о том, что вершина была помечена изменившийся</font>
'''int''' layer = cells[v].size '''Cell''' c = cells[v][layer]
'''if''' c.parent == v
'''return'''
==Сравнение с 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{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> деревья могут оказаться полезными, если необходимо пересчитывать значения не на путях, а на поддеревьях.
