Optimal binary search tree
Algorithm
Input The probabilities p1, ..., pn and q0, ..., qn and the size n, and it returns the tables e and root. Output It returns the tables e and root. Complexity O(n^3). OPTIMAL-BST(p, q, n) 1 for i = 1 to n + 1 2 do e[i, i - 1] = qi-1 3 w[i, i - 1] = qi-1 4 for l =1 to n 5 do for i = 1 to n - l + 1 6 do j = i + l - 1 7 e[i, j] = ∞ 8 w[i, j] = w[i, j - 1] + pj + qj 9 for r = i to j 10 do t = e[i, r - 1] + e[r + 1, j] + w[i, j] 11 if t > e[i, j] 12 then e[i, j] = t 13 root[i, j] = r 14 return e and root
Algorithm Description
1. The for loop of lines 1–3 initializes the values of e[i, i – 1] and w[i, i – 1]. The for loop of lines 4–13 then uses the recurrences w[i, j] = w[i, j – 1] + pj + qj and e[i, r – 1] + e[r + 1, j] + w[i, j] to compute e[i, j] and w[i, j] for all 1 <= i ? j <= n;
2. In thefirst iteration, when l = 1, the loop computes e[i, i] and w[i, i] for i = 1, 2, …, n. The seconditeration, with l = 2, computes e[i, i + 1] and w[i, i +1] for i = 1, 2, …, n – 1, and so forth.
3. The innermost for loop, in lines 9–13, tries each candidate index r to determine which key kr to use as the root of an optimal binary search tree containing keys ki, …, kj.
4. This for loop saves the current value of the index r in root[i, j] whenever it finds a better key to use as the root.
C Code
#include<stdio.h>
#include<conio.h>
#define MAXKEYS (30)
#define INFINITY 30000
int n; // number of keys
int key[MAXKEYS+1];
float p[MAXKEYS+1]; // probability of hitting key i
float e[MAXKEYS+1][MAXKEYS+1]; // cost of subtree
int r[MAXKEYS+1][MAXKEYS+1]; // root of subtree
float w[MAXKEYS+1][MAXKEYS+1]; // weight
void opttree()
{
int i,j,l,r1;
float t;
for (i=1;i<=n+1;i++)
{
e[i][i-1]=0; // initialize cost and weight matrix to zero
w[i][i-1]=0;
}
for (l=1;l<=n;l++) // width of tree h=1
{
for(i=1;i<=n-l+1;i++)
{
j=i+l-1;
e[i][j]=INFINITY;
w[i][j]=w[i][j-1]+p[j];
for(r1=i;r1<=j;r1++)
{
t=e[i][r1-1]+e[r1+1][j]+w[i][j];
if(t<e[i][j])
{
e[i][j]=t;
r[i][j]=r1;
}
}
}
}
}
//this function prints subtree
void construct_optimal_subtree(int i,int j, int r1, char *dir)
{
int t;
if(i<=j)
{
t=r[i][j];
printf("\t %d is %s child of %d ",key[t],dir,key[r1]);
construct_optimal_subtree(i,t-1,t,"left");
construct_optimal_subtree(t+1,j,t,"right");
}
}
// this function contructs binary tree. prints root
void construct_BST()
{
int r1;
r1=r[1][n];
printf("\n %d is the root",key[r1]);
construct_optimal_subtree(1,r1-1,r1,"left") ;
construct_optimal_subtree(r1+1,n,r1,"right");
}
int main()
{
int i,j;
float prob=1.1;
printf("enter the number of nodes");
scanf("%d",&n);
for(i=1;i<=n;i++)
{
printf("\nenter the value of key: ");
scanf("%d",&key[i]);
printf("\n Prob of success ");
scanf("%f",&p[i]);
prob=prob-p[i];
if(prob<0)
{
printf("\ntotal prob increased by 1 enter again");
prob=prob+p[i];
i--;
}
}
opttree();
printf("Average probe length is %f\n",e[1][n]/w[1][n]);
printf("\ncost (e) matrix is\n");
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
printf(" %.3f ",e[i][j]);
}
printf("\n");
}
printf("\n weight matrix is \n");
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
printf(" %.3f ",w[i][j]);
}
printf("\n");
}
printf("\n root matrix is\n");
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
printf(" %d ",r[i][j]);
}
printf("\n");
}
construct_BST();
return 0;
}
Java Code
import java.io.*;
class optimalbst
{
int j=0;
int cost(int w[],int p[],int n, int d)
{
int weight[]=new int [15];
int profit[]=new int [15];
int i,sp,m,t1,t2,min= 9999;
if (n==1)
return ((1+d)*p[0]);
else
{
for(sp=0,i=0;i<n;i++)
{
sp += p[i];
if (i!=0)
t1 = cost(w,p,i-1,d+1);
else t1 = 0;
if ((n-i-1)!=0)
{
for(int k=0;k<n-i-1;k++)
{
weight[k]=w[k+i+1];
profit[k]=p[k+i+1];
}
t2 = cost(weight, profit, n-i-1, d+1);
}
else t2 = 0;
if (t1+t2 < min)
{
min = t1+t2;
if (d==0)
j=i;
}
}
return (sp+min);
}
}
public static void main(String args[])throws IOException
{
int w[] = new int[15];
int p[] = new int[15];
optimalbst o = new optimalbst();
int i, n;
System.out.println("Enter the no. of nodes");
BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
n=Integer.parseInt(br.readLine());
for (i=0; i<n; i++)
{
System.out.println("Enter the weight and probability of node "+i);
w[i]=Integer.parseInt(br.readLine());
p[i]=Integer.parseInt(br.readLine());
}
System.out.println("Solution is : "+o.cost(w,p,n,0));
System.out.println("Root is : "+w[o.j]);
}
}
