92 lines
2.3 KiB
C++
92 lines
2.3 KiB
C++
/*
|
|
THIS CODE HAS BEEN TESTED AND IS FULLY OPERATIONAL.
|
|
|
|
Problem Statement: Given sequence k = k1 <k2 < … <kn of n sorted keys, with a search probability pi for each key ki . Build the Binary search tree that has the least search cost given the access probability for each key?
|
|
|
|
Code from DataStructuresAndAlgorithms (SPPU - Second Year - Computer Engineering - Content) repository on KSKA Git: https://git.kska.io/sppu-se-comp-content/DataStructuresAndAlgorithms/
|
|
*/
|
|
|
|
// BEGINNING OF CODE
|
|
#include<iostream>
|
|
using namespace std;
|
|
#define MAX 10
|
|
int find(int,int);
|
|
void print(int,int);
|
|
int p[MAX],q[MAX],w[10][10],c[10][10],r[10][10],i,j,k,n,m;
|
|
char idnt[7][10];
|
|
|
|
int main()
|
|
{
|
|
cout<<"Number of identifiers:\t";
|
|
cin>>n;
|
|
cout<<"Enter identifiers:"<<endl;
|
|
for(i=1;i<=n;i++) {
|
|
cout<<"Identifier "<<i<<":\t";
|
|
cin>>idnt[i];
|
|
}
|
|
cout<<"Enter success probability for identifiers:\n";
|
|
for(i=1;i<=n;i++) {
|
|
cout<<"Identifier "<<i<<":\t";
|
|
cin>>p[i];
|
|
}
|
|
cout<<"Enter failure probability for identifiers:\n";
|
|
for(i=0;i<=n;i++) {
|
|
cout<<"Identifier "<<i<<":\t";
|
|
cin>>q[i];
|
|
}
|
|
cout<<"\n Weight Cost Root \n";
|
|
|
|
for(i=0;i<=n;i++)
|
|
{
|
|
w[i][i]=q[i];
|
|
c[i][i]=r[i][i]=0;
|
|
cout<<"\n"<<w[i][i]<<" "<<c[i][i]<<" "<<r[i][i];
|
|
cout<<"-------------------------------------------------------------------------";
|
|
}
|
|
for(i=0;i<n;i++)
|
|
{
|
|
j=i+1;
|
|
w[i][j]= p[j]+q[i]+q[j]; // w(i,j)= p[j]+q[i]+w(i,j-1)
|
|
c[i][j]=q[i]+c[i][j-1]+c[j][j]; // c(i,j)= min { c (i,k-1)+c(k+1, j) }+ w(i,j))
|
|
r[i][j]=j;
|
|
cout<<"\n"<<w[i][j]<<" "<<c[i][j]<<" "<<r[i][j];
|
|
cout<<"-------------------------------------------------------------------------";
|
|
}
|
|
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<<"\n"<<w[i][j]<<" "<<c[i][j]<<" "<<r[i][j];
|
|
}
|
|
}
|
|
cout<<"-------------------------------------------------------------------------";
|
|
cout<<endl<<endl<<"THE FINAL OBST IS:";
|
|
print(0,n);
|
|
return 0;
|
|
}
|
|
int find(int i,int j)
|
|
{
|
|
int min=2000,m,l; //c[i][j];
|
|
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)
|
|
cout<<"\n"<<idnt[r[i][j]];
|
|
else
|
|
return;
|
|
print(i,r[i][j]-1);
|
|
print(r[i][j],j);
|
|
}
|
|
// END OF CODE
|