DP #08. Optimal Binary Search Tree. - mbhushan/dynpro GitHub Wiki

(8). Optimal Binary Search Tree.

Given keys and frequency at which these keys are searched, how would you create 
binary search tree from these keys such that cost of searching is minimum.

Input:
      Keys[] = {10, 12, 16, 21}
frequency [] = {4, 2, 6, 3}

We take the bottoms up approach here and keep track of the cost of BST of
len=1 to len=size(A).

T[i][j] = Min (
              T[i][j],
              sum + min(T[i][k-1] + T[k+1][j]) for all i <= k <= j
              //where sum is Sum(freqency[i] .. frequency[j])
              );

• T[i][j] = cost(x) means total cost of BST with x as root

Index	0	1	2	3
Keys	10	12	16	21
Frequency	4	2	6	3
Index	0	1	2	3
0	4	8(0)	20(2)	26(2)
1		2	10(2)	16(2)
2			6	12(2)
3				3

//Formula and code below:

public int minCost(int [] keys, int [] freq) {
	int [][] T = new int[keys.length][keys.length];
		
	for(int i=0; i < T.length; i++){
            T[i][i] = freq[i];
        }
		
		for (int L=2; L <= keys.length; L++) {
			for (int i=0; i<=keys.length-L; i++) {
				int j = i + L -1;
				T[i][j] = Integer.MAX_VALUE;
				int sum = getSum(freq, i, j);
				for (int k=i; k<=j; k++) {
					int val = sum + (k-1 < i? 0: T[i][k-1]) + 
							(k+1 > j ? 0: T[k+1][j]);
					if (val < T[i][j]) {
						T[i][j] = val;
					}
				}
			}
		}
		
		return T[0][keys.length-1];
	}

        private int getSum(int [] freq, int i, int j) {
		int total = 0;
		for (int x=i; x<=j; x++) {
			total += freq[x];
		}
		return total;
	}

Optimal BST

• Time Complexity: O(n^3)
• Space Complexity: O(n^2)