Disjoint-Set Data Structure

Disjoint-set data structure (also called a union–find data structure or merge–find set) is a pointer-forest data structure within computation and algorithms that maintains a dynamic collection of non-overlapping sets S = {S₁, S₂, ..., S_k} partitioning a finite universe U of n elements. Introduced by Bernard A. Galler and Michael J. Fischer in 1964 to resolve FORTRAN EQUIVALENCE variable aliasing statements, each disjoint set S_i is represented as a rooted tree in which every node stores a single parent pointer *parent*[x] directed upward toward the tree root, and the root r_i (satisfying *parent*[r_i] = r_i) serves as the canonical representative of the equivalence class S_i.

When equipped with two complementary structural heuristics—union by rank (or union by size) and path compression—a sequence of m operations (Make-Set, Union, and Find-Set) on n elements executes in worst-case O(m α(n)) time, as proved by Robert E. Tarjan in 1975 and matched by Fredman and Saks's (1989) cell-probe lower bound within computational complexity theory. Here α(n) is the inverse Ackermann function, which satisfies α(n) ≤ 4 for all physically realizable input sizes n < 2⁶⁵⁵³⁶, making disjoint-set operations near-constant-time in practice. Across graph theory, statistical physics, and genomics, the disjoint-set forest powers Kruskal's algorithm for minimum spanning trees, Tarjan's offline lowest common ancestors, Hoshen–Kopelman lattice percolation clustering, and single-linkage homologous gene family clustering.

Dynamic Equivalence Relations and Core Operations

Let ∼ be a dynamically evolving equivalence relation over a ground set U = {0, 1, ..., n − 1} initialized to the identity relation (x ∼ y ⇔ x = y), and let the equivalence classes of ∼ be the pairwise disjoint subsets S₁, S₂, ..., S_k satisfying S_i ∩ S_j = ∅ for i ≠ j and ⋃_i=1..k S_i = U (contrast with directed mutual reachability classes computed statically by Tarjan's strongly connected components algorithm). The disjoint-set abstract data type supports three primitive operations:

1. Make-Set(x): Initializes a new singleton equivalence class {x} with representative x by setting *parent*[x] ← x, *rank*[x] ← 0, and *size*[x] ← 1 in O(1) time.
2. Find-Set(x): Follows parent pointers x → *parent*[x] → *parent*[*parent*[x]] → ... upward until reaching the unique root r satisfying *parent*[r] = r, and returns r. Two elements x and y belong to the same equivalence class if and only if Find-Set(x) = Find-Set(y).
3. Union(x, y): Computes the roots r_x = Find-Set(x) and r_y = Find-Set(y). If r_x ≠ r_y, merges the two equivalence classes S_x and S_y into S_x ∪ S_y by redirecting the parent pointer of one root to point to the other.

Because all n trees in the disjoint-set forest can be stored inside two flat integer arrays *parent*[0..n − 1] and *rank*[0..n − 1] (or packed into a single signed integer array where a root r stores −*size*[r] < 0 and a non-root x stores *parent*[x] ≥ 0), the entire data structure consumes 4n to 8n bytes of memory with zero dynamic heap allocations.

Union by Size and Union by Rank (Logarithmic Depth Bound)

In an unoptimized parent-pointer forest where Union(x, y) attaches r_x under r_y arbitrarily, a chain of n − 1 unions builds a linear list of height n − 1, degrading Find-Set to Θ(n) time. Attaching the smaller or shallower tree under the larger or taller root eliminates this pathology:

• Union by Size: Each root r tracks its component size *size*[r]; attach the smaller root under the larger root and add their sizes.
• Union by Rank: Each root r tracks an upper bound *rank*[r] on its subtree height; attach the smaller-rank root under the larger-rank root, incrementing rank by 1 only when the two ranks are equal.

By induction, a root of rank k contains at least 2^k nodes, bounding tree depth without path compression by ⌊log₂ n⌋.

Path Compression, Path Halving, and Path Splitting

Path compression flattens traversed paths during Find-Set(x) by redirecting *parent*[u] ← r for every ancestor u along the path from x to root r:

Tarjan and van Leeuwen (1984) showed that two non-recursive single-pass variants—path splitting (setting *parent*[u] ← *parent*[*parent*[u]] at every visited node) and path halving (setting *parent*[x] ← *parent*[*parent*[x]] at every other node)—achieve the same Θ(n + m α(m, n)) bound.

Ackermann Growth Hierarchy and Optimality

Define A₀(j) = j + 1 and A_k(j) = A_k−1^(j+1)(j) for k ≥ 1. Even at j = 1, A₀(1) = 2, A₁(1) = 3, A₂(1) = 7, A₃(1) = 2047, and A₄(1) > 10⁸⁰. The inverse Ackermann function α(n) = min {k : A_k(1) ≥ n} is therefore ≤ 4 for all practical inputs, and Fredman and Saks (1989) proved in the cell-probe model that Ω(m α(m, n)) memory probes are necessary for any disjoint-set data structure.

When edge deletions must be supported in an offline dynamic graph (where the lifespan interval [t_start, t_end] of every edge is known), path compression is omitted and union by rank/size is paired with a segment tree over time, allowing each Union to be undone from an undo stack in O(1) time. Across the sciences, the disjoint-set forest underpins Kruskal's algorithm, Tarjan's offline Lowest Common Ancestor (LCA) algorithm, the Hoshen–Kopelman algorithm (1976) for statistical physics percolation clusters, and single-linkage orthologous gene clustering (MMseqs2, CD-HIT) across protein sequence databases.

Why is the rank of a node called "rank" instead of "height" when path compression is active?

Without path compression, *rank*[x] equals the height of the subtree rooted at x. Once path compression is enabled, Find-Set operations reattach deep descendants directly under the root, which can decrease the true height of interior subtrees without updating their stored rank values. Thus *rank*[x] remains an upper bound on the subtree height of x.

Can elements be deleted from a disjoint-set forest in O(α(n)) time?

Deleting a single element x from its current set (moving x to a new singleton set) can be supported in O(α(n)) time via indirection: each logical element x points to an internal forest node v_x, and deleting x marks v_x as a routing node while allocating a fresh singleton node v′_x. Splitting an entire merged component back into subsets requires offline rollback or dynamic-graph Euler-tour structures in O(log² n) time.

1. Galler, B. A., & Fischer, M. J. (1964). "An improved equivalence algorithm." Communications of the ACM, 7(5), 301–303. https://doi.org/10.1145/364099.364331
2. Tarjan, R. E. (1975). "Efficiency of a good but not linear set union algorithm." Journal of the ACM, 22(2), 215–225. https://doi.org/10.1145/321879.321884
3. Hoshen, J., & Kopelman, R. (1976). "Percolation and cluster distribution. I. Cluster multiple labeling technique and critical concentration algorithm." Physical Review B, 14(8), 3438–3445. https://doi.org/10.1103/PhysRevB.14.3438
4. Tarjan, R. E., & van Leeuwen, J. (1984). "Worst-case analysis of set union algorithms." Journal of the ACM, 31(2), 245–281. https://doi.org/10.1145/62.2160
5. Fredman, M. L., & Saks, M. E. (1989). "The cell probe complexity of dynamic data structures." Proceedings of the 21st Annual ACM Symposium on Theory of Computing (STOC), 345–354. https://doi.org/10.1145/73007.73040