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.
For example:
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 1
‘s children’).
Better approach O(N)
Use indirect union instead.
Rather than linking all of root(1) children to 3
, just link the root 1
->3
.
This takes O(1) time / union.
Betterer approach O(log2N)
Source: https://www.hackerearth.com/practice/notes/disjoint-set-union-union-find/