Изменения

Представим дерево в виде последовательности вершин, посещенных в порядке эйлерова обхода, начиная с корнем в вершине вершины <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>\{c, g\} \T1</tex>Выберем любое вхождение вершины и <tex>сT2</tex> , будем хранить эйлеровы обходы в эйлеров обход T1двоичных деревьях поиска. Разрежем эйлеров обход T1 на 2 частиКлючом вершины для построения дерева поиска будет время посещения этой вершины эйлеровым обходом.A1 - часть обхода до выбранного вхождения Для каждой вершины дерева <tex>с(T1, T2)</tex>будем хранить указатель на вершину в дереве поиска, которая соответствует вхождению вершины дерева в эйлеров обход. A2 - часть обхода после выбранного вхождения вершины Тогда за <tex>сO(1)</tex>Аналогичнопереходим от вершины дерева к вершине дерева поиска, выберем любое вхождение вершины по которой за <tex>gO(\log n)</tex> в эйлеров обход T2 и разрежем его можно будет разделить дерево поиска на 2 две части B1 и B2Соберем результирующий эйлеров обход в порядке A1 B2 B1 A2.

Чтобы быстро находить место, где разрезать эйлеровы [[Файл:Link22.png |thumb|400px|center|Рис.1a Исходный лес <br>Рис.1b Эйлеровы обходы T1 и T2, будем хранить эйлеровы обходы в двоичных деревьях деревьев<br> Рис.1с Двоичные деревья поиска. Ключом вершины, для построения дерева поиска, будет время посещения этой вершины эйлеровым обходомхранения эйлеровых обходов <br> Рис.Для каждой вершины дерева (T1, T2) будем хранить указатель на вершину в дереве поиска, которая соответствует вхождению вершины дерева в 1d Результирующий эйлеров обход. Тогда за O(1) переходим от вершины дерева к вершине дерева поиска, по которой за O(log n) можно будет разделить дерево поиска на 2 части. ]]

Для разбиения дерева на два поддерева путем разрезания удаления ребра <tex>\{(g, j\} \)</tex> необходимо:*Переподвесить дерево к вершине Найдем в эйлеровом обходе дерева <tex>T</tex> две пары посещений концов удаляемого ребра <tex>g,j</tex>.*Разделить дерево на части и <tex>E1j, V, E2g</tex>, где которые соответствуют прохождениям по ребру <tex>V(g, j)</tex> отрезок между первым и последним вхождением вершины в дереве <tex>jT</tex>.*Эйлеров Разрежем эйлеров обход первого поддерева образуется соединением дерева по этим парам на три части: <tex>A1, A2, A3</tex>.*Соединив <tex>E1A1</tex> и <tex>E2A3</tex>(без повторяющейся первой вершины), с удалением повторного получим эйлеров обход первого дерева, а <tex>\{g\}A2</tex> дает эйлеров обход второго дерева. Чтобы быстро находить места в месте их соединенияэйлеровом обходе, которые соответствуют прохождению удаляемого ребра в дереве, будем для каждого ребра в дереве хранить ссылку на те места эйлерова обхода, где последовательно посещаем концы удаляемого ребра.*Эйлеров обход второго поддерева образует Так, для ребра <tex>V(g, j)</tex>храним ссылки на узлы дерева поиска, соответствующие парам посещений концов этого ребра.

[[Файл:Cut2Link23.png|thumb|350px400px|center|Рис.1a Исходное дерево <br>Рис.1b Эйлеров обход исходного дерева<br> Рис.1с Двоичное дерево поиска для хранения эйлерового обхода <br> Рис.1d Эйлеровы обходы получившихся деревьев]]

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

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

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

Будем хранить последовательность вершин эйлерова обхода в виде сбалансированного двоичного дерева поиска, например, в виде [[Файл: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]]