Изменения

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

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

1007 байт добавлено, 19:44, 4 сентября 2022
м
rollbackEdits.php mass rollback
<br>
Представим дерево в виде последовательности вершин, посещенных в порядке эйлерова обхода, начиная с корнем в вершине вершины <tex>a</tex> в виде последовательности вершин, посещеннных в порядке эйлерова обхода.
[[Файл:Tour1.png|thumb|320px|center]]
 
{{Утверждение
|statement=Последовательность вершин между первым и последним вхождениями вершины <tex>h</tex> в эйлеров обход дерева, представляет эйлеров обход поддерва с корнем в <tex>h</tex>.
|proof=Действительно, при обходе дерева последний раз выйдем из вершины, только после посещения всех вершин ее поддерева.
[[Файл:Tour2.png|thumb|320px|center]]
}}
==Операции c эйлеровыми обходами==
Представление деревьев в виде их эйлеровых обходов позволяет свести задачу о динамической связности к следующим операциям с последовательностями вершин:
 
===Изменение корня дерева (переподвешивание)===
Дано дерево с корнем в вершине <tex>a</tex>. Требуется переподвесить его к вершине <tex>h</tex>.
 
[[Файл:Tour14.png |thumb|320px|center]]
 
Для переподвешивания (англ. ''rerooting'') необходимо:
*Разбить эйлеров обход на три части:
*: <tex>S1</tex> - вершины, посещенные эйлеровым обходом до захода в <tex>h</tex>.
*: <tex>H</tex> - вершины между первым и последним вхождением нового корня <tex>h</tex>.
*: <tex>S2 </tex> - вершины, посещенные эйлеровым обходом после выхода из <tex>h</tex>.
*Удалить первую вершину в <tex>S1 </tex>.
*Соединить в следующем порядке: <tex>H</tex>, <tex>S2 </tex>, <tex>S1 </tex>.
*Добавить <tex>\{h\}</tex> в конец последовательности.
 
[[Файл:Tour13.png |thumb|320px|center]]
 
В результате получим:
 
[[Файл:Proba.png |center]]
===Добавление ребра===
[[ФайлДля добавления ребра <tex>(c, g)</tex>:Link11*Выберем любое вхождение вершины <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>.png |thumb|400px|center]]
Для связывания Чтобы быстро находить место, где разрезать эйлеровы обходы деревьев <tex>T1 </tex> и <tex>T2</tex>, где будем хранить эйлеровы обходы в двоичных деревьях поиска. Ключом вершины для построения дерева поиска будет время посещения этой вершины эйлеровым обходом.Для каждой вершины дерева <tex>c\in (T1\ </tex>, а <tex>g\in T2\</tex> добавлением ребра <tex>\{c, g\} \</tex> необходимо:*Переподвесить дерево <tex>T1</tex> к вершине <tex>c)</tex>будем хранить указатель на вершину в дереве поиска, если корнем которая соответствует вхождению вершины дерева была другая вершинав эйлеров обход.*Переподвесить дерево Тогда за <tex>T2O(1)</tex> переходим от вершины дерева к вершине <tex>g</tex>дерева поиска, если корнем дерева была другая вершина.*Соединить получившиеся эйлеровы обходы.*Добавить по которой за <tex>O(\{c\}log n)</tex> в конец последовательностиможно будет разделить дерево поиска на две части.
[[Файл:Link2Link22.png|thumb|400px |center]] В результате получим эйлеров обход дерева с корнем в вершине |Рис.1a Исходный лес <texbr>cРис.1b Эйлеровы обходы деревьев</texbr>: [[Файл:Link3Рис.png|center1с Двоичные деревья поиска для хранения эйлеровых обходов <br> Рис.1d Результирующий эйлеров обход]]
===Разрезание ребра===
[[Файл:Cut1.png|thumb|350px|center]]
Для разбиения дерева на два поддерева путем разрезания удаления ребра <tex>\{(g, j\} \)</tex> необходимо:*Переподвесить дерево к вершине Найдем в эйлеровом обходе дерева <tex>T</tex> две пары посещений концов удаляемого ребра <tex>g,j</tex>.*Разделить дерево на части и <tex>E1j, V, E2g</tex>, где которые соответствуют прохождениям по ребру <tex>V(g, j)</tex> отрезок между первым и последним вхождением вершины в дереве <tex>jT</tex>.*Эйлеров Разрежем эйлеров обход первого поддерева образуется соединением дерева по этим парам на три части: <tex>E1A1, A2, A3</tex> и .*Соединив <tex>E2A1</tex>, с удалением повторного и <tex>\{g\}A3</tex> в месте их соединения.*Эйлеров (без повторяющейся первой вершины), получим эйлеров обход второго поддерева образует первого дерева, а <tex>VA2</tex>дает эйлеров обход второго дерева.
[[Файл:Cut2Чтобы быстро находить места в эйлеровом обходе, которые соответствуют прохождению удаляемого ребра в дереве, будем для каждого ребра в дереве хранить ссылку на те места эйлерова обхода, где последовательно посещаем концы удаляемого ребра.Так, для ребра <tex>(g, j)</tex> храним ссылки на узлы дерева поиска, соответствующие парам посещений концов этого ребра.png|thumb|350px|center]]
В результате получим:[[Файл:Cut3Link23.png|thumb|350px400px|center|Рис.1a Исходное дерево <br>Рис.1b Эйлеров обход исходного дерева<br> Рис.1с Двоичное дерево поиска для хранения эйлерового обхода <br> Рис.1d Эйлеровы обходы получившихся деревьев]]
==Реализация структуры=Проверка на связность===Для того, чтобы проверить, лежат ли две вершины в одном дереве, достаточно подняться от вхождения каждой вершины в эйлеров обход (ссылку на которое мы храним) до корня дерева поиска, хранящего этот эйлеров обход.
{{Задача|definition = Определить структуру данных для хранения эйлеровых обходов деревьев для наиболее эффективного выполнения указанных операций.}}=Способы реализации структуры==
===Balanced TreesСбалансированное дерево поиска===[[Файл:Balanced tree.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>.
Для каждой вершины храним указатели на её первое и последнее вхождение в последовательность. Значит, имеем доступ к ним за <tex>O(1)</tex>.===Декартово дерево по неявному ключу===
Запрос о принадлежности Также, можем хранить последовательности вершин к одной компоненте связности выполняется за эйлерова обхода в [[Декартово_дерево_по_неявному_ключу|декартовом дереве по неявному ключу]]. Глубина декартового дерева, построенного на массиве из <tex>n</tex> вершин, будет поддерживаться равной <tex>O(\log n)</tex> проверкой лежат ли эти вершины в одном дереве.
[[Файл:Balanced tree1Операции объединения и разделения также выполняются за <tex>O(\log n)</tex>.png |center]]
==См. также==
* [[Link-Cut Tree]]
 
== Примечания ==
<references/>
==Источники информации==
* [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 Лекториум{{---}} Лекция Павла Маврина об эйлеровых обходах]
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Обходы графов]]
[[Категория: Эйлеровы графы]]
1632
правки

Навигация