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.10, your procedure should print out the structure

Figure 15.10

k₂ is the root

k₁ is the left child of?k²

d₀ is the left child of?k¹

d₁ is the right child of?k¹

k₅ is the right child of?k²

k₄ is the left child of?k⁵

k₃ is the left child of?k⁴

d₂ is the left child of?k³

d₃ is the right child of?k³

d₄ is the right child of?k⁴

d₅ is the right child of?k⁵

corresponding to the optimal binary search tree shown in Figure 15.9(b).

Transcribed Image Text:

5. 1 5 1 j (2.75 i j (1.00 4 <1.75 3 (1.25 1.20X1.30 4 0.70 i 2.00 3 (0.80 4 0.90 3 (0.55X0.50X0.60 0.35 2 4 0.90X0.70X0.60 0.45 0.25 (0.30 0.50 5 0.35 1 0.45X0.400.25 0.05 0.10 0.30 0.50 0.05 0.05 0.10 0.15 0.20 0.05 0.30 0.05 0.05 0.10 0.05 0.05 0.10 root 5 1 j 2 i 4. 2 4 3 2 3 2 1 4 5 4. 4 2. 2. 3. 2. 2. of