Изменения

Представим дерево в виде последовательности вершин, посещенных в порядке эйлерова обхода, начиная с корнем в вершине вершины <tex>a</tex> в виде последовательности вершин, посещеннных в порядке эйлерова обхода.

[[ФайлДля добавления ребра <tex>(c, g)</tex>:Link11*Выберем любое вхождение вершины <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 |thumb|400px|center]]

Для связывания Чтобы быстро находить место, где разрезать эйлеровы обходы деревьев <tex>T1 </tex> и <tex>T2</tex>, где будем хранить эйлеровы обходы в двоичных деревьях поиска. Ключом вершины для построения дерева поиска будет время посещения этой вершины эйлеровым обходом.Для каждой вершины дерева <tex>c\in (T1\ </tex>, а <tex>g\in T2\</tex> добавлением ребра <tex>\{c, g\} \</tex> необходимо:*Переподвесить дерево <tex>T1</tex> к вершине <tex>c)</tex>будем хранить указатель на вершину в дереве поиска, если корнем которая соответствует вхождению вершины дерева была другая вершинав эйлеров обход.*Переподвесить дерево Тогда за <tex>T2O(1)</tex> переходим от вершины дерева к вершине <tex>g</tex>дерева поиска, если корнем дерева была другая вершина.*Соединить получившиеся эйлеровы обходы.*Добавить по которой за <tex>O(\{c\}log n)</tex> в конец последовательностиможно будет разделить дерево поиска на две части.

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

[[ФайлДля удаления ребра <tex>(g, j)</tex>:Link3*Найдем в эйлеровом обходе дерева <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> дает эйлеров обход второго дерева.png|center]]

===Разрезание Чтобы быстро находить места в эйлеровом обходе, которые соответствуют прохождению удаляемого ребра===в дереве, будем для каждого ребра в дереве хранить ссылку на те места эйлерова обхода, где последовательно посещаем концы удаляемого ребра.[[Файл:Cut1Так, для ребра <tex>(g, j)</tex> храним ссылки на узлы дерева поиска, соответствующие парам посещений концов этого ребра.png|thumb|350px|center]]

Для разбиения дерева на два поддерева путем разрезания ребра <tex>\{g, j\} \</tex> необходимо[[Файл:*Переподвесить дерево к вершине <tex>g</tex>Link23.png |thumb|400px|center|Рис.*Разделить 1a Исходное дерево на части <tex>E1, V, E2</tex>, где <tex>V</tex> отрезок между первым и последним вхождением вершины <tex>j</texbr>Рис.*1b Эйлеров обход первого поддерева образуется соединением <tex>E1</tex> и <tex>E2</tex>, с удалением повторного исходного дерева<texbr>\{g\}</tex> в месте их соединенияРис.*Эйлеров обход второго поддерева образует <tex>V1с Двоичное дерево поиска для хранения эйлерового обхода </texbr>Рис. 1d Эйлеровы обходы получившихся деревьев]]

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

==Реализация структуры=Сбалансированное дерево поиска===

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

Операции объединения и разделения красно-черных деревьев выполняется за <tex>O(\log n)</tex><ref>[[Файлhttp:Balanced tree//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><ref>[http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.109.4875&rep=rep1&type=pdf]</ref>. Декартово дерево по неявному ключу===

Для каждой вершины храним указатели на её первое и последнее вхождение Также, можем хранить последовательности вершин эйлерова обхода в последовательность[[Декартово_дерево_по_неявному_ключу|декартовом дереве по неявному ключу]]. ЗначитГлубина декартового дерева, построенного на массиве из <tex>n</tex> вершин, имеем доступ к ним за будет поддерживаться равной <tex>O(1\log n)</tex>.

Запрос о принадлежности вершин к одной компоненте связности выполняется Операции объединения и разделения также выполняются за <tex>O(\log n)</tex> проверкой лежат ли эти вершины в одном дереве. [[Файл:Balanced tree1.png |center]]