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

2019-10-26T07:27:02Z

78.85.13.123: /* Декартово дерево по неявному ключу */

==Задача о динамической связности==
{{Задача
|definition = Для динамически изменяющегося дерева выполнить следующие запросы:
* '''<tex>\mathrm{link(u, w)}</tex>''' {{---}} добавить ребро <tex>(u, w)</tex> (при условии, что вершины <tex>u</tex> и <tex>w</tex> принадлежат разным деревьям),
* '''<tex>\mathrm{cut(u, w)}</tex>''' {{---}} разрезать ребро <tex>(u, w)</tex> (при условии, что ребро <tex>(u, w)</tex> принадлежит дереву),
* '''<tex>\mathrm{isConnected(u, w)}</tex>''' {{---}} определить принадлежат ли вершины <tex>u</tex> и <tex>w</tex> одной компоненте связности.
}}

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

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

[[Файл:Tree.png|300px|thumb|left|Пример дерева]]
[[Файл:Euler graph.png|300px|thumb|right|Соответствующий эйлеров граф]]

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

Получившийся [[Основные определения теории графов|ориентированный граф]] будет эйлеровым согласно [[Эйлеровость графов|критерию]].
 
 
 
 
 
 
 
 

Представим дерево в виде последовательности вершин, посещенных в порядке эйлерова обхода, начиная с вершины <tex>a</tex>.
[[Файл:Tour1.png|thumb|320px|center]]

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

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

Для добавления ребра <tex>(c, g)</tex>:
*Выберем любое вхождение вершины <tex>c</tex> в эйлеров обход дерева <tex>T1</tex>.
*Разрежем эйлеров обход <tex>T1</tex> на две части:
*: <tex>A1</tex> {{---}} часть обхода до выбранного вхождения вершины <tex>c</tex>, включая ее.
*: <tex>A2</tex> {{---}} часть обхода после выбранного вхождения вершины <tex>c</tex>, включая ее.
*Аналогично, выберем любое вхождение вершины <tex>g</tex> в эйлеров обход дерева <tex>T2</tex> и разрежем его на две части <tex>B1</tex> и <tex>B2</tex>.
*Соберем результирующий эйлеров обход в порядке <tex>A1, B2, B1</tex> (без первой повторяющейся вершины), <tex>A2</tex>.

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

[[Файл:Link22.png |thumb|400px|center|Рис.1a Исходный лес Рис.1b Эйлеровы обходы деревьев Рис.1с Двоичные деревья поиска для хранения эйлеровых обходов Рис.1d Результирующий эйлеров обход]]

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

Для удаления ребра <tex>(g, j)</tex>:
*Найдем в эйлеровом обходе дерева <tex>T</tex> две пары посещений концов удаляемого ребра <tex>g,j</tex> и <tex>j,g</tex>, которые соответствуют прохождениям по ребру <tex>(g, j)</tex> в дереве <tex>T</tex>.
*Разрежем эйлеров обход дерева по этим парам на три части: <tex>A1, A2, A3</tex>.
*Соединив <tex>A1</tex> и <tex>A3</tex> (без повторяющейся первой вершины), получим эйлеров обход первого дерева, а <tex>A2</tex> дает эйлеров обход второго дерева.

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

[[Файл:Link23.png |thumb|400px|center|Рис.1a Исходное дерево Рис.1b Эйлеров обход исходного дерева Рис.1с Двоичное дерево поиска для хранения эйлерового обхода Рис.1d Эйлеровы обходы получившихся деревьев]]

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

==Способы реализации структуры==

===Сбалансированное дерево поиска===

Будем хранить последовательность вершин эйлерова обхода в виде сбалансированного двоичного дерева поиска, например, в виде [[Красно-черное дерево|красно-черного дерева]]. При построении дерева ключом вершины будет время посещения этой вершины эйлеровым обходом.

Операции объединения и разделения красно-черных деревьев выполняется за <tex>O(\log n)</tex><ref>[http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.109.4875&rep=rep1&type=pdf Ron Wein {{---}} Efficient Implementation of Red-Black Trees.]</ref>.

===Декартово дерево по неявному ключу===

Также, можем хранить последовательности вершин эйлерова обхода в [[Декартово_дерево_по_неявному_ключу|декартовом дереве по неявному ключу]]. Глубина декартового дерева, построенного на массиве из <tex>n</tex> вершин, будет поддерживаться равной <tex>O(\log n)</tex>.

Операции объединения и разделения также выполняются за <tex>O(\log n)</tex>.

==См. также==
* [[Link-Cut Tree]]

== Примечания ==
<references/>

==Источники информации==
* [https://en.wikipedia.org/wiki/Euler_tour_technique Wikipedia {{---}} Euler tour technique]
* [http://courses.csail.mit.edu/6.851/spring07/scribe/lec05.pdf Advanced Data Structures {{---}} Euler tour trees]
* [http://codeforces.com/blog/entry/18369?mobile=true&locale=en CodeForces {{---}} On Euler tour trees]
* [http://logic.pdmi.ras.ru/csclub/node/2819 Лекториум{{---}} Лекция Павла Маврина об эйлеровых обходах]

[[Категория: Алгоритмы и структуры данных]]
[[Категория: Обходы графов]]
[[Категория: Эйлеровы графы]]

Викиконспекты - Вклад участника [ru]

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