Union-Find: Merging Sets in Near-Constant Time

Two operations, one forest

A disjoint-set (union-find) structure keeps a collection of elements partitioned into non-overlapping groups and answers two questions fast: find(x) - which group is x in? - and union(x, y) - merge x's group with y's group. Internally each set is a tree, and every element stores only a pointer to its parent. The root of a tree is the group's canonical representative: two elements sit in the same set exactly when their roots match.

Kruskal's minimum spanning tree algorithm is the classic use case: sort edges by weight, then walk them in increasing order and add an edge to the tree unless its two endpoints are already connected - a question union-find answers in the time it takes to walk two short chains to their roots. The same structure tracks connected components as edges stream in one at a time, detects cycles in a graph, and merges regions in image segmentation.

The naive version, and why it degrades

A first attempt makes find walk parent pointers to the root, and union attach one root under the other arbitrarily. That works, but nothing stops a tree from becoming a long chain - union elements in increasing order, always attaching the new root under the previous one, and you get a straight line of n nodes. Find then costs O(n) instead of the O(log n) or better you actually want.

function find(x) {
  while (parent[x] !== x) x = parent[x];
  return x;
}
function union(x, y) {
  const rx = find(x), ry = find(y);
  if (rx !== ry) parent[rx] = ry;   // arbitrary attachment - can chain badly
}

Union by rank

The fix is to always attach the shallower tree under the deeper one. Track either an exact size or an upper-bound rank (roughly, tree height) per root; when merging, the root with the smaller rank becomes a child of the root with the larger rank, and ties bump the winner's rank by one. This alone caps every tree's height at O(log n), because a tree of rank r can only be built by merging two trees of rank r minus 1, so it takes at least 2 to the power r elements to reach rank r.

Path compression: flattening as you go

Union by rank bounds the height, but you can do much better by rewriting history every time you walk to a root. Path compression makes every node visited during a find() point directly at the root once that root is known, so the next find from any of those nodes is O(1).

function find(x) {
  if (parent[x] !== x) parent[x] = find(parent[x]);   // point straight at the root
  return parent[x];
}

Tarjan and van Leeuwen proved that combining union by rank with path compression drives the amortized cost of any sequence of m operations on n elements down to O(m · alpha(n)), where alpha is the inverse of the fast-growing Ackermann function. For every practical n, alpha(n) is at most 4 or 5, so the structure behaves as if each operation were O(1) - a rare case where a genuinely non-constant bound is indistinguishable from constant time on real inputs.

Frequently asked questions

Try it live

Everything above runs in your browser - open Union-Find and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.