Optimal Binary Search Trees–Dynamic Programming

Dynamic programming algorithm for optimal binary search trees

The final problem we considered in the previous chapter was the optimal binary search tree problem. The input is a sorted array $A[1 .. n]$ of search keys and an array $f [1 .. n]$ of frequency counts, where $f [i]$ is the number of times we will search for $A[i]$. Our task is to construct a binary search tree for that set such that the total cost of all the searches is as small as possible.

Fix the frequency array $f$, and let $OptCost(i, k)$ denote the total search time in the optimal search tree for the subarray $A[i .. k].$ We derived the following recurrence for the function $OptCost$:

$$OptCost(i,k)=\begin{cases} & \text{ 0 } \hspace{5.65cm} if\space i>k \\ & \underset{j=i}{\overset{k}{\sum}}f[j]+\underset{i\leq r\leq k}{min} \begin{Bmatrix} OptCost(i,r-1) \\ + OptCost(r+1,k) \end{Bmatrix} \hspace{0.3cm} \text{otherwise} \end{cases}$$

We can probably guess what we’re going to do with this recurrence eventually, but let’s get rid of that cumbersome summation first. For any pair of indices $i ≤ k$, let $F(i,k)$ denote the total frequency count for all the keys in the interval $A[i .. k]$:

$$F(i,k) := \underset{j=1}{\overset{k}{\sum}} f [j].$$

This function satisfies the following simple recurrence:

$$F(i,k)=\begin{cases} & f [i] \hspace{3cm} if\space i=k \\ & F(i,k−1)+ f[k] \hspace{0.86cm} \text{otherwise} \end{cases}$$

We can compute all possible values of $F(i,k)$ in $O(n^2)$ time using—you guessed it!—dynamic programming! The usual mechanical steps give us the following dynamic programming algorithm: