188
правок
Изменения
→Построение
|}
<br><br>
Для того, чтобы выбирать множество вершин для применения операции <tex>\mathrm{Compress}</tex> будем использовать следующий метод: для каждой вершины с помощью генератора псевдослучайных чисел выберем случайный бит. Вершина добавляется в множество, если у нее ровно один ребенок, она не является корнем и биты, которые были сгенерированы для нее, ребенка и родителя равны 0, 1 и 1 соответственно.
Рассмотрим более подробно, как необходимо хранить клетки таблицы Rake-Compress дерева. Для вершины необходимо сохранить ее родителя, а также множество детей. Для того, чтобы обрабатывать каждую клетку таблицы за <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>
Псевдокод хранения клетки таблицы:
'''struct''' Cell''':'''
'''int''' id, parent, cntChild, sumChild
'''int''' newParent, diffCntChild, diffSumChild
'''func''' applyChanges()''':'''
parent = newParent
sumChild += diffSumChild
cntChild += diffCntChild
diffCntChild = diffSumChild = 0
'''func''' addChild(v)''':'''
diffCntChild++
diffSumChild += v
'''func''' removeChild(v)''':'''
diffCntChild--
diffSumChild -= v
Для хранения Rake-Compress дерева будем использовать следующие данные:
* <tex>\mathrm{cells[]}</tex> {{---}} список клеток, которые ей соответствуют, для каждой вершины,
* <tex>\mathrm{rand}</tex> {{---}} генератор псевдослучайных чисел,
* <tex>\mathrm{time}</tex> {{---}} счётчик количества примененных операций по изменению структуры леса,
* <tex>\mathrm{lastUpdateTime[]}</tex> {{---}} массив, в котором для каждой вершины запишем номер последней операции, при обработки которой была изменена хотя бы одна клетка, которая соответствуют вершине: это позволит эффективно узнавать, была ли вершина уже помечена как поменявшаяся или нет.
'''struct''' RCTree(n: '''int''')''':'''
rand = RandBitsGenerator()
time = 0
'''for''' i = 0 '''to''' n
lastUpdateTime[i] = 0
cells[i] = []
Рассмотрим, как работает алгоритм построения Rake-Compress дерева. Будем строить таблицу по строкам. В каждый момент будем хранить множество вершин, которые еще не были сжаты, и перестраивать следующий слой. Также будем делать операции <tex>\mathrm{Rake}</tex> и <tex>\mathrm{Compress}</tex> одновременно. Чтобы определить, нужно ли сжимать вершину, воспользуемся следующим алгоритмом:
'''bool''' shouldRemoveVertex(c: '''Cell''', rand, layer: '''int''')''':'''
'''if''' c.cntChild == 0
'''return''' ''true''
'''if''' c.cntChild > 1 '''or''' c.parent == c.id
'''return''' ''false''
'''if''' getCellForVertex(c.sumChild).cntChild == 0
'''return''' ''false''
'''if''' rand.getBit(c.id, layer) == 0 '''and''' rand.getBit(c.sumChild, layer) == 1 '''and''' rand.getBit(c.parent, layer) == 1:
'''return''' ''true''
'''return''' ''false''
Таким образом, алгоритм построения дерева выглядит следующим образом:
'''func''' build(parent: '''int[]''')''':'''
alive = <tex>\{0 \dots n - 1\}</tex>
layer = 0
'''for''' i = 0 '''to''' n
cells[i].add(Cell(parent[i]))
'''while''' <tex>\mathrm{alive} \neq \emptyset</tex>
nextAlive = <tex>\emptyset</tex>
'''for''' <tex>v \in \mathrm{alive}</tex>
c = getCellForVertex(v)
'''if''' shouldRemoveVertex(c, rand, layer)
'''if'' c.cntChild == 1
getCellForVertex(c.sumChild).newParent = c.parent
getCellForVertex(c.parent).addChild(c.sumChild)
'''if''' c.parent <tex>\neq</tex> v
getCellForVertex(c.parent).remove(v)
'''else'''
nextAlive.add(v)
alive = nextAlive
'''for''' <tex>v \in \mathrm{alive}</tex>
newCell = getCellForVertex(v).clone().appleChanges()
cells[v].add(newCell)
layer++
==Возможность параллельного построения==
Операции <tex>\mathrm{Rake}</tex> и <tex>\mathrm{Compress}</tex> можно выполнять параллельно для всех вершин. Если предположить, что множество детей можно пересчитывать за <tex>O(1)</tex>, то Rake-Compress дерево можно построить за <tex>O(\log{n})</tex> в модели PRAM в случае наличия <tex>\Omega(n)</tex> процессоров.
