Union-Find

The problem

Keep track of a collection of elements split into groups, as groups merge: which pixels form one region, which computers are on one network, which nodes Kruskal's algorithm has already connected. Two operations are needed:

union(a, b): merge the groups holding a and b.
find(x): name x's group, so that a and b are connected exactly when find(a) = find(b).

Trees of parent pointers

Each group is stored as a tree in which every element points to a parent. The root points to itself and names the group. find(x) follows pointers from x up to the root; union(a, b) finds both roots and makes one point to the other. That's all, but the trees must be kept flat, or a find can take as long as a walk down a list.

Naive: first root under second

Union by rank

Two tricks

Union by rank. Each root has a rank, an upper bound on its tree's height. Hang the root with the smaller rank under the other, so the tree doesn't grow. Only when the ranks are equal does the new root's rank go up by one. (On a tie, these pages put b's root under a's.)
Path compression. After find(x), point every node on the path straight at the root. The work of this find makes later ones nearly free.

With union by rank alone, trees stay at most log₂ n tall. With both tricks, a long run of operations costs O(α(n)) each, amortised. α, the inverse Ackermann function, is at most 4 for any input that fits in the universe, so in practice it's constant.

Reading the pictures

Each set is a tree with its root filled in and its rank (r) underneath; a line joins each element to its parent above it. Nodes glide to their new parents on a union or a compression.