Rake-Compress деревья

Задача, которая решается с помощью динамических деревьев, формулируется следующим образом. Необходимо поддерживать лес деревьев и выполнять на нем следующие операции:

• $\mathrm{link(u, v)}$ — добавить ребро $(u, v)$. Вершина $u$ должна быть корнем некоторого дерева. Вершины $u$ и $v$ должны находиться в разных деревьях,
• $\mathrm{cut(u, v)}$ — удалить ребро $(u, v)$. Ребро $(u, v)$ должно присутствовать в графе,
• $\mathrm{query()}$ — некоторый запрос относительно структуры дерева.

Идея

Описание

Дано некоторое дерево $T$, алгоритм сжатия дерева (англ. tree-contraction algorithm), предложенный Миллером и Райфом сжимает $T$ в одну вершину путем применения операций $\mathrm{Rake}$ и $\mathrm{Compress}$ в несколько раундов:

• $\mathrm{Rake}$ — все листья дерева сжимаются к своим родителям,
• $\mathrm{Compress}$ — выбирается и объединяется некоторое множество несмежных друг с другом вершин, имеющих ровно одного сына.

Операция $\mathrm{Rake}$

Операция $\mathrm{Compress}$

Сжатие дерева требует линейного времени и логарифмическое число раундов.

Рассмотрим, как изменяется количество вершин в дереве после применения к нему операций $\mathrm{Rake}$ и $\mathrm{Compress}$.
Разобьём все вершины дерева на три группы:

• $T_0$ — входящая степень равна нулю,
• $T_1$ — входящая степень равна одному,
• $T_2$ — входящая степень больше одного.

Лемма (1):

$T_2 \leqslant T_0 - 1$.

Доказательство:

$\triangleright$

Докажем по индукции по высоте дерева. База Для дерева из одной вершины утверждение верно. Переход Пусть утверждение доказано для деревьев высоты меньше $h$. Докажем для дерева высоты ровно $h$. Рассмотрим степень корня: Если корень имеет ровно одного ребенка, то переходим к случаю дерева высоты $h - 1$. Если у дерева несколько поддеревьев, то имеем: $T_2 = 1 + \sum\limits_{u \in *: children(root)}T_2(u) \leqslant 1 + \sum\limits_{u \in children(root)}(T_0(u) - 1)$  $\leqslant -1 + \sum\limits_{u \in children}T_0(u) \leqslant -1 + T_0 = T_0 - 1$.

$\triangleleft$

Заметим, что для леса деревьев лемма также справедлива.

Лемма (2):

После применения операций $\mathrm{Rake}$ и $\mathrm{Compress}$ к лесу, математическое ожидание количества вершин в нём не превосходит $\dfrac{7}{8}$ от их исходного числа.

Доказательство:

$\triangleright$

Математическое ожидание количества удаленных вершин $\mathrm{deleted} = T_0 + \dfrac{T_1}{8}$ (так как все листья будут удалены после операции $\mathrm{Rake}$, а каждая вершина, у которой ровно один сын, будет удалена с вероятностью $\dfrac{1}{8}$ после операции $\mathrm{Compress}$). Из предыдущей леммы получаем: $\mathrm{deleted} = \dfrac{1}{2} (T_0 + T_2) + \dfrac{1}{8} T_1 \geqslant \dfrac{1}{8} (T_0 + T_1 + T_2)$.

$\triangleleft$

Теорема:

Математическое ожидание количества операций $\mathrm{Rake}$ и $\mathrm{Compress}$, которые будут выполнены до полного сжатия дерева, равно $O(\log{n})$, где $n$ — общее количество вершин.

Доказательство:

$\triangleright$

Из леммы 2 известно, что после каждой итерации применения операций $\mathrm{Rake}$ и $\mathrm{Compress}$ число вершин в среднем уменьшается в константное число раз. Значит, количество итераций в среднем ограничено $O(\log{n})$.

$\triangleleft$

Для конкретного применения можно предположить, что рёбра дерева имеют вес, а вершины имеют метки.

Пример операций

В качестве примера сжатия дерева рассмотрим следующее взвешенное дерево:

Исходное дерево $T$.

Алгоритм сжатия дерева $T$.

На каждом раунде сжатия (перечислены сверху вниз) удаляется множество вершин с использованием операций $\mathrm{Rake}$ и $\mathrm{Compress}$:

• Операция $\mathrm{Rake}$ удаляет лист и ребро, смежное с ним и сохраняет в соседях данные — метку удалённой вершины, вес удалённого ребра и данные о сжатых на предыдущих раундах вершинах.
• Операция $\mathrm{Compress}$ удаляет вершины, имеющую ровно одного сына, и два смежных с ней ребра. Например, для вершины $v$ c сыном $w$ и родителем $u$ будут удалены рёбра $(u, v)$ и $(v, w)$. После этого добавляется ребро $(u, w)$, а данные вершины $v$ и удалённых рёбер сохраняются в соседние вершины — метку удалённой вершины, сохранённые данные и веса удалённых рёбер.

Например, для приведённого дерева на первом раунде сжатия применяется операция $\mathrm{Rake}$ для вершин $a$, $d$, $n$, $k$ и операция $\mathrm{Compress}$ для $g$ и $i$.

Сжатие может быть рассмотрено как рекурсивная кластеризация дерева в один кластер. Изначально вершины и рёбра составляют базовый кластер. Операции $\mathrm{Rake}$ и $\mathrm{Compress}$ формируют большие кластеры из нескольких меньших кластеров.

На иллюстрации примера все кластеры (кроме базового) обозначены зелёными лепестками. Каждый кластер помечен заглавной буквой метки вершины, входящей в него. Например, кластер $A$, полученный после сжатия вершины $a$ содержит вершины $a$, $b$ и ребро $(a, b)$; сжатая вершина $g$ создает кластер $G$, содержащий эту вершину и рёбра $(f, g)$ и $(g, h)$. Во втором раунде, после сжатия вершины $b$ создается кластер $B$, содержащий кластер $A$ и ребро $(b, c)$.
Представление сжатого дерева в виде кластеров:

Кластеризованное дерево $T$.

Определим кластер как поддерево исходного дерева, порожденное множеством вершин.

Определение:

Для кластера $C$ скажем, что вершина $v$ из $C$ называется граничной вершиной, если $v$ смежная с вершинами не из $C$.

Определение:

Граница кластера — множество граничных вершин кластера. Степень кластера — количество граничных вершин кластера.

Например, для рассматриваемого дерева кластер $A$ имеет границу $\{b\}$ и степень $1$, а кластер $G$ имеет границу $\{f, g\}$ и степень $2$. При сжатии дерева все кластеры, кроме последнего, имеют степени $1$ и $2$. Свойством алгоритмом сжатия является то, что:

• операции $\mathrm{Rake}$ создают кластеры со степенью $1$,
• операции $\mathrm{Compress}$ создают кластеры со степенью $2$,
• финальный кластер имеет степень $0$.

Процесс сжатия исходного дерева может быть представлен в виде нового дерева, называемого $\mathrm{RC-tree}$.
Пример такого дерева для рассматриваемого исходного дерева:

RC-tree для дерева $T$.

Поскольку матожидание количества раундов — логарифм, то такое дерево будет сбалансированным.
$\mathrm{RC}$ дерево можно использовать для ответа на динамические запросы для статического дерева. Для этого в $\mathrm{RC}$ дереве сохраним требуемую информацию (необходимо модифицировать для пересчёта информации операции $\mathrm{Rake}$ и $\mathrm{Compress}$) и используем обход для ответа на запросы. Поскольку дерево с большой вероятностью является сбалансированным, обход дерева также можно осуществить за логарифм.
Для динамических деревьев, например, если доступны операции добавления/удаления ребра (операции $\mathrm{link}$ и $\mathrm{cut}$), нужно эффективно перестраивать отдельные кластеры, пересчитывая данные. Для этого можно обновлять данные начиная с листа дерева, соответствующего обновляемой вершине в исходном дереве, и подниматься вверх.

Реализация

Хранение

Для того, чтобы отвечать на запросы относительно структуры леса необходимо сохранить информацию о том, как происходил процесс сжатия леса. Для этого будем хранить таблицу, в каждой строке которой записана информация о структуре леса после выполнения операций. Каждая клетка таблицы будет хранить информацию о вершине после выполнения операций $\mathrm{Rake}$ и $\mathrm{Compress}$. Из информации будем сохранять родителя вершины, множество детей и метку, сжата ли вершина.
Пример таблицы для следующей последовательности операций:

Пример выполнения операций.

Шаг	Операция	$1$	$2$	$3$	$4$
4	$\mathrm{Rake}$	Родитель: — Дети: $\emptyset$	—	—	—
3	$\mathrm{Compress}$	Родитель: — Дети: $\{3\}$	—	Родитель: $1$ Дети: $\emptyset$	—
2	$\mathrm{Rake}$	Родитель: — Дети: $\{2\}$	Родитель: $1$ Дети: $\{3\}$	Родитель: $2$ Дети: $\emptyset$	—
1		Родитель: — Дети: $\{2\}$	Родитель: $1$ Дети: $\{3\}$	Родитель: $2$ Дети: $\{4\}$	Родитель: $3$ Дети: $\emptyset$

Для того, чтобы выбирать множество вершин для применения операции $\mathrm{Compress}$ будем использовать следующий метод: для каждой вершины с помощью генератора псевдослучайных чисел выберем случайный бит. Вершина добавляется в множество, если у нее ровно один ребенок, она не является корнем и биты, которые были сгенерированы для нее, ребенка и родителя равны $0$, $1$ и $1$ соответственно.

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

Рассмотрим, в каких случаях можно сжать вершину:

• если детей у вершины больше одного, то ее точно нельзя сжать,
• если у неё нет детей, то ее можно сжать только во время операции $\mathrm{Rake}$
• если у вершины один ребёнок, то её возможно сжать во время операции $\mathrm{Compress}$.

Чтобы определить, можно ли применить операцию $\mathrm{Compress}$ к вершине, в том случае, когда у нее один ребёнок, нужно узнать, какой бит был сгенерирован на текущей итерации для ребёнка (один из трёх битов, генерируемых при операции $\mathrm{Compress}$). Для этого необходимо знать номер вершины-ребёнка. Значит, нам нужно определять, какие элементы находятся в множестве детей только в том случае, когда размер множества равен $1$. Поэтому, всю информацию о множестве можно хранить с помощью двух величин — хранить количество элементов в множестве и сумму их номеров. Поддерживая сумму номеров детей и их количество, можно эффективно узнавать номер вершины-ребёнка, когда это необходимо. Данная оптимизация позволяет за $O(1)$ получать номер ребёнка и за $O(1)$ обновлять множество детей.

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

Псевдокод хранения клетки таблицы:

• $\mathrm{id}$ — номер вершины,
• $\mathrm{parent}$ — родитель вершины,
• $\mathrm{cntChild}$ — количество детей вершины,
• $\mathrm{sumChild}$ — сумма номеров детей,
• $\mathrm{newParent}$ — новый родитель вершины после изменений,
• $\mathrm{diffCntChild}$ и $\mathrm{diffSumChild}$ — изменения, произведенные с полями $\mathrm{cntChild}$ и $\mathrm{sumChild}$ соответственно.

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

Для хранения $\mathrm{Rake-Compress}$ дерева будем использовать следующие данные:

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

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

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

Построение

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

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

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

Как только некоторая вершина помечается как изменившаяся, отменим её действие на таблицу:

1. Найдем момент времени, когда вершина сжимается к родителю.
2. Рассмотрим, какие вершины поменяются при сжатии данной: это ее родитель (если он есть), а также сын (если он есть). Для каждой из этих вершин поменяем значения изменений, которые необходимо применить к состоянию.
3. Пометим, что эти вершины поменялись на этом слое. Для этого на каждом слое будем хранить список вершин, которые на нем поменялись. А перед тем как обрабатывать очередной слой будем добавлять в множество изменившихся вершин вершины из соответствующего списка.
4. Кроме удаления эффекта от изменившихся вершин также необходимо и добавить правильный эффект. Для этого будем для каждой из изменившихся вершин определять, как ее состояние меняется при переходе к следующему слою. Если вершина сжимается к ее родителю, то пометим родителя и ребенка (если он есть) и поменяем изменение, которое хранится в соответствующих клетках. А для пересчета состояния клеток воспользуемся значениями изменений, которые сохранены в клетках.
   

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

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

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

Операции $\mathrm{Rake}$ и $\mathrm{Compress}$ можно выполнять параллельно для всех вершин. Если предположить, что множество детей можно пересчитывать за $O(1)$, то $\mathrm{Rake-Compress}$ дерево можно построить за $O(\log{n})$ в модели PRAM в случае наличия $\Omega(n)$ процессоров.

См. также

• Link-Cut Tree

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

• Wikipedia — Parallel Tree Contraction
• Б. Ю. Минаев — Реализация динамических $\mathrm{Rake-Compress}$ деревьев в случае отсутствия ограничения на степени вершин
• Acar, Blelloch, and Vittes — RC-Tree implementation
• 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