Деревья Эйлерова обхода — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Свойства эйлерова обхода)
м (rollbackEdits.php mass rollback)
 
(не показано 195 промежуточных версий 7 участников)
Строка 1: Строка 1:
==Введение==
+
==Задача о динамической связности==
'''Динамические деревья''' (англ.''dynamic tree'') используются в двух областях:.........
+
{{Задача
 
+
|definition = Для динамически изменяющегося дерева выполнить следующие запросы:
Нужно поддерживать следующие операции
+
* '''<tex>\mathrm{link(u, w)}</tex>''' {{---}} добавить ребро <tex>(u, w)</tex> (при условии, что вершины <tex>u</tex> и <tex>w</tex> принадлежат разным деревьям),
* '''<tex>\mathrm{link(u, w)}</tex>''' {{---}} добавить ребро (u, w) (при условии, что вершины u w принадлежат разным деревьям)
+
* '''<tex>\mathrm{cut(u, w)}</tex>''' {{---}} разрезать ребро <tex>(u, w)</tex> (при условии, что ребро <tex>(u, w)</tex> принадлежит дереву),
* '''<tex>\mathrm{cut(u, w)}</tex>''' {{---}} разрезать ребро (u, w) (при условии, что ребро (u, w) принадлежит дереву),
+
* '''<tex>\mathrm{isConnected(u, w)}</tex>''' {{---}} определить принадлежат ли вершины <tex>u</tex> и <tex>w</tex> одной компоненте связности.
* '''<tex>\mathrm{isConnected(u, w)}</tex>''' {{---}} принадлежат ли вершины u и w одной компоненте связности.
+
}}
  
''' Euler tour tree''' - The data structure we'll develop can perform these operations time O(log n) each.
+
Для решения поставленной задачи будем представлять дерево в виде его [[Эйлеровость графов|эйлерова графа]], а затем будем работать с [[Эйлеровость графов|эйлеровым обходом]] (англ.''Euler tour tree'') этого графа. Это позволит выполнять указанные запросы за <tex>O(\log n)</tex>.
  
 
==Представление деревьев в виде эйлерова графа==
 
==Представление деревьев в виде эйлерова графа==
Строка 17: Строка 17:
  
 
Получившийся [[Основные определения теории графов|ориентированный граф]] будет эйлеровым согласно [[Эйлеровость графов|критерию]].
 
Получившийся [[Основные определения теории графов|ориентированный граф]] будет эйлеровым согласно [[Эйлеровость графов|критерию]].
 +
<br>
 +
<br>
 +
<br>
 +
<br>
 +
<br>
 +
<br>
 +
<br>
 +
<br>
  
{{Задача
+
Представим дерево в виде последовательности вершин, посещенных в порядке эйлерова обхода, начиная с вершины <tex>a</tex>.
|definition = High-level idea: Instead of storing the trees in the forest, store their Euler tours.
+
[[Файл:Tour1.png|thumb|320px|center]]
Each edge insertion or deletion translates into a set of manipulations on the Euler tours of the trees in the forest.<br>
 
Checking whether two nodes are connected can be done by checking if they're in the same Euler tour.
 
}}
 
 
 
==Свойства эйлерова обхода==
 
 
 
Представим дерево в виде последовательности вершин, посещеннных в порядке эйлерова обхода с корнем в вершине <tex>a</tex>.
 
[[Файл:Tour1.png|thumb|400px|center]]
 
При этом последовательность вершин между первым и последним вхождением вершины <tex>h</tex> дает эйлеров обход поддерева с корнем <tex>h</tex>.
 
[[Файл:Tour2.png|thumb|400px|center]]
 
 
 
==Операции==
 
 
 
===Изменение корня дерева (переподвешивание)===
 
 
 
[[Файл:Tour3.png |center|Пример ]]
 
 
 
*Разбить последовательность на три части S₁, R, и S₂, где R состоит из вершин между первым и последним вхождением нового корня r.
 
*Удалить первую вершину в S₁.
 
*Соединить R, S₂, S₁, {r}.
 
 
 
Algorithm:
 
 
 
Split the tour into three parts: S₁, R, and S₂, where R consists of the nodes between the first and last occurrence of the new root r.<br>
 
Delete the first node in S₁.<br>
 
Concatenate R, S₂, S₁, {r}.
 
 
 
 
 
[[Файл:Proba.png |center|Пример ]]
 
 
 
===Связывание деревьев===
 
 
 
[[Файл:Link11.png |center|Пример ]]
 
 
 
Для связывания деревьев <tex>T_1 </tex> и <tex>T_2</tex>, где <tex>u \in T_1\ </tex>, а <tex>v \in T_2\</tex> добавлением ребра <tex>\{u, v\} \</tex> необходимо:
 
*Переподвесить дерево <tex>T₁</tex> к вершине <tex>u</tex>.
 
*Переподвесить дерево <tex>T₂</tex> к вершине <tex>v</tex>.
 
*Соединить получившиеся эйлеровы обходы.
 
*Добавить <tex>\{u\}</tex> в конец последовательности.
 
 
 
[[Файл:Link2.png |center|Пример ]]
 
 
 
В результате получим:
 
 
 
[[Файл:Link3.png |center|Пример ]]
 
 
 
===cut(u ,v)===
 
 
 
Given a tree T, executing cut(u, v) cuts the edge {u, v} from the tree (assuming it exists).<br>
 
Watch what happens to the Euler tour of T:
 
 
 
[[Файл:Cut.png |center|Пример ]]
 
 
 
To cut T into T₁ and T₂ by cutting {u, v}:<br>
 
Let E be an Euler tour for T.<br>
 
Rotate u to the front of E.<br>
 
Split E into E₁, V, E₂, where V is the span between the first and last occurrence of v.<br>
 
T₁ has the Euler tour formed by concatenating E₁ and E₂, deleting the extra u at the join point.<br>
 
T₂ has Euler tour V.
 
 
 
[[Файл:Cut1.png |center|Пример ]]
 
 
 
==Реализация структуры==
 
 
 
Goal: Implement link, cut, and is-connected as efficiently as possible.
 
 
 
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:<br>
+
==Операции c эйлеровыми обходами==
How do we efficiently implement these joins and splits?<br>
 
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:<br>
+
Для добавления ребра <tex>(c, g)</tex>:
Identify the first and last copy of a node in a sequence.<br>
+
*Выберем любое вхождение вершины <tex>c</tex> в эйлеров обход дерева <tex>T1</tex>.
Split a sequence at those positions.<br>
+
*Разрежем эйлеров обход <tex>T1</tex> на две части:
Concatenate sequences.<br>
+
*: <tex>A1</tex> {{---}} часть обхода до выбранного вхождения вершины <tex>c</tex>, включая ее.
Add a new copy of a node to a sequence.<br>
+
*: <tex>A2</tex> {{---}} часть обхода после выбранного вхождения вершины <tex>c</tex>, включая ее.
Delete a duplicate copy of a node from a sequence.<br>
+
*Аналогично, выберем любое вхождение вершины <tex>g</tex> в эйлеров обход дерева <tex>T2</tex> и разрежем его на две части <tex>B1</tex> и <tex>B2</tex>.
How do we do this efficiently?
+
*Соберем результирующий эйлеров обход в порядке <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> можно будет разделить дерево поиска на две части.
  
===Linked Lists===
+
[[Файл:Link22.png |thumb|400px|center|Рис.1a Исходный лес <br>Рис.1b Эйлеровы обходы деревьев<br> Рис.1с Двоичные деревья поиска для хранения эйлеровых обходов <br> Рис.1d Результирующий эйлеров обход]]
  
[[Файл:Linked lists.png |center|Пример ]]
+
===Разрезание ребра===
  
 +
Для удаления ребра <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> дает эйлеров обход второго дерева.
  
Each split or concatenate takes time O(1).<br>
+
Чтобы быстро находить места в эйлеровом обходе, которые соответствуют прохождению удаляемого ребра в дереве, будем для каждого ребра в дереве хранить ссылку на те места эйлерова обхода, где последовательно посещаем концы удаляемого ребра.
The first and last copy of a node can be identified in time O(1).<br>
+
Так, для ребра <tex>(g, j)</tex> храним ссылки на узлы дерева поиска, соответствующие парам посещений концов этого ребра.
A new copy of a node can be appended to the end of the sequence in time O(1).<br>
 
A redundant copy of a node can be deleted in time O(1).<br>
 
Everything sounds great!<br>
 
Question: How do you test for connectivity?
 
  
Euler tours give a simple, flexible encoding of tree structures.<br>
+
[[Файл:Link23.png |thumb|400px|center|Рис.1a Исходное дерево <br>Рис.1b Эйлеров обход исходного дерева<br> Рис.1с Двоичное дерево поиска для хранения эйлерового обхода <br> Рис.1d Эйлеровы обходы получившихся деревьев]]
Using doubly-linked lists, concatenation and splits take time O(1) each, but testing connectivity takes time Θ(n) in the worst-case.<br>
 
Can we do better?
 
  
===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.
+
===Сбалансированное дерево поиска===
  
[[Файл:Balanced tree.png |center|Пример ]]
+
Будем хранить последовательность вершин эйлерова обхода в виде сбалансированного двоичного дерева поиска, например, в виде [[Красно-черное дерево|красно-черного дерева]]. При построении дерева ключом вершины будет время посещения этой вершины эйлеровым обходом.
  
Observation 1: Can still store pointers to the first and last occurrence of each tree node.
+
Операции объединения и разделения красно-черных деревьев выполняется за <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>.
  
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.
+
Также, можем хранить последовательности вершин эйлерова обхода в [[Декартово_дерево_по_неявному_ключу|декартовом дереве по неявному ключу]]. Глубина декартового дерева, построенного на массиве из <tex>n</tex> вершин, будет поддерживаться равной <tex>O(\log n)</tex>.  
  
[[Файл:Balanced tree1.png |center|Пример ]]
+
Операции объединения и разделения также выполняются за <tex>O(\log n)</tex>.
  
The data structure:<br>
+
==См. также==
Represent each tree as an Euler tour.<br>
+
* [[Link-Cut Tree]]
Store those sequences as balanced binary trees.<br>
 
Each node in the original forest stores a pointer to its first and last occurrence.<br>
 
Each node in the balanced trees stores a pointer to its parent.<br>
 
link, cut, and is-connected queries take time only O(log n) each.
 
  
 +
== Примечания ==
 +
<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 Лекториум{{---}} Лекция Павла Маврина об эйлеровых обходах]
  
==Похожие структуры==
+
[[Категория: Алгоритмы и структуры данных]]
Про link-cut trees
+
[[Категория: Обходы графов]]
 +
[[Категория: Эйлеровы графы]]

Текущая версия на 19:44, 4 сентября 2022

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

Задача:
Для динамически изменяющегося дерева выполнить следующие запросы:
  • [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].

Tour1.png

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

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

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

  • Выберем любое вхождение вершины [math]c[/math] в эйлеров обход дерева [math]T1[/math].
  • Разрежем эйлеров обход [math]T1[/math] на две части:
    [math]A1[/math] — часть обхода до выбранного вхождения вершины [math]c[/math], включая ее.
    [math]A2[/math] — часть обхода после выбранного вхождения вершины [math]c[/math], включая ее.
  • Аналогично, выберем любое вхождение вершины [math]g[/math] в эйлеров обход дерева [math]T2[/math] и разрежем его на две части [math]B1[/math] и [math]B2[/math].
  • Соберем результирующий эйлеров обход в порядке [math]A1, B2, B1[/math] (без первой повторяющейся вершины), [math]A2[/math].

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

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

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

Для удаления ребра [math](g, j)[/math]:

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

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

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

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

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

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

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

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

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

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

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

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

См. также

Примечания

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