Изменения

Перейти к: навигация, поиск

Деревья Эйлерова обхода

427 байт добавлено, 01:36, 31 декабря 2016
Операции c эйлеровыми обходами
Чтобы быстро находить места в эйлеровом обходе, которые соответствуют прохождению удаляемого ребра в дереве, будем для каждого ребра в дереве хранить ссылку на те места эйлерова обхода, где последовательно посещаем концы удаляемого ребра.
Так, для ребра (g, j) храним ссылки на узлы дерева поиска, соответствующие парам посещений концов этого ребра.
 
===Проверка на связность===
Для того, чтобы проверить, лежат ли 2 вершины в одном дереве, достаточно подняться от вхождения каждой вершины в эйлеров обход (ссылку на которое мы храним) до корня дерева поиска, хранящего этот элеров обход.
==Реализация структуры==
Анонимный участник

Навигация