Union-Find (Disjoint Sets)

Tip: click a node, then another node, to add union of the two. Click the same node twice to add find.

Why is it "almost constant"? The α(n) intuition

Union by size alone keeps every tree at height ≤ log₂ n: a node gets one level deeper only when its tree is hung under a tree at least as big, so its group at least doubles each time (Levitin §9.2). Path compression then makes every node on a walked path point straight at the root, so the next walk is short. Together, any sequence of m operations costs O(m·α(n)), where α is the inverse Ackermann function. It grows so slowly that α(n) ≤ 4 for any n you could ever store.

A friendlier cousin is the iterated logarithm log* n: how many times you press "log₂" before reaching 1. The easier bound O(log* n) per operation (Hopcroft and Ullman) is already tiny:

Race every variant on a big input (no animation, just the totals). "Work" counts parent/id entries read while walking plus entries written, the same unit as the counters above.

How to read this

• The forest (top): each arrow points from a node to its parent. A node with an orange ring is a root, the representative ("boss") of its set. Under each root you see its size (or rank).
• The array (bottom) is what the computer actually stores: parent[i] for quick-union or id[i] for quick-find. Quick-find is drawn as flat stars because every element stores its representative directly.
• Colors: blue = where a find starts, yellow = pointers walked, green = the root that was found, red = entries rewritten (a link, a relabel, or a path-compression shortcut), purple = the two roots about to be linked.
• Counters: reads = parent/id entries read while walking, writes = entries changed. Work per op = (reads + writes) / operations; that's the amortized cost you can see.
• Operation log: one bar per operation; click a row to jump to it. Expensive operations become rare once the forest is flat.

Try this

1. Keep the lesson trace with union by size + path compression and run it. The parent array should end as 0 0 0 0 0 4 0 0: the final find(7) walks 7 → 6 → 4 → 0 and then rewires 7 and 6 straight to 0.
2. Press Worst-case chain, choose Naive linking and switch compression off. The tree becomes a single path of height n − 1, and each find(0) reads n entries. Now turn on compression: the first find is still expensive, the next ones cost 2 reads.
3. Same chain, but Quick-find + Naive: every union relabels the whole growing group, 1 + 2 + … + (n − 1) = n(n − 1)/2 writes. Switch to union by size: each union relabels only one element.
4. Turn on union by size with compression off and click nodes to build the tallest tree you can. You can't beat height log₂ n (height 3 for n = 8, 4 for n = 16).
5. In the race, compare "Quick-union naive" with "size + compression" on the chain workload: work per operation drops from about a thousand to about 3. Then try the random workload: naive quick-union still grows trees hundreds of levels tall, while size/rank keeps them to a handful of levels. Quick-find that relabels the smaller group is cheap here too, because each of its finds is a single read.

Go deeper