Editing Disjoint-set data structure (section)

{{Short description|Data structure for storing non-overlapping sets}}
{{Infobox data structure
| name = Disjoint-set/Union-find Forest
| type = multiway tree
| invented_by = [[Bernard A. Galler]] and [[Michael J. Fischer]]
| invented_year = 1964|
| space_avg = {{math|''O''(''n'')}}<ref name="tarjan1975">{{cite journal|last1=Tarjan|first1=Robert Endre|author1-link=Robert E. Tarjan|year=1975|title=Efficiency of a Good But Not Linear Set Union Algorithm|journal=Journal of the ACM|volume=22|issue=2|pages=215&ndash;225|doi=10.1145/321879.321884|hdl=1813/5942|s2cid=11105749|hdl-access=free }}</ref>
| space_worst = {{math|''O''(''n'')}}<ref name="tarjan1975"/>
| search_avg = {{math|''O''(α(''n''))}}<ref name="tarjan1975"/> (amortized)
| search_worst = {{math|''O''(α(''n''))}}<ref name="tarjan1975"/> (amortized)
| insert_avg = {{math|''O''(1)}}<ref name="tarjan1975"/>
| insert_worst = {{math|''O''(1)}}<ref name="tarjan1975"/>
}}

In [[computer science]], a '''disjoint-set data structure''', also called a '''union–find data structure''' or '''merge–find set''', is a [[data structure]] that stores a collection of [[Disjoint sets|disjoint]] (non-overlapping) [[Set (mathematics)|sets]]. Equivalently, it stores a [[partition of a set]] into disjoint [[subset]]s. It provides operations for adding new sets, merging sets (replacing them with their [[Union (set theory)|union]]), and finding a representative member of a set. The last operation makes it possible to determine efficiently whether any two elements belong to the same set or to different sets.

While there are several ways of implementing disjoint-set data structures, in practice they are often identified with a particular implementation known as a '''disjoint-set forest'''. This specialized type of [[Forest (graph theory)|forest]] performs union and find operations in near-constant [[Amortized analysis|amortized time]]. For a sequence of {{mvar|m}} addition, union, or find operations on a disjoint-set forest with {{mvar|n}} nodes, the total time required is {{math|[[Big O notation|''O'']](''m''α(''n''))}}, where {{math|α(''n'')}} is the extremely slow-growing [[inverse Ackermann function]]. Although disjoint-set forests do not guarantee this time per operation, each operation rebalances the structure (via tree compression) so that subsequent operations become faster. As a result, disjoint-set forests are both [[asymptotically optimal]] and practically efficient.

Disjoint-set data structures play a key role in [[Kruskal's algorithm]] for finding the [[minimum spanning tree]] of a graph. The importance of minimum spanning trees means that disjoint-set data structures support a wide variety of algorithms. In addition, these data structures find applications in symbolic computation and in compilers, especially for [[register allocation]] problems.