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.

By placing frequently accessed keys closer to the root, the total weighted path length is reduced. The expected number of comparisons is the total weighted cost divided by the total frequency.

Dynamic Programming Recurrence

The optimal cost for a sequence of keys from index i to j can be computed using dynamic programming. Let C(i, j) be the optimal weighted comparison cost for searching the keys in the interval [i, j].

C(i, j) = sum(f_k for k=i..j) + min_r(C(i, r-1) + C(r+1, j))

For an empty interval, the cost is 0. By iterating through all possible lengths and starting indices, we build up the costs for all intervals up to the full sequence. In our case of three keys, we evaluate the intervals [10], [20], [30], [10, 20], [20, 30], and [10, 30].

Worked example: Frequencies 2, 3, 1

Consider the frequencies f(10)=2, f(20)=3, and f(30)=1. The total frequency is 6. We evaluate the five valid binary search tree shapes:

Tree Structure (Preorder)	Weighted Cost Calculation	Total Cost
[10, 20, 30]	1×2 + 2×3 + 3×1	11
[10, 30, 20]	1×2 + 3×3 + 2×1	13
[20, 10, 30]	2×2 + 1×3 + 2×1	9
[30, 10, 20]	2×2 + 3×3 + 1×1	14
[30, 20, 10]	3×2 + 2×3 + 1×1	13

The tree with root 20 and preorder [20, 10, 30] yields the minimal cost of 9. The expected number of comparisons is exactly 9/6, which reduces to 3/2.

Experiment: Finding optimal structures

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

Set Frequency 10 to 3, Frequency 20 to 1 and Frequency 30 to 1. Reset rewinds the trace while preserving those frequencies.
Press Step three times to evaluate the three length-one intervals in order: C(0, 0), C(1, 1), and C(2, 2).
Continue pressing Step to evaluate intervals of length 2 and finally the full sequence of length 3.
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.
Adjust the slider for Frequency 20 to 4 and Frequency 10 to 1. The total frequency is now 6.
Press Finish. The root key shifts to 20, with preorder [20, 10, 30], cost 8, and expected comparisons 4/3.
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.

Limitations

This module fixes the number of keys to three and does not consider unsuccessful searches (searches for keys not in the tree). In a more general optimal binary search tree model, probabilities for missing keys (gaps) are also included in the dynamic programming recurrence.

The keys are structurally constrained to 10, 20, and 30, and the frequencies are restricted to integers from 0 to 9 to allow for tractable step-by-step trace generation.

References

The formulation of the dynamic programming solution for the optimal binary search tree, including the interval recurrence and successful-search cost, is covered extensively in literature.

CMU 15-451: Dynamic Programming, Section 7, covers successful-search cost and the interval recurrence.

Optimal Binary Search Tree