explore the dynamic programming method for building an Optimal Binary
Search Tree in C++. Specifically you will design a class (OptimalBST) that, given an array of n keys (int K,
do not assume that K is sorted!) and probabilities, (double P) of each key, builds an Optimal Binary Search
Tree. Note that P[i] denotes the probability of key K[i] (p(ki)). Your function will return a pointer to the
root node of the constructed binary search tree.
I have created a header and source file that you must
use, OptimalBST.h and [url removed, login to view], available on the recitation web page. Refer to this file for further
create your own test driver and test your class on as many different instances as
you can since one instance never proves that your algorithm always works correctly.