Изменения

==ВведениеЗадача о динамической связности=='''Динамические деревья''' (англ.''dynamic tree'') используются в двух областях:.........{{Задача Нужно поддерживать |definition = Для динамически изменяющегося дерева выполнить следующие операции запросы:* '''<tex>\mathrm{link(u, w)}</tex>''' {{---}} добавить ребро <tex>(u, w) </tex> (при условии, что вершины <tex>u </tex> и <tex>w </tex> принадлежат разным деревьям),* '''<tex>\mathrm{cut(u, w)}</tex>''' {{---}} разрезать ребро <tex>(u, w) </tex> (при условии, что ребро <tex>(u, w) </tex> принадлежит дереву),* '''<tex>\mathrm{isConnected(u, w)}</tex>''' {{---}} определить принадлежат ли вершины <tex>u </tex> и <tex>w </tex> одной компоненте связности.}}

'Для решения поставленной задачи будем представлять дерево в виде его [[Эйлеровость графов|эйлерова графа]], а затем будем работать с [[Эйлеровость графов|эйлеровым обходом]] (англ.'' Euler tour tree''' - The data structure we'll develop can perform these operations time ) этого графа. Это позволит выполнять указанные запросы за <tex>O(\log n) each</tex>.

{{Задача|definition = High-level idea: Instead of storing the trees in the forest, 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.<br>Checking whether two nodes are connected can be done by checking if they're in the same Euler tour.}} ==Свойства эйлерова обхода== Представим дерево в виде последовательности вершин, посещеннных посещенных в порядке эйлерова обхода , начиная с корнем в вершине вершины <tex>a</tex>.

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?.

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 Эйлеровы обходы получившихся деревьев]]

===Balanced TreesПроверка на связность===Для того, чтобы проверить, лежат ли две вершины в одном дереве, достаточно подняться от вхождения каждой вершины в эйлеров обход (ссылку на которое мы храним) до корня дерева поиска, хранящего этот эйлеров обход.

Будем хранить последовательность вершин эйлерова обхода в виде сбалансированного двоичного дерева поиска, например, в виде [[Файл:Balanced tree.png |centerКрасно-черное дерево|Пример красно-черного дерева]]. При построении дерева ключом вершины будет время посещения этой вершины эйлеровым обходом.

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 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]]

==Похожие [[Категория: Алгоритмы и структуры==данных]]Про link-cut trees[[Категория: Обходы графов]][[Категория: Эйлеровы графы]]