Optimal Binary Search Trees-Dynamic Programming

Understand the different techniques used to solve the optimal binary search trees problem efficiently.

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]A[1 .. n] of search keys and an array f[1..n]f [1 .. n] of frequency counts, where f[i]f [i] is the number of times we will search for A[i]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 ff, and let OptCost(i,k)OptCost(i, k) denote the total search time in the optimal search tree for the subarray A[i..k]A[i .. k]. We derived the following recurrence for the function OptCostOptCost:

OptCost(i,k)={ 0 if i>kkj=if[j]+minirk{OptCost(i,r1)+OptCost(r+1,k)}otherwiseOptCost(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 iki ≤ k, let F(i,k)F(i,k) denote the total frequency count for all the keys in the interval A[i..k]A[i .. k]:

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

This function satisfies the following simple recurrence:

F(i,k)={f[i]if i=kF(i,k1)+f[k]otherwiseF(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)F(i,k) in O(n2)O(n^2) time using—you guessed it!—dynamic programming. The usual mechanical steps give us the following dynamic programming algorithm:

Create a free account to access the full course.

By signing up, you agree to Educative's Terms of Service and Privacy Policy