Disjoint Set Union (Union-Find) — path compression + union by rank → α(n): Question bank

Warm-up picture 1 — a small DSU run you can trace by eye

Before the traps, pin down what the words mean by watching a tiny run. Below we do five unions on nodes {0..5}, drawing the forest after each. An arrow points from a child to its parent; a node with a self-loop (no arrow up) is a root. The little number beside a root is its rank.

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

Read the panels left-to-right. Notice the rule in action: when two roots of equal rank merge (panels 1, 2, 3) the survivor's rank ticks up by 1; when a lower-rank root joins a taller one (panel 5) nothing about rank changes — the short tree simply tucked inside the tall one's existing height. That single observation is the whole of "union by rank."

Warm-up picture 2 — what path compression does to a find

Now find(5) on the tree we just built. It climbs 5 → 4 → 0, discovers root 0, then re-points every node it passed straight at the root. The left panel is the tall "before", the right is the flattened "after".

The dashed orange arrows on the right are the new short-cuts. The next find(5) or find(4) is now a single hop. Crucially, rank[0] stays 2 even though the true height dropped to 1 — this is exactly why rank is only an upper bound, a fact several traps below hinge on.

Warm-up picture 3 — WHY a rank- $r$ tree owns at least $2^{r}$ nodes

Many True/False items lean on the claim "rank $r \Rightarrow\geq 2^{r}$ nodes $\Rightarrow r \leq lo g_{2} n$ ." Here is the whole inductive reason in one figure: a rank only rises from $r$ to $r + 1$ when two rank- $r$ roots merge, so the new tree's size is the sum of two things each already $\geq 2^{r}$ .

Warm-up picture 4 — where α(n) comes from (schematic, not the full proof)

You do not need Tarjan's full potential-function proof, but you should see its shape so the α(n) traps make sense. First, two symbols we will use: let $n$ be the number of elements in the DSU and let $m$ be the number of operations (find/union calls) in the whole sequence we run. The idea: ranks partition into blocks by the Ackermann hierarchy (block boundaries at $0, 1, 2, 4, 16, 65536, \dots$ — each the previous tower of twos). A find climbs the tree; each step either crosses into a new block (few of these — at most $α (n)$ , the number of blocks) or stays within a block, in which case path compression charges that step to the node itself so it can't be charged twice. Total work over all $m$ operations $= O (m α (n))$ , i.e. $O (α (n))$ amortized per operation.

True or false — justify

True or false: parent[x] == x is the only reliable way to test whether x is a root.

True — the root is defined as the node pointing to itself, so this self-loop is the universal end-of-climb signal; there is no separate "is-root" flag.

True or false: after path compression, the stored rank of a root equals the tree's true height.

False — as picture 2 shows, find(5) flattened the tree but rank[0] stayed 2 while the real height fell to 1; rank is a (possibly loose) upper bound, and that staleness is intentional.

True or false: union by rank guarantees every tree has height at most

lo g_{2} n

even without path compression.

True — by the doubling invariant of picture 3, a rank-

r

root owns

\geq 2^{r}

nodes, so

2^{r} \leq n

forces

r \leq lo g_{2} n

, capping height all on its own.

True or false: path compression alone (no union by rank or by size) still gives

O (α (n))

amortized.

False — with no merge heuristic, path compression by itself gives only

O (lo g n)

amortized per operation; you need both compression and union-by-rank/size together to reach

O (α (n))

True or false: union by size and union by rank produce identical trees on the same input.

False — they use different tie/merge decisions (node count vs height bound), so shapes can differ; but both hit the same

O (α (n))

bound with compression.

True or false: rank[x] is meaningful for a non-root node.

False — only a root's rank is consulted (during union); a non-root's rank is stale leftover data and must never be read.

True or false: union(x, y) where x and y are already in the same set is a harmless no-op if you forget the early return.

False — without if rx == ry: return you may do parent[rx] = rx (harmless) or bump a rank on a self-merge (corrupting the height bound), so the guard is mandatory.

True or false: the inverse Ackermann

α (n)

is a true constant.

False — it grows, just unfathomably slowly; as picture 4 hints, it counts hierarchy blocks whose boundaries are towers of twos, so it is

\leq 4

for every storable

n

— we treat it as constant while knowing it technically isn't. See Ackermann Function.

True or false: DSU can tell you how many connected components a graph has after processing all edges.

True — count the roots (nodes with parent[x] == x); each root is exactly one component, which is why DSU underlies Connected Components.

True or false: DSU can efficiently split a set back into two.

False — DSU supports only union and find; it has no undo/split, because compression destroys the history of who was merged when.

Spot the error

Error hunt: def find(x): return x if parent[x]==x else find(parent[x]) — what's missing?

It finds the root but never writes back — parent[x] is never reassigned, so there's no compression (contrast picture 2's short-cuts) and the α(n) guarantee is lost; it must be parent[x] = find(parent[x]).

Error hunt: in union, someone writes parent[rx] = ry right after ensuring rank[rx] >= rank[ry].

Backwards — after the swap rx is the taller root, so the shorter ry must hang under rx (parent[ry] = rx); this line hangs the tall tree under the short one, wrecking the height bound.

Error hunt: if rank[rx] == rank[ry]: rank[ry] += 1 after parent[ry] = rx.

Wrong root bumped — ry is no longer a root, so raising its rank does nothing useful; the surviving root rx is the one whose rank must increment on a tie.

Error hunt: a student updates rank[root] down to the true height after each find "to keep it accurate."

Needless and analysis-breaking — recomputing height is expensive, and the amortized proof assumes rank stays a stale upper bound; leave it alone.

Error hunt: union(x, y) is called with raw x, y and immediately does parent[y] = x without any find.

It links two arbitrary nodes, not their roots, so it may attach a root under a non-root and shatter the tree structure; you must find both endpoints first.

Error hunt: someone initializes rank = [1]*n instead of [0]*n.

The

\geq 2^{r}

node-count invariant assumes rank-0 singletons; starting at 1 doesn't break correctness but silently loosens the bound and makes every tie bump land one level too high — start ranks at 0.

Why questions

Why does parent[x] = parent[parent[x]] (path halving) count as compression without full recursion?

Each visited node jumps to its grandparent, roughly halving its distance to the root every pass, so paths shorten iteratively without the stack cost of recursion.

Why does hanging the shorter tree under the taller one keep the combined height equal to the taller height?

The short tree's deepest node sits one level below the tall root's top, still within the tall tree's existing depth — so the max depth is unchanged unless the two heights were equal (see picture 1, panel 5).

Why does the height grow only when two ranks are equal?

If ranks differ, the shorter tree tucks entirely inside the taller one's height budget; only equal heights force the loser's leaves one level past the winner's old bottom, adding exactly 1.

Why is rank an upper bound rather than exact height even before any compression?

It's exact until the first compression, but the algorithm is written to only rely on it as a comparison key for merges, so treating it as an upper bound is the safe, general contract.

Why can we get away with never recomputing rank after compression?

Rank is used solely to decide which root wins a merge; an over-estimate only makes merges slightly more conservative, never incorrect, and Tarjan's analysis is built around exactly this stale rank.

Why do union by rank and path compression together beat either one alone?

Union by rank keeps ranks small (

\leq lo g n

); compression keeps flattening so real depth lags far behind rank — the interplay is what the block-charging argument of picture 4 exploits to reach

α (n)

Why does Kruskal use DSU instead of a plain visited-array?

Kruskal must test whether an edge's two endpoints are already connected (would form a cycle) across a growing forest — exactly same(x,y), which DSU answers in near-constant time. See Graph Cycle Detection.

Why is

α (n)

(inverse Ackermann) the right function to describe the cost, and not

lo g n

lo g^{*} n

The amortized accounting matches the Ackermann-hierarchy blocks a rank can climb through (picture 4);

α

counts those blocks and is provably below even

lo g^{*} n

Edge cases

Edge case: find(x) on a fresh singleton set — what happens?

The loop condition parent[x] != x is immediately false, so it returns x in zero climbs; a lone node is its own root.

Edge case: union(x, x) — same element twice.

find returns the same root for both, rx == ry, and the early return fires — a clean no-op, no rank change, no corruption.

Edge case: merging two singletons (both rank 0).

Ranks tie, so one hangs under the other and the survivor's rank becomes 1 — the smallest possible height increase (picture 1, panel 1).

Edge case: repeatedly union-ing every pair in one already-connected component.

Every call after the first hits rx == ry and returns instantly, so redundant unions cost only two finds and do nothing structural.

Edge case: DSU over n nodes with zero unions performed.

There are exactly n roots and n components — every node is its own singleton set, the identity state.

Edge case: does the order of union calls change the final grouping of elements?

No — the partition into sets depends only on which pairs were unioned, not the order; only the internal tree shape (and thus rank values) can differ. This is why DSU cleanly models Trees and Forests as an evolving forest.

Recall One-line self-test

If someone hands you stale rank and a heavily compressed tree, can you still union correctly? Yes ::: rank is only a comparison key for choosing the surviving root; correctness never needs it to equal true height.