obst.cpp

ooptimal binary search tree algorithm using dynamic approach

#include<iostream.h>
#include<conio.h>
//give the key values in ascending order//
int te,lo,ro[20][20],ir,jl,jr,il,u2;
float p[20],maint[20][20],tot=0.0,val[20],mini,maxi,mi;
int root[20][20],id[20],i,n,j,k,loc,h,fl=0,o,v,loc1,loc2,tree[30],u,l,key[30];
void min();
void max();
void minim();
void main()
{
cout<<"\nenter the no of key values";
cin>>n;
cout<<"\nenter the values\n";
for(i=1;i<=n;i++)
{
cin>>key[i];
}
cout<<"\nenter the probability of occurrence of each key value";
for(i=1;i<=n;i++)
{
cout<<"\n"<<"key "<<i<<"  ";
cin>>p[i];
id[i]=i;
}
/*for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
if(key[i]<key[j])
{
te=key[i];
key[i]=key[j];
key[j]=te;

te=p[i];
p[i]=p[j];
p[j]=te;
}
}
}*/
for(i=1;i<=20;i++)
{
val[i]=1000.0;
}
for(i=1;i<=n+1;i++)
{
for(j=0;j<=n;j++)
{
maint[i][j]=100.0;
root[i][j]=0;
ro[i][j]=0;
}
}
for(i=1;i<=n+1;i++)
{
for(j=0;j<=n;j++)
{
if(i==j)
{
maint[i][j]=p[i];
}
if(i==j+1)
{
maint[i][j]=0.0;
}
if(j<i)
{
maint[i][j]=0.0;
}
}
}
for(i=1;i<=n+1;i++)
{
for(j=0;j<=n;j++)
{
if(i==j)
{
root[i][j]=i;
ro[i][j]=i;
}
}
}
ln:
{
fl=0;
for(i=1;i<=n+1;i++)
{
for(j=0;j<=n;j++)
{
tot=0;
if((maint[i][j]==100.0)&&(maint[i][j-1]!=100.0)&&(maint[i+1][j]!=100.0))
{
for(k=i;k<=j;k++)
{
tot=tot+p[k];
//cout<<"  "<<tot;
}
for(k=i;k<=j;k++)
{
val[k]=maint[i][k-1]+maint[k+1][j]+tot;
//cout<<"  "<<val[k];
}
min();
maint[i][j]=mini;
root[i][j]=loc;
minim();
ro[i][j]=lo;
}
}
}
for(i=1;i<=n+1;i++)
{
for(j=0;j<=n;j++)
{
if(maint[i][j]==100.0)
{
fl=1;
break;
}
}
}
}
if(fl==1)
goto ln;
cout<<"\nMAIN TABLE\n";
for(i=1;i<=n+1;i++)
{
for(j=0;j<=n;j++)
{
cout<<maint[i][j];
cout<<"\t";
}
cout<<"\n";
}
cout<<"\nROOT TABLE\n";
for(i=1;i<=n+1;i++)
{
for(j=0;j<=n;j++)
{
cout<<root[i][j];
cout<<"\t";
}
cout<<"\n";
}
cout<<"\nanother root table is\n";
for(i=1;i<=n+1;i++)
{
for(j=0;j<=n;j++)
{
cout<<ro[i][j];
cout<<"\t";
}
cout<<"\n";
}
max();
cout<<"\nthe max is "<<maxi;
cout<<"\nits location is "<<loc1<<"  "<<loc2;
cout<<"\n";
tree[1]=root[loc1][loc2];
k=root[loc1][loc2];
i=loc1;
j=loc2;
tree[2*1]=root[i][k-1];
u=2*1;
il=i;
jl=k-1;
tree[(2*1)+1]=root[k+1][j];
ir=k+1;
jr=j;
k=root[il][jl];
tree[2*u]=root[il][k-1];
tree[(2*u)+1]=root[k+1][jl];
u2=(2*1)+1;
k=root[ir][jr];
tree[(2*u2)]=root[ir][k-1];
tree[(2*u2)+1]=root[k+1][jr];
cout<<"\nThe tree is\n\n";
for(l=1;l<=n+1;l++)
{
cout<<key[tree[l]]<<"\t";
}
cout<<"\n\n0 denotes that no key is present";
getch();
}
void min()
{
mini=1000;
for(h=i;h<=j;h++)
{
if(val[h]<mini)
{
mini=val[h];
loc=h;
}
}
}
void minim()
{
mi=1000;
for(h=i;h<=j;h++)
{
if(val[h]<=mi)
{
mi=val[h];
lo=h;
}
}
}
void max()
{
maxi=0;
for(o=1;o<=n+1;o++)
{
for(v=0;v<=n;v++)
{
if(maint[o][v]>maxi)
{
maxi=maint[o][v];
loc1=o;
loc2=v;
}
}
}
}