Learn · The Concrete Discrete Math of Real Systems

growing

The Forest Learns Which Trees Are One

Union–find turns a changing equivalence relation into a forest whose paths flatten under questioning, closing the book where laws become executable structure.

Published 2 weeks ago · Updated 2 weeks ago

discrete-math, union-find, equivalence-relations, amortized-analysis, algorithms, learn

This paper considers the problem of merging sets formed from a total of $n$ items.

— John E. Hopcroft and Jeffrey D. Ullman, “Set Merging Algorithms,” 1973

The preceding chapter queried a static structure without unpacking it. The final chapter maintains a dynamic partition. You will derive union–find from equivalence classes, prove that forest representation changes preserve the partition, understand union by rank and path compression, and connect the resulting amortized bound to the book's opening promise: name the structure and its laws, then transfer them.

Connections create classes

Begin with six computers, each isolated. Every computer is equivalent only to itself under “connected by some path.” Add links (A,B), (B,C), and (D,E). The partition is now {A,B,C}, {D,E}, {F}.

Connectivity is an equivalence relation:

reflexive: a vertex reaches itself;
symmetric: an undirected path can be reversed;
transitive: an A→B path followed by B→C gives A→C.

Chapter 5 said every equivalence relation is a partition. Here the partition changes by merging classes and never splitting them.

Three operations suffice:

make(x) creates the singleton class {x};
find(x) returns the representative of $x$ 's class;
union(x,y) merges the two classes.

Then $x\sim y$ exactly when find(x) = find(y).

Disjoint-set union (union–find) — a data structure maintaining a partition under class merges and representative queries. The representative is an implementation name, not a privileged member of the mathematical class.

Retrieval — equality is class membership.

A forest represents the partition

Give every element one parent pointer. A root points to itself and names one class; every node following parents reaches exactly one root. find follows that path. To union two classes, find their roots and make one root the child of the other.

Many forests represent the same partition. A class may be a chain, a star, or a balanced tree without changing which nodes share a root. This freedom is the optimization budget.

The invariant is concise:

Two elements are equivalent exactly when their parent paths end at the same root. Every optimization may change paths but must preserve roots as class identities.

Keep trees shallow, then flatten them

Naively attaching one root under another can build a chain of length $n$ . Union by rank attaches the shallower tree beneath the deeper. A root's rank increases only when two equal-rank trees merge, so a rank- $r$ tree contains at least $2^r$ nodes. Rank is therefore at most $\log_2 n$ .

Path compression improves find. After discovering the root, point every node on the traversed path directly to it. The answer is unchanged, but later finds become shorter. A query pays partly for itself and leaves the representation better than it found it.

Prediction — mutate shape without mutating meaning.

With both heuristics, a sequence of $m$ operations on $n$ elements takes $O(m\alpha(n))$ time, where $\alpha$ is the inverse Ackermann function. It grows so slowly that it is below 5 for any practical input, yet calling the algorithm literally constant-time would erase the theorem's conditions. The correct phrase is “nearly constant amortized time.”

Amortized analysis — a bound on the total cost of a sequence, allowing an individual operation to be expensive when it makes later operations cheaper. It is a worst-case statement about sequences, not an average over random inputs.

Note

The people behind the bound. Robert Endre Tarjan proved the celebrated inverse-Ackermann upper bound in “Efficiency of a Good But Not Linear Set Union Algorithm” (1975), building on set merging work including John Hopcroft and Jeffrey Ullman's 1973 paper. Union by size and path-shortening ideas have a broader history; the eponym-free name “union–find” appropriately describes the interface rather than assigning the entire structure to one inventor.

The same structure, three times

Kruskal's minimum spanning tree. Process edges from lightest to heaviest. Add an edge exactly when its endpoints are in different components; union them afterward. find is the cycle test.

Image segmentation. Treat neighboring pixels as equivalent when a criterion says they belong to one region. Unions build connected components; roots label regions.

Unification and equivalence closure. Compilers, theorem provers, and type inferencers repeatedly learn that terms are equal. Union–find maintains the quotient classes so a later equality query is a pair of finds, not a replay of every equation.

It does not support arbitrary deletion or splitting efficiently. If connections disappear, use a dynamic-connectivity structure or process events offline in an order that turns deletion into addition.

Where union–find runs out

It answers whether two elements are connected, not the path between them.
Representatives are unstable implementation choices; never expose a root identifier as durable semantic identity.
Path compression mutates the forest. Persistent snapshots require a different design or carefully controlled versioning.
The inverse-Ackermann bound assumes the union and compression heuristics and amortizes over a sequence.

Lessons

A dynamic connectivity relation is a changing partition into equivalence classes.
A forest represents each class by a root; union links roots and find names the class.
Union by rank prevents tall growth; path compression makes questions improve future questions.
Representation may change aggressively while the equivalence invariant remains fixed.

Practice

Starting from eight singletons, union equal-size classes in rounds. Track ranks and prove a rank- $r$ root has at least $2^r$ descendants.
Draw a length-five parent chain, run find with path compression on its leaf, and draw the result.
Explain why exposing the root as a permanent user ID is a mistake.
One month later, identify a new system as union–find from only this clue: “classes only merge; queries ask whether two names are now the same.”

The opening claim, paid in full

At the beginning of this book, an if statement looked like prose. It became Boolean algebra once its operations and laws had names. Since then the same move has repeated:

a loop became induction when “what stays true?” was named;
a changing build became a reachability cone;
a distributed aggregation became a monoid homomorphism;
completion became a residual language;
repeated inference became a least fixed point;
connectivity became a maintained equivalence relation.

The point was never to make familiar programs sound mathematical. It was to gain the transfer that names and laws permit. Once you recognize the structure, an argument in one domain becomes an algorithm in another; a counterexample becomes a test; a law becomes a safe optimization; a boundary becomes an honest product limit.

Union–find is the final miniature of that method. “Are these connected?” sounds like a graph search. Name the growing equivalence relation and a forest appears. State the root invariant and paths may flatten. Prove a sequence bound and “fast” becomes a checkable claim. The implementation did not acquire decoration. It acquired reasons.

When a familiar implementation gains a structural name, its laws become portable—and the next unfamiliar system stops being unfamiliar.

The book ends here as a route, not as a finish line. Return to any system you know well. Ask what values exist, which distinctions matter, what combines, what orders, what remains invariant, and where the laws stop. The next aha is already running in it.

References

Hopcroft and Ullman. “Set Merging Algorithms.” SIAM Journal on Computing, 1973. — early nearly-linear set-merging algorithms and analysis
Tarjan. “Efficiency of a Good But Not Linear Set Union Algorithm.” Journal of the ACM, 1975. — the inverse-Ackermann analysis
“Robert Tarjan.” Princeton University. — institutional biography and publication record
Cormen, Leiserson, Rivest, Stein. “Introduction to Algorithms, 4th ed..” MIT Press, 2022. — disjoint-set forests, minimum spanning trees, and amortized analysis

Connections arrive one by one: two accounts belong to one person, two pixels lie in one region, two machines share a network component. The question “are these equivalent now?” could search the graph every time. Union–find instead stores each class as a rooted tree. Roots name classes; unions link roots; finds flatten paths. The questions teach the structure how to answer the next question faster.