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 |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 |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Для того, чтобы проверить, лежат ли две вершины в одном дереве, достаточно подняться от вхождения каждой вершины в эйлеров обход (ссылку на которое мы храним) до корня дерева поиска, хранящего этот эйлеров обход.
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При построении дерева ключом вершины будет время посещения этой вершины эйлеровым обходом.
Algorithm:===Декартово дерево по неявному ключу===
Split the tour into three parts: S₁Также, Rможем хранить последовательности вершин эйлерова обхода в [[Декартово_дерево_по_неявному_ключу|декартовом дереве по неявному ключу]]. Глубина декартового дерева, and S₂построенного на массиве из <tex>n</tex> вершин, where R consists of the nodes between the first and last occurrence of the new root r.будет поддерживаться равной <brtex>Delete the first node in S₁.O(\log n)<br/tex>Concatenate R, S₂, S₁, {r}.
Given two trees T₁ and T₂, where u ∈ T₁ and v ∈ T₂, executing link(u, v) links the trees together by adding edge ==Источники информации==* [https://en.wikipedia.org/wiki/Euler_tour_technique Wikipedia {{u, v---}}Euler tour technique]* [http://courses.<br>csail.mit.edu/6.851/spring07/scribe/lec05.pdf Advanced Data Structures {{---}} Euler tour trees]Watch what happens to the * [http://codeforces.com/blog/entry/18369?mobile=true&locale=en CodeForces {{---}} On Euler tourstour trees]* [http://logic.pdmi.ras.ru/csclub/node/2819 Лекториум{{---}} Лекция Павла Маврина об эйлеровых обходах]
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 |thumb|320px|center|Пример ]]
==Properties of Euler Tours=Разрезание ребра===
[[Файл:Tour2Link23.png |thumb|400px|center|Пример Рис.1a Исходное дерево <br>Рис.1b Эйлеров обход исходного дерева<br> Рис.1с Двоичное дерево поиска для хранения эйлерового обхода <br> Рис.1d Эйлеровы обходы получившихся деревьев]]
==ОперацииСпособы реализации структуры==
===Rerooting a TourСбалансированное дерево поиска===
Операции объединения и разделения красно-черных деревьев выполняется за <tex>O(\log n)</tex><ref>[[Файлhttp:Tour3//citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.109.4875&rep=rep1&type=pdf Ron Wein {{---}} Efficient Implementation of Red-Black Trees.png |center|Пример ]]</ref>.
Операции объединения и разделения также выполняются за <tex>O(\log n)</tex>.
==См. также==* [[Файл:Tour4.png |center|Пример Link-Cut Tree]]
===link(u ,v)=Примечания ==<references/>
[[ФайлКатегория:Two trees.png |center|Пример Алгоритмы и структуры данных]] To link T₁ and T₂ by adding {u, v}[[Категория:<br>Let E₁ and E₂ be Euler tours of T₁ and T₂, respectively.<br>Rotate E₁ to root the tour at u.<br>Rotate E₂ to root the tour at v.<br>Concatenate E₁, E₂, {u}.Обходы графов]][[ФайлКатегория:Two trees1.png |center|Пример Эйлеровы графы]] ===cut(u ,v)=== Given a tree T, executing cut(u, v) cuts the edge {u, v} from the tree (assuming it exists).<br>Watch what happens to the Euler tour of T: ==Реализация структуры== ===Linked Lists=== ===Balanced Trees=== Сравнительная табличка ==Похожие структуры==Про link-cut trees
