1. One-Liner
Union by rank always attaches the smaller-height tree under the taller root so the forest stays balanced-ish.
2. The Problem It Solves
Naive union can create linear chains; rank caps approximate height, making find cheaper in practice before path compression.
3. The Core Idea
Maintain rank (upper bound on height). On union, if ranks differ, hang the lower root under the higher; if equal, pick a parent and increment that rank.
4. How It Works (Step-by-Step)
| Step | Action |
|---|---|
| 1 | rank[i]=0 initially |
| 2 | find(x) as basic (iterative) |
| 3 | For union: compare rank[ra], rank[rb] |
| 4 | Attach smaller rank under larger; if tie, increment winner's rank |
5. Dry Run Example
Both rank 0: union(0,1) → rank of root becomes 1. Another union with rank-0 node attaches under taller root without increasing height unnecessarily.
6. Key Properties
| Property | Detail |
|---|---|
| Rank | Height upper bound, not exact depth with path comp |
| Tie-break | Either side; consistent rule matters |
| With path comp | Rank may become outdated but still safe |
7. Where It Is Used
| Domain / System | Use |
|---|---|
| Kruskal MST | Standard DSU |
| Percolation | Cluster merging |
| Compilers | Union-find equivalence classes |
8. Interview Tips
Explain why rank helps; contrast with only path compression. Know union by size is similar (count nodes).
9. Comparison with Other Algorithms
| Technique | Notes |
|---|---|
| Naive union | O(n) skew |
| Path compression alone | Great with rank |
| Link-cut trees | More general dynamic trees |
10. Complexity
| -- | -- |
|---|---|
| Time | O(α(n)) amortized per op with path compression + rank |
| Space | O(n) parent + rank |
Implementation Example (PYTHON)
class UnionFind:
def __init__(self, n):
self.p = list(range(n))
self.r = [0] * n
def find(self, x):
while self.p[x] != x:
x = self.p[x]
return x
def union(self, a, b):
ra, rb = self.find(a), self.find(b)
if ra == rb:
return False
if self.r[ra] < self.r[rb]:
ra, rb = rb, ra
self.p[rb] = ra
if self.r[ra] == self.r[rb]:
self.r[ra] += 1
return True