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 :
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 |
package com.omt.learn.algo; import com.omt.learn.algo.util.matrix.MatrixUtil; import com.omt.learn.algo.util.tree.BiTreeNode; import com.omt.learn.algo.util.tree.TreeUtil; public class OptimalBinarySearchTree { public static void main(String[] args) { int keys[] = { 10, 12, 16, 21 };// { 10, 12, 20, 35, 46 }; int freq[] = { 4, 2, 6, 3 };// { 34, 8, 50, 21, 16 }; int gotRoot = initOptimalBinary(keys, freq); generateTree(gotRoot, keys); } public static void generateTree(int gotRoot, int a[]) { BiTreeNode root = new BiTreeNode("" + a[gotRoot]); root.value = a[gotRoot]; for (int i = 0; i < a.length; i++) { if (i != gotRoot) { BiTreeNode n = new BiTreeNode("" + a[i]); n.value = a[i]; root.addBiTreeNode(n); } } System.out.println("Generated Tree Is :"); TreeUtil.printTree(root); } public static int initOptimalBinary(int a[], int b[]) { int[][] cal = new int[a.length][a.length]; int[][] roots = new int[a.length][a.length]; for (int l = 1; l <= a.length; l++) { for (int i = 0; i < a.length; i++) { if (l == 1) { cal[i][i] = b[i]; roots[i][i] = i; } else if (i + l <= a.length) { // Consider i is a root int total = b[i]; roots[i][i + l - 1] = i; cal[i][i + l - 1] = cal[i + 1][i + l - 1]; for (int j = i + 1; j < i + l; j++) { // Test what if current j is a root total += b[j]; int temp = cal[i][j - 1]; // make sure it should not be a index out of bound. if (j + 1 < i + l) { temp += cal[j + 1][i + l - 1]; } // Check if current j is a capable for root position. if (temp < cal[i][i + l - 1]) { cal[i][i + l - 1] = temp; roots[i][i + l - 1] = j; } } cal[i][i + l - 1] += total; // Add all total in final // result. } } } System.out.println("Total search cost :"); MatrixUtil.printMatrix(cal); System.out.println(); System.out.println("Roots selected :"); MatrixUtil.printMatrix(roots); return roots[0][a.length - 1]; } } |
