1632
правки
Изменения
м
{{Утверждение
|statement=Последовательность вершин между первым и последним вхождениями вершины <tex>h</tex> в эйлеров обход дерева, представляет эйлеров обход поддерва с корнем в <tex>h</tex>.
|proof=Действительно, при обходе дерева последний раз выйдем из вершины, только после посещения всех вершин ее поддерева.
[[Файл:Tour2.png|thumb|320px|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]]
rollbackEdits.php mass rollback
<br>
Представим дерево в виде последовательности вершин, посещенных в порядке эйлерова обхода, начиная с корнем в вершине вершины <tex>a</tex> в виде последовательности вершин, посещеннных в порядке эйлерова обхода.
[[Файл:Tour1.png|thumb|320px|center]]
==Операции c эйлеровыми обходами==
*Выберем любое вхождение вершины <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>(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> дает эйлеров обход второго дерева.
===Проверка на связность===
Для того, чтобы проверить, лежат ли 2 две вершины в одном дереве, достаточно подняться от вхождения каждой вершины в эйлеров обход (ссылку на которое мы храним) до корня дерева поиска, хранящего этот элеров эйлеров обход.
==Реализация Способы реализации структуры==
Будем хранить последовательность вершин эйлерова обхода в виде сбалансированного двоичного дерева поиска, например, в виде [[Файл:Balanced tree.png Красно-черное дерево|centerкрасно-черного дерева]]. При построении дерева ключом вершины будет время посещения этой вершины эйлеровым обходом.
==См. также==
* [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 Лекториум{{---}} Лекция Павла Маврина об эйлеровых обходах]
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Обходы графов]]
[[Категория: Эйлеровы графы]]
