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