Let \(π=4\) and \((π_1,π_2,π_3,π_4)\) = (do, if, int, while). Letβ¦
2015
LetΒ \(π=4\)Β andΒ \((π_1,π_2,π_3,π_4)\)Β = (do, if, int, while). LetΒ \(π(1:4)\) = \((\frac 3 8,\frac 3 8,\frac 1 8, \frac 1 8)\)Β andΒ \(π(1:4)=(\frac 2 8,\frac 3 8,\frac 1 8,\frac 1 8,\frac 1 8)\)Β whereΒ \(π(π)\)Β andΒ \(π(π)\)Β denotes the probability with which we searchΒ \(π_π\)Β and the identifierΒ \(π₯\)Β being searched satisfyΒ \(π_π < π₯ < π_{π+1}\)Β respectively. The optimal search tree is given by:
Attempted by 157 students.
Show answer & explanation
Answer: The optimal search tree is the tree with 'if' as the root, 'do' as its left child, and 'int' as its right child with 'while' as the right child of 'int'.
Reasoning (compute expected search cost):
For the chosen tree (root = 'if'): key depths are: do at depth 2, if at depth 1, int at depth 2, while at depth 3.
Contribution from keys: (3/8)*2 + (3/8)*1 + (1/8)*2 + (1/8)*3 = 14/8 = 1.75.
External (dummy) node depths and contribution: q0, q1, q2 are at depth 3 and q3, q4 are at depth 4, so (2/8)*3 + (3/8)*3 + (1/8)*3 + (1/8)*4 + (1/8)*4 = 26/8 = 3.25.
Total expected cost = 1.75 + 3.25 = 5.0.
Comparison with the other candidate trees (computed similarly):
Tree with 'int' as root (and 'if' left, 'while' right, 'do' under 'if'): expected cost = 5.875.
Tree with 'while' as root (and 'if' left, 'do' under 'if', 'int' right): expected cost = 5.75.
Tree with 'if' as root but 'int' as left child and 'while' as right child: expected cost = 5.625.
Since the tree with 'if' as root yields the smallest expected cost (5.0), it is the optimal search tree.