Optimal Binary search tree

Optimal binary search tree can be static or dynamic. The tree cannot be modified in static optimality. The tree can be modified any time in the dynamic optimality. The tree can be rotated in the dynamic problem. Binary search tree is a binary search tree which provides the smallest possible search time for a given sequence of accesses.

Write a program to implement optimal binary search tree

source Code

package com.dsacode.Algorithm.dynamic;
 
import java.util.Arrays;
  
class OBST{
   static String [] idnt;
   static int [][] c,r,w;
   static int [] p,q ;
     
   static int find(int i,int j) {
      int l=0,min=2000;
      for(int m = i+1; m <= j; m++)
         if(c[i][m-1]+c[m][j] < min)
           {
             min=c[i][m-1]+c[m][j];
             l=m;
           }
      return l;
   }
     
   static void print(int i,int j) {
       if( i < j)
           System.out.print(idnt[r[i][j]] + ' ');
       else
           return;
       print(i,r[i][j]-1);
       print(r[i][j],j);
   }
     
   public static void main(String[] args) {
       int noId=3;
        
        System.out.println("Number of identifiers: " + noId);
      
        int s=noId+2;
        idnt=new String[s];
        c=new int[s][s];
        r=new int[s][s];
        p=new int[s];
        q=new int[s];
        w=new int[s][s]; 
         
        for(Integer i = 1; i <= noId; i++)
            idnt[i]=i.toString();
        System.out.println("Identifiers: " + Arrays.toString(idnt));
         
         
        for(int i = 1; i <= noId; i++)
            p[i] = i+3;;
        System.out.println("Success probability  for identifiers: " + Arrays.toString(p));
             
         
        for(int i = 0; i <= noId; i++)
            q[i] = 6+i;
         
        System.out.println("Failure probability  for identifiers: " + Arrays.toString(q));
         
        for(int i = 0; i <= noId; i++){
                w[i][i]=q[i];
                c[i][i]=r[i][i] = 0;
                w[i][i+1]=q[i]+q[i+1]+p[i+1];
                r[i][i+1]=i+1;
                c[i][i+1]=q[i]+q[i+1]+p[i+1];
         }
        int n=noId;
         w[n][n]=q[n];
         r[n][n]=c[n][n]=0;
         for(int m = 2; m <= n; m++)
                for(int i = 0, j,k; i <= n-m; i++) {
                    j=i+m;
                    w[i][j]=w[i][j-1]+p[j]+q[j];
                    k=find(i,j);
                    r[i][j]=k;
                    c[i][j]=w[i][j]+c[i][k-1]+c[k][j];
                 }
           System.out.print( "Tree in pre order : ");
           print(0,n);           
  }
} 

Output

Number of identifiers: 3
Identifiers: [null, 1, 2, 3, null]
Success probability for identifiers: [0, 4, 5, 6, 0]
Failure probability for identifiers: [6, 7, 8, 9, 0]
Tree in pre order: 2 1 3

Algorithm Explanation

	Initialize the Number of identifiers, Success probability for identifiers and Failure probability for identifiers.
	Pass the arguments to solve utility function.
	Return the optimal tree and print the values

Time Complexity

Reference

1. https://en.wikipedia.org/wiki/Optimal_binary_search_tree
2. http://www.radford.edu/~nokie/classes/360/dp-opt-bst.html
3. https://www.cs.auckland.ac.nz/software/AlgAnim/opt_bin.html