Chapter 12 problems

ch12-problems
- 12-1
- 12-2
- 12-3
- 12-4

ch12-problems

12-1

a.

If we use TREE-INSERT to insert $n$ items with identical keys into an initially empty binary search tree, it's same as we are inserting $n$ strictly sorted items, which takes totally $\Theta(n^2)$ running time.
b.

The number of nodes in the tree rooted at $x.left$, whose keys are identical with $x$, are approximately the same as those in the tree rooted at $x.right$, thus after having inserted $n$ items with identical keys, we balance the binary search tree, the height of the tree should be $\Theta(\lg n)$. Hence, the total running time is $\Theta(n\lg n)$, and we only require $O(1)$ extra memory space.
c.

If the running time of list insertion is a constant, then the totally running time is $O(n)$, and finally the height of the binary search tree is $0$, but we need $O(n)$ extra memory space outside the tree.
d.

When a node is inserting into the tree rooted at node $x$, if the key of the node is identical with $x$, then the node will be equally likely inserted into the tree rooted at $x.left$ or $x.right$. Thus, after having inserted $n$ items with identical keys, the binary search tree is on expect balanced, hence the expected running time is $O(n\lg n)$, but the worst-case running time is still $O(n^2)$, and the extra memory space we need is $O(1)$.

12-2

Consider a node $x$ and its children $x.left$ and $x.right$ in the radix tree, then we know that lexicographically $x < x.left < x.right$ by the rules, which corresponding to the preorder tree traverse. Thus, we could traverse the radix tree in preorder, to sort $S$ lexicographically, the running time is $\Theta(n)$ if the lengths of strings in $S$ sum to n.

12-3

a.

We obtain the average depth of a node in $T$ by its definition, which is
\begin{align*} \frac{1}{n}\sum_{x\in T}d(x,T)=\frac{1}{n}P(T) \end{align*}
Hence if we have proved that the expected value of $P(T)$ is $O(n\lg n)$, then the expected value the average depth of a node in $T$ should be $O(\lg n)$, and we could obtain that the average depth of a node in a randomly built binary search tree with $n$ nodes is $O(\lg n)$.
b.

There are totally $n - 1$ nodes in $T_L$ and $T_R$, and for each node $x$ in $T_L$, we have $d(x, T_L) = d(x, T) - 1$, so was that for $T_R$. And the depth of the root of $T$ in $T$ is $0$, thus we have $P(T) = P(T_L) + P(T_R) + n - 1$.
c.

For a randomly built binary search tree, the root is the first element of the input permutation, if there are $n$ nodes in the tree $T$, then for $i \in [1, n]$, let $x_i$ denote the $i$th smallest element of the input permutation, the possibility for $x_i$ to be the root of $T$ is $1/n$, then $T_L$ is randomly built from $x_1,\ldots,x_{i-1}$, and $T_R$ is randomly built from $x_{i+1},\ldots,x_n$. Thus, we have
\begin{align*} P(n) &=P(T)\\ &=\sum_{i=1}^{n}\Bigg(\frac{1}{n}(P(T_L)+P(T_R)+n-1)\Bigg)\\ &=\frac{1}{n}\sum_{i=0}^{n-1}(P(i)+P(n-i-1)+n-1) \end{align*}
d.

We have
\begin{align*} P(n) &=\frac{1}{n}\sum_{i=0}^{n-1}(P(i)+P(n-i-1)+n-1)\\ &=\frac{2}{n}\sum_{k=1}^{n-1}P(k)+n-1\\ &=\frac{2}{n}\sum_{k=1}^{n-1}P(k)+\Theta(n) \end{align*}
e.

Guess $P(n) \leq an\lg n$, then
\begin{align*} P(n) &=\frac{2}{n}\sum_{k=1}^{n-1}P(k)+\Theta(n)\\ &\leq \frac{2}{n}\sum_{k=1}^{n-1}ak\lg k+\Theta(n)\\ &\leq \frac{2a}{n}\Big(\frac{1}{2}n^2\lg n-\frac{1}{8}n^2\Big)+\Theta(n)\\ &=an\lg n-\frac{an}{4}+\Theta(n)\\ &\leq an\lg n &\text{, for enough large constant $a$} \end{align*}
Thus $P(n) = O(n\lg n)$.

During the partitions, we need to take the first element as the pivot, and keep the orders of the elements in the left part also the right part, as they were before the partition. Below is the implementation.

PARTITION(A, p, r)
    let left be a new array
    let right be a new array
    x = A[p]
    for i = p + 1 to r
        if A[i] < x
            left.append(A[i])
        else right.append(A[i])
    for j = 1 to left.length
        A[j] = left[j]
    A[left.length + 1] = x
    for k = 1 to right.length
        A[left.length + 1 + k] = right[k]
    return left.length + 1

QUICKSORT(A, p, r)
    if p < r
        q = PARTITION(A, p, r)
        QUICKSORT(A, p, q - 1)
        QUICKSORT(A, q + 1, r)

12-4

a.

The binary search tree with $0$ nodes is a special empty tree, thus $b_0 = 1$, and for $n \geq 1$, we could first choose an element to be the root, if the root is the $i$th smallest element, the left subtree of the root would have $i - 1$ elements, and the right subtree of the root would have $n - i$ elements, hence we have
\begin{align*} b_n &= \sum_{k=0}^{n-1}b_k b_{n-1-k} \end{align*}
b.

We have
\begin{align*} B(x) &=\sum_{n=0}^{\infty}b_n x^n\\ &=b_0 x^0+\sum_{n=1}^{\infty}\sum_{k=0}^{n-1}b_k b_{n-1-k}x^n\\ &=1+x\sum_{n=1}^{\infty}\sum_{k=0}^{n-1}b_k x^k b_{n-1-k}x^{n-1-k}\\ &=1+xB(x)^2 \end{align*}
Solve the equations $B(0) = 0$ and $B(x) = xB(x)^2 + 1$, we have
\begin{align*} B(x) &= \frac{1}{2x}(1-\sqrt{1-4x}) \end{align*}
c.

Define $g(x) = \sqrt{1-4x}$, and perform Taylor expansion of $g(x)$ around the point $x = 0$, we have
\begin{align*} B(x) &=\frac{1}{2x}(1-\sqrt{1-4x})\\ &=\frac{1}{2x}\bigg(1-\sum_{k=0}^{\infty}\frac{g^{(k)}(0)}{k!}x^k\bigg)\\ &=\sum_{k=1}^{\infty}\frac{(2(k-1)!}{(k-1)!k!}x^{k-1}\\ &=\sum_{n=0}^{\infty}\bigg(\frac{1}{n+1}\binom{2n}{n}x^k\bigg) \end{align*}
Substitute the equation above with $B(x)=\sum_{n=0}^{\infty}b_n x^n$, we have $b_n = \frac{1}{n+1}\binom{2n}{n}$.
d.

Using Stirling's approximation
\begin{align*} n! &= \sqrt{2\pi n}\Big(\frac{n}{\mathrm{e}}\Big)^n \Bigg(1+\Theta\bigg(\frac{1}{n}\bigg)\Bigg) \end{align*}
we have
\begin{align*} b_n &=\frac{1}{n+1}\binom{2n}{n}\\ &=\frac{(2n)!}{n!(n+1)!}\\ &=\frac{1}{n+1}\cdot\frac{4^n}{\sqrt{\pi n}} \cdot\frac{1+\Theta(\frac{1}{2n})}{(1+\Theta({1+\frac{1}{n})})^2}\\ &=\frac{4^n}{\sqrt{\pi}n^{3/2}}(1+O(1/n)) \end{align*}