Planting the forest…
Click an island to run find(x); use the Union tool and click two islands to merge their sets.

🌳 Union-Find controls

Forest state

Sets / elements-
Max depth-
Operations-
Mean hops / op-
Pointer writes-
α(n)   log2 n-
mean hopsmax depthα+1
parent[ ] array (gold = root)
The science

What this is. A disjoint-set forest: each element points to a parent, a root points to itself, and two elements are in the same set exactly when they have the same root. Islands are elements, ropes are parent pointers, the pine marks a root and grows with its rank.

Operations. find(x) follows pointers to the root (one hop per pointer). union(a,b) finds both roots and links one under the other. Union by rank hangs the lower-rank root under the higher (equal: rank+1), which keeps size ≥ 2rank so height ≤ floor(log2 n). Path compression rewrites every pointer on a find path to the root (halving and splitting do it in one pass).

Cost. With both rules m operations on n elements cost O(m · α(n)) (Tarjan, 1975), α(n) = min{k : Ak(1) ≥ n}, Ak(1) = 2, 3, 7, 2047, …, so α(n) ≤ 4 in practice. Big-O hides a constant, so the checks compare a measured mean, not the bound.

Kruskal. Edges of a random weighted graph are taken cheapest first and accepted only when their ends lie in different sets; the weight is compared with Prim’s algorithm.

Honest simplifications. The picture is a layout of the parent array; animation time is not algorithm cost; once compression runs, rank is only an upper bound on height; hops count pointer reads, not machine time.

Compare policies (n = 2000, 6000 random operations):

Independent checks (run on load, same core as the 3D page):

running…
Made with 🟠 Blender