Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Disjoint-set data structure
open-in-new
<p>In <a href="/facts/Computer_science/lN3pEyPz">computer science</a>, a disjoint-set data structure, also called a union–find data structure or merge–find set, is a <a href="/facts/Data_structure/yNsNvL1I">data structure</a> that stores a collection of <a href="/facts/Disjoint_sets/nLr8XRVd">disjoint</a> (non-overlapping) <a href="/facts/Set_(mathematics)/BfucfHMq">sets</a>. Equivalently, it stores a <a href="/facts/Partition_of_a_set/VeP9g8CA">partition of a set</a> into disjoint <a href="/facts/Subset/SJGERmbA">subsets</a>. It provides operations for adding new sets, merging sets (replacing them with their <a href="/facts/Union_(set_theory)/KVVXKfWl">union</a>), 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. </p><p>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 <a href="/facts/Forest_(graph_theory)/TCWk4Joy">forest</a> performs union and find operations in near-constant <a href="/facts/Amortized_analysis/9fFYenJz">amortized time</a>. For a sequence of m addition, union, or find operations on a disjoint-set forest with n nodes, the total time required is <a href="/facts/Big_O_notation/weFFjSWg"><i>O</i></a>(<i>m</i>α(<i>n</i>)), where α(<i>n</i>) is the extremely slow-growing <a href="/facts/Inverse_Ackermann_function/WQNpCWHn">inverse Ackermann function</a>. 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 <a href="/facts/Asymptotically_optimal/fnfvbMYE">asymptotically optimal</a> and practically efficient. </p><p>Disjoint-set data structures play a key role in <a href="/facts/Kruskal%2527s_algorithm/sg8v1BHB">Kruskal's algorithm</a> for finding the <a href="/facts/Minimum_spanning_tree/kgkGmY9s">minimum spanning tree</a> 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 <a href="/facts/Register_allocation/rB1vkhxU">register allocation</a> problems. </p>