An OBST (optimal BST) minimizes the average search time across
all keys in the BST. Given 5 ordered keys.
k1<k2<k3<k4<k5, with probabilities of occurrence (0.25,
0.15, 0.10, 0.20, 0.30), respectively
Use a Greedy algorithm that attempts to construct a BST that is
an OBST.
What is the complexity of your Greedy
algorithm?
Is your Greedy BST an OBST? Explain
apply the DP algorithm to acquire an OBST
show your work, including tables and the extraction of the
actual OBST
analyze...