Skip to content

Disjoint-Set Data Structure

Maintain a mutable partition under Make-Set, Find, and Union, typically with representative-rooted forests, union by rank or size, and path compression for inverse-Ackermann amortized time.

Version
v2 · 2026-09-06 · History
Domain-specific #
1691
Origin domain
computer science
Subdomain
data structures
Aliases
Union–find, Union-find data structure, Merge–find set, Disjoint-set union, DSU

Core Idea

A disjoint-set data structure maintains a partition of elements into pairwise-disjoint sets. Make-Set(x) creates a singleton, Find(x) returns a representative of the unique block containing \(x\), and Union(x,y) merges the two blocks when distinct. The standard disjoint-set forest represents each block as a rooted tree; union by rank/size limits height and path compression rewires search paths toward the root.[1]

The recognition invariant is mutable partition + stable representative equivalence test + union-only coarsening + forest heuristics + amortized efficiency.

Structural Signature

  • A universe of registered elements.
  • A current partition into disjoint blocks.
  • One representative per block.
  • Make-Set, Find, and Union operations.
  • Membership equivalence tested by representative equality.
  • Union-only evolution: blocks merge but do not split in the classic structure.
  • Parent-pointer forest implementation.
  • Roots serving as representatives.
  • Union by rank or size.
  • Path compression during Find.
  • Structural mutations preserving partition semantics.
  • Near-constant inverse-Ackermann amortized complexity for standard operation sequences.
  • Applications requiring incremental connectivity/equivalence.

What It Is Not

It is not set union as a mathematical operation alone, nor a static partition. It is an abstract data type plus implementations maintaining partitions under updates. The disjoint-set forest is the standard implementation, not the only possible realization.[2]

Classic union–find does not support deletion, splitting blocks, arbitrary rollback, or fully dynamic connectivity without extensions. Path compression also changes the internal forest while preserving the represented partition.

Scope of Application

Union–find supports Kruskal’s minimum-spanning-tree algorithm, incremental graph connectivity, connected-component labeling, equivalence-class computation, unification-like tasks, image processing, percolation simulation, and offline least-common-ancestor algorithms.

It excels when the required relation only coarsens. If connectivity edges are deleted or equivalence decisions must be undone, another structure or explicit rollback/persistence scheme is needed.

Clarity

Representatives are identifiers, not necessarily canonical semantic elements. Different union orders and heuristics can select different roots while representing the same partition. Correctness depends on equivalence classes, not on one particular forest shape.

The inverse-Ackermann bound is amortized over a sequence, not a worst-case constant guarantee for each individual operation. Its practical smallness does not make the mathematical distinction disappear.[3]

Manages Complexity

The structure avoids storing each block as a repeatedly copied set. It maintains enough indirection to answer same-block queries and merge blocks cheaply. Path compression invests work during Find to accelerate later operations; rank/size prevents pathological growth during Union.

Abstract Reasoning

  1. Initialize every element as a singleton.
  2. Maintain one parent pointer per forest node.
  3. Follow parents to locate a representative.
  4. Compress the traversed path without changing membership.
  5. Before union, find both roots.
  6. If different, link the lower-rank/smaller tree under the other and update metadata.
  7. Prove that every element has one root and blocks remain disjoint.
  8. Analyze sequences amortized, not operations in isolation.
  9. Reject the classic structure when splits or deletions are required.

Knowledge Transfer

The portable structure is representing an evolving equivalence relation by delegated representatives and cheap irreversible merges. The proposed immediate parent is Data Structure.

Examples

Kruskal. Before adding an edge, compare endpoint representatives; unequal roots mean the edge joins two components, after which the blocks are unioned.

Equivalence declarations. Repeatedly union declared-equal objects, then use Find to enumerate equivalence classes.[4]

Non-example. A graph structure supporting arbitrary edge deletion is not handled by classic union–find alone.

Structural Tensions

  • Abstract partition semantics versus mutable forest shape.
  • Fast amortized sequences versus per-operation worst case.
  • Representative convenience versus canonical identity.
  • Compression speed versus rollback/persistence.
  • Union-only simplicity versus fully dynamic requirements.
  • Theoretical inverse-Ackermann analysis versus practical near-constancy.

Structural–Framed Character

Partition maintenance, representation delegation, irreversible merging, and amortization are structural. Parent arrays, rank, path compression, graph connectivity, and algorithm bounds are computer-science frame.

Structural Core vs. Domain Accent

The portable core is maintaining equivalence classes through representative-based merges. The constitutive accent is the Make/Find/Union contract, forest implementation, heuristics, and complexity analysis.

Data Structure is the proposed immediate parent. Partition, Union, Disjointness, Equivalence, Indirection, Compression, and Amortization are related.

The prospective queue contains one strict edge to prime:data_structure. No live DAG mutation is authorized.

Relationships to Other Abstractions

Local relationship map for Disjoint-Set Data StructureParents appear above the current abstraction, mutual partners to the right, and children below. Node labels state whether each abstraction is prime or domain-specific; colors identify relation types.Disjoint-SetData StructureDOMAINPrime abstraction: Data Structure — is a kind ofData StructurePRIME

Current abstraction Disjoint-Set Data Structure Domain-specific

Parents (1) — more general patterns this builds on

  • Disjoint-Set Data Structure is a kind of Data Structure Prime

    Data Structure is the proposed immediate parent.

Hierarchy path (1) — routes to 1 parentless root

Neighborhood in Abstraction Space

Disjoint-Set Data Structure sits in a sparse region of the domain-specific corpus (83rd percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.

Family — Discrete Structures & Graph Algorithms (17 abstractions)

Nearest neighbors

Computed from structural-signature embeddings · 2026-09-08

Not to Be Confused With

  • Mathematical set union.
  • Static partition data.
  • General graph data type.
  • Strongly connected components algorithm.
  • Fully dynamic connectivity.
  • A representative treated as semantic canonical value.
  • Worst-case constant time per operation.

References

[1] Bernard A. Galler and Michael J. Fischer, “An Improved Equivalence Algorithm,” Communications of the ACM 7 (1964): 301–303. registry ↩

[2] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, Introduction to Algorithms, 4th ed., MIT Press, 2022. registry ↩a ↩b

[3] Robert E. Tarjan, “Efficiency of a Good But Not Linear Set Union Algorithm”, Journal of the ACM 22 (1975): 215–225. registry ↩

[4] Harold N. Gabow and Robert E. Tarjan, “A Linear-Time Algorithm for a Special Case of Disjoint Set Union,” Journal of Computer and System Sciences 30 (1985): 209–221. registry ↩