Disjoint-set data structure: Difference between revisions

Revision as of 19:34, 9 November 2024

Revision as of 21:28, 11 December 2024

Line 13:

}}

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 bywith their [[Union (set theory)|union]]), and finding a representative member of a set. The last operation makes it possible to find outdetermine efficiently ifwhether any two elements arebelong into 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 called a '''disjoint-set forest'''. This is a specialized type of [[Forest (graph theory)|forest]] which performs unions and finds in near-constant [[Amortized analysis|amortized time]]. To perform a sequence of {{mvar|m}} addition, union, or find operations on a disjoint-set forest with {{mvar|n}} nodes requires total time {{math|[[Big O notation|''O'']](''m''α(''n''))}}, where {{math|α(''n'')}} is the extremely slow-growing [[inverse Ackermann function]]. Disjoint-set forests do not guarantee this performance on a per-operation basis. Individual union and find operations can take longer than a constant times {{math|α(''n'')}} time, but each operation causes the disjoint-set forest to adjust itself so that successive operations are faster. Disjoint-set forests are both [[asymptotically optimal]] and practically efficient.