Scribd
Upload
16 views1 page

K K 1

The document presents a C++ program that constructs an optimal binary search tree (OBST) based on given sorted keys and their associated search probabilities. It calculates the minimum expected search cost using dynamic programming by evaluating various tree configurations. The program prompts the user for the number of keys and their probabilities, then outputs the minimum expected cost of the OBST.

Uploaded by

omshi112233
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as TXT, PDF, TXT or read online on Scribd
16 views1 page

K K 1

The document presents a C++ program that constructs an optimal binary search tree (OBST) based on given sorted keys and their associated search probabilities. It calculates the minimum expected search cost using dynamic programming by evaluating various tree configurations. The program prompts the user for the number of keys and their probabilities, then outputs the minimum expected cost of the OBST.

Uploaded by

omshi112233
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as TXT, PDF, TXT or read online on Scribd
You are on page 1/ 1

/*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? */
#include<iostream>
#include<vector>
#include<limits>
using namespace std;

float sum(const vector<float>& p, int i, int j){


float total = 0;
for(int k = i ;k <= j; k++)
total += p[k];
return total;

}
float optimalBST(const vector<float>& p,int n){
vector<vector<float>>cost(n,vector<float>(n,0));
for(int i= 0 ; i<n ; i++){
cost[i][i]=p[i];
}
for(int L=2 ; L<=n ; L++){
for(int i=0 ;i <= n-L ;i++){
int j = i + L - 1;
cost[i][j]=numeric_limits<float>::max();

for(int r = i ;r <= j; r++){


float left = (r>i)?cost[i][r-1] : 0;
float right = (r<j)?cost[r+1][j] : 0;
float total = left + right + sum(p,i,j);
cost[i][j]=min(cost[i][j],total);
}

}
}
return cost [0] [n-1] ;
}

int main(){
int n;
cout<<"Enter no of keys : ";
cin>>n;
vector<float> p(n);
cout<<"Enter probabilities for "<< n <<" keys : ";
for(int i = 0; i < n ; i++){
cin>>p[i];
}
float minCost = optimalBST(p , n );
cout<<"Minimum expected cost of OBST is "<< minCost <<endl;

return 0;

You might also like