What this is. A disjoint-set forest (union-find): 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. Here every element is a floating island; a rope runs from each island to its parent; the root carries a pine whose height grows with its rank.
Operations. find(x) follows parent 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 root of smaller rank under the larger one (equal ranks: rank+1), which keeps size ≥ 2rank and therefore tree height ≤ floor(log2 n). Path compression makes every node on the path of a find point straight to the root (halving and splitting do it in one pass with the same asymptotics).
Cost. With both rules, any sequence of m operations on n elements costs O(m · α(n)) (Tarjan, 1975), where α(n) = min{k : Ak(1) ≥ n} is the inverse Ackermann function: Ak(1) = 2, 3, 7, 2047, …, so α(n) ≤ 4 for every n you will ever meet. The big-O hides a constant, so the checks compare a measured mean, not the bound itself.
Kruskal. The button sorts the edges of a random weighted graph and accepts an edge only if its endpoints are in different sets (a find on each, then a union), building a minimum spanning tree; the total weight is compared with Prim’s algorithm.
Honest simplifications. The picture is a layout of the parent array (roots on top, y = depth); islands glide to new places so you can see pointers change, but the animation time is not the algorithm’s cost. Rank is only an upper bound on height once compression runs. Hops count parent-pointer reads, not machine time or cache effects.
Compare policies (n = 2000, 6000 random operations):
Independent checks (run on load, same core as the 2D page):
| running… |