# How to analyze the worst case of weighted quick-union method on union-find

Here is exercise 1.5.15 in Algorithms 4th Edition by Robert Sedgewick and Kevin Wayne.

Show that the number of nodes at each level in the worst-case trees for weighted quick-union are binomial coefficients. Compute the average depth of a node in a worst-case tree with $$k = 2^n$$ nodes.

Here are my questions:

1) What is the worst-case tree for weighted quick union?

2) How I compute the average depth of a node in this worst-case tree with $$2^n$$ nodes?

I tried to show through induction that the number of nodes at each level for the worst-case tree in weighted quick-union are binomial coefficients (the first level has $$\frac{1!}{0!(1-0)!} = 1$$ node). From there I tried to think about how, generally, there are at most $$\frac{n!}{r!(n-r)!}$$ nodes at the next level. However, I'm unable to think of reasons as to how this makes sense.

Any help with this question is appreciated.

• What have you tried? Where did you get stuck? Please include any work you have done so far. Dec 16 '18 at 9:01
• That problem is somewhat misleading in the sense that binomial coefficients might be not true when the worst case tree has, for example, 6 nodes. It is only true when the number of nodes is $2^n$. Dec 16 '18 at 17:02
• @Apass.Jack I think we're supposed to assume that the tree has $2^n$ nodes. If you could provide some assistance in how to devise a proof for a weighted quick-union tree of $2^n$ nodes, then that would be great. Dec 16 '18 at 17:10

We will use without a proof the following claim that appears in the "Weighted quick-union analysis" of section "1.5 CASE STUDY: UNION-FIND" of the book.

Claim of (strong) worst case: the worst case for weighted quick-union happens when the sizes of the trees to be merged by union() are always equal (and a power of 2).

Define tree $$W_n$$ recursively. $$W_0$$ is the tree with one node whose component root is itself. $$W_{n+1}$$ is the tree obtained by combining two $$W_n$$ using the union procedure. According to the above claim, a worse case is $$W_n$$ for some $$n$$. Let $$D(T)$$ be the average depth of a node in a rooted tree $$T$$.

(Structure of $$W_n$$) $$W_n$$ has $$2^n$$ nodes in total and $$\binom ni$$ nodes at level $$i$$ for $$0\le i\le n$$. $$D(W_n)=n/2$$.

Proof. The base case when $$n=0$$ and $$n=1$$ is easy.

Suppose it is true when $$n=k$$. $$W_{k+1}$$ is the join of two $$W_{k}$$. WLOG, let us say one of them is at the left and its root is selected as the root of $$W_{k+1}$$ during the join. Note that depths of all nodes in the left $$W_k$$ remains the same after the join while depths of all nodes in the right $$W_k$$ are increased by 1 after the join. So, $$D(W_{k+1})=\frac12 D(W_k) + \frac12 (D(W_k)+1) = \frac12(\frac k2+(\frac k2 +1))= \frac {k+1}2$$ $$W_{k+1}$$ has one root at level 0 and one node at level $$k+1$$, which was the unique node at level $$k$$ of the right $$W_k$$. The nodes in $$W_{k+1}$$ at level $$i$$ come from the nodes in the left $$W_k$$ at level $$i$$ and the nodes in the right $$W_k$$ at level $$i-1$$, so the number of them is $$\binom ki+\binom k{i-1}=\binom {k+1}i,$$ for all $$0. Proof is done.

For completeness, let us define a reasonable version of worst cases. As the above, let $$D(T)$$ be the average depth of a node in a rooted tree $$T$$. Let $$I$$ be a quick-find implementation of the union-find data structure, such as (naive) quick-find or weighted quick-find.

A definition of general worst cases. Given implementation $$I$$, the worst case of $$I$$ with $$k$$ nodes is a rooted tree $$T$$ with $$k$$ nodes such that the average depth of nodes in $$T$$ is the largest among all trees obtained by $$I$$ on $$k$$ nodes.

Let us define $$\mathcal W_k$$ recursively as follows. $$\mathcal W_0$$ is the rooted tree with a single node. $$\mathcal W_{2^n+m}$$ is the tree obtained by combining $$\mathcal W_{2^n}$$ and $$\mathcal W_m$$ using the weighted union procedure, for $$n\ge0$$ and $$1\le m\le 2^n$$.

(Another version of exercise 1.5.15) Show that any worst case of weighted quick-union is $$\mathcal W_{k}$$ for some $$k$$. Compute $$D(\mathcal W_{2^n})$$.

(Sameness of worst cases) Let $$\mathcal A_k$$ be the tree obtained by weight quick-union on $$k$$ nodes using the most accesses. Show that $$\mathcal A_k$$ is the same as $$\mathcal W_k$$.

• This is fantastic. I just have 2 questions about the second part of your proof. (1) Would the base case for the number of nodes at each level be when $k=1$ and $i=0$, i.e, ${1 \choose 0}$? (2) Wouldn't the nodes on the left $W_k$ would contribute to the nodes at level $i$ while the nodes on the right $W_k$ would be at level $i+1$ right? Therefore, wouldn't the sum be ${k \choose i} + {k \choose i-1}$? Thanks for all the help. Dec 16 '18 at 21:09
• (1), for $\binom ki+\binom k{i-1}=\binom {k+1}i$ to make sense, $i$ should be greater than 0 and less than $k+1$. Or do you mean I am using $\binom k0=1$ and $\binom kk=1$? 2), it looks like we are writing the same formula, $\binom ki+\binom k{i-1}$, aren't we? Dec 16 '18 at 22:08
• I think I understand after I read it a second time. Thanks for the clarification. Dec 16 '18 at 22:09

This is just a note for myself in the future, in case anyone else out their ends up getting stumped by this problem. This answer expands off of @Apass.Jack's answer.

To prove that each level has a binomial coefficient, we use induction. The base case of $$n=1$$ is $${1 \choose 0}$$ is 1. $$n$$ represents the height of the nodes while the $$0$$ is just an arbitrary level of the tree. Now, assume that at each level the number of nodes is $${n \choose i}$$ where $$0 \le i < n$$ for a tree $$T_n$$. When we combine 2 trees of size $$2^n$$ (let's call them $$T_1$$ or $$T_2$$), then one of them is chosen to point to the root and the other is chosen to become the root. Let's say that the root of $$T_1$$ is chosen to point to $$T_2$$. If this is the case, the depth of each nodes increases by 1. That means, in a sense, each node is "pushed" down the tree to the next level below. Now, if, by the inductive hypothesis, we have $${n \choose i}$$ nodes at each level of $$T_2$$. However, for each level $$i$$ in the $$T_1$$, the number of nodes at is equivalent to the previous level in $$T_1$$, $$i-1$$. Therefore, for each level $$i$$ in $$T_1$$ connected to $$T_2$$, the number of nodes is $${n \choose i-1}$$. So, if we count the number of nodes on each level, it's just the sum of the number of nodes at each level of $$T_2$$ and then the number of nodes at each level of $$T_1$$ connected to $$T_2$$. So, the number of nodes is $${n \choose i} + {n \choose i-1} = {n+1 \choose i}$$. This fits the form of the inductive hypothesis; therefore it is proven.