635
правок
Изменения
→Balanced Trees
Представим последовательность вершин эйлерова обхода в виде сбалансированного двоичного дерева. Будем использовать [[Красно-черное дерево|красно-черное дерево]].
Объединение и разделение красно-черных деревьев выполняется за <tex>O(\log n)</tex>.
Для каждой вершины храним указатели на её первое и последнее вхождение в последовательность. Значит, имеем доступ к ним за <tex>О(1)</tex>.
Запрос о принадлежности вершин к одной компоненте связности выполняется за <tex>O(\log n) </tex> проверкой лежат ли эти вершины в одном дереве.
[[Файл:Balanced tree1.png |center|Пример ]]
