Disjoint-set data structure
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 (non-overlapping) sets.
≈ 11 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
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 (non-overlapping) sets. Equivalently, it stores a partition of a set into disjoint subsets.
It provides operations for adding new sets, merging sets (replacing them with their 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 performs union and find operations in near-constant amortized time.
For a sequence of addition, union, or find operations on a disjoint-set forest with nodes, the total time required is , where 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.…
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 (non-overlapping) sets. Equivalently, it stores a partition of a set into disjoint subsets.
It provides operations for adding new sets, merging sets (replacing them with their 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 performs union and find operations in near-constant amortized time.
For a sequence of addition, union, or find operations on a disjoint-set forest with nodes, the total time required is , where 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. x.parent := x x.size := 1 // if nodes store size x.rank := 0 // if nodes store rank end if end function This operation has linear time complexity. In particular, initializing a disjoint-set forest with nodes requires time.
Lack of a parent assigned to the node implies that the node is not present in the forest. In practice, MakeSet must be preceded by an operation that allocates memory to hold .
As long as memory allocation is an amortized constant-time operation, as it is for a good dynamic array implementation, it does not change the asymptotic performance of the random-set forest. x.parent := Find(x.parent) return x.parent else return x end if end function This implementation makes two passes, one up the tree and one back down. It requires enough scratch memory to store the path from the query node to the root (in the above pseudocode, the path is implicitly represented using the call stack).
This can be decreased to a constant amount of memory by performing both passes in the same direction. The constant memory implementation walks from the query node to the root twice, once to find the root and once to update pointers: function Find(x) is root := x while root.parent ≠ root do root := root.parent end while while x.parent ≠ root do parent := x.parent x.parent := root x := parent end while return root end function Tarjan and Van Leeuwen also developed one-pass Find algorithms that retain the same worst-case complexity but are more efficient in practice.
These are called path splitting and path halving. Both of these update the parent pointers of nodes on the path between the query node and the root.
Path splitting replaces every parent pointer on that path by a pointer to the node's grandparent: function Find(x) is while x.parent ≠ x do (x, x.parent) := (x.parent, x.parent.parent) end while return x end function Path halving works similarly but replaces only every other parent pointer: function Find(x) is while x.parent ≠ x do x.parent := x.parent.parent x := x.parent end while return x end function
Union by size
In the case of union by size, a node stores its size, which is simply its number of descendants (including the node itself). When the trees with roots and are merged, the node with more descendants becomes the parent. If the two nodes have the same number of descendants, then either one can become the parent.
In both cases, the size of the new parent node is set to its new total number of descendants. function Union(x, y) is // Replace nodes by roots x := Find(x) y := Find(y) if x = y then return // x and y are already in the same set end if // If necessary, swap variables to ensure that // x has at least as many descendants as y if x.size Find operation, so storing ranks avoids the extra effort of keeping the height correct. In pseudocode, union by rank is: function Union(x, y) is // Replace nodes by roots x := Find(x) y := Find(y) if x = y then return // x and y are already in the same set end if // If necessary, rename variables to ensure that // x has rank at least as large as that of y if x.rank \lfloor \log n \rfloor or less.
Consequently, each rank can be stored in bits and all the ranks can be stored in bits. This makes the ranks an asymptotically negligible portion of the forest's size. It is clear from the above implementations that the size and rank of a node do not matter unless a node is the root of a tree.
Once a node becomes a child, its size and rank are never accessed again. There is a variant of the Union operation in which the user determines the representative of the formed set. It is not hard to add this functionality to the above algorithms without losing efficiency.
In general, if the -th bucket contains vertices with ranks from interval \left[r, 2^r - 1\right] = [r, R - 1] , then the (B+1)st bucket will contain vertices with ranks from interval \left[R, 2^R - 1\right]. For B \in \mathbb{N} , let \text{tower}(B) = \underbrace{2^{2^{\cdots^2}}}_{B \text{ times}} .
Then bucket B will have vertices with ranks in the interval [\text{tower}(B-1), \text{tower}(B)-1] . We can make two observations about the buckets' sizes. The total number of buckets is at most .
Proof: Since no vertex can have rank greater than n , only the first \log^* (n) buckets can have vertices, where \log^* denotes the inverse of the \text{tower} function defined above. The maximum number of elements in bucket \left[B, 2^B - 1\right] is at most \frac{2n}{2^B} .
Proof: The maximum number of elements in bucket \left[B, 2^B - 1\right] is at most \frac{n}{2^B} + \frac{n}{2^{B+1}} + \frac{n}{2^{B+2}} + \cdots + \frac{n}{2^{2^B - 1}} \leq \frac{2n}{2^B}. Let represent the list of "find" operations performed, and let T_1 = \sum_F\text{(link to the root)} T_2 = \sum_F\text{(number of links traversed where the buckets are different)} T_3 = \sum_F\text{(number of links traversed where the buckets are the same).} Then the total cost of finds is T = T_1 + T_2 + T_3.
Since each find operation makes exactly one traversal that leads to a root, we have . Also, from the bound above on the number of buckets, we have . For , suppose we are traversing an edge from to , where and have rank in the bucket and is not the root (at the time of this traversing, otherwise the traversal would be accounted for in ).
Fix and consider the sequence v_1, v_2, \ldots, v_k that take the role of in different find operations. Because of path compression and not accounting for the edge to a root, this sequence contains only different nodes and because of Lemma 1 we know that the ranks of the nodes in this sequence are strictly increasing.
By both of the nodes being in the bucket we can conclude that the length of the sequence (the number of times node is attached to a different root in the same bucket) is at most the number of ranks in the buckets , that is, at most 2^B - 1 - B Therefore, T_3 \leq \sum_{[B, 2^B - 1]} \sum_u 2^B. From Observations 1 and 2, we can conclude that T_3 \leq \sum_{B} 2^B \frac{2n}{2^B} \leq 2 n \log^* n. Therefore, T = T_1 + T_2 + T_3 = O(m \log^*n).
Better worst-case time per operation
The worst-case time of the Find operation in trees with Union by rank or Union by weight is \Theta(\log n) (i.e., it is O(\log n) and this bound is tight). In 1985, N. Blum gave an implementation of the operations that does not use path compression, but compresses trees during union .
His implementation runs in O(\log n / \log\log n) time per operation, and thus in comparison with Galler and Fischer's structure it has a better worst-case time per operation, but inferior amortized time. In 1999, Alstrup et al. gave a structure that has optimal worst-case time O(\log n / \log\log n) together with inverse-Ackermann amortized time.
Deletion
The regular implementation as disjoint-set forests does not react favorably to the deletion of elements, in the sense that the time for Find will not improve as a result of the decrease in the number of elements. However, there exist modern implementations that allow for constant-time deletion and where the time-bound for Find depends on the current number of elements
Backtracking
It is possible to extend certain disjoint-set forest structures to allow backtracking. The basic form of backtracking is to allow a Backtrack(1) operation, that undoes the last Union . A more advanced form allows Backtrack(i) , which undoes the last i unions.
The following complexity result is known: there is a data structure which supports Union and Find in O(\log n / \log \log n) time per operation, and Backtrack in O(1) time. In this result, the freedom of Union to choose the representative of the formed set is essential. Better amortized time cannot be achieved within the class of separable pointer algorithms.
Text derived from https://en.wikipedia.org/w/index.php?oldid=1378824711 under CC BY-SA 4.0; modifications have been made.