Union by Rank or Size
Union-Find: lesson 3 of 4
Hang the smaller tree under the bigger one and depth barely grows.
Lesson 3 of 4 · 5 min
Union by Rank or Size
Step 1 of 8
Two groups, each two deep. Every root keeps a size: how many elements hang below it.
The Idea
union has a choice: which root goes under which. Choose badly every time and the structure degrades into a chain.
Keep a size per root and always hang the smaller tree under the bigger one. Only the smaller side gets deeper, so depth can only grow when two equal trees meet — which takes doubling to reach.
Real-World Example
Merging two chat communities. Moving the 40-person server into the 4,000-person one means 40 people relearn an address instead of 4,000. The rule is the same one, and it is chosen for the same reason.
The Code
parent, size = list(range(5)), [1] * 5
def find(x):
while parent[x] != x:
parent[x] = parent[parent[x]] # halve the path on the way up
x = parent[x]
return x
def union(a, b):
ra, rb = find(a), find(b)
if ra == rb: return
if size[ra] > size[rb]: ra, rb = rb, ra # smaller root goes underneath
parent[ra] = rb
size[rb] += size[ra]
union(0, 1); union(2, 3); union(1, 3)
print(find(0) == find(2), size[find(0)])Your turn
Put the steps in the right order.
- Add the smaller size into the surviving root's size
- Find the root of each element
- Point the smaller root at the larger root
- Stop if the two roots are already the same
- Compare the two roots' sizes and swap so the smaller one is first
Mini quiz
1 / 3