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