Answer to Question #109686 in Math for Gnanamani CT

Question

Determine the cost and structure of an optimal binary search tree (OBST) for a set of n = 5 keys with the probabilities given below. You need to calculate the tables e[i, j], w[i, j] and root[i, j]. (30 marks)


i
0
1
2
3
4
5

pi

0.15
0.10
0.05
0.10
0.20

qi
0.05
0.05
0.05
0.10
0.05
0.10

Answer 1

w(i, j) = w(i, r - 1) + pr + w(r + 1, j),

e[i, j ] = pr + (e[i, r - 1] + w(i, r - 1)) + (e[r + 1, j] + w(r + 1, j)).

 

The cost of an optimal binary search tree is 0.85

w[i,j] = 1.

The root is 0.1

References:

https://www.euroinformatica.ro/documentation/programming/!!!Algorithms_CORMEN!!!/DDU0091.html

Introduction To Algorithms

By Thomas H.. Cormen, Thomas H Cormen, Charles E Leiserson, Ronald L Rivest, Clifford Stein

the expected cost of a search was obtained as

package binary_tree;


 
 
class Main2
{
  
  public final static double MD = Double.MAX_VALUE;
  
  
  public static double findOptimalCost(double[] freq, int i, int j, int level ){
 
      if (j < i)  {
        return 0.0;        
      }
      double optimalCost = MD;
     
      for (int k = i; k <= j; k++)
      {
 
        double leftOptimalCost = findOptimalCost(freq, i, k - 1, level + 1 );
 
        double rightOptimalCost = findOptimalCost(freq, k + 1, j, level + 1 );
 
        double cost = freq[k] * level + leftOptimalCost + rightOptimalCost;
 
        optimalCost = Double.min(optimalCost, cost);
 
      }
 
      return optimalCost;
    }
  
  public static double findSumOfProbabilities(double[] prob, double[] freq, int i, int j){
     double sum = 0.0;
      
     for (int k = i; k < j; k++)
       sum += prob[k];
      
     for (int k = (i - 1); k < j; k++)
       sum += freq[k];
      
     return sum;
  }
 
 
  public static void main(String[] args){
      int keys[] =   {0,   1,     2,     3,     4,     5};
      double prob[] = {MD,  0.15,   0.10,  0.05,   0.10,   0.20};
      double freq[] = {0.05,   0.05,  0.05,   0.10,  0.05,  0.10};
 
      System.out.print("The optimal cost of BST is ");
      System.out.println(findOptimalCost(freq, 0, freq.length - 1, 1));
      System.out.println();
    System.out.print("The sum of probabilities of BST is ");
      System.out.println(findSumOfProbabilities(prob, freq, 1, freq.length));
 
    }
  }

and structure