Изменения

Перейти к: навигация, поиск

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

470 байт добавлено, 19:44, 4 сентября 2022
м
rollbackEdits.php mass rollback
==ВведениеЗадача о динамической связности=={{Задача|definition = Для решения задачи о динамической связности (англ.''dynamic connectivity problem'') требуется выполнение следующих операцийдинамически изменяющегося дерева выполнить следующие запросы:* '''<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''' - The data structure we'll develop can perform these operations time ) этого графа. Это позволит выполнять указанные запросы за <tex>O(\log n) each</tex>.
==Представление деревьев в виде эйлерова графа==
Получившийся [[Основные определения теории графов|ориентированный граф]] будет эйлеровым согласно [[Эйлеровость графов|критерию]].
<br>
<br>
<br>
<br>
<br>
<br>
<br>
<br>
{{Задача|definition = 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.<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|320px|center]]
При этом последовательность вершин между первым и последним вхождением вершины <tex>h</tex> дает эйлеров обход поддерева с корнем <tex>h</tex>.
[[Файл:Tour2.png|thumb|320px|center]]
 
[[Файл:Tour5.png|thumb|320px|center|<span style="font-size: 13pt" >''a b a g h i d c d e d i j l j i h g f g k g a''</span>]]
"font-family: times, serif; font-size:14pt; font-style:italic"
"font-size: 13pt"
 
==Операции==
 
===Изменение корня дерева (переподвешивание)===
 
[[Файл:Tour13.png |thumb|320px|center]]
Для переподвешивания необходимо:*Разбить эйлеров обход на три части <tex>S1 </tex>, <tex>H</tex>, и <tex>S2 </tex>, где <tex>H</tex> состоит из вершин между первым и последним вхождением нового корня <tex>h</tex>.*Удалить первую вершину в <tex>S1 </tex>.*Соединить в следующем порядке: <tex>H</tex>, <tex>S2 </tex>, <tex>S1 </tex>.*Добавить <tex>\{h\}</tex> в конец последовательности. В результате получим: [[Файл:Proba.png |center]]==Операции c эйлеровыми обходами==
===Добавление ребра===
[[ФайлДля добавления ребра <tex>(c, g)</tex>:Link11.png |thumb|400px|center]] Для связывания деревьев *Выберем любое вхождение вершины <tex>T1 c</tex> и в эйлеров обход дерева <tex>T2T1</tex>, где .*Разрежем эйлеров обход <tex>c\in T1\ </tex>, а на две части:*: <tex>g\in T2\A1</tex> добавлением ребра {{---}} часть обхода до выбранного вхождения вершины <tex>\{c, g\} \</tex> необходимо:, включая ее.*Переподвесить дерево : <tex>T1A2</tex> к вершине {{---}} часть обхода после выбранного вхождения вершины <tex>c</tex>, включая ее.*Переподвесить дерево Аналогично, выберем любое вхождение вершины <tex>g</tex> в эйлеров обход дерева <tex>T2</tex> к вершине и разрежем его на две части <tex>B1</tex> и <tex>gB2</tex>.*Соединить получившиеся эйлеровы обходы.*Добавить Соберем результирующий эйлеров обход в порядке <tex>A1, B2, B1</tex> (без первой повторяющейся вершины), <tex>\{c\}A2</tex> в конец последовательности. [[Файл:Link2.png|thumb|400px |center]]
В результате получим:Чтобы быстро находить место, где разрезать эйлеровы обходы деревьев <tex>T1</tex> и <tex>T2</tex>, будем хранить эйлеровы обходы в двоичных деревьях поиска. Ключом вершины для построения дерева поиска будет время посещения этой вершины эйлеровым обходом.Для каждой вершины дерева <tex>(T1, T2)</tex> будем хранить указатель на вершину в дереве поиска, которая соответствует вхождению вершины дерева в эйлеров обход. Тогда за <tex>O(1)</tex> переходим от вершины дерева к вершине дерева поиска, по которой за <tex>O(\log n)</tex> можно будет разделить дерево поиска на две части.
[[Файл:Link3Link22.png|thumb|400px|center|Рис.1a Исходный лес <br>Рис.1b Эйлеровы обходы деревьев<br> Рис.1с Двоичные деревья поиска для хранения эйлеровых обходов <br> Рис.1d Результирующий эйлеров обход]]
===Разрезание ребра===
[[Файл:Cut1.png|thumb|350px|center]]
 
Для разбиения дерева на два поддерева путем разрезания ребра <tex>\{g, j\} \</tex> (если оно существует) необходимо:
*Переподвесить дерево к вершине <tex>g</tex>.
*Разделить дерево на части <tex>E1, V, E2</tex>, где <tex>V</tex> отрезок между первым и последним вхождением вершины <tex>j</tex>.
*Эйлеров обход первого поддерева образуется соединением <tex>E1</tex> и <tex>E2</tex>, с удалением повторного <tex>\{g\}</tex> в месте их соединения.
*Эйлеров обход второго поддерева образует <tex>V</tex>.
 
[[Файл:Cut2.png|thumb|350px|center]]
 
В результате получим:
[[Файл:Cut3.png|thumb|350px|center]]
 
==Реализация структуры==
 
{{Задача
|definition = Реализовать добавление и разрезание ребер, а также проверку принадлежности вершин одной компоненте связности наиболее эффективным образом.
}}
 
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>
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>
Identify the first and last copy of a node in a sequence.<br>
Split a sequence at those positions.<br>
Concatenate sequences.<br>
Add a new copy of a node to a sequence.<br>
Delete a duplicate copy of a node from a sequence.<br>
How do we do this efficiently?
 
 
===Связные списки===
 
[[Файл: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)Чтобы быстро находить места в эйлеровом обходе, которые соответствуют прохождению удаляемого ребра в дереве, будем для каждого ребра в дереве хранить ссылку на те места эйлерова обхода, где последовательно посещаем концы удаляемого ребра. Каждое разбиение и соединение последовательностей требует О(1) времени.<br>The first and last copy of a node can be identified in time O(1).Определение первого и последнего вхождения вершины в последовательность происходит за О(1).Так, для ребра <brtex>A new copy of a node can be appended to the end of the sequence in time O(1g, j).Новая копия вершины может быть добавлена в конец последовательности за О(1).<br/tex>A redundant copy of a node can be deleted in time O(1)храним ссылки на узлы дерева поиска, соответствующие парам посещений концов этого ребра.Лишняя копия вершины может быть удалена за О(1).<br>Everything sounds great!<br>Question: How do you test for connectivity?
Euler tours give a simple, flexible encoding of tree structures[[Файл:Link23.png |thumb|400px|center|Рис.1a Исходное дерево <br>Рис.1b Эйлеров обход исходного дерева<br>Using doubly-linked lists, concatenation and splits take time O(1) each, but testing connectivity takes time Θ(n) in the worst-caseРис.1с Двоичное дерево поиска для хранения эйлерового обхода <br>Can we do better?Используя двойные связные списки добавление и разрезание ребра может быть проведено за время О(1), но определение принадлежности вершин одной компоненте связности занимает Θ(n) в худшем случаеРис.1d Эйлеровы обходы получившихся деревьев]]
===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 Операции объединения и разделения красно-черных деревьев выполняется за <tex>O(\log n)</tex><ref>[http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1: Can still store pointers to the first and last occurrence .1.109.4875&rep=rep1&type=pdf Ron Wein {{---}} Efficient Implementation of each tree nodeRed-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Также, можем хранить последовательности вершин эйлерова обхода в [[Декартово_дерево_по_неявному_ключу|декартовом дереве по неявному ключу]]. Глубина декартового дерева, построенного на массиве из <tex>n</black trees can be split and joined in time tex> вершин, будет поддерживаться равной <tex>O(\log n) each</tex>.
[[Файл:Balanced tree1Операции объединения и разделения также выполняются за <tex>O(\log n)</tex>.png |center|Пример ]]
The data structure:<br>Represent each tree as an Euler tour.<br>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* [[Link-connected queries take time only O(log n) each.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 Лекториум{{---}} Лекция Павла Маврина об эйлеровых обходах]
==Похожие [[Категория: Алгоритмы и структуры==данных]]Про link-cut trees[[Категория: Обходы графов]][[Категория: Эйлеровы графы]]
1632
правки

Навигация