12. Binary Search Trees

Exercises

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

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.

12.1-3

Available in the latest revision of the IM.

12.1-4

Available in the latest revision of the IM.

12.1-5

Available in the latest revision of the IM.

12.2-1 🌟

Establishes a useful property of keys encountered during the search. As search for key $k$ goes down a binary search tree, keys less than $k$ must monotonically increase and keys greater than $k$ must monotonically decrease.

Available in the latest revision of the IM.

12.2-2

Available in the latest revision of the IM.

12.2-3

Available in the latest revision of the IM.

12.2-4

Available in the latest revision of the IM.

12.2-5

Available in the latest revision of the IM.

12.2-6

Available in the latest revision of the IM.

12.2-7

Available in the latest revision of the IM.

12.2-8

Available in the latest revision of the IM.

12.2-9

Available in the latest revision of the IM.

12.3-1

Available in the latest revision of the IM.

12.3-2

Available in the latest revision of the IM.

12.3-3

Available in the latest revision of the IM.

12.3-4

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

12.3-5

Available in the latest revision of the IM.

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.

Also, in the pseudocde of Tree-Insert the line setting w's successor should be w.succ = z.

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.

Problems

12-1 Binary search trees with equal keys

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).

12-2 Radix trees

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.

12-3 Average node depth in a randomly built binary search tree

Available in the latest revision of the IM.

12-4 Number of different binary trees

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.

$$\begin{align*} B(x) &= \sum_{n=0}^{\infty} b_nx^n \\ &= b_0x^0+\sum_{n=1}^{\infty} b_nx^n \\ &= 1+\sum_{n=1}^{\infty} \left(\sum_{k=0}^{n-1} b_kb_{n-1-k}\right)x^n && \text{(by part (b))} \\ &= 1+x\sum_{n=1}^{\infty} \left(\sum_{k=0}^{n-1} b_kb_{n-1-k}\right)x^{n-1} \\ &= 1+x\sum_{n=0}^{\infty} \left(\sum_{k=0}^{n} b_kb_{n-k}\right)x^{n} && \text{(reindexing)} \\ &= 1+xB(x)^2. \end{align*}$$

The last line follows by definition of a discrete convolution of power series. We can use the formula for a quadratic equation to get

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

To reconcile $B(x)$ with the base case $B(0)=1$, we should pick the minus sign in the numerator. This gives the formula from the book.

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.

$$\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$.