Flatten

Every explainer for union-find draws the parent array. The array is the implementation. The idea is a forest, and the idea worth having is that find is not a read — it is a write. It walks a path to the root, and on the way back it re-points every node it passed at the root, so the query pays for its own future. A data structure that gets faster because you used it is rare enough to be worth watching happen rather than reading about.

So the piece draws the trees. Every root sits on the top line, which means a node’s row is its depth, and its depth is exactly what finding it costs — one horizontal line across the whole picture is one price. Everything else follows from that one decision.

• Click a node to find it. The walked path lights up, the hop count is printed, and every node on it swings up to hang directly off the root. The status line names them and says what the same find costs now: 1.
• Drag one node onto another to union them. Both finds run first (compressing as they go), then the attach — and the line says which root won and why, in rank’s own words.
• The two switches are the argument. Toggling either one replays the same union sequence from scratch, so the difference in the picture is attributable to the switch and nothing else.

The default sequence is union(i, i-1) for i = 1..n, which is what a loop over sorted edges does and looks entirely innocent. With union by rank off it builds a linked list wearing a tree’s clothes: n = 16 gives a staircase 15 deep, Σ depth 120, and every find on the far end costs 15 hops. Turn rank on and the same sequence produces a star of depth 1, because each new singleton has rank 0 and rank refuses to hang the taller tree off the shorter one.

The other preset is the doubling order — pair up, then pair the pairs — which is the tallest a rank-union forest can be made: every union is a tie, so rank has to break it and the height climbs by one per doubling. Thirty-two nodes, five levels, and that is the worst case rather than an unlucky one.

Three things the picture is built to make visible:

• The high-water mark. An amber dashed line sits at the deepest any node has been since the reset, and the vertical scale is held there — so when a single find collapses a 15-deep chain onto its root, the empty space it leaves behind is the measurement. You can make the tree grow. You can do it once, and the next query takes it apart.
• Rank goes stale, and that is fine. A root wears its rank; when compression has lowered the tree below it, the true height appears under it in teal. Rank is never decreased — recomputing it would cost a traversal and buy nothing — so after any compression it is an upper bound rather than a measurement. It still orders the roots correctly, which is the only thing the union rule ever asked of it.
• Hops per find, as a strip along the bottom. With compression on, a storm of random finds spikes on the first deep one and then flatlines near 1 — the amortization, drawn in the units it is actually paid in. With compression off, run the same storm: the bars stay tall, the structure is untouched, and the next storm costs the same again. That is the whole of α(n) without anyone having to say “inverse Ackermann”.

Presets are the union order and n (8 / 16 / 32). u unions a random pair, q runs a storm of twelve finds, f finds the currently deepest node, c and k flip compression and rank, r resets.

Reuse

src/dsu.js is a framework-free ES module. Every mutating call returns a trace instead of a bare answer, because the interesting part of union-find is the path it walked and what it did to that path:

• create(n) — n singletons.
• root(state, x) — the representative, touching nothing.
• findTrace(state, x, { compress }) — { root, path, hops, reparented }. reparented lists only the pointers that actually moved, which is what a renderer wants to animate.
• unionTrace(state, a, b, { byRank, compress }) — the two finds, then the attach: { merged, winner, loser, rankRose, reason, traces, hops }. reason is a sentence, so a UI can quote the rule rather than restate it.
• depths(state), heights(state), childrenOf(state), roots(state), stats(state) — { sets, maxDepth, deepest, totalDepth, avgDepth, maxRank }.
• layoutForest(state, { gap, lean }) — tidy layout in abstract units, every root at y = 0 so y is depth across the whole forest.
• chainOrder(n), binomialOrder(n), randomOrder(n, rng) — the union sequences worth having: the degenerate one, the worst case under rank, and noise.

No rendering, no timers, no DOM. The canvas demo is reference code.

Gotchas

• findTrace mutates when compress is true. That is the point of the structure, but it means a “read” invalidates any layout you cached, and a renderer has to recompute after every find.
• layoutForest leans a whole-path tree into a staircase instead of stacking it in one column — pure cosmetics, and only for trees with no branching, so a leaning run can never collide with a sibling subtree. y is always exactly the depth.
• depths and heights recurse over parent pointers; both memoize, so a 16-deep chain costs one pass, but neither is meant for a forest with millions of nodes inside a frame loop.
• Rank is only maintained when byRank is on. With it off the array stays at zero and the demo hides the badges, rather than showing a number that means nothing.
• The demo bundles its own copy of dsu.js (self-contained by contract); re-copy it after editing src/.