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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Rerooting a Tour)
м (rollbackEdits.php mass rollback)
 
(не показаны 264 промежуточные версии 7 участников)
Строка 1: Строка 1:
==Введение==
+
==Задача о динамической связности==
'''Динамические деревья''' (англ.''dynamic tree'') используются в двух областях:.........
+
{{Задача
 +
|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>.
* '''<tex>\mathrm{link(u, w)}</tex>''' {{---}} добавить ребро (u, w) (при условии, что вершины u  w принадлежат разным деревьям)
 
* '''<tex>\mathrm{cut(u, w)}</tex>''' {{---}} разрезать ребро (u, w) (при условии, что ребро (u, w) принадлежит дереву),
 
* '''<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 Tours on Trees==
+
[[Файл:Tree.png|300px|thumb|left|Пример дерева]]
 +
[[Файл:Euler graph.png|300px|thumb|right|Соответствующий эйлеров граф]]
  
Euler Tours
+
Для представления [[Дерево, эквивалентные определения|дерева]] в виде [[Эйлеровость графов|эйлерового графа]] заменим каждое ребро <tex>\{u, v\} \</tex> дерева на два ребра <tex>(u, v)</tex> и <tex>(v, u)</tex>.
  
In a graph G, an Euler tour is a path through the graph that visits every edge exactly once.<br>
+
Получившийся [[Основные определения теории графов|ориентированный граф]] будет эйлеровым согласно [[Эйлеровость графов|критерию]].
Mathematically formulates the “trace this figure without picking up your pencil or redrawing any lines” puzzles.
+
<br>
 +
<br>
 +
<br>
 +
<br>
 +
<br>
 +
<br>
 +
<br>
 +
<br>
  
[[Файл:Simple graph.png |center|Пример ]]
+
Представим дерево в виде последовательности вершин, посещенных в порядке эйлерова обхода, начиная с вершины <tex>a</tex>.
 +
[[Файл:Tour1.png|thumb|320px|center]]
  
Euler Tours on Trees
+
==Операции c эйлеровыми обходами==
  
In general, trees do not have Euler tours.
+
===Добавление ребра===
  
[[Файл:Euler graph.png |center|Пример ]]
+
Для добавления ребра <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>.
  
Technique: replace each edge {u, v} with two edges (u, v) and (v, u).<br>
+
Чтобы быстро находить место, где разрезать эйлеровы обходы деревьев <tex>T1</tex> и <tex>T2</tex>, будем хранить эйлеровы обходы в двоичных деревьях поиска.
Resulting graph has an Euler tour.
+
Ключом вершины для построения дерева поиска будет время посещения этой вершины эйлеровым обходом.
 +
Для каждой вершины дерева <tex>(T1, T2)</tex> будем хранить указатель на вершину в дереве поиска, которая соответствует вхождению вершины дерева в эйлеров обход.
 +
Тогда за <tex>O(1)</tex> переходим от вершины дерева к вершине дерева поиска, по которой за <tex>O(\log n)</tex> можно будет разделить дерево поиска на две части.
  
High-level idea: Instead of storing the trees in the forest, store their Euler tours.
+
[[Файл:Link22.png |thumb|400px|center|Рис.1a Исходный лес <br>Рис.1b Эйлеровы обходы деревьев<br> Рис.1с Двоичные деревья поиска для хранения эйлеровых обходов <br> Рис.1d Результирующий эйлеров обход]]
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.
 
  
==Properties of Euler Tours==
+
===Разрезание ребра===
  
The sequence of nodes visited in an Euler tour of a tree is closely connected to the structure of the tree.
+
Для удаления ребра <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> дает эйлеров обход второго дерева.
  
[[Файл:Tour1.png |center|Пример ]]
+
Чтобы быстро находить места в эйлеровом обходе, которые соответствуют прохождению удаляемого ребра в дереве, будем для каждого ребра в дереве хранить ссылку на те места эйлерова обхода, где последовательно посещаем концы удаляемого ребра.
 +
Так, для ребра <tex>(g, j)</tex> храним ссылки на узлы дерева поиска, соответствующие парам посещений концов этого ребра.
  
[[Файл:Tour2.png |center|Пример ]]
+
[[Файл:Link23.png |thumb|400px|center|Рис.1a Исходное дерево <br>Рис.1b Эйлеров обход исходного дерева<br> Рис.1с Двоичное дерево поиска для хранения эйлерового обхода <br> Рис.1d Эйлеровы обходы получившихся деревьев]]
  
Begin by directing all edges toward the the first node in the tour.<br>
+
===Проверка на связность===
Claim: The sequences of nodes visited between the first and last instance of a node v gives an Euler tour of the subtree rooted at v.
+
Для того, чтобы проверить, лежат ли две вершины в одном дереве, достаточно подняться от вхождения каждой вершины в эйлеров обход (ссылку на которое мы храним) до корня дерева поиска, хранящего этот эйлеров обход.
  
==Операции==
+
==Способы реализации структуры==
  
===Rerooting a Tour===
+
===Сбалансированное дерево поиска===
  
The subtrees defined by ranges in Euler tours on trees depend on the root.<br>
+
Будем хранить последовательность вершин эйлерова обхода в виде сбалансированного двоичного дерева поиска, например, в виде [[Красно-черное дерево|красно-черного дерева]]. При построении дерева ключом вершины будет время посещения этой вершины эйлеровым обходом.  
In some cases, we will need to change the root of the tree.
 
  
[[Файл:Tour3.png |center|Пример ]]
+
Операции объединения и разделения красно-черных деревьев выполняется за <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>.
  
[[Файл:Tour4.png |center|Пример ]]
+
===Декартово дерево по неявному ключу===
  
===link(u ,v)===
+
Также, можем хранить последовательности вершин эйлерова обхода в [[Декартово_дерево_по_неявному_ключу|декартовом дереве по неявному ключу]]. Глубина декартового дерева, построенного на массиве из <tex>n</tex> вершин, будет поддерживаться равной <tex>O(\log n)</tex>.
  
===cut(u ,v)===
+
Операции объединения и разделения также выполняются за <tex>O(\log n)</tex>.
  
 +
==См. также==
 +
* [[Link-Cut Tree]]
  
==Реализация структуры==
+
== Примечания ==
 +
<references/>
  
===Linked Lists===
+
==Источники информации==
 +
* [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 Лекториум{{---}} Лекция Павла Маврина об эйлеровых обходах]
  
===Balanced Trees===
+
[[Категория: Алгоритмы и структуры данных]]
 
+
[[Категория: Обходы графов]]
 
+
[[Категория: Эйлеровы графы]]
Сравнительная табличка
 
 
 
==Похожие структуры==
 
Про 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].

См. также

Примечания

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