Sign in to watch this lesson
Algorithms - Trees and Range Queries · 4:55
Disjoint Set Union
A disjoint set union stores groups as a forest of parent pointers, where each root names its set. We build it from make_set, find_set and union_sets, watch path compression flatten a tall tree and union by size keep every tree at most log2 n tall, then measure the plain version against both tricks and see why alpha(n) is constant in practice.
You will learn
- Implement make_set, find_set and union_sets on a parent array, with the root as each set's representative
- Explain how path compression and union by size each shorten the trees, and prove that union by size keeps the height at most log2 n
- State the O(alpha(n)) amortized bound for both tricks together and recognise that alpha(n) <= 4 for every practical n
- Avoid the usual bugs: deep recursion on a chain, linking elements instead of roots, and adding sizes to the wrong root