7.OBST

File: /home/saiesh/ADS/Assignment No 7/ads7.cpp
Page 1 of 2
#include<iostream>
#define MAX 10
using namespace std;
char idnt[7][10];
int i,j,k,n,m,r[10][10];
float p[MAX],q[MAX],w[10][10],c[10][10];
int find(int i,int j)
{
int min=2000,m,l;
for(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;
}
void print(int i,int j)
{
if(i>=j)
return;
if(r[i][r[i][j]-1]!=0)
cout<<"\nLeft child of "<<idnt[r[i][j]]<<" is\t: "<<idnt[r[i][r[i]
[j]-1]];
if(r[r[i][j]][j]!=0)
cout<<"\nRight child of "<<idnt[r[i][j]]<<" is\t: "<<idnt[r[r[i]
[j]][j]];
print(i,r[i][j]-1);
print(r[i][j],j);
return;
}
int main()
{
cout<<"\n\tOptimal Binary Search Tree\n";
cout<<"\nEnter the number of identifiers\t\t: ";
cin>>n;
for(i=1;i<=n;i++)
{
cout<<"Enter identifier "<<i<<"\t\t\t: ";
cin>>idnt[i];
}
cout<<"\n";
for(i=1;i<=n;i++)
{
cout<<"Enter success probability of p["<<i<<"]\t: ";
cin>>p[i];
}
cout<<"\n";
for(i=0;i<=n;i++)
{
cout<<"Enter failure probability of q["<<i<<"]\t: ";
cin>>q[i];
}
cout<<"\n";
for(i=0;i<=n;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];
}
w[n][n]=q[n];File: /home/saiesh/ADS/Assignment No 7/ads7.cpp
r[n][n]=c[n][n]=0;
for(m=2;m<=n;m++)
{
for(i=0;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];
}
}
cout<<"\tOptimal Binary Search Tree \n";
cout<<"\nRoot is\t\t\t: "<<idnt[r[0][j]];
print(0,n);
cout<<"\nTotal cost of OBST is\t: "<<c[0][j]<<"\n";
return 0;
}
/*
OUTPUT
saiesh@saiesh :~$ g++ ads7.cpp
saiesh@saiesh :~$ ./a.out
Optimal Binary Search Tree
Enter
Enter
Enter
Enter
Enter the number
identifier
identifier
identifier
identifier
of identifiers
1
2
3
4
Enter
Enter
Enter
Enter success
success
success
success probability
probability
probability
probability of
of
of
of
Enter
Enter
Enter
Enter
Enter failure
failure
failure
failure
failure probability
probability
probability
probability
probability of
of
of
of
of
:
:
:
:
: 4
do
if
read
while
p[1]
p[2]
p[3]
p[4] :
:
:
: 1
3
1
3
q[0]
q[1]
q[2]
q[3]
q[4] :
:
:
:
: 1
2
1
1
3
Optimal Binary Search Tree
Root is
Left child of if is
Right child of if is
Left child of while is
Total cost of OBST is
saiesh@saiesh :~$ */
:
:
:
:
:
if
do
while
read
32
Page 2 of 2