Изменения

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

*Выберем любое вхождение вершины <tex>c </tex> в эйлеров обход дерева <tex>T1</tex>.

*: <tex>A1 </tex> {{- --}} часть обхода до выбранного вхождения вершины <tex>c</tex>, включая ее.*: <tex>A2 </tex> {{-- -}} часть обхода после выбранного вхождения вершины <tex>c</tex>, включая ее.*Аналогично, выберем любое вхождение вершины <tex>g </tex> в эйлеров обход дерева <tex>T2 </tex> и разрежем его на 2 две части <tex>B1 </tex> и <tex>B2</tex>.*Соберем результирующий эйлеров обход в порядке <tex>A1 , B2 , B1</tex> (без первой повторяющейся вершины) , <tex>A2</tex>.

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

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

Для удаления ребра <tex>\{(g, j\} \)</tex>:*Найдем в эйлеровом обходе дерева <tex>T </tex> две пары посещений концов удаляемого ребра gj <tex>g,j</tex> и jg<tex>j,g</tex>, которые соответствуют прохождениям по ребру <tex>(g, j) </tex> в дереве <tex>T</tex>.*Разрежем эйлеров обход дерева по этим парам на 3 три части: <tex>A1, A2, A3</tex>.*В результате получатся 2 дерева с эйлеровыми обходами Соединив <tex>A1 </tex> и <tex>A3</tex> (без повторяющейся первой вершины) и , получим эйлеров обход первого дерева, а <tex>A2 соответственно</tex> дает эйлеров обход второго дерева.

Так, для ребра <tex>(g, j) </tex> храним ссылки на узлы дерева поиска, соответствующие парам посещений концов этого ребра.

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

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

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

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

Объединение Операции объединения и разделение разделения красно-черных деревьев выполняется за <tex>O(\log n)</tex><ref>[http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.109.4875&rep=rep1&type=pdf Ron Wein {{---}} Efficient Implementation of Red-Black Trees.]</ref>.

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

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