Chapter 12

Exercise 12.1-1

We can use VisuAlgo for demonstrating BSTs of various heights. For each session, choose the command Create to create an empty tree. Afterward, select Insert(v) and copy-paste the matching sequence, as shown below. We can control the height of a BST by entering numbers in specific order.

• Height 2: 10,4,5,1,17,21,16

• Height 3: 4,10,5,1,17,21,16

• Height 4: 4,5,1,10,17,21,16

• Height 5: 1,4,5,10,17,21,16

• Height 6: 1,4,5,10,16,17,21

Exercise 12.1-2

Available in the latest revision of the IM.

The solution in the IM talks about the max-heap instead of the min-heap property. This doesn't change the conclusion, but may cause confusion.

Exercise 12.1-3

Available in the latest revision of the IM.

Exercise 12.1-4

Available in the latest revision of the IM.

Exercise 12.1-5

Available in the latest revision of the IM.

Exercise 12.2-1

Available in the latest revision of the IM.

Exercise 12.2-2

Available in the latest revision of the IM.

Exercise 12.2-3

Available in the latest revision of the IM.

Exercise 12.2-4

Available in the latest revision of the IM.

Exercise 12.2-5

Available in the latest revision of the IM.

Exercise 12.2-6

Available in the latest revision of the IM.

Exercise 12.2-7

Available in the latest revision of the IM.

Exercise 12.2-8

Available in the latest revision of the IM.

Exercise 12.2-9

Available in the latest revision of the IM.

Exercise 12.3-1

Available in the latest revision of the IM.

Exercise 12.3-2

Available in the latest revision of the IM.

Exercise 12.3-3

Available in the latest revision of the IM.

Exercise 12.3-4

When the node to be deleted or its successor farther down the tree is a leaf node.

Exercise 12.3-5

Available in the latest revision of the IM.

Exercise 12.3-6

Available in the latest revision of the IM.

The solution in the IM repeats the same issue as the book. Namely, the Tree-Delete procedure from the book violates the single level of abstraction (SLA) principle at line 5. It would be better to simply call Tree-Successor(z). The price for breaking this principle is even higher in the IM, since it also introduces inefficiency besides thwarting other code quality attributes, like readability. It makes no sense to find the successor if that is already available inside a newly introduced field succ. So, calling Tree-Successor(T, z) would make things proper, as it is tuned to work with this new field.

Exercise 12.3-7

Replace lines 5-12 with the following snippet:

else y = Tree-Predecessor(z)        // y is z's predecessor
    if y != z.left                  // is y farther down the tree?
        Transplant(T, y, y.left)    // replace y by its left child
        y.left = z.left             // z's left child becomes
        y.left.p = y                //     y's left child
    Transplant(T, z, y)             // replace z by its predecessor y
    y.right = z.right               // and give z's right child to y,
    y.right.p = y                   //    which had no right child

To implement a fair strategy mentioned in the book, you may simulate coin flipping with a pseudorandom number generator. Based on the outcome, you would execute the "successor" or "predecessor" block of code.

Problem 12-1

a.

The performance deteriorates to $\Theta(n^2)$, since the tree becomes a linear chain of nodes.

b.

This strategy results in a balanced tree with height $\Theta(\lg n)$. Therefore, inserting $n$ equal keys demands $\Theta(n \lg n)$ time.

c.

Each new node could be prepended in constant time to a list of nodes with equal keys. Thus, inserting $n$ equal keys demands $\Theta(1)\cdot\Theta(n)=\Theta(n)$ time.

d.

The worst-case performance is the same as in part (a). This may occur if the random number generator always returns the same value. On average, according to the law of large numbers, we may expect to have a balanced situation similar to part (b).

Problem 12-2

Available in the latest revision of the IM.

There is a bug in the pseudocode in the IM. The argument in the last line should be x.right instead of x.left.

Problem 12-3

Available in the latest revision of the IM.

Problem 12-4

a.

There is only one empty binary tree, so $b_0=1$.

A tree with $n$ nodes may have $0 \le k <n$ nodes in its left subtree and $n-1-k$ nodes in its right subtree. For a given $k$ we can have $b_kb_{n-1-k}$ structurally different binary trees, as all unique ways to setup the left and right subtrees contribute to the total. Since, binary trees are positional trees (see section B.5.3 of the book), we must count each distribution of nodes (specified by $k$) separately. Therefore, $b_n=\sum_{k=0}^{n-1} b_kb_{n-1-k}$.

b.

Let's start by calculating $xB(x)^2$, treating $B(x)^2$ as the Cauchy product of two power series. We have

$$\begin{align*} xB(x)^2 &= x\left(\sum_{n=0}^{\infty} b_nx^n \right)\left(\sum_{n=0}^{\infty} b_nx^n \right) \\ &= x\sum_{n=0}^{\infty} \left( \sum_{k=0}^{n} b_kb_{n-k} \right)x^n \\ &= x\sum_{n=0}^{\infty} b_{n+1}x^n && \text{(by part (a))} \\ &= \sum_{n=0}^{\infty} b_{n+1}x^{n+1} \\ &= \sum_{n=1}^{\infty} b_nx^n && \text{(reindexing the sum)} \\ &= B(x)-b_0 \\ &= B(x)-1 \\ &\therefore B(x)=xB(x)^2+1 \end{align*}$$

We can use the formula for a quadratic equation to get

$$B(x)=\cfrac{1±\sqrt{1-4x}}{2x}$$

For a limit to exist when $x \to 0$, we should choose $B(x)$ as in the book (with minus in the numerator). In this case, we can apply L'Hôpital's rule and show that $\lim_{x \to 0} B(x)=1$.

c.

Denote $f(x)=\sqrt{1-4x}$ and let's calculate its derivatives.

$$\begin{align*} f'(x) &= \frac{1}{2}(1-4x)^{-1/2}(-4) \\ f''(x) &= \frac{1}{2}\left(-\frac{1}{2}\right)(1-4x)^{-3/2}(-4)^2 \\ \hdashline \\ f^{(n)}(x) &= \frac{1}{2}\left(-\frac{1}{2}\right)\left(-\frac{3}{2}\right)\dots\left(-\frac{2n-3}{2}\right)(1-4x)^{(1-2n)/2}(-4)^n \\ &= -2^n(1 \cdot 3 \cdot \cdot \cdot (2n-3))(1-4x)^{(1-2n)/2} \\ &= -2^n(2n-3)!!(1-4x)^{(1-2n)/2} \end{align*}$$

In the last line, $(2n-3)!!$ is a double factorial. We can transform it into an ordinary factorial by using the corresponding conversion formula, so $(2n-3)!!=\frac{(2n-3)!}{2^{n-2}(n-2)!}$.

The Taylor expansion of $f(x)$ around the point $x=0$ is given by

$$\begin{align*} f(x)&=1-2x-\sum_{n=2}^{\infty} \frac{2^n(2n-3)!}{n!2^{n-2}(n-2)!} \cdot x^n \\ &=1-2x-\sum_{n=2}^{\infty} 4 \cdot \frac{n(n-1)}{2n(2n-1)(2n-2)} \cdot \frac{(2n)!}{n!n!} \cdot x^n\\ &=1-2x-\sum_{n=2}^{\infty} \frac{1}{2n-1} \binom{2n}{n}x^n \\ &=-\sum_{n=0}^{\infty} \frac{1}{2n-1} \binom{2n}{n}x^n \end{align*}$$

We can now substitute $f(x)$ instead of $\sqrt{1-4x}$ in $B(x)$ (see part (b)) to get

$$\begin{align*} B(x) &= \frac{1}{2x}\left(1+\sum_{n=0}^{\infty} \frac{1}{2n-1} \binom{2n}{n}x^n\right) \\ &= \frac{1}{2}\sum_{n=1}^{\infty} \frac{1}{2n-1} \binom{2n}{n}x^{n-1} \\ &= \frac{1}{2}\sum_{n=0}^{\infty} \frac{1}{2n+1} \binom{2n+2}{n+1}x^n \\ &= \sum_{n=0}^{\infty} \frac{1}{n+1} \binom{2n}{n}x^n \\ &= \sum_{n=0}^{\infty} b_nx^n \end{align*}$$

d.

We need to find an asymptotic approximation of $b_n$.

$$\begin{align*} b_n &= \frac{1}{n+1} \binom{2n}{n} \\ &\approx \frac{1}{n} \binom{2n}{n} && \text{($n/(n+1) \to 1$ for sufficiently large $n$)} \\ &= \frac{4^n}{\sqrt{\pi}n^{3/2}}(1+O'(1/n)) && \text{(by Exercise C.1.13)} \end{align*}$$

See the solution of Exercise C.1.13 to understand why $O'$ is used here instead of $O$.