Visual walkthrough — Disjoint Set Union (Union-Find) — path compression + union by rank → α(n)

We only assume you can read a picture of dots-and-arrows. Everything else — the word "root", the array parent[], the number "rank", even "$\log$" — is built here.

Step 1 — A set is a picture of arrows pointing home

WHAT. Draw every element as a dot. Draw one arrow out of each dot: "who is my boss?" Follow arrows and you always arrive at one special dot whose arrow loops back to itself. That self-pointing dot is the root (also called the representative — the one name that stands for the whole group).

WHY this picture and not a list? Because merging two groups must be cheap. If a group were a plain list of names, merging two lists of size $n$ costs $O(n)$ copying (recall $n$ is the total dot count). With arrows, merging is a single arrow flip — point one root at the other. That is the entire reason we choose a tree-of-arrows over a list.

PICTURE. Look at figure s01. Three separate groups. Inside each, follow any dot's arrow upward and you reach its root. The one array we store is parent[]:

$\underset{\text{the dot }x\text{ points at}}{\underbrace{\text{parent}[x]}}=x⟺\underset{\text{arrow loops to itself}}{\underbrace{x\text{ is a root}}}$

Read it term by term: parent[x] is the dot at the tip of x's arrow; when that tip is x again, the arrow is a self-loop, so x is a root. That single equality is our entire test for "am I the leader?"

Step 2 — find(x): walk the arrows until one loops home

WHAT. To answer "who is x's leader?", start at x and keep hopping along arrows until you hit a dot whose arrow loops to itself.

def find(x):
    while parent[x] != x:   # not a root yet: arrow points elsewhere
        x = parent[x]       # hop one arrow up
    return x                # loop-to-self reached: this is the root

WHY. parent[x] != x is literally "my arrow does not loop back to me" — so I am not yet the leader, keep climbing. The moment the loop-to-self is true, we stop. Nothing clever yet; this is the honest, slow version.

PICTURE. Figure s02 traces find on a tall chain. The red path is the sequence of hops. Count the hops: in a chain of height $h$, find costs $h$ arrow-follows. If an adversary built a straight chain of all $n$ dots, one find costs $n$ hops. This is the disaster we must prevent — and the next steps do exactly that.

Step 3 — Union by rank: the short tree bows to the tall one

WHAT. To merge two groups we flip one root's arrow onto the other root. But which onto which? Give every root a number rank[x] — an upper bound on the tree's height (how many arrow-hops from the deepest dot to the root). All dots start at rank = 0. Rule: hang the smaller-rank root under the larger-rank root.

def union(x, y):
    rx, ry = find(x), find(y)
    if rx == ry: return             # already one group — stop
    if rank[rx] < rank[ry]:
        rx, ry = ry, rx             # make rx the taller (or equal) root
    parent[ry] = rx                 # flip smaller root's arrow onto bigger
    if rank[rx] == rank[ry]:
        rank[rx] += 1               # a tie: new height is one taller

WHY. Look at what "hang short under tall" does to height. If the tall tree has height $H$ and the short one height $h<H$, gluing the short root just under the tall root makes total height

$\text{new height}=\max (H,h+1)=H(\text{because }h+1\le H).$

Term by term: $H$ is the taller tree's height; $h+1$ is the shorter tree's dots pushed one level deeper by the new arrow; the $\max$ picks the winner — and the tall one still wins. The tree got no taller. Only when the two heights are equal ($H=h$) does $h+1$ exceed $H$, so height rises by exactly $1$ — and that is the one case where we do rank[rx] += 1.

PICTURE. Figure s03 shows both cases side by side: the unequal merge (green — height unchanged, no rank bump) and the tie merge (yellow — height grows by one, rank bumps).

Step 4 — Why rank stays tiny: each rank hides $2^r$ dots

WHAT. We now prove the payoff of Step 3: a root of rank $r$ owns at least $2^r$ dots.

WHY this matters. If rank-$r$ needs $\ge 2^r$ dots, then rank can never exceed ${\log }_{2}n$ (you simply run out of dots — remember $n$ is all the dots there are). Since height $\le$ rank, every find costs at most ${\log }_{2}n$ hops — the tall-chain disaster of Step 2 is impossible.

The argument, drawn. A rank climbs from $r$ to $r+1$ only in the tie case (Step 3). Before that tie, each of the two merging roots was rank $r$, so — by the same claim one level down — each already owned $\ge 2^r$ dots. Glue them:

$\underset{\text{tree A}}{\underbrace{2^r}}+\underset{\text{tree B}}{\underbrace{2^r}}=\underset{\text{merged, now rank }r+1}{\underbrace{2^{r+1}}}$

Base case: a lone dot has rank $0$ and $2^0=1$ dot. ✔ The induction rolls upward forever.

$\text{size}\ge 2^r⟹2^r\le n⟹r\le {\log }_{2}n.$

Read the chain: a rank-$r$ tree needs $\ge 2^r$ dots; those dots all fit inside the $n$ total, so $2^r\le n$; take ${\log }_2$ of both sides and $r$ can be at most ${\log }_{2}n$.

PICTURE. Figure s04 stacks the doubling: rank 0 = 1 dot, rank 1 = 2, rank 2 = 4, rank 3 = 8 — a perfect binary pyramid. To reach rank 30 you'd need over a billion dots.

Step 5 — Path compression: flatten the trail while you read it

WHAT. Union by rank stops trees getting tall. Path compression makes them get short again for free, every time you look. During a find, after reaching the root, repoint every dot you passed straight at the root.

def find(x):
    if parent[x] == x:      # already a root: nothing above me
        return x
    root = find(parent[x])  # recurse up: root is the leader
    parent[x] = root        # adopt the leader directly — flatten
    return root

Or the loop version with path halving (each node adopts its grandparent):

def find(x):
    while parent[x] != x:
        parent[x] = parent[parent[x]]  # skip one level: point at grandparent
        x = parent[x]
    return x

WHY. The first find on a deep dot has to pay for the climb — but why waste that work? On the way back we already hold the root's name, so writing it into every visited dot costs nothing extra and makes every future find on those dots a single hop. The line parent[x] = parent[parent[x]] reads: "let x's arrow skip its parent and point to its grandparent," halving the remaining distance on the spot.

PICTURE. Figure s05: a 4-deep chain before find(bottom) on the left, and after on the right — every dot on the red path now points directly at the root, a flat starburst.

Step 6 — The two together: rank stops climbing, so cost collapses to α(n)

WHAT. Let $m$ = ==the total number of find/union calls you make== over the whole run (the length of your sequence of operations). Union by rank caps rank at ${\log }_{2}n$ (Step 4). Path compression keeps deleting the height that made ranks meaningful (Step 5). Spreading the rare expensive climbs across the many cheap ones — an amortized argument — gives, over those $m$ operations:

$\underset{\text{all }m\text{ ops summed}}{\underbrace{\text{total cost}}}=O(\underset{\text{how many ops}}{\underbrace{m}}\cdot \underset{\text{cost credited to each}}{\underbrace{\alpha (n)}})⟹\underset{\text{per operation, amortized}}{\underbrace{\alpha (n)}}.$

Here $\alpha (n)$ is the inverse of the monstrously fast Ackermann function: it grows so slowly that $\alpha (n)\le 4$ for any $n$ you could ever store.

WHY α and not merely $\log n$ — the potential-function picture. Here is the intuition without the full proof. Give every non-root dot a "level" based on how its rank compares to its parent's rank. Ranks along any path are strictly increasing (a child always has smaller rank than its parent), so as you climb, ranks jump upward fast. Group the possible ranks into a handful of bands where each band is exponentially wider than the last — band 0 is $\{0\}$, then $\{1\}$, then $\{2,3,4\}$, then $\{5,\dots ,2^{16}\}$, and so on, each boundary an Ackermann-style leap.

The key bookkeeping trick: every time path compression re-points a dot, that dot's parent jumps to a strictly higher rank. A dot can only be "re-pointed cheaply" so many times within its own band before its parent's rank crosses into the next band — and the number of bands needed to cover all ranks up to ${\log }_{2}n$ is exactly $\alpha (n)$. Figure s06 draws these widening bands: because bands grow at Ackermann speed, it takes only $\alpha (n)\le 4$ of them to swallow every rank, so each dot pays only ~$\alpha (n)$ across its whole lifetime. That is why the rate is inverse-Ackermann and not the plain $\log n$ you'd get from rank alone.

Step 7 — The degenerate cases (never skipped)

WHAT & WHY — walk each corner so no scenario surprises you:

• union(x, x) / union of two already-joined dots. find(x) == find(y), so the early return fires. Why it must be there: without it you'd flip a root's arrow onto itself or wrongly bump a rank — self-corruption. (See the parent note's mistake box.)
• A lone dot. parent[x] = x, rank[x] = 0. find(x) returns instantly (loop-to-self on hop zero). The base case of Step 4.
• All-equal-rank merges (worst case for height). Every union is a tie, so rank climbs as fast as it ever can — yet Step 4 proves that even this caps at ${\log }_{2}n$, and Step 5 flattens it back down on the first read.
• A giant flat star. After heavy compression a rank-$r$ root may point directly to thousands of dots while its rank value is still, say, $20$. That stale-but-safe gap is not a bug — it is the α(n) speed.

PICTURE. Figure s07 shows the self-union no-op (arrow stays put) and a lone dot beside a flattened star, so you see both extremes at once.

The one-picture summary

Figure s08 is the whole derivation on one canvas: loose dots → arrows to roots (Step 1) → find climbs (Step 2) → union-by-rank keeps it short, $2^r$ pyramid caps rank at $\log n$ (Steps 3–4) → compression flattens on read (Step 5) → both together give the flat α(n) line (Step 6).

Recall