Optimal Binary Search Tree

An optimal binary search tree rearranges ordered keys to minimize the expected search cost. In this explorer, we consider a fixed set of three keys: 10 < 20 < 30. Each key has an associated integer frequency representing the number of successful searches for that key.

Experiment: Finding optimal structures

Open the Optimal Binary Search Tree explorer to observe the dynamic programming algorithm in action.

1. Set Frequency 10 to 3, Frequency 20 to 1 and Frequency 30 to 1. Reset rewinds the trace while preserving those frequencies.
2. Press Step three times to evaluate the three length-one intervals in order: C(0, 0), C(1, 1), and C(2, 2).
3. Continue pressing Step to evaluate intervals of length 2 and finally the full sequence of length 3.
4. Press Finish to immediately reveal the terminal state. The chosen tree has root 10, preorder keys [10, 20, 30], weighted comparison cost 8, and expected comparisons 8/5.
5. Adjust the slider for Frequency 20 to 4 and Frequency 10 to 1. The total frequency is now 6.
6. Press Finish. The root key shifts to 20, with preorder [20, 10, 30], cost 8, and expected comparisons 4/3.
7. Set all frequencies to 0. Press Finish. The weighted comparison cost is 0, and the expected comparisons are "Undefined: no searches" rather than a numerical zero, as an empty domain has no defined expectation.