Collapse

Two disjoint-set forests, the same stream of union and find operations, side by side. The left forest is plain quick-union — hang the root of one tree under the root of the other, no heuristics. The right is union by rank with path compression. Both answer every query correctly and end with exactly the same components; the only thing that differs is what the pointers cost, and a strip along the bottom draws the two running hop counts pulling apart.

The payoff is a thing complexity tables assert and never show: a find is not just a read. When the compressed forest walks four pointers to reach a root, all four nodes are repointed straight at it on the way back down — the path lights up, then the tree visibly collapses under it, and the next query through any of those nodes is one hop. The query paid for its successors. That is the whole of amortization, and it is a picture rather than a paragraph.

The default stream is adversarial on purpose: it always unions the same node into a fresh one, which under plain quick-union hangs the entire accumulated tree under the newcomer every single time. The left pane becomes one chain as tall as the node count and every subsequent step walks all of it; the right pane is a flat star of height 1 by the third operation. Switch to random pairs for the honest average case, where the gap is smaller but still lopsided, and where the second detail shows up.

That second detail is on the root badges, which read h·/r·: the tree’s actual height against the stored rank. Rank is only ever an upper bound — it goes up when two equal-rank roots merge and is never lowered, because compression flattens trees without telling anyone. So a tree that has been queried hard sits at height 1 while claiming rank 3, the pill turns amber, and the algorithm remains correct anyway: the bound is used to pick which root survives a merge, and a bound that is too large only ever makes that choice conservative. Wrong-looking but sound, which is the interesting half of union-find.

Hover any node to see its chain to the root drawn in both forests at once, with the two hop counts in the readout — the fastest way to feel what the difference actually buys.

Reuse

src/collapse.js is a framework-free ES module with no canvas and no timers:

• simulate(n, ops, { byRank, compress }) — one frame per operation (plus a frame 0 for the all-singletons start), each carrying the parent array, ranks, the path the step walked, the nodes compression repointed, the step’s hop count and the running total, per-tree { size, height, rank }, and how many trees currently carry a stale rank bound. Turning either option off gives you quick-union, compression-only or rank-only from the same code path — which is what makes the three right-pane modes one argument rather than three implementations.
• randomOps(n, count, { rand, findRatio }) and chainOps(n) — the two streams, both taking an injected RNG.
• rng(seed) — mulberry32, so a stream is reproducible from its seed.
• pathTo, rootOf, depths, trees — side-effect-free readers used by the renderer for hover paths and badges.

Same trace-per-tick shape as rho, sift, window and astar-grid: the module produces frames, the demo draws them.

Gotchas

• The forest layout is recomputed every frame and rendered positions lerp toward it. That is deliberate — the collapse is the animation — but it means a screenshot taken immediately after jumping frames catches nodes mid-flight. The thumbnail script waits for them to settle.
• chainOps is only adversarial against the plain pane. Against union by rank it is a best case, which is the point of pairing them.
• Rank is not size. Union by size would make the badge comparison less interesting, because size never goes stale — it stays exactly right under compression, and there is nothing to notice.
• The demo bundles its own copy of collapse.js (self-contained by contract); re-copy after editing src/.