3 stages of union find
Investigated this when doing query optimization.
Naive approach O(N^2)
When doing union and merging new sub-trees, set all sub-tree roots to base root.
root(1) = 1-2-3 root(3) = 3-4 union(1,3) -- 3 is the new parent
We have to set all of 1’s children to have 3 as their root.
This takes N time since we union N nodes. N time for each union, since we need to iterate over all nodes, and update their root if they have
1 as root (are
Better approach O(N)
Use indirect union instead.
Rather than linking all of root(1) children to
3, just link the root
This takes O(1) time / union.
Betterer approach O(log2N)