Write a C++ program to find the optimal
binary search tree for the given set
Optima binary
search tree:-
We can construct [1/(n+1)](2ncn) binary search
trees for a given set which will be a time consuming process.in order to reduce
that we will solve this problem by using dynamic programming.
Formulas
for obst
c[i][i]=0.0;
r[i][i]=0;
wt[i][i]=q[i];
wt[i][j]=p[j]+q[j]+wt[i][j-1];
c[i][j]=c[i][k-1]+c[k][j]+wt[i][j];
r[i][j]=k;
To construct a tree consider the last row first column of a tree
T[i][j]=t[i][k-1],t[k][j];
Algorithm
void
con_obst(void)
{
int i,j,k,min;
for(i=0 to n)
{ //Initialisation
c[i][i]=0.0;
r[i][i]=0;
w[i][i]=q[i];
j=i+1;
k=j;
w[i][j]=p[j]+q[j]+w[i][j-1];
c[i][j]=c[i][k-1]+c[k][j]+w[i][j];
r[i][j]=k;
}
//for j-i=2,3,4….,n
for(j=2 to n)
{
for(i=0;i<=n-j;i++)
{
j=j+i;
w[i][j]=p[j]+q[j]+w[i][j-1];
c[i][j]=9999;
for(k=i+1 to j)
{
if(c[i][j]>(c[i][k-1]+c[k][j]))
{
c[i][j]=c[i][k-1]+c[k][j];
r[i][j]=k;
}
}
c[i][j]+=w[i][j];
j=j-i;
}
cout<<endl;
}
Analysis:-
The time complexity is O(n3)
Program
#include<iostream>
using
namespace std;
//#include<conio.h>
//#include<stdio.h>
class
obst
{
public:
void
obstm(int);
void
print(int,int);
public:
float
p[20],q[20],wt[20][20],c[20][20];
int
r[20][20],i,j,t[20][20],k;
};
void
obst::obstm(int n)
{
// int i;
cout<<"\n****** PROGRAM FOR
OBST ******\n";
// cout<<"\nEnter the no. of
nodes : ";
//
cin>>n;
cout<<"\nEnter the p values
";
for(i=1;i<=n;i++)
{
cout<<"\np["<<i<<"] :";
cin>>p[i];
}
cout<<"\nEnter the q values
";
for(i=0;i<=n;i++)
{
cout<<"\nq["<<i<<"] :";
cin>>q[i];
}
// int i,j;
for(i=0;i<=n;i++)
{ //Initialisation
c[i][i]=0.0;
r[i][i]=0;
wt[i][i]=q[i];
j=i+1;
k=j;
wt[i][j]=p[j]+q[j]+wt[i][j-1];
c[i][j]=c[i][k-1]+c[k][j]+wt[i][j];
r[i][j]=k;
}
//for j-i=2,3,4….,n
for(j=2;j<=n;j++)
{
for(i=0;i<=n-j;i++)
{
j=j+i;
wt[i][j]=p[j]+q[j]+wt[i][j-1];
c[i][j]=9999;
for(k=i+1;k<=j;k++)
{
if(c[i][j]>(c[i][k-1]+c[k][j]))
{
c[i][j]=c[i][k-1]+c[k][j];
r[i][j]=k;
}
}
c[i][j]+=wt[i][j];
j=j-i;
}
cout<<endl;
}
cout<<"\n\nOptimal BST is ::
";
cout<<"w values are\n";
for(i=0;i<=n;i++)
{
k=0;
for(j=i;j<=n;j++,k++)
cout<<wt[k][j]<<"\t";
cout<<"\n";
}
cout<<"c values are \n";
for(i=0;i<=n;i++)
{
k=0;
for(j=i;j<=n;j++,k++)
cout<<c[k][j]<<"\t";
cout<<"\n";
}
cout<<"r values are \n";
for(i=0;i<=n;i++)
{
k=0;
for(j=i;j<=n;j++,k++)
{
t[k][j]=r[k][j];
cout<<r[k][j]<<"\t";
}
cout<<"\n";
}
}
void
obst::print(int i,int j)
{
int k;
if(i>=0&&i!=j)
{
k=t[i][j];
cout<<"\n Left child of "<<k<<" is "<<t[i][k-1];
cout<<"\n Right child of "<<k<<" is "<<t[k][j];
print(i,k-1);
print(k,j);
}
return;
}
int
main()
{
int
n;
cout<<"enter
n";
cin>>n;
obst
o;
o.obstm(n);
o.print(0,n);
return
0;
}
Enter
the no. of nodes : 4
Enter
the p values
p[1] :3
p[2] :3
p[3] :1
p[4] :1
Enter
the q values
q[0] :2
q[1] :3
q[2] :1
q[3] :1
q[4] :1
Output
Optimal
BST is :: w values are
2 3
1 1 1
8 7
3 3
12 9
5
14 11
16
c
values are
0 0
0 0 0
8 7
3 3
19 12
8
25 19
32
r
values are
0 0
0 0 0
1 2
3 4
1 2
3
2 2
2
Left child of
2 is :: 1
Right child of
2 is :: 3
Right child of
3 is :: 4
Output-2
p[1] :1
p[2] :4
p[3] :2
p[4] :1
Enter
the q values
q[0] :4
q[1] :2
q[2] :4
q[3] :1
q[4] :1
Optimal
BST is :: w values are
4 2
4 1 1
7 10
7 3
15 13
9
18 15
20
c
values are
0 0 0 0 0
7 10 7 3
22 20 12
32 27
39
r
values are
0 0
0 0 0
1 2
3 4
2 2
4
1 2
1
Left child of
1 is 0
Right child of
1 is 2
Left child of
2 is 0
Right child of
2 is 4
Left child of
4 is 3
Right child of
4 is 0
Left child of
3 is 0
Right child of
3 is 0
No comments:
Post a Comment