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

You 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: