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{Compress}[/math] будем использовать следующий метод: для каждой вершины с помощью генератора псевдослучайных чисел выберем случайный бит. Вершина добавляется в множество, если у нее ровно один ребенок, она не является корнем и биты, которые были сгенерированы для нее, ребенка и родителя равны 0, 1 и 1 соответственно.

Рассмотрим более подробно, как необходимо хранить клетки таблицы Rake-Compress дерева. Для вершины необходимо сохранить ее родителя, а также множество детей. Для того, чтобы обрабатывать каждую клетку таблицы за [math]O(\log{n})[/math], нужно производить операции с множеством детей за [math]O(1)[/math].

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

Если вершина является корнем, то в качестве ее родителя будем хранить ее номер. Кроме того необходимо хранить изменения, которые произойдут с клеткой при переходе к следующему слою: будем хранить, кто должен стать новым родителем, на сколько изменится количество детей, а также как изменится сумма их номеров. Все это необходимо для того, чтобы обрабатывать каждую изменившуюся клетку за [math]O(1)[/math].
Псевдокод хранения клетки таблицы:

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 дерева будем использовать следующие данные:

• [math]\mathrm{cells[]}[/math] — список клеток, которые ей соответствуют, для каждой вершины,
• [math]\mathrm{rand}[/math] — генератор псевдослучайных чисел,
• [math]\mathrm{time}[/math] — счётчик количества примененных операций по изменению структуры леса,
• [math]\mathrm{lastUpdateTime[]}[/math] — массив, в котором для каждой вершины запишем номер последней операции, при обработки которой была изменена хотя бы одна клетка, которая соответствуют вершине: это позволит эффективно узнавать, была ли вершина уже помечена как поменявшаяся или нет.

struct RCTree(n: int):
    rand = RandBitsGenerator()
    time = 0
    for i = 0 to n
        lastUpdateTime[i] = 0
        cells[i] = []

Построение

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

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 = [math]\{0 \dots n - 1\}[/math]
    layer = 0
    for i = 0 to n
        cells[i].add(Cell(parent[i]))
    while [math]\mathrm{alive} \neq \emptyset[/math]
        nextAlive = [math]\emptyset[/math]
        for [math]v \in \mathrm{alive}[/math]
            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 [math]\neq[/math] v
                    getCellForVertex(c.parent).remove(v)
            else
                nextAlive.add(v)
        alive = nextAlive
        for [math]v \in \mathrm{alive}[/math]
            newCell = getCellForVertex(v).clone().appleChanges()
            cells[v].add(newCell)
        layer++

Операции удаления и добавления ребра

Как только некоторая вершина помечается как изменившаяся, отменим её действие на таблицу. А именно, найдем момент времени, когда вершина сжимается к родителю. Рассмотрим, какие вершины поменяются при сжатии данной. Это ее родитель (если он есть), а также сын (если он есть). Для каждой из этих вершин поменяем значения изменений, которые необходимо применить к состоянию. Также пометим, что эти вершины поменялись на этом слое. Для этого на каждом слое будем хранить список вершин, которые на нем поменялись. А перед тем как обрабатывать очередной слой будем добавлять в множество изменившихся вершин вершины из соответствующего списка. Кроме удаления эффекта от изменившихся вершин также необходимо и добавить правильный эффект. Для этого будем для каждой из из- менившихся вершин определять, как ее состояние меняется при переходе к следующему слою. Если вершина сжимается к ее родителю, то пометим родителя и ребенка (если он есть) и поменяем изменение, которое хранится в соответствующих клетках. А для пересчета состояния клеток воспользуемся значениями изменений, которые сохранены в клетках.
Рассмотрим, что происходит с таблицей при изменении одного ребра. Основная идея заключается в том, чтобы научится пересчитывать все изменения таблицы за время пропорциональное их количеству. Для этого будем эффективно поддерживать множество изменившихся клеток. В момент, когда вершина помечается, как изменившаяся, найдем, как она влияет на таблицу и отменим это влияние.
Для начала необходимо найти момент времени, когда вершина сжимается. В этот момент она влияет на не более чем две вершины. Изменим значения [math]\mathrm{cntChild}[/math], [math]\mathrm{sumChild}[/math] и [math]\mathrm{newParent}[/math] нужным образом. Также необходимо добавить эти вершины в множество изменившихся (в момент, когда будет обработан соответствующий слой). Поэтому, для каждого слоя еще будем хранить список вершин, которые должны быть помечены перед обработкой слоя.
Алгоритм обновления дерева:

func changeTree([math](u, v)[/math]: Edge):
    time = time + 1
    affected = [math]\emptyset[/math]
    markAffected(u)                     // пусть из дерева было удалено ребро [math](u, v)[/math]
    markAffected(v)
    cells[u].parent = u
    cells[v].cntChild--
    cells[v].sumChild -= u
    layer = 0
    while [math]\mathrm{affected} \neq \emptyset[/math]
        for [math]v \in \mathrm{affectedOnLayer}[/math]
            markAffected(v)
        for [math]v \in \mathrm{affected}[/math]
            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 [math]\neq[/math] v
                getCellForVertex(c.parent).removeChild(v)
                markAffected(c.parent)
            affected.remove(v)
        for [math]v \in \mathrm{affected}[/math]
            newCell = getCellForVertex(v).clone().applyChanges()
            cells[v][layer + 1] = newCell
        layer++

func markAffected(v: int):
   if lastUpdateTime[v] == time
       return                          // вершина уже помечена
   lastUpdateTime[v] = time
   affected.add(v)
   removeEffectOfVertex(v)

func removeEffectOfVertex(v: int):
   layer = cells[v].size
   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

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

Операции [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].

См. также

• Link-Cut Tree

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

• Wikipedia — Parallel Tree Contraction
• Б. Ю. Минаев — Реализация динамических Rake-Compress деревьев в случае отсутствия ограничения на степени вершин
• G. L. Miller, J. H. Reif — Parallel Tree Contraction
• R. Werneck — Design and Analysis of Data Structures for Dynamic Trees