Let a1< a2< a3< a4< a5< a6 be 6 numbers accessible with the following probabilities: p1 = 1/20, p2 = 1/20, p3 = 3/20, p4 = 5/20, p5 = 4/20 and p6=1/20. Let q0 be the probability of searching for an item a6, and qi the probability of searching for an item between ai and ai+1 for i = 1, 2, 3, 4, 5. Take q0=0, and qi = 1/20 for i=2,...,6. You are to construct an optimal binary search tree.

a. Write down a table for the wij's, and a table for the Cij's and their corresponding rij's as defined in the algorithm for optimal binary search trees.

b. Construct the optimal binary search tree.