===Balanced Trees===
[[Файл:Balanced tree.png |center|Пример ]]
Представим последовательность вершин эйлерова обхода в виде сбалансированного двоичного дерева. Будем использовать красно-черное дерево.
Объединение и разделение красно-черных деревьев выполняется за O(log n).
These are not binary search treesДля каждой вершины храним указатели на её первое и последнее вхождение в последовательность. We're using the shape of a red/black tree to ensure balance. [[Файл:Balanced tree.png |center|Пример ]] Observation 1: Can still store pointers to the first and last occurrence of each tree node. Observation 2: If nodes store pointers to their parentsЗначит, can answer is-connectedимеем доступ к ним за <tex>О(u, v1) in time O(log n) by seeing if u and v are in the same tree</tex>.
Observation 3: Red/black trees can be split and joined in time Запрос о принадлежности вершин к одной компоненте связности выполняется за O(log n) eachпроверкой лежат ли эти вершины в одном дереве.
[[Файл:Balanced tree1.png |center|Пример ]]
The data structure:<br>
Represent each tree as an Euler tour.<br>
Store those sequences as balanced binary trees.<br>
Each node in the original forest stores a pointer to its first and last occurrence.<br>
Each node in the balanced trees stores a pointer to its parent.<br>
link, cut, and is-connected queries take time only O(log n) each.
Сравнительная табличка
==Похожие структуры==
Про link-cut trees
