Union by Rank and Path Compression: Near-alpha(n) Amortized

What This Concept Is

Union by size attaches the smaller component root below the larger. Union by rank instead maintains a historical height bound: increase rank only when linking equal-rank roots. Path compression rewrites a traversed find path to its root. After compression, rank is not current height and nonroot size is not a live subtree-size field. The reference uses size and iterative full compression.

Why It Matters Here

It is useful to prove the simpler doubling argument before quoting the deeper inverse-Ackermann theorem. This prevents "effectively constant" from erasing sequence length, initialization or worst-operation latency.

Concrete Examples

Without compression, union by size gives depth at most floor(log2 n). Each time a vertex gains an ancestor through a merge, its component size at least doubles. Rank-based linking has a related invariant: a rank-r root represents at least 2^r elements. These arguments prove a logarithmic depth bound; they do not derive the inverse-Ackermann result.

For n singleton initialization and q later find/union operations, a convenient bound with both heuristics is O(n+q*alpha(n)) total under the standard model (handle n=0 separately). The inverse-Ackermann bound is a theorem about aggregate work; this module assigns a source proof outline rather than pretending a small trace proves it. Exact small numeric values depend on the function convention.

Build pairs 0-1,2-3,4-5,6-7, then merge the first two pairs and last two, then merge the resulting size-4 sets. A deepest find traverses multiple parents; full compression makes that path point directly to its root. Later finds can be cheaper, while all equivalence answers remain unchanged.

Halving and splitting update different pointers during traversal. They require their own precise loop description. Do not claim they universally halve measured pointer cost; the asymptotic guarantee and constant-factor performance are separate.

Common Confusion / Misconceptions

The alpha bound is not a per-call worst-case constant. Initializing n elements costs Θ(n). The historical rank invariant survives compression precisely because ranks are not recomputed as current heights. Bounds for compression alone depend on the operation model; avoid an unqualified substitute theorem.

How To Use It

Write the size/rank invariant, count initialization, and distinguish successful unions from no-ops. Trace a balanced merge sequence before compression, then compare parent paths afterward. Tests establish partition preservation; a source argument establishes complexity. State the primitive cost model and avoid universal claims about alpha at a particular huge input.

Check Yourself

Why does compression leave root component size unchanged? Which simple proof yields log n but not alpha(n)? What work is hidden by omitting initialization?

Mini Drill or Application

Construct the eight-vertex sequence above and inspect a deepest path before/after find. Feedback: compression changes routing, not component count (1) or component size (8). Explain why rank could stay above the new height.

Read This Only If Stuck

CLRS: disjoint-set forests, rank lemmas and inverse-Ackermann analysis. Read the proof in layers; separate the established theorem from the doubling lemma you derive here.