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