Изменения

==ВведениеЗадача о динамической связности=={{Задача|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>\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 одной компоненте связности.

В основном, Для представления [[Дерево, эквивалентные определения|деревьядерева]] не являются в виде [[Эйлеровость графов|эйлеровыми графамиэйлерового графа]]заменим каждое ребро <tex>\{u, v\} \</tex> дерева на два ребра <tex>(u, v)</tex> и <tex>(v, u)</tex>.

Получившийся [[Файл:Euler graph.png Основные определения теории графов|centerориентированный граф]] будет эйлеровым согласно [[Эйлеровость графов|Пример критерию]].<br><br><br><br><br><br><br><br>

Technique: replace each edge {uПредставим дерево в виде последовательности вершин, v} with two edges (uпосещенных в порядке эйлерова обхода, v) and (v, u).начиная с вершины <tex>a<br/tex>.Resulting graph has an Euler tour[[Файл:Tour1.png|thumb|320px|center]]

==Properties of Euler Tours=Добавление ребра===

The sequence of nodes visited in an Euler tour of a tree is closely connected to the structure of the treeДля добавления ребра <tex>(c, g)</tex>:*Выберем любое вхождение вершины <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>.

[[Файл:Tour1Чтобы быстро находить место, где разрезать эйлеровы обходы деревьев <tex>T1</tex> и <tex>T2</tex>, будем хранить эйлеровы обходы в двоичных деревьях поиска. Ключом вершины для построения дерева поиска будет время посещения этой вершины эйлеровым обходом.Для каждой вершины дерева <tex>(T1, T2)</tex> будем хранить указатель на вершину в дереве поиска, которая соответствует вхождению вершины дерева в эйлеров обход. Тогда за <tex>O(1)</tex> переходим от вершины дерева к вершине дерева поиска, по которой за <tex>O(\log n)</tex> можно будет разделить дерево поиска на две части.png |center|Пример ]]

[[Файл:Tour2Link22.png |thumb|400px|center|Пример Рис.1a Исходный лес <br>Рис.1b Эйлеровы обходы деревьев<br> Рис.1с Двоичные деревья поиска для хранения эйлеровых обходов <br> Рис.1d Результирующий эйлеров обход]]

The subtrees defined by ranges in Euler tours on trees depend on the root[[Файл:Link23.png |thumb|400px|center|Рис.1a Исходное дерево <br>Рис.1b Эйлеров обход исходного дерева<br> Рис.1с Двоичное дерево поиска для хранения эйлерового обхода <br>In some cases, we will need to change the root of the treeРис.1d Эйлеровы обходы получившихся деревьев]]

[[Файл:Tour3===Проверка на связность===Для того, чтобы проверить, лежат ли две вершины в одном дереве, достаточно подняться от вхождения каждой вершины в эйлеров обход (ссылку на которое мы храним) до корня дерева поиска, хранящего этот эйлеров обход.png |center|Пример ]]

Операции объединения и разделения красно-черных деревьев выполняется за <tex>O(\log n)</tex><ref>[[Файлhttp:Proba//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>.

===link(u ,v)Декартово дерево по неявному ключу===

Given two trees T₁ and T₂Также, where u ∈ T₁ and v ∈ T₂можем хранить последовательности вершин эйлерова обхода в [[Декартово_дерево_по_неявному_ключу|декартовом дереве по неявному ключу]]. Глубина декартового дерева, построенного на массиве из <tex>n</tex> вершин, executing linkбудет поддерживаться равной <tex>O(u, v\log n) links the trees together by adding edge {u, v}.<br/tex>Watch what happens to the Euler tours:.

[[Файл:Two treesОперации объединения и разделения также выполняются за <tex>O(\log n)</tex>.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}.* [[Link-Cut Tree]]

==Источники информации=cut(u ,v)=* [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 Лекториум{{---}} Лекция Павла Маврина об эйлеровых обходах]

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: [[ФайлКатегория:Cut.png |center|Пример ]] To cut T into T₁ and T₂ by cutting {u, v}:<br>Let E be an Euler tour for T.<br>Rotate u to the front of E.<br>Split E into E₁, V, E₂, where V is the span between the first and last occurrence of v.<br>T₁ has the Euler tour formed by concatenating E₁ and E₂, deleting the extra u at the join point.<br>T₂ has Euler tour V. [[Файл:Cut1.png |center|Пример ]] ==Реализация Алгоритмы и структуры== Goal: Implement link, cut, and is-connected as efficiently as possible. 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=== [[Файл:Linked lists.png |center|Пример данных]]  Each split or concatenate takes time O(1).<br>The first and last copy of a node can be identified in time O(1).<br>A new copy of a node can be appended to the end of the sequence in time O(1).<br>A redundant copy of a node can be deleted in time O(1).<br>Everything sounds great!<br>Question: How do you test for connectivity? Euler tours give a simple, flexible encoding of tree structures.<br>Using doubly-linked lists, concatenation and splits take time O(1) each, but testing connectivity takes time Θ(n) in the worst-case.<br>Can we do better? ===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 1: Can still store pointers to the first and last occurrence of each tree node. 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/black trees can be split and joined in time O(log n) each. [[ФайлКатегория:Balanced tree1.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-connected queries take time only O(log n) each.  Сравнительная табличка ==Похожие структуры==Про link-cut trees