Disjoint-set data structure

The MakeSet operation adds a new element. This element is placed into a new set containing only the new element, and the new set is added to the data structure. If the data structure is instead viewed as a partition of a set, then the MakeSet operation enlarges the set by adding the new element, and it extends the existing partition by putting the new element into a new subset containing only the new element.

In a disjoint-set forest, MakeSet initializes the node's parent pointer and the node's size or rank. If a root is represented by a node that points to itself, then adding an element can be described using the following pseudocode:

function MakeSet(x) is
    if x is not already in the forest then
        x.parent := x
        x.size := 1     // if nodes store size
        x.rank := 0     // if nodes store rank
    end if
end function

This operation has constant time complexity. In particular, initializing a disjoint-set forest with n nodes requires O(n) time.

In practice, MakeSet must be preceded by an operation that allocates memory to hold x. 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.

The Find operation follows the chain of parent pointers from a specified query node x until it reaches a root element. This root element represents the set to which x belongs and may be x itself. Find returns the root element it reaches.

Performing a Find operation presents an important opportunity for improving the forest. The time in a Find operation is spent chasing parent pointers, so a flatter tree leads to faster Find operations. When a Find is executed, there is no faster way to reach the root than by following each parent pointer in succession. However, the parent pointers visited during this search can be updated to point closer to the root. Because every element visited on the way to a root is part of the same set, this does not change the sets stored in the forest. But it makes future Find operations faster, not only for the nodes between the query node and the root, but also for their descendants. This updating is an important part of the disjoint-set forest's amortized performance guarantee.

There are several algorithms for Find that achieve the asymptotically optimal time complexity. One family of algorithms, known as path compression, makes every node between the query node and the root point to the root. Path compression can be implemented using a simple recursion as follows:

function Find(x) is
    if x.parent ≠ x then
        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 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.[4] 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

The operation Union(x, y) replaces the set containing x and the set containing y with their union. Union first uses Find to determine the roots of the trees containing x and y. If the roots are the same, there is nothing more to do. Otherwise, the two trees must be merged. This is done by either setting the parent pointer of x to y, or setting the parent pointer of y to x.

The choice of which node becomes the parent has consequences for the complexity of future operations on the tree. If it is done carelessly, trees can become excessively tall. For example, suppose that Union always made the tree containing x a subtree of the tree containing y. Begin with a forest that has just been initialized with elements 1, 2, 3, ..., n, and execute Union(1, 2), Union(2, 3), ..., Union(n − 1, n). The resulting forest contains a single tree whose root is n, and the path from 1 to n passes through every node in the tree. For this forest, the time to run Find(1) is O(n).

In an efficient implementation, tree height is controlled using union by size or union by rank. Both of these require that a node store information besides just its parent pointer. This information is used to decide which root becomes the new parent. Both strategies ensure that trees do not become too deep.

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 x and y 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, rename variables to ensure that
    // x has at least as many descendants as y
    if x.size < y.size then
        (x, y) := (y, x)
    end if

    // Make x the new root
    y.parent := x
    // Update the size of x
    x.size := x.size + y.size
end function

The number of bits necessary to store the size is clearly the number of bits necessary to store n. This adds a constant factor to the forest's required storage.

For union by rank, a node stores its rank, which is an upper bound for its height. When a node is initialized, its rank is set to zero. To merge trees with roots x and y, first compare their ranks. If the ranks are different, then the larger rank tree becomes the parent, and the ranks of x and y do not change. If the ranks are the same, then either one can become the parent, but the new parent's rank is incremented by one. While the rank of a node is clearly related to its height, storing ranks is more efficient than storing heights. The height of a node can change during a 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 < y.rank then
        (x, y) := (y, x)
    end if

    // Make x the new root
    y.parent := x
    // If necessary, increment the rank of x
    if x.rank = y.rank then
        x.rank := x.rank + 1
    end if
end function

It can be shown that every node has rank ⌊lg n⌋ or less.[10] Consequently the rank can be stored in O(log log n) bits, making it 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.

The precise analysis of the performance of a disjoint-set forest is somewhat intricate. However, there is a much simpler analysis that proves that the amortized time for any m Find or Union operations on a disjoint-set forest containing n objects is O(log^* n), where log^* denotes the iterated logarithm.[11][12][13][14]

Lemma 1: As the find function follows the path along to the root, the rank of node it encounters is increasing.

Proof: claim that as Find and Union operations are applied to the data set, this fact remains true over time. Initially when each node is the root of its own tree, it's trivially true. The only case when the rank of a node might be changed is when the Union by Rank operation is applied. In this case, a tree with smaller rank will be attached to a tree with greater rank, rather than vice versa. And during the find operation, all nodes visited along the path will be attached to the root, which has larger rank than its children, so this operation won't change this fact either.

Lemma 2: A node u which is root of a subtree with rank r has at least 2^r nodes.

Proof: Initially when each node is the root of its own tree, it's trivially true. Assume that a node u with rank r has at least 2^r nodes. Then when two trees with rank r Union by Rank and form a tree with rank r + 1, the new node has at least 2^r + 2^r = 2^{r + 1} nodes.

Lemma 3: The maximum number of nodes of rank r is at most n/2^r.

Proof: From lemma 2, we know that a node u which is root of a subtree with rank r has at least 2^r nodes. We will get the maximum number of nodes of rank r when each node with rank r is the root of a tree that has exactly 2^r nodes. In this case, the number of nodes of rank r is n/2^r

For convenience, we define "bucket" here: a bucket is a set that contains vertices with particular ranks.

We create some buckets and put vertices into the buckets according to their ranks inductively. That is, vertices with rank 0 go into the zeroth bucket, vertices with rank 1 go into the first bucket, vertices with ranks 2 and 3 go into the second bucket. If the Bth bucket contains vertices with ranks from interval [r, 2^r − 1] = [r, R - 1] then the (B+1)st bucket will contain vertices with ranks from interval [R, 2^R − 1].

Proof of ${\displaystyle O(\log ^{*}n)}$ Union Find

We can make two observations about the buckets.

1. The total number of buckets is at most log^*n

   Proof: When we go from one bucket to the next, we add one more two to the power, that is, the next bucket to [B, 2^B − 1] will be [2^B, 2^2B − 1]

2. The maximum number of elements in bucket [B, 2^B – 1] is at most 2n/2^B

   Proof: The maximum number of elements in bucket [B, 2^B – 1] is at most n/2^B + n/2^B+1 + n/2^B+2 + … + n/2^{2B – 1} ≤ 2n/2^B

Let F represent the list of "find" operations performed, and let

${\displaystyle T_{1}=\sum _{F}{\text{(link to the root)}}}$

${\displaystyle T_{2}=\sum _{F}{\text{(number of links traversed where the buckets are different)}}}$

${\displaystyle T_{3}=\sum _{F}{\text{(number of links traversed where the buckets are the same).}}}$

Then the total cost of m finds is T = T₁ + T₂ + T₃

Since each find operation makes exactly one traversal that leads to a root, we have T₁ = O(m).

Also, from the bound above on the number of buckets, we have T₂ = O(mlog^*n).

For T₃, suppose we are traversing an edge from u to v, where u and v have rank in the bucket [B, 2^B − 1] and v is not the root (at the time of this traversing, otherwise the traversal would be accounted for in T₁). Fix u and consider the sequence v₁,v₂,...,v_k that take the role of v 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 k of the sequence (the number of times node u is attached to a different root in the same bucket) is at most the number of ranks in the buckets B, i.e. at most 2^B − 1 − B < 2^B.

Therefore, ${\displaystyle T_{3}\leq \sum _{[B,2^{B}-1]}\sum _{u}2^{B}.}$

From Observations 1 and 2, we can conclude that ${\displaystyle T_{3}\leq \sum _{B}2^{B}{\frac {2n}{2^{B}}}\leq 2n\log ^{*}n.}$

Therefore, T = T₁ + T₂ + T₃ = O(m log^*n).