A greedy approach to the optimal binary search tree problem would proceed as follows: For the root, choose the key with the greatest probability. For each subtree, choose the root to be the key with the greatest probability of those in the subtree, and so on. Show that this greedy algorithm works on the set of keys given in Problem 105. Then find a another list of keys and probabilities for which this greedy algorithm fails to give the optimal binary search tree.

Problem 105. Determine the expected cost of searching for a node in the following bina search tree, given the key probabilities below Then propose a single left rotation that will reduce the cost of the tree. Key: 1 3 4 5 6 7 8 9 10 11 pi 0.20 0.20 0.01 0.04 0.05 0.05 0.05 0.10 0.10 0.10 0.10 10 1 3 5 7