Disjoint-set data structure

A disjoint-set data structure, also called a union–find data structure, represents a partition of a finite set into mutually disjoint subsets. It supports the incremental merging of subsets while maintaining enough information to determine whether two elements currently belong to the same subset. The structure is central to algorithms involving equivalence relations, incremental connectivity, and the construction of minimum spanning trees.

The standard representation is a collection of rooted trees known as a disjoint-set forest. Each element stores a reference to a parent element, while the root of each tree refers to itself and serves as the representative of the corresponding subset. The identity of a representative is an implementation property rather than a mathematical property of the partition; changing a root does not change which elements are equivalent.

Abstract operations

The abstract data type is defined by three operations whose interaction determines the represented partition.

MakeSet(x) creates a singleton subset containing the element (x). In a forest representation, the new element is its own parent and therefore forms a tree with one vertex.

Find(x) returns the representative associated with the subset containing (x). A forest implementation follows parent references from (x) until it reaches a root. Two elements belong to the same subset exactly when their find operations return the same representative.

Union(x,y) replaces the subsets containing (x) and (y) with their set-theoretic union. The operation first identifies both representatives and, when they are distinct, makes one root a descendant of the other. If both elements already have the same representative, the partition remains unchanged.

These operations maintain an equivalence relation on the stored elements. Reflexivity follows because every element belongs to its own subset, symmetry follows from common subset membership, and transitivity follows because each element belongs to exactly one tree.

Forest representation

A direct forest implementation can develop trees whose height is linear in the number of elements. For example, repeatedly attaching an existing root beneath a newly created root produces a chain. A find operation beginning at the deepest vertex then requires time proportional to the chain length.

Two structural rules substantially alter this behavior. Under union by size, the root of the tree containing fewer vertices becomes a child of the root containing more vertices. Under union by rank, each root stores an upper bound on tree height, and the root with smaller rank becomes a child of the root with larger rank. Equal ranks permit either root to become the parent, after which the surviving root’s rank increases by one.

Union by rank maintains a logarithmic bound on height when used without path compression. A root of rank (r) represents at least (2^r) elements, because its rank increases only after two trees of equal rank are combined. Consequently, no rank exceeds (\lfloor \log_2 n \rfloor) in a structure containing (n) elements.

Path compression changes parent references during a find operation. After the representative has been located, vertices encountered along the search path are attached directly to that representative. This transformation preserves the partition because every redirected vertex remains in the same rooted tree. Rank ceases to describe the current height after compression, although the stored rank values remain sufficient for choosing roots during later unions.

Variants such as path splitting and path halving also shorten search paths. Path splitting redirects every visited vertex toward its grandparent, whereas path halving performs such redirection on alternating vertices. Their amortized behavior is closely related to that of full path compression.

Complexity

Neither path compression nor union by rank alone yields the strongest standard bound. Their combination gives an amortized running time of

[ O!\left(m,\alpha(m,n)\right) ]

for a sequence of (m) operations applied to (n) elements, under the usual model in which the elements have first been introduced by make-set operations. The function (\alpha) is a two-parameter form of the inverse Ackermann function. A common simplified statement writes the bound as (O(m\alpha(n))).

The inverse Ackermann function grows more slowly than the iterated logarithm and remains a small integer for every input size arising in finite computation. The asymptotic statement nevertheless differs from a constant-time bound, because the function is unbounded. The result concerns amortized complexity: an individual find operation can traverse a comparatively long path, while the total cost of a sufficiently long operation sequence remains within the stated bound.

The analysis associates rank ranges with rapidly growing functions derived from the Ackermann function. When a parent reference is traversed, the ranks encountered increase strictly. Path compression limits how often an element can be charged for traversals within each rank range, while the definition of the ranges limits how many such categories can occur. The number of relevant categories is expressed by the inverse Ackermann function.

In the cell-probe model, Michael Fredman and Michael Saks established a matching lower bound for the disjoint-set problem under the corresponding assumptions. Thus, the inverse-Ackermann factor is not solely an artifact of the conventional forest analysis.

Historical development

Bernard A. Galler and Michael J. Fischer presented an early forest-based equivalence algorithm in 1964. Their formulation connected set merging with rooted-tree representations and incorporated weighted linking, an antecedent of the size and rank rules used in later implementations.

John Hopcroft and Jeffrey Ullman subsequently analyzed the interaction between linking rules and path shortening. Their 1973 treatment obtained an amortized bound involving the iterated logarithm, refining the earlier logarithmic analyses of tree height.

In 1975, Robert Endre Tarjan and You Watanabe developed the inverse-Ackermann amortized analysis for the combined use of rank-based linking and path compression. Their argument established the asymptotic form associated with the modern union–find structure and distinguished the total cost of an operation sequence from the worst-case cost of an isolated operation.

Later work clarified lower bounds, alternative computational models, and variants supporting additional information. These results placed the forest representation within the broader study of amortized analysis, where occasional expensive transformations are accounted for through their effects on subsequent operations.

Correctness properties

At every point in an execution, each tree corresponds to one block of the represented partition. Make-set introduces a new block without modifying existing blocks. Find observes the root of a tree and can change internal parent references, but it does not transfer any element between trees. Union combines exactly two blocks when their representatives differ and has no effect when both arguments already lie in the same block.

Path compression preserves rootedness because each modified parent reference points to an ancestor from the original search path. Since that ancestor has the same root as the modified vertex, the representative relation remains unchanged. Rank-based linking also preserves the partition because it changes only the parent reference of one root, thereby merging two complete trees.

The representative returned for a subset can change after a union. Algorithms using the structure therefore treat representatives as transient identifiers rather than stable names for mathematical sets. Information intended to describe an entire subset is commonly stored at its current root and transferred or combined when roots are linked.

Applications in graph algorithms

In Kruskal’s algorithm, every graph vertex initially belongs to a separate subset. Edges are considered in nondecreasing order of weight, and the endpoints of an edge are compared through find operations. An edge whose endpoints have different representatives joins two previously disconnected components, after which a union operation records their new connectivity. An edge whose endpoints already share a representative would create a cycle and is excluded from the spanning forest.

The same mechanism supports incremental connectivity in an undirected graph. Each inserted edge merges the components containing its endpoints, and a connectivity query reduces to comparing representatives. The ordinary structure does not support arbitrary edge deletion because its forest records component membership rather than the individual graph edges responsible for that membership. Fully dynamic connectivity therefore requires different structures or additional offline transformations.

Disjoint-set forests also occur in algorithms for connected-component labeling. Temporary labels assigned during a scan can denote regions later discovered to be equivalent. Union operations record these equivalences, while subsequent find operations replace temporary labels with representatives of the completed components.

An offline algorithm for the lowest common ancestor problem uses disjoint sets while traversing a rooted tree. Completed subtrees are merged with their parents, and representatives are associated with ancestors that answer previously registered queries. This application uses union–find to encode the progress of a traversal rather than connectivity in a changing graph.

Extensions and limitations

A disjoint-set structure can maintain aggregate metadata when the value for a merged subset is computable from the values stored for its two constituent subsets. The aggregate is retained at the root selected by the linking rule. Path compression does not disturb such root-based data, although information attached to nonroot parent edges requires additional update rules.

Rollback variants retain a history of parent and size changes so that earlier partition states can be restored. Ordinary full path compression modifies many parent references during a single find operation, which complicates this history. Rollback implementations therefore often use rank-based or size-based linking without unrestricted compression, producing logarithmic tree height while limiting the number of recorded changes.

The structure represents only partitions generated by mergers. It cannot directly divide one subset into two, and it does not retain a canonical record of the sequence of unions that produced the current state. Problems involving splits, deletions, or persistent access to many historical versions belong to broader areas of dynamic graph algorithms and persistent data structures.