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