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

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}$?

Computing $w(i, j)$ from the equation is $\Theta(j - i)$, since the loop below on lines 10-14 is also $\Theta(j - i)$, it wouldn't affect the asymptotic running time of $\text{OPTIMAL-BST}$ which would stay $\Theta(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

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