Question

Given a search problem where some elements are searched more than others, it is more important to minimize the total cost of several searches rather than the worst-case cost of a single search. If x is a more frequent search target than y, building a tree where the depth of x is smaller than the depth of y will work better, even if that means increasing the overall depth of the tree. A perfectly balanced tree is not the best choice if some items are significantly more popular than others.
Suppose we are given a sorted array of keys A[1..n] and an array of corresponding access frequencies f[1..n]. Build the binary search tree that minimizes the total search time, assuming that there will be exactly f[i] searches for each key A[i]. Suggest a recursive definition of the cost function, such that Cost(T, f[1..n]]=..., where T is the tree.

Answer 1

1. This is very famous dynamic programming problem known as optimal cost binary search tree.

Lets understand problem with a example

suppose keys = [ 5,7]

frequency = [10 , 14)

so we can have trees in these two forms

5 or 7

\ /

7 5

Cost = 10*1 + 14*2 = 38 cost = 14*1 + 10*2 = 34

So in right side of tree cost of searching is minimum.  

Here cost[i][j] denotes min cost binary search tree which can we formed taking R as a root and

freq[i...j] denotes sum of frequency of keys from i to j.

Base case

i == j only one element so return freq[i]

i>j return 0. As no elements occur between [j,i]

Here we are calculating cost[i][j] using cost[i][R] and cost[R+1][j] as this problems satisfy optimal substructure property.

Feel free to ask doubts in comments if any