Disjoint-Set Data Structures: Union-Find with Rank and Path Compression

The Disjoint-Set Abstract Data Type

A Disjoint-Set data structure (also called Union-Find) maintains a collection of non-overlapping sets, supporting three operations: MAKE-SET(x) creates a new set containing only x, UNION(x, y) merges the sets containing x and y into one, and FIND-SET(x) returns a representative element identifying which set x currently belongs to.

Representing Sets as Trees

The standard implementation, called a Disjoint-Set Forest, represents each set as a tree, where each node points only to its parent, and the root of the tree serves as the set's representative.

MAKE-SET(x):
  x.p = x           // x is its own parent, forming a single-node tree
  x.rank = 0

FIND-SET(x):
  if x ≠ x.p:
      return FIND-SET(x.p)
  return x

UNION(x, y):
  LINK(FIND-SET(x), FIND-SET(y))

LINK(x, y):
  x.p = y           // makes y the parent of x, merging the two trees

This naive version works correctly, but has a serious weakness: repeatedly linking trees in an unlucky order can produce a tree that degenerates into a long chain, making FIND-SET take Θ(n) time in the worst case — the same danger of unbalanced structure that motivated the red-black trees discussed earlier in this series.

First Optimization: Union by Rank

Union by Rank tracks an approximate upper bound on each tree's height, called its Rank, and always attaches the shorter tree under the root of the taller tree during a union, rather than arbitrarily choosing a direction.

LINK(x, y):
  if x.rank > y.rank:
      y.p = x
  else:
      x.p = y
      if x.rank == y.rank:
          y.rank = y.rank + 1

Since the shorter tree is always attached beneath the taller one, the resulting tree's height only increases when the two trees being merged have equal rank, and even then, by only one level. This is analogous in spirit to the balanced-splitting insight discussed earlier in this series regarding B-trees and red-black trees: careful attachment order prevents the pathological chain structure that would otherwise be possible.

Using union by rank alone, it can be proven that a tree with rank r has at least 2^r nodes, which means the maximum possible rank for n elements is O(log n), bounding every FIND-SET operation to O(log n) time — already a dramatic improvement over the unoptimized O(n) worst case.

Second Optimization: Path Compression

Path Compression is applied during FIND-SET itself: as the algorithm walks up the tree to find the root, it makes every node visited along the way point directly to the root, flattening the tree for all future queries involving those nodes.

FIND-SET(x):
  if x ≠ x.p:
      x.p = FIND-SET(x.p)     // recursively find the root,
                                // then attach x directly to it
  return x.p

Before FIND-SET(d), with chain a-b-c-d:
a → b → c → d(root)

After FIND-SET(d):
a → d(root)
b → d(root)
c → d(root)
(every node on the path now points directly to the root)

This optimization does not change the immediate cost of the current FIND-SET call, but dramatically speeds up every future FIND-SET call on any node along the path that was just compressed, since those nodes now require only a single step to reach the root.

The Combined Effect: Near-Constant Amortized Time

Applying both optimizations together produces a striking result. Using the amortized analysis techniques discussed earlier in this series, it can be proven that a sequence of m operations on n elements takes O(m · α(n)) total time, where α(n) is the Inverse Ackermann Function, an extraordinarily slowly growing function.

The inverse Ackermann function α(n) grows so slowly
that for any input size conceivable in practice
(even far beyond the number of atoms in the observable universe),
α(n) ≤ 4

For all practical purposes, α(n) can be treated as a constant,
making the amortized cost per operation effectively O(1)

This is one of the most remarkable results in the analysis of data structures: two simple, easy-to-implement heuristics, combined, yield a running time that is for all practical purposes constant per operation, despite the underlying worst-case tree structure theoretically still being able to grow arbitrarily.

Why Either Optimization Alone Is Weaker

It is worth noting that either optimization applied in isolation already provides a significant improvement over the naive implementation: union by rank alone guarantees O(log n) per operation, and path compression alone (without union by rank) can be shown to guarantee O(log n) amortized time as well. It is specifically the combination of both techniques together that pushes the bound all the way down to the near-constant O(α(n)) — a clear illustration of how two individually good optimizations can compound into a qualitatively better result when combined.

Why Disjoint-Set Structures Matter for Graph Algorithms

The disjoint-set structure described in this article is not merely a theoretical curiosity; it is the essential engine behind Kruskal's Algorithm for finding a minimum spanning tree, covered later in this series, where the algorithm repeatedly needs to check whether adding a given edge would create a cycle (by checking if its two endpoints are already in the same set) and merge sets when an edge is accepted. Without the near-constant time guarantees this structure provides, Kruskal's algorithm's efficiency, and that of many other algorithms relying on dynamic connectivity queries, would be substantially worse.