instagram

Optimal Binary Search Tree

Given a sorted array keys[0.. n-1] of search keys and an array freq[0.. n-1] of frequency counts, where freq[i] is the number of searches to keys[i]. Construct a binary search tree of all keys such that the total cost of all the searches is as small as possible.

Input:

int keys[] = { 10, 12, 16, 21 };
int freq[] = { 4, 2, 6, 3 };

Output :

Total search cost :
4  8  20 26 
0  2  10 16 
0  0  6  12 
0  0  0  3  

Roots selected :
0  0  2  2  
0  1  2  2  
0  0  2  2  
0  0  0  3  

Generated Tree Is :

     16
10       21
   12       
      

Algorithm :


Share