1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ What have you tried? Where did you get stuck? Please include any work you have done so far. $\endgroup$ – dkaeae Dec 16 '18 at 9:01
  • $\begingroup$ 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$. $\endgroup$ – Apass.Jack Dec 16 '18 at 17:02
  • $\begingroup$ @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. $\endgroup$ – S. Sharma Dec 16 '18 at 17:10
0
$\begingroup$

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<i\le k$. 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$.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – S. Sharma Dec 16 '18 at 21:09
  • $\begingroup$ (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? $\endgroup$ – Apass.Jack Dec 16 '18 at 22:08
  • $\begingroup$ I think I understand after I read it a second time. Thanks for the clarification. $\endgroup$ – S. Sharma Dec 16 '18 at 22:09
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.