# 15.5 Optimal binary search trees

## 15.5-1

Write pseudocode for the procedure $\text{CONSTRUCT-OPTIMAL-BST}(root)$ which, given the table $root$, outputs the structure of an optimal binary search tree. For the example in Figure 15.10, your procedure should print out the structure

\begin{aligned} & \text{k_2 is the root} \\ & \text{k_1 is the left child of k_2} \\ & \text{d_0 is the left child of k_1} \\ & \text{d_1 is the right child of k_1} \\ & \text{k_5 is the right child of k_2} \\ & \text{k_4 is the left child of k_5} \\ & \text{k_3 is the left child of k_4} \\ & \text{d_2 is the left child of k_3} \\ & \text{d_3 is the right child of k_3} \\ & \text{d_4 is the right child of k_4} \\ & \text{d_5 is the right child of k_5} \end{aligned}

corresponding to the optimal binary search tree shown in Figure 15.9(b).

 1 2 3 4 5 6 7 8 9 10 11 CONSTRUCT-OPTIMAL-BST(root, i, j, last) if i == j return if last == 0 print root[i, j] + "is the root" else if j < last: print root[i, j] + "is the left child of" + last else print root[i, j] + "is the right child of" + last CONSTRUCT-OPTIMAL-BST(root, i, root[i, j] - 1, root[i, j]) CONSTRUCT-OPTIMAL-BST(root, root[i, j] + 1, j, root[i, j])

## 15.5-2

Determine the cost and structure of an optimal binary search tree for a set of $n = 7$ keys with the following probabilities

$$\begin{array}{c|cccccccc} i & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ \hline p_i & & 0.04 & 0.06 & 0.08 & 0.02 & 0.10 & 0.12 & 0.14 \\ q_i & 0.06 & 0.06 & 0.06 & 0.06 & 0.05 & 0.05 & 0.05 & 0.05 \end{array}$$

Cost is $3.12$.

\begin{aligned} & \text{k_5 is the root} \\ & \text{k_2 is the left child of k_5} \\ & \text{k_1 is the left child of k_2} \\ & \text{d_0 is the left child of k_1} \\ & \text{d_1 is the right child of k_1} \\ & \text{k_3 is the right child of k_2} \\ & \text{d_2 is the left child of k_3} \\ & \text{k_4 is the right child of k_3} \\ & \text{d_3 is the left child of k_4} \\ & \text{d_4 is the right child of k_4} \\ & \text{k_7 is the right child of k_5} \\ & \text{k_6 is the left child of k_7} \\ & \text{d_5 is the left child of k_6} \\ & \text{d_6 is the right child of k_6} \\ & \text{d_7 is the right child of k_7} \end{aligned}

## 15.5-3

Suppose that instead of maintaining the table $w[i, j]$, we computed the value of $w(i, j)$ directly from equation $\text{(15.12)}$ in line 9 of $\text{OPTIMAL-BST}$ and used this computed value in line 11. How would this change affect the asymptotic running time of $\text{OPTIMAL-BST}$?

Each of the $\Theta(n^2)$ values of $w[i, j]$ would require computing those two sums, both of which can be of size $O(n)$, so, the asymptotic runtime would increase to $O(n^3)$.

## 15.5-4 $\star$

Knuth [212] has shown that there are always roots of optimal subtrees such that $root[i, j - 1] \le root[i, j] \le root[i + 1, j]$ for all $1 \le i < j \le n$. Use this fact to modify the $\text{OPTIMAL-BST}$ procedure to run in $\Theta(n^2)$ time.

Change the for loop of line 10 in $\text{OPTIMAL-BST}$ to

 1 for r = r[i, j - 1] to r[i + 1, j]

Knuth's result implies that it is sufficient to only check these values because optimal root found in this range is in fact the optimal root of some binary search tree. The time spent within the for loop of line 6 is now $\Theta(n)$. This is because the bounds on $r$ in the new for loop of line 10 are nonoverlapping.

To see this, suppose we have fixed $l$ and $i$. On one iteration of the for loop of line 6, the upper bound on $r$ is

$$r[i + 1, j] = r[i + 1, i + l - 1].$$

When we increment $i$ by $1$ we increase $j$ by $1$. However, the lower bound on $r$ for the next iteration subtracts this, so the lower bound on the next iteration is

$$r[i + 1, j + 1 - 1] = r[i + 1, j].$$

Thus, the total time spent in the for loop of line 6 is $\Theta(n)$. Since we iterate the outer for loop of line 5 $n$ times, the total runtime is $\Theta(n^2)$.