Disjoint-Set Union Complexity

This section is reproduced and adapted from Time Complexity — A Brief Discussion of Potential Analysis, with the original author's permission.

Definitions

The Ackermann Function

We first define $\alpha(n)$. To give this definition, we first define $A_k(j)$.

Define $A_k(j)$ as follows:

$$A_k(j)=\left\{ \begin{aligned} &j+1& &k=0&\\ &A_{k-1}^{(j+1)}(j)& &k\geq1& \end{aligned} \right.$$

That is, the Ackermann function.

Here, $f^i(x)$ denotes applying $f$ to $x$ consecutively $i$ times; that is, $f^0(x)=x$ and $f^i(x)=f(f^{i-1}(x))$.

Now define $\alpha(n)$ as the smallest integer such that $A_{\alpha(n)}(1)\geq n$. Note that we previously described it as $A_{\alpha(n)}(\alpha(n))\geq n$; in any case, they grow so slowly that their values do not exceed 4.

Basic Definitions

Every node has a rank. Here rank does not mean the number of nodes, but the depth. The initial rank of a node is 0. During a merge, if two nodes have different ranks, merge the lower-rank node into the higher-rank node without updating the higher-rank node's rank. Otherwise, randomly merge one node into the other and increase the root's rank by 1. The rank of the root gives the height of the tree. Let the rank of x be $rnk(x)$, and similarly let the parent of x be $fa(x)$. We always have $rnk(x)+1\leq rnk(fa(x))$.

To define the potential function, we first need to define an auxiliary function $level(x)$. Let $level(x)=\max(k:rnk(fa(x))\geq A_k(rnk(x)))$. When $rnk(x)\geq1$, also define an auxiliary function $iter(x)=\max(i:rnk(fa(x))\geq A_{level(x)}^i(rnk(x))$. The $x$ covered by these definitions always satisfies $rnk(x)>0$ and this $x$ is not the root of a tree.

The definitions above may be a little dizzying. Let us sort them out. For an $x$ and $fa(x)$, if $rnk(x)>0$, we can always find a pair $i,k$ such that $rnk(fa(x))\geq A_k^i(rnk(x))$, while $level(x)=\max(k)$ and, under this premise, $iter(x)=\max(i)$. $level$ describes the maximum iteration level of $A$, while $iter$ describes the maximum number of iterations at that maximum level.

For these two functions, $level(x)$ always increases or remains unchanged as operations proceed. If $level(x)$ does not increase, $iter(x)$ also only increases or remains unchanged. They always satisfy the following two inequalities:

$$0\leq level(x)<\alpha(n)$$ $$1\leq iter(x)\leq rnk(x)$$

Considering the definitions of $level(x)$, $iter(x)$, and $A_k^j$, these facts are easy to prove; we leave them to the reader as practice with the definitions.

Define the potential function $\Phi(S)=\sum\limits_{x\in S}\Phi(x)$, where $S$ denotes an entire disjoint-set union and $x$ is a node in the disjoint-set union. Define $\Phi(x)$ as follows:

$$\Phi(x)= \begin{cases} \alpha(n)\times \mathit{rnk}(x)& \mathit{rnk}(x)=0\ \text{或}\ x\ \text{为某棵树的根节点}\\ (\alpha(n)-\mathit{level}(x))\times \mathit{rnk}(x)-iter(x)& \text{otherwise} \end{cases}$$

We can now prove that the amortized time complexity is $\Theta(\alpha(n))$ through the change in potential caused by operations. Note that the $union(x,y)$ operation considered here guarantees that $x$ and $y$ are both roots of trees, so it does not need to additionally execute $find(x)$ and $find(y)$.

It can be seen that the potential is always nonnegative. Also, at the beginning, the potential of the disjoint-set union is $0$.

Proof

The union(x,y) Operation

Its cost is $\Theta(1)$, so we consider the change in potential that it causes.

Here, assume $rnk(x)\leq rnk(y)$, meaning that $x$ is attached to $y$. Thus, the only nodes whose potential increases are $x$ (which changes from a tree root to a non-root), $y$ (whose rank may increase), and the children of $y$ before the operation (whose parent's rank may increase). We first prove that the potential of a child $c$ of $y$ before the operation cannot increase, and if it decreases, it decreases by at least $1$.

Let the potential of $c$ before the operation be $\Phi(c)$ and after the operation be $\Phi(c')$. Here $c$ can be any non-root node with $rnk(c)>0$, and the operation can be any operation, including the find operation below. We discuss four cases.

1. $iter(c)$ and $level(c)$ do not increase. Clearly, $\Phi(c)=\Phi(c')$.
2. $iter(c)$ increases while $level(c)$ does not. Here $iter(c)$ increases by at least one, so $\Phi(c')\leq \Phi(c)-1$; the potential decreases by at least 1.
3. $level(c)$ increases, while $iter(c)$ may decrease. Since $0<iter(c)\leq rnk(c)$, $iter(c)$ can decrease by at most $rnk(c)-1$, while $level(c)$ increases by at least $1$. By the definition $\Phi(c)=(\alpha(n)-level(c))\times rnk(c)-iter(c)$, we obtain $\Phi(c')\leq\Phi(c)-1$.
4. Any other case. Since $rnk(c)$ does not change and $rnk(fa(c))$ does not decrease, this case cannot occur.

Therefore, the only nodes whose potential can increase are $x$ and $y$. When $x$ changes from a tree root to a non-root, if $rnk(x)=0$, then $\Phi(x)=\Phi(x')=0$ always. Otherwise, we always have $\alpha(x)\times rnk(x)\geq(\alpha(n)-level(x))\times rnk(x)-iter(x)$. Hence, $\Phi(x')\leq \Phi(x)$.

Thus, the only point whose potential may increase is $y$. The potential of $y$ can increase by at most $\alpha(n)$. Therefore, the amortized time complexity of the $union$ operation is $\Theta(\alpha(n))$.

The find(a) Operation

If the search path contains $\Theta(s)$ nodes, its search time complexity is clearly $\Theta(s)$. If the find operation increases the potential of no node and decreases the potential of at least $s-\alpha(n)$ nodes by at least $1$, then it can be proved that the amortized time complexity of $find(a)$ is $\Theta(\alpha(n))$. To avoid confusion, we use $a$ as the parameter here, while every $x$ that appears refers generically to a node in a disjoint-set union.

First, prove that no node's potential increases. It is obvious: as proved above, the potential of every non-root node does not increase, and the rank $rnk$ of a root does not change, so no node's potential increases.

Next, prove that the potential of at least $s-\alpha(n)$ nodes decreases by at least $1$. We proved above that if $level(x)$ or $iter(x)$ changes, their potential decreases by at least $1$. Thus, it is enough to prove that $level(x)$ or $iter(x)$ changes for at least $s-\alpha(n)$ nodes.

Recall the definition of the potential of a non-root node, $\Phi(x)=(\alpha(n)-level(x))\times rnk(x)-iter(x)$, where $level(x)$ and $iter(x)$ are the maximum values such that $rnk(fa(x))\geq A_{level(x)}^{iter(x)}(rnk(x))$.

Therefore, if $root_x$ represents the root of the tree containing $x$, it is enough to prove that $rnk(root_x)\geq A_{level(x)}^{iter(x)+1}(rnk(x))$. By the definition of $A_k^i$, $A_{level(x)}^{iter(x)+1}(rnk(x))=A_{level(x)}(A_{level(x)}^{iter(x)}(rnk(x)))$.

We may use $k(x)$ to represent $level(x)$ and $i(x)$ to represent $iter(x)$ to avoid making the formulas too long. In this notation, $rnk(root_x)\geq A_{k(x)}(A_{k(x)}^{i(x)}(x))$.

When you reach this point, you may feel like “what on earth is this?”. This means that you may need to read it several more times, or skip some of the content and return later.

Here, we need an outer $A_{k(x)}$, which means that we may need to find another point $y$. Let $y$ be the point after $x$ on the search path that satisfies $k(y)=k(x)$; here, “after the search path” is equivalent to “an ancestor of $x$”. Clearly, not every $x$ has such a $y$. It is easy to prove that there are at most $\alpha(n)+2$ values of $x$ without such a $y$, because only the last $x$ for each $k$, along with $a$ and $root_a$, has no such $y$.

Let us emphasize once again that $fa(x)$ refers to the parent of $x$ before path compression; after path compression, the parent of $x$ is always denoted by $root_x$. For every $x$ for which $y$ exists, we have $rnk(y)\geq rnk(fa(x))$. At the same time, we have $rnk(fa(x))\geq A_{k(x)}^{i(x)}(rnk(x))$. Since $k(x)=k(y)$, use $k$ as shorthand for both; that is, $rnk(fa(x))\geq A_k^{i(x)}(rnk(x))$. We need to construct one $A_k$, so we can ignore the value of $iter(y)$ and directly use the weakened form $rnk(fa(y))\geq A_k(rnk(y))$.

If we combine the inequalities, something magical happens. We find that $rnk(fa(y))\geq A_k^{i(x)+1}(rnk(x))$. In other words, to iterate from $rnk(x)$ to $rnk(fa(y))$, we can iterate $A_k$ at least $i(x)+1$ times without exceeding $rnk(fa(y))$.

Clearly, $rnk(root_y)\geq rnk(fa(y))$, and $rnk(x)$ does not change during path compression. Therefore, we obtain $rnk(root_x)\geq A_k^{i(x)+1}(rnk(x))$. In other words, the value of $iter(x)$ increases by at least 1; if $rnk(x)$ does not increase, then $level(x)$ must increase.

Therefore, $\Phi(x)$ decreases by at least 1. Since there are at least $s-\alpha(n)-2$ such $x$ nodes, $\Phi(S)$ ultimately decreases by at least $s-\alpha(n)-2$, and the amortized time complexity is therefore $\Theta(\alpha(n)+2)=\Theta(\alpha(n))$.

Why Disjoint-Set Union Can Be Broken

This question is asking what properties are destroyed if we do not use union by rank, causing the time complexity of disjoint-set union to no longer be guaranteed to be $\Theta(m\alpha(n))$.

If, during merging, the node with larger $rnk$ is merged into the node with smaller $rnk$, we set the $rnk$-smaller node's $rnk$ value to the other node's $rnk$ value plus one. This guarantees $rnk(fa(x))\geq rnk(x)+1$, so we avoid a situation where the properties fail in a way resembling a floor covered in compile errors.

Clearly, in this case, what we break is the statement in the $union(x,y)$ function that “the potential of y can increase by at most $\alpha(n)$”.

There is a structure that can reduce the time complexity of path-compressed disjoint-set union to $\Omega(m\log_{1+\frac{m}{n}}n)$, defined as follows:

A binomial tree (which is actually somewhat different from an ordinary binomial tree), where j is a constant and $T_k$ consists of a $T_{k-1}$ with a $T_{k-j}$ added as a child of its root.

The boundary condition is that $T_1$ through $T_j$ are each a single point.

Let $rnk(T_k)=r_k$. Here we have $r_k=(k-1)/j$ (proof omitted). In each round of operations, we attach it to a single-node tree and then query the bottom $j$ nodes. In other words, when we attach it to the single node, the potential of the single node increases by $(k-1)/j+1$. When $j=\lfloor\frac{m}{n}\rfloor$, $i=\lfloor\log_{j+1}\frac{n}{2}\rfloor$, and $k=ij$, the increase in potential is:

$$\alpha(n)\times((ij-1)/j+1)=\alpha(n)\times((\lfloor\log_{\lfloor\frac{m}{n}\rfloor+1}\frac{n}{2}\rfloor\times \lfloor\frac{m}{n}\rfloor-1)/\lfloor\frac{m}{n}\rfloor+1)$$

After transforming this and removing all floor symbols, we obtain an increase in potential of $\geq \alpha(n)\times(\log_{1+\frac{m}{n}}n-\frac{n}{m})$. Over m operations, this is $\Omega(m\log_{1+\frac{m}{n}}n-n)=\Omega(m\log_{1+\frac{m}{n}}n)$.

About Union by Size

Since union by rank is harder to write than union by size, many experts choose to use union by size when implementing disjoint-set union. Specifically, maintain a $size(x)$ for each root, and each time merge the smaller $size$ into the larger one.

So, can union by size be broken?

First, this can be explained from the properties of rank used in the proof. If $size$ can replace $rnk$, then union by size can be used. To summarize, the properties involving rank in the proof are the following three:

1. At most one node's rank increases on each merge, and it increases by at most 1.
2. We always have $rnk(fa(x))\geq rnk(x)+1$.
3. A node's rank never decreases.

The second and third properties are clearly satisfied by $siz$, but the first is not: if $x$ is merged into $y$, then $siz(y)$ increases by as much as $siz(x)$.

Therefore, we can consider using $\log_2 siz(x)$ in place of $rnk(x)$.

For the first property, since a node's $siz$ can increase by at most a factor of two, $\log_2 siz(x)$ increases by at most 1. The conclusion for the second and third properties is fairly obvious, so their proofs are omitted.

Thus, if you do not want to implement union by rank, just use union by size; the time complexity remains $\Theta(m\alpha(n))$.