How It Works: Tracing find and union

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.

Initial state

Every element starts in its own set, so each one is its own parent. All sizes are 1.

The problem with unoptimized merging

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 3

Union by size

The 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.

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.

Path compression

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 root

Compression 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

Before and after compression

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.

Summary

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.