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

Задача о динамической связности

Задача:

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

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

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

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

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

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

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

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

Утверждение:

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

[math]\triangleright[/math]

Действительно, при обходе дерева последний раз выйдем из вершины, только после посещения всех вершин ее поддерева.

[math]\triangleleft[/math]

Операции c эйлеровыми обходами

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

Для добавления ребра (c, g):

• Выберем любое вхождение вершины c в эйлеров обход T1.
• Разрежем эйлеров обход T1 на 2 части:

  A1 - часть обхода до выбранного вхождения вершины c, включая ее.

  A2 - часть обхода после выбранного вхождения вершины c, включая ее.

• Аналогично, выберем любое вхождение вершины g в эйлеров обход T2 и разрежем его на 2 части B1 и B2.
• Соберем результирующий эйлеров обход в порядке A1 B2 B1(без первой повторяющейся вершины) A2.

Чтобы быстро находить место, где разрезать эйлеровы обходы деревьев T1 и T2, будем хранить эйлеровы обходы в двоичных деревьях поиска. Ключом вершины, для построения дерева поиска, будет время посещения этой вершины эйлеровым обходом. Для каждой вершины дерева (T1, T2) будем хранить указатель на вершину в дереве поиска, которая соответствует вхождению вершины дерева в эйлеров обход. Тогда за O(1) переходим от вершины дерева к вершине дерева поиска, по которой за O(log n) можно будет разделить дерево поиска на 2 части.

Рис.1a Исходный лес
Рис.1b Эйлеровы обходы деревьев Т1 и Т2
Рис.1с Двоичные деревья поиска для хранения эйлеровых обходов
Рис.1d Результирующий эйлеров обход

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

Для удаления ребра [math]\{g, j\} \[/math]:

• Найдем в эйлеровом обходе дерева T две пары посещений концов удаляемого ребра gj и jg, которые соответствуют прохождениям по ребру (g, j) в T.
• Разрежем эйлеров обход дерева по этим парам на 3 части: A1, A2, A3
• В результате получатся 2 дерева с эйлеровыми обходами A1 A3(без повторяющейся первой вершины) и A2 соответственно

Чтобы быстро находить места в эйлеровом обходе, которые соответствуют прохождению удаляемого ребра в дереве, будем для каждого ребра в дереве хранить ссылку на те места эйлерова обхода, где последовательно посещаем концы удаляемого ребра. Так, для ребра (g, j) храним ссылки на узлы дерева поиска, соответствующие парам посещений концов этого ребра.

Рис.1a Исходное дерево
Рис.1b Эйлеров обход исходного дерева
Рис.1с Двоичное дерево поиска для хранения эйлерового обхода
Рис.1d Эйлеровы обходы получившихся деревьев

Проверка на связность

Для того, чтобы проверить, лежат ли 2 вершины в одном дереве, достаточно подняться от вхождения каждой вершины в эйлеров обход (ссылку на которое мы храним) до корня дерева поиска, хранящего этот элеров обход.

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

Представим последовательность вершин эйлерова обхода в виде сбалансированного двоичного дерева. Будем использовать красно-черное дерево.

Объединение и разделение красно-черных деревьев выполняется за [math]O(\log n)[/math].

Для каждой вершины храним указатели на её первое и последнее вхождение в последовательность. Значит, имеем доступ к ним за [math]O(1)[/math].

Запрос о принадлежности вершин к одной компоненте связности выполняется за [math]O(\log n)[/math] проверкой лежат ли эти вершины в одном дереве.

См. также

• Link-Cut Tree

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

• Wikipedia — Euler tour technique
• Advanced Data Structures — Euler tour trees
• CodeForces — On Euler tour trees