1632
правки
Изменения
м
Нужно поддерживать следующие операции * '''<tex>\mathrm{linkДля решения поставленной задачи будем представлять дерево в виде его [[Эйлеровость графов|эйлерова графа]], а затем будем работать с [[Эйлеровость графов|эйлеровым обходом]] (u, w)}</tex>англ.''Euler tour tree' {{---}} добавить ребро (u, w) (при условии, что вершины u w принадлежат разным деревьям)* '''<tex>\mathrm{cut(u, w)}этого графа. Это позволит выполнять указанные запросы за </tex>''' {{---}} разрезать ребро O(u, w) (при условии, что ребро (u, w) принадлежит дереву),* '''<tex>\mathrm{isConnected(u, wlog n)}</tex>''' {{---}} принадлежат ли вершины u и w одной компоненте связности.
''' Euler tour tree''' - The data structure we'll develop can perform these operations time O(log n) each.==Представление деревьев в виде эйлерова графа==
==[[Файл:Tree.png|300px|thumb|left|Пример дерева]][[Файл:Euler Tours on Trees==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><br>Mathematically formulates the “trace this figure without picking up your pencil or redrawing any lines” puzzles.<br><br><br><br><br><br>
Euler Tours on Trees==Операции c эйлеровыми обходами==
In general, trees do not have Euler tours.===Добавление ребра===
[[ФайлДля добавления ребра <tex>(c, g)</tex>:Euler graph*Выберем любое вхождение вершины <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 |400px|thumb|center|Пример ]]
Technique: replace each edge {uЧтобы быстро находить место, v} with two edges где разрезать эйлеровы обходы деревьев <tex>T1</tex> и <tex>T2</tex>, будем хранить эйлеровы обходы в двоичных деревьях поиска. Ключом вершины для построения дерева поиска будет время посещения этой вершины эйлеровым обходом.Для каждой вершины дерева <tex>(uT1, vT2) and </tex> будем хранить указатель на вершину в дереве поиска, которая соответствует вхождению вершины дерева в эйлеров обход. Тогда за <tex>O(v1)</tex> переходим от вершины дерева к вершине дерева поиска, uпо которой за <tex>O(\log n).<br/tex>Resulting graph has an Euler tourможно будет разделить дерево поиска на две части.
High-level idea[[Файл: Instead of storing the trees in the forest, store their Euler toursLink22.Each edge insertion or deletion translates into a set of manipulations on the Euler tours of the trees in the forestpng |thumb|400px|center|Рис.1a Исходный лес <br>Checking whether two nodes are connected can be done by checking if they're in the same Euler tourРис.1b Эйлеровы обходы деревьев<br> Рис.1с Двоичные деревья поиска для хранения эйлеровых обходов <br> Рис.1d Результирующий эйлеров обход]]
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Чтобы быстро находить места в эйлеровом обходе, которые соответствуют прохождению удаляемого ребра в дереве, будем для каждого ребра в дереве хранить ссылку на те места эйлерова обхода, где последовательно посещаем концы удаляемого ребра.Так, для ребра <tex>(g, j)</tex> храним ссылки на узлы дерева поиска, соответствующие парам посещений концов этого ребра.png |400px|thumb|center|Пример ]]
[[Файл:Tour2===Проверка на связность===Для того, чтобы проверить, лежат ли две вершины в одном дереве, достаточно подняться от вхождения каждой вершины в эйлеров обход (ссылку на которое мы храним) до корня дерева поиска, хранящего этот эйлеров обход.png |400px|thumb|center|Пример ]]
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Операции объединения и разделения красно-черных деревьев выполняется за <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.]<br/ref>In some cases, we will need to change the root of the tree.
===cutТакже, можем хранить последовательности вершин эйлерова обхода в [[Декартово_дерево_по_неявному_ключу|декартовом дереве по неявному ключу]]. Глубина декартового дерева, построенного на массиве из <tex>n</tex> вершин, будет поддерживаться равной <tex>O(u ,v\log n)===</tex>.
rollbackEdits.php mass rollback
==ВведениеЗадача о динамической связности=={{Задача|definition = Для динамически изменяющегося дерева выполнить следующие запросы:* '''Динамические деревья<tex>\mathrm{link(u, w)}</tex>''' {{---}} добавить ребро <tex>(англ.u, w)</tex> (при условии, что вершины <tex>u</tex> и <tex>w</tex> принадлежат разным деревьям),* '''<tex>\mathrm{cut(u, w)}</tex>'dynamic tree''{{---}} разрезать ребро <tex>(u, w) используются в двух областях:........</tex> (при условии, что ребро <tex>(u, w)</tex> принадлежит дереву),* '''<tex>\mathrm{isConnected(u, w)}</tex>''' {{---}} определить принадлежат ли вершины <tex>u</tex> и <tex>w</tex> одной компоненте связности.}}
Представим дерево в виде последовательности вершин, посещенных в порядке эйлерова обхода, начиная с вершины <tex>a</tex>.[[Файл:Simple graphTour1.png |400pxthumb|thumb320px|center|Пример ]]
==Properties of Euler Tours=Разрезание ребра===
[[Файл:Link23.png |thumb|400px|center|Рис.1a Исходное дерево <br>Рис.1b Эйлеров обход исходного дерева<br> Рис.1с Двоичное дерево поиска для хранения эйлерового обхода <br> Рис.1d Эйлеровы обходы получившихся деревьев]]
==Операции=Сбалансированное дерево поиска===
===link(u ,v)Декартово дерево по неявному ключу===
Операции объединения и разделения также выполняются за <tex>O(\log n)</tex>.
==Реализация структурыСм. также==* [[Link-Cut Tree]]
===Linked Lists=Примечания ==<references/>
==Источники информации=Balanced Trees=* [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[[Категория: Эйлеровы графы]]
