Released · improving
Union-find guide · 2/6
This chapter follows a small example with eight elements (0 to 7) and shows how the parent array changes. First we see how trees degrade without optimizations, then how union by size and path compression fix the problem.
Every element starts in its own set, so each one is its own parent. All sizes are 1.
| Element | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
| parent | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| size | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
Suppose union always hangs the second root under the first. Calling union(1, 0), union(2, 1) and union(3, 2) puts 0 under 1, 1 under 2 and 2 under 3, producing a chain 0 → 1 → 2 → 3. Now find(0) has to climb three links to reach the root 3. With n elements, a single find can cost O(n) in the worst case.
parent = list(range(8))
def find(x):
steps = 0
while parent[x] != x:
x = parent[x]
steps += 1
return x, steps
def naive_union(a, b):
ra, _ = find(a)
rb, _ = find(b)
if ra != rb:
parent[rb] = ra
for i in range(1, 4):
naive_union(i, i - 1) # 0 → 1 → 2 → 3
print(find(0)) # (3, 3): three steps to root 3The fix is to hang the smaller tree under the larger one. Then whenever an element's depth grows by one, the set it belongs to at least doubles in size. A set can never exceed n elements, so no depth can exceed log2 n. Union by rank, which compares an upper bound on height instead of the size, gives the same guarantee.
Let us run the following sequence on the same eight elements, merging by size. Each union first calls find on both arguments to get their roots.
| Step | Operation | Roots compared | Result |
|---|---|---|---|
| 1 | union(0, 1) | size 1 vs 1, ties keep the first root | parent[1] = 0, size[0] = 2 |
| 2 | union(2, 3) | size 1 vs 1 | parent[3] = 2, size[2] = 2 |
| 3 | union(1, 3) | root 0 (size 2) vs root 2 (size 2) | parent[2] = 0, size[0] = 4 |
| 4 | union(4, 5) | size 1 vs 1 | parent[5] = 4, size[4] = 2 |
| 5 | union(6, 4) | root 6 (size 1) vs root 4 (size 2) | parent[6] = 4, size[4] = 3 |
| 6 | union(7, 1) | root 7 (size 1) vs root 0 (size 4) | parent[7] = 0, size[0] = 5 |
After step 6 there are two sets, {0, 1, 2, 3, 7} and {4, 5, 6}. The path from element 3 is 3 → 2 → 0, length 2, well within the maximum depth of 3 that eight elements allow.
Calling find(3) walks 3 → 2 → 0 and discovers the root 0. Path compression then points every node on that path directly at the root. The next find(3) needs only one hop.
def find(x):
root = x
while parent[root] != root: # pass 1: locate the root
root = parent[root]
while parent[x] != root: # pass 2: point visited nodes at the root
parent[x], x = root, parent[x]
return rootCompression happens automatically inside find, so callers never have to think about it. The more often the same elements are queried, the shorter their paths become and the bigger the payoff.
A popular one-pass variant is path halving: while walking up, link each node to its grandparent. The code is shorter and the performance guarantee is the same.
def find_halving(x):
while parent[x] != x:
parent[x] = parent[parent[x]] # skip to the grandparent
x = parent[x]
return x| Element | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
| parent before find(3) | 0 | 0 | 0 | 2 | 4 | 4 | 4 | 0 |
| parent after find(3) | 0 | 0 | 0 | 0 | 4 | 4 | 4 | 0 |
parent[3] changed from 2 to 0. Compression only flattens the shape of a tree; it never changes which set an element belongs to. Sizes only matter at roots, so they need no update during compression.
Without optimizations, union-find trees can degrade into long chains. Union by size or rank, which hangs the smaller tree under the larger, bounds tree height by log n, and path compression or path halving flattens trees on every find. The two techniques are independent and work best together.
0 comments
Sign in · Sign in to leave a comment.
Be the first to comment.