Деревья Эйлерова обхода

Введение

Для решения задачи о динамической связности (англ.dynamic connectivity problem) требуется выполнение следующих операций:

• [math]\mathrm{link(u, w)}[/math] — добавить ребро (u, w) (при условии, что вершины u w принадлежат разным деревьям),
• [math]\mathrm{cut(u, w)}[/math] — разрезать ребро (u, w) (при условии, что ребро (u, w) принадлежит дереву),
• [math]\mathrm{isConnected(u, w)}[/math] — определить принадлежат ли вершины u и w одной компоненте связности.

Дерево эйлерова обхода (англ.Euler tour tree) — способ представления динамического дерева, позволяющий выполнять указанные операции за [math]O(log n)[/math].

Представление деревьев в виде эйлерова графа

Пример дерева

Соответствующий эйлеров граф

Для представления дерева в виде эйлерового графа заменим каждое ребро [math]\{u, v\} \[/math] дерева на два ребра [math](u, v)[/math] и [math](v, u)[/math].

Получившийся ориентированный граф будет эйлеровым согласно критерию.

Задача:

High-level idea: Instead of storing the trees in the forest, store their Euler tours. Each edge insertion or deletion translates into a set of manipulations on the Euler tours of the trees in the forest. Checking whether two nodes are connected can be done by checking if they're in the same Euler tour.

Свойства эйлерова обхода

Представим дерево в виде последовательности вершин, посещеннных в порядке эйлерова обхода с корнем в вершине [math]a[/math].

При этом последовательность вершин между первым и последним вхождением вершины [math]h[/math] дает эйлеров обход поддерева с корнем [math]h[/math].

a b a g h i d c d e d i j l j i h g f g k g a

"font-family: times, serif; font-size:14pt; font-style:italic" "font-size: 13pt"

Операции

Изменение корня дерева (переподвешивание)

Для переподвешивания необходимо:

• Разбить эйлеров обход на три части [math]S1 [/math], [math]H[/math], и [math]S2 [/math], где [math]H[/math] состоит из вершин между первым и последним вхождением нового корня [math]h[/math].
• Удалить первую вершину в [math]S1 [/math].
• Соединить в следующем порядке: [math]H[/math], [math]S2 [/math], [math]S1 [/math].
• Добавить [math]\{h\}[/math] в конец последовательности.

В результате получим:

Добавление ребра

Для связывания деревьев [math]T1 [/math] и [math]T2[/math], где [math]c\in T1\ [/math], а [math]g\in T2\[/math] добавлением ребра [math]\{c, g\} \[/math] необходимо:

• Переподвесить дерево [math]T1[/math] к вершине [math]c[/math].
• Переподвесить дерево [math]T2[/math] к вершине [math]g[/math].
• Соединить получившиеся эйлеровы обходы.
• Добавить [math]\{c\}[/math] в конец последовательности.

В результате получим:

Разрезание ребра

Для разбиения дерева на два поддерева путем разрезания ребра [math]\{g, j\} \[/math] (если оно существует) необходимо:

• Переподвесить дерево к вершине [math]g[/math].
• Разделить дерево на части [math]E1, V, E2[/math], где [math]V[/math] отрезок между первым и последним вхождением вершины [math]j[/math].
• Эйлеров обход первого поддерева образуется соединением [math]E1[/math] и [math]E2[/math], с удалением повторного [math]\{g\}[/math] в месте их соединения.
• Эйлеров обход второго поддерева образует [math]V[/math].

В результате получим:

Реализация структуры

Задача:

Реализовать добавление и разрезание ребер, а также проверку принадлежности вершин одной компоненте связности наиболее эффективным образом.

By representing trees via their Euler tours, can implement link and cut so that only O(1) joins and splits are necessary per operation.

Questions to answer:
How do we efficiently implement these joins and splits?
Once we have the tours, how do we answer connectivity queries?

Implementing the Structure

The operations we have seen require us to be able to efficiently do the following:
Identify the first and last copy of a node in a sequence.
Split a sequence at those positions.
Concatenate sequences.
Add a new copy of a node to a sequence.
Delete a duplicate copy of a node from a sequence.
How do we do this efficiently?

Связные списки

Each split or concatenate takes time O(1). Каждое разбиение и соединение последовательностей требует О(1) времени.
The first and last copy of a node can be identified in time O(1).Определение первого и последнего вхождения вершины в последовательность происходит за О(1).
A new copy of a node can be appended to the end of the sequence in time O(1).Новая копия вершины может быть добавлена в конец последовательности за О(1).
A redundant copy of a node can be deleted in time O(1).Лишняя копия вершины может быть удалена за О(1).
Everything sounds great!
Question: How do you test for connectivity?

Euler tours give a simple, flexible encoding of tree structures.
Using doubly-linked lists, concatenation and splits take time O(1) each, but testing connectivity takes time Θ(n) in the worst-case.
Can we do better? Используя двойные связные списки добавление и разрезание ребра может быть проведено за время О(1), но определение принадлежности вершин одной компоненте связности занимает Θ(n) в худшем случае.

Balanced Trees

Claim: It is possible to represent sequences of elements balanced binary trees.

These are not binary search trees. We're using the shape of a red/black tree to ensure balance.

Observation 1: Can still store pointers to the first and last occurrence of each tree node.

Observation 2: If nodes store pointers to their parents, can answer is-connected(u, v) in time O(log n) by seeing if u and v are in the same tree.

Observation 3: Red/black trees can be split and joined in time O(log n) each.

The data structure:
Represent each tree as an Euler tour.
Store those sequences as balanced binary trees.
Each node in the original forest stores a pointer to its first and last occurrence.
Each node in the balanced trees stores a pointer to its parent.
link, cut, and is-connected queries take time only O(log n) each.

Сравнительная табличка

Похожие структуры

Про link-cut trees