635
правок
Изменения
→Balanced Trees
===Balanced Trees===
Claim: It is possible to represent sequences of elements balanced binary trees.
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(u, v) in time O(log n) by seeing if u and v are in the same tree.
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.
