1632
правки
Изменения
м
==Properties of Для решения поставленной задачи будем представлять дерево в виде его [[Эйлеровость графов|эйлерова графа]], а затем будем работать с [[Эйлеровость графов|эйлеровым обходом]] (англ.''Euler Tours==tour tree'') этого графа. Это позволит выполнять указанные запросы за <tex>O(\log n)</tex>.
The sequence of nodes visited in an Euler tour of a tree is closely connected to the structure of the tree.==Представление деревьев в виде эйлерова графа==
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.<br>In some cases, we will need to change the root of the tree. Получившийся [[Файл:Tour3.png |centerОсновные определения теории графов|Пример ориентированный граф]] Algorithm: Split the tour into three parts: S₁, R, and S₂, where R consists of the nodes between the first and last occurrence of the new root r.<br>Delete the first node in S₁.<br>Concatenate R, S₂, S₁, {r}. будет эйлеровым согласно [[Файл:Proba.png Эйлеровость графов|center|Пример критерию]] ===link(u ,v)=== Given two trees T₁ and T₂, where u ∈ T₁ and v ∈ T₂, executing link(u, v) links the trees together by adding edge {u, v}.<br>Watch what happens to the Euler tours: [[Файл: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: [[Файл: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посещенных в порядке эйлерова обхода, начиная с вершины <tex>a</tex>.[[Файл:Tour1.png|thumb|320px|center]]
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?==Операции c эйлеровыми обходами==
Implementing the Structure===Добавление ребра===
The operations we have seen require us to be able to efficiently do the followingДля добавления ребра <tex>(c, g)</tex>:*Выберем любое вхождение вершины <tex>c<br/tex>в эйлеров обход дерева <tex>T1</tex>.Identify the first and last copy of a node in a sequence.*Разрежем эйлеров обход <tex>T1<br/tex>на две части:Split a sequence at those positions*: <tex>A1</tex> {{---}} часть обхода до выбранного вхождения вершины <tex>c</tex>, включая ее.*: <brtex>A2</tex> {{---}} часть обхода после выбранного вхождения вершины <tex>c</tex>, включая ее.Concatenate sequences*Аналогично, выберем любое вхождение вершины <tex>g</tex> в эйлеров обход дерева <tex>T2</tex> и разрежем его на две части <tex>B1</tex> и <tex>B2</tex>.*Соберем результирующий эйлеров обход в порядке <tex>A1, B2, B1<br/tex>Add a new copy of a node to a sequence.(без первой повторяющейся вершины), <brtex>Delete a duplicate copy of a node from a sequence.A2<br/tex>How do we do this efficiently?.
===Linked Lists===[[Файл:Link22.png |thumb|400px|center|Рис.1a Исходный лес <br>Рис.1b Эйлеровы обходы деревьев<br> Рис.1с Двоичные деревья поиска для хранения эйлеровых обходов <br> Рис.1d Результирующий эйлеров обход]]
[[Файл: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).Так, для ребра <brtex>A new copy of a node can be appended to the end of the sequence in time O(1g, j).<br/tex>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[[Файл:Link23.png |thumb|400px|center|Рис.1a Исходное дерево <br>Рис.1b Эйлеров обход исходного дерева<br>Using doubly-linked lists, concatenation and splits take time O(1) each, but testing connectivity takes time Θ(n) in the worst-caseРис.1с Двоичное дерево поиска для хранения эйлерового обхода <br>Can we do better?Рис.1d Эйлеровы обходы получившихся деревьев]]
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.===Сбалансированное дерево поиска===
Observation Операции объединения и разделения красно-черных деревьев выполняется за <tex>O(\log n)</tex><ref>[http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1: Can still store pointers to the first and last occurrence .1.109.4875&rep=rep1&type=pdf Ron Wein {{---}} Efficient Implementation of each tree nodeRed-Black Trees.]</ref>.
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Также, можем хранить последовательности вершин эйлерова обхода в [[Декартово_дерево_по_неявному_ключу|декартовом дереве по неявному ключу]]. Глубина декартового дерева, построенного на массиве из <tex>n</black trees can be split and joined in time tex> вершин, будет поддерживаться равной <tex>O(\log n) each</tex>.
[[Файл:Balanced tree1Операции объединения и разделения также выполняются за <tex>O(\log n)</tex>.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* [[Link-connected queries take time only O(log n) each.Cut Tree]]
Сравнительная табличка==Источники информации==* [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[[Категория: Обходы графов]][[Категория: Эйлеровы графы]]
rollbackEdits.php mass rollback
==Введение=='''Динамические деревья''' (англ.''dynamic tree'') используются в двух областях:......... Нужно поддерживать следующие операции * '''<tex>\mathrm{link(u, w)}</tex>''' {{---}} добавить ребро (u, w) (при условии, что вершины u w принадлежат разным деревьям)* '''<tex>\mathrm{cut(u, w)}</tex>''' {{---}} разрезать ребро (u, w) (при условии, что ребро (u, w) принадлежит дереву),* '''<tex>\mathrm{isConnected(u, w)}</tex>''' {{---}} принадлежат ли вершины u и w одной компоненте Задача о динамической связности. ''' Euler tour tree''' - The data structure we'll develop can perform these operations time O(log n) each. ==Представление деревьев в виде их эйлерова обхода== [[Файл:Euler graph.png |right|Пример ]]В основном, [[Дерево, эквивалентные определения|деревья]] не являются [[Эйлеровость графов|эйлеровыми графами]]. Заменим каждое ребро <tex>\{v, u\} \</tex> дерева на два ребра <tex>(u, v)</tex> и <tex>(v, u)</tex>. Получившийся [[Основные определения теории графов|ориентированный граф]] будет эйлеровым согласно [[Эйлеровость графов|критерию]].
{{Задача
|neat definition = 1Для динамически изменяющегося дерева выполнить следующие запросы:|definition = High* '''<tex>\mathrm{link(u, w)}</tex>''' {{---level idea: Instead of storing the trees in the forest}} добавить ребро <tex>(u, w)</tex> (при условии, что вершины <tex>u</tex> и <tex>w</tex> принадлежат разным деревьям), store their Euler tours.Each edge insertion or deletion translates into a set of manipulations on the Euler tours of the trees in the forest.* '''<brtex>\mathrm{cut(u, w)}</tex>''' {{---}} разрезать ребро <tex>(u, w)</tex> (при условии, что ребро <tex>(u, w)</tex> принадлежит дереву),Checking whether two nodes are connected can be done by checking if they* '''<tex>\mathrm{isConnected(u, w)}</tex>'re in the same Euler tour'' {{---}} определить принадлежат ли вершины <tex>u</tex> и <tex>w</tex> одной компоненте связности.
}}
[[Файл:Tour1Tree.png |center300px|thumb|left|Пример дерева]][[Файл:Euler graph.png|300px|thumb|right|Соответствующий эйлеров граф]]
Для представления [[Файл:Tour2.png Дерево, эквивалентные определения|centerдерева]] в виде [[Эйлеровость графов|Пример эйлерового графа]]заменим каждое ребро <tex>\{u, v\} \</tex> дерева на два ребра <tex>(u, v)</tex> и <tex>(v, u)</tex>.
Чтобы быстро находить место, где разрезать эйлеровы обходы деревьев <tex>T1</tex> и <tex>T2</tex>, будем хранить эйлеровы обходы в двоичных деревьях поиска.
Ключом вершины для построения дерева поиска будет время посещения этой вершины эйлеровым обходом.
Для каждой вершины дерева <tex>(T1, T2)</tex> будем хранить указатель на вершину в дереве поиска, которая соответствует вхождению вершины дерева в эйлеров обход.
Тогда за <tex>O(1)</tex> переходим от вершины дерева к вершине дерева поиска, по которой за <tex>O(\log n)</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> дает эйлеров обход второго дерева.
===Balanced TreesПроверка на связность===Для того, чтобы проверить, лежат ли две вершины в одном дереве, достаточно подняться от вхождения каждой вершины в эйлеров обход (ссылку на которое мы храним) до корня дерева поиска, хранящего этот эйлеров обход.
Будем хранить последовательность вершин эйлерова обхода в виде сбалансированного двоичного дерева поиска, например, в виде [[Файл:Balanced tree.png |centerКрасно-черное дерево|Пример красно-черного дерева]]. При построении дерева ключом вершины будет время посещения этой вершины эйлеровым обходом.
== Примечания ==
<references/>
