C++ Program for OBST (Optimal Binary Search Tree)














































C++ Program for OBST (Optimal Binary Search Tree)



This is a Program to understand Optimal Binary Search Tree.

So First of all What is the Problem Statement?

Given a sorted array key[0.. n-1] of search keys and an array freq[0.. n-1] of frequency counts, where freq[i] is the number of searches for keys[i]. Construct a binary search tree of all keys such that the total cost of all the searches is as small as possible.


we organize a binary search tree so as to minimize the number of nodes visited in all searches, given that we know how often each element occurs, For this what we need is an Optimal Binary Search Tree.


Formally, we are given a sequence K = <k1, k2, ... , kn> of n distinct keys in sorted order,

(so that k1 < k2 < ... < kn), and we wish to build a binary search tree from these keys. For each key ki, we have a probability pi that a search will be for ki Some searches may be for values not in K, and so we also have n + 1 “dummy keys” d0, d1, d2, ... , dn representing values not in K.


Because we have probabilities of searches for each key and each dummy key, we can determine the expected cost of a search in a given binary search tree T.


General formula for calculating the minimum cost is:

C[i,j] = min{c[i, k-1] + c[k,j]} + w(i,j) 



Here is the sample code for more clarification.

C++ CODE 

#include <bits/stdc++.h> using namespace std; int sum(int frequency[], int i, int j) { int sum = 0; for (int x = i; x <= j; x++) sum += frequency[x]; return sum; } int optimalCost(int frequency[], int i, int j) { if (j < i) return 0; if (j == i) return frequency[i]; int frequencySum = sum(frequency, i, j); int min = INT_MAX; for (int r = i; r <= j; ++r) { int cost = optimalCost(frequency, i, r - 1) + optimalCost(frequency, r + 1, j); if (cost < min) min = cost; } return min + frequencySum; } int optimalSearchTree(int keys[], int frequency[], int n) { return optimalCost(frequency, 0, n - 1); } int main() { int keys[] = {10, 12, 20}; int frequency[] = {34, 8, 50}; int n = sizeof(keys) / sizeof(keys[0]); cout << "Cost of Optimal BST is " << optimalSearchTree(keys, frequency, n); return 0; } /* OUTPUT Cost of Optimal BST is 142 */

More Articles of Anand Dasani:

Name Views Likes
C++ Program for OBST (Optimal Binary Search Tree) 4135 1
C++ Program for Matrix Chain Multiplication 3027 1
C++ Program for Huffman Code 3601 1
C++ Program for 8 Queen problem 2794 1
C++ Program for KnapSack Problem TopDown Solution 576 1
C++ Program for KnapSack Problem Memoization Solution 722 1
C++ Program for KnapSack Problem Recursive Solution 629 1
C++ Program for Tower Of Hanoi problem 507 1
C++ Program to Evaluate the Postfix string using stack 439 1
C++ Program to check Balanced Parenthesis in string using stack 447 1
C++ Program for String Palindrome check using stack 2997 1
C++ Program to Convert Infix Expression to Prefix Expression including Parenthesis 337 1
C++ Program To Convert Infix Expression to Prefix Expression without Parenthesis 663 1
C++ PROGRAM TO CONVERT INFIX EXPRESSION TO POSTFIX EXPRESSION WITHOUT PARENTHESIS 333 1
C++ Program to Convert Infix Expression to Postfix Expression including Parenthesis 357 1
C++ Program to Convert Decimal Value to Hexa Decimal using Stack 798 1
C++ Program to Convert Decimal Value to Octal using Stack 983 1
C++ Program to Convert Decimal Value to Binary using Stack 612 1
C++ Program for Upper Triangular Matrix 587 1
C++ Program for Lower Triangular Matrix 317 1
C++ Program for Diagonal Matrix 465 1
C++ Program to Perform Full Deletion operation in BST 278 1
C++ Program to count the nodes having Degree 2 in BST 649 1
C++ Program to count the nodes having 1 Degree in BST 482 1
C++ Program to count the nodes having 0 Degree in BST 338 1
C++ Program to count the Height of Binary Search Tree 299 1
C++ Program to prevent deletion of node having degree 2 in Binary Search Tree 261 2
C++ Program to prevent deletion of node having degree 0 or 1 in Binary Search Tree 279 1

Comments