THE FOLD / CO-OP / THE MERGE / THE UNION-FIND
THE UNION-FIND
merge sets & test connectivity in near-constant time
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Union-Find (Disjoint Set Union) tracks items grouped into non-overlapping sets, with two operations: UNION (merge two sets) and FIND (which set is this item in?). It is the backbone of minimum spanning trees, connected components, percolation, and image segmentation.
Each set is a tree; FIND follows parent pointers to the root, UNION links one root under another. Two tricks make it astonishingly fast: union by rank (attach the shorter tree under the taller) and path compression (after a FIND, point every visited node straight at the root, flattening the tree). Together they give an amortized cost per operation of α(n) — the inverse Ackermann function — which is ≤ 4 for any n that could exist in the physical universe. Effectively constant, though provably not quite.
LIT verified live: after dozens of random unions, “same root?” agrees with a brute-force connected-components search for every pair, and path compression flattens the trees to near-depth-1 (window.__unionfind). FIG no framing; the connectivity correctness and the flattening are exact, cross-checked against BFS.
Each set is a tree; FIND follows parent pointers to the root, UNION links one root under another. Two tricks make it astonishingly fast: union by rank (attach the shorter tree under the taller) and path compression (after a FIND, point every visited node straight at the root, flattening the tree). Together they give an amortized cost per operation of α(n) — the inverse Ackermann function — which is ≤ 4 for any n that could exist in the physical universe. Effectively constant, though provably not quite.
LIT verified live: after dozens of random unions, “same root?” agrees with a brute-force connected-components search for every pair, and path compression flattens the trees to near-depth-1 (window.__unionfind). FIG no framing; the connectivity correctness and the flattening are exact, cross-checked against BFS.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this in THE MERGE — the co-op domain where separate things fold into one. Union-Find is merging as a data structure: two groups become one with a single pointer, and membership stays instantly queryable. AVAN (AI) built the instrument: the forest of sets, the path-compressing find, the irreversibility inverse.
The weave: David names the seat (two groups merge into one); I make unions join sets and finds flatten the trees, checked against a full component search — the forest in 1D, the compressing find in 2D, the one-way-merge inverse in 3D. The sphere is the seam. Credit: Bernard Galler & Michael Fischer (1964); the inverse-Ackermann analysis by Robert Tarjan (1975). See [[kruskal-mst]].
The weave: David names the seat (two groups merge into one); I make unions join sets and finds flatten the trees, checked against a full component search — the forest in 1D, the compressing find in 2D, the one-way-merge inverse in 3D. The sphere is the seam. Credit: Bernard Galler & Michael Fischer (1964); the inverse-Ackermann analysis by Robert Tarjan (1975). See [[kruskal-mst]].
3 ONE DIMENSION
The elements and their current roots — each item points, directly or through a short chain, to the representative of its set. Items sharing a root are in the same set; the number of distinct roots is the number of sets.
4 TWO DIMENSIONS · INTERACTIVE
Elements as nodes. Union two of them and watch a root link under another; run a find and watch path compression re-point the whole chain straight at the root, flattening the tree. A connectivity check confirms two items share a set — matched against a full component scan.
5 THREE DIMENSIONS + AVAN’S INVERSE
The forest of sets turning, trees flattening as finds run — the green forward step: UNION folds two sets into one, and each set collapses toward a single root.
AVAN’s addition (the inverse-companion): the magenta is the inverse that does not exist — you cannot cheaply un-merge. UNION is a one-way ratchet: fold two sets together and the boundary between them is gone, so ‘which two sets did this come from?’ cannot be answered from the structure alone. To undo a union you must have remembered the history separately — a log of the merges — exactly as a Merkle chain must keep its links to be un-foldable. Plain Union-Find is a lossy fold: it keeps connectivity perfectly and forgets provenance entirely. And path compression makes that loss even sharper, rewriting the very pointers that recorded how the tree grew. The magenta split is why ‘Union-Find with rollback’ needs an extra stack the base structure refuses to carry. Green merges and flattens toward one root; magenta is the seam that vanished when they joined — the merge remembers that you are together, never how you came to be.
LIT Genuine Union-Find with union by rank and path compression (Bernard Galler & Michael Fischer 1964; inverse-Ackermann amortized analysis by Robert Tarjan 1975). Verified live: after 60 random unions among 100 elements, 'same root?' agrees with a brute-force BFS connected-components search for every pair, and path compression flattens the trees to near-depth-1 (window.__unionfind.connectivityMatches && maxDepthAfterCompression small). The connectivity correctness and flattening are exact, cross-checked against BFS.
FIG No framing: the connectivity queries and path-compression flattening are real and verified against an independent BFS component search in-browser. The AVAN inverse is honest and genuine — UNION is a lossy one-way fold that keeps connectivity but forgets the merge boundary, so un-merging requires a separately-remembered history (like a Merkle chain's links); plain Union-Find provides no cheap inverse.
FIG No framing: the connectivity queries and path-compression flattening are real and verified against an independent BFS component search in-browser. The AVAN inverse is honest and genuine — UNION is a lossy one-way fold that keeps connectivity but forgets the merge boundary, so un-merging requires a separately-remembered history (like a Merkle chain's links); plain Union-Find provides no cheap inverse.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE MERGE · David Lee Wise (ROOT0), with AVAN