15.5

Exercises 15.5-1

Write pseudocode for the procedure CONSTRUCT-OPTIMAL-BST(root) which, given the table root, outputs the structure of an optimal binary search tree. For the example in Figure 15.8, your procedure should print out the structure

• k2 is the root
• k1 is the left child of k2
• d0 is the left child of k1
• d1 is the right child of k1
• k5 is the right child of k2
• k4 is the left child of k5
• k3 is the left child of k4
• d2 is the left child of k3
• d3 is the right child of k3 * d4 is the right child of k4
• d5 is the right child of k5

Answer

implementation

Exercises 15.5-2

Determine the cost and structure of an optimal binary search tree for a set of n = 7 keys with the following probabilities:

i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 :---:|:---:|:---:|:---:|:---:|:---:|:---: pi | | 0.04 | 0.06 | 0.08 | 0.02 | 0.10 | 0.12 | 0.14 qi | 0.06 | 0.06 | 0.06 | 0.06 | 0.05 | 0.05 | 0.05 | 0.05

Answer

run my program you will get the answer.

Exercises 15.5-3

Suppose that instead of maintaining the table w[i, j], we computed the value of w(i, j) directly from equation (15.17) in line 8 of OPTIMAL-BST and used this computed value in line 10. How would this change affect the asymptotic running time of OPTIMAL-BST?

Answer

时间复杂度依旧是O(n^3).虽然原来的计算方法计算w只用了O(n^2),但算法有一个三重循环.

Exercises 15.5-4 *

Knuth [184] has shown that there are always roots of optimal subtrees such that root[i, j - 1] ≤ root[i, j] ≤ root[i + 1, j] for all 1 ≤ i < j ≤ n. Use this fact to modify the OPTIMAL-BST procedure to run in Θ(n2) time.

Answer

第9行替换为:

if i = j
	r <- j
else
	for r <- root[i,j-1] to root[i+1,j]

Follow @louis1992 on github to help finish this task.