86 lines
2.2 KiB
C++
86 lines
2.2 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;
|
|
|
|
int find(int, int);
|
|
void print(int, int);
|
|
int c[20][20], w[20][20], r[20][20], p[20], q[20], k, m, i, j, n;
|
|
char idtr[10][7];
|
|
|
|
int main()
|
|
{
|
|
cout<<"\nEnter number of identifiers: ";
|
|
cin>>n;
|
|
for(i = 1; i <= n; i++)
|
|
{
|
|
cout<<"Enter Identifier "<<i<<": ";
|
|
cin>>idtr[i];
|
|
}
|
|
for(i = 1; i <= n; i++)
|
|
{
|
|
cout<<"Enter successful probability of "<<i<<": ";
|
|
cin>>p[i];
|
|
}
|
|
for(i = 0; i <= n; i++)
|
|
{
|
|
cout<<"Enter unsuccessful probability of "<<i<<": ";
|
|
cin>>q[i];
|
|
}
|
|
for(i = 0; i <= n; i++)
|
|
{
|
|
w[i][i] = q[i];
|
|
c[i][i] = r[i][i] = 0;
|
|
cout<<"\nW: "<<w[i][i]<<" | c: "<<c[i][i]<<" | r: "<<r[i][i];
|
|
}
|
|
for(i = 0; i < n; i++)
|
|
{
|
|
j = i + 1;
|
|
w[i][j] = p[j] + q[j] + q[i];
|
|
c[i][j] = w[i][j];
|
|
r[i][j] = j;
|
|
cout<<"\nW: "<<w[i][j]<<" | c: "<<c[i][j]<<" | r: "<<r[i][j];
|
|
}
|
|
for(m = 2; m <= n; m++)
|
|
{
|
|
for(i = 0; i <= n-m; i++)
|
|
{
|
|
j = i + m;
|
|
w[i][j] = p[j] + q[j] + w[i][j-1];
|
|
c[i][j] = 1000;
|
|
for(k = i + 1; k <= j; k++)
|
|
{
|
|
int cost = c[i][k-1] + c[k][j];
|
|
if(cost < c[i][j])
|
|
{
|
|
c[i][j] = cost;
|
|
r[i][j] = k;
|
|
}
|
|
}
|
|
c[i][j] += w[i][j];
|
|
cout<<"\nW: "<<w[i][j]<<" | c: "<<c[i][j]<<" | r: "<<r[i][j];
|
|
}
|
|
}
|
|
cout<<"\nFinal OBST is: ";
|
|
print(0, n);
|
|
return 0;
|
|
}
|
|
|
|
void print(int i, int j)
|
|
{
|
|
if(i < j)
|
|
cout<<"\n"<<idtr[r[i][j]];
|
|
else
|
|
return;
|
|
print(i, r[i][j] - 1);
|
|
print(r[i][j], j);
|
|
}
|
|
// END OF CODE
|