Problem 6 (13 points) In class we stindied an algorithm which, given the probabilities-of-query for each of the keys and "gaps". in a binary search tree, determined the optimal (i.e., least-average-search-cost) structure for the tree. Determine an optimal binary search treo containing precisely the following keys, with the indicated corresponding query probabilities, assuming that all queries are for keys that are present in the tree (i.c., that all gap probabilities are zero). ALPHA BAKER CHARLIE DELTA ECHO FOXTROT GOLF HOTEL 0.12 0.06 0.11 0.08 0.13 0.26 0.04 0.20 (a) Give the ROOT table for the optimal binary search tree. (b) Draw the optimal binary search tree, being sure to include the associated key value in each node. (c) Give the average search cost for the optimal binary search tree (again assuming that all queries will be for keys that are present in the tree). Round your answer to the nearest 0.01 : AVERAGE SEARCH COST =