Chapter 8 · Dynamic Programming
Optimal Binary Search Tree
Some keys are searched far more often than others. An optimal Binary Search Tree (BST) puts popular keys near the root so the average number of comparisons is as small as possible. Dynamic programming finds it by trying every root for every range of keys — shortest ranges first.
predictions: 0 / 0
Up to 8 keys. Probabilities need not add up to 1 (they act as weights); only successful searches are modelled, as in Levitin §8.3.
Cost table C[i, j]
Root table R[i, j]
🤔 Predict:
Root candidates k for the current cell
Tree
cell being filled
sub-tree costs read for candidate k
best so far / final answer
root chosen from R
unused (j < i − 1)
How to read this
- C[i, j] is the smallest average number of comparisons for a BST holding keys i..j. R[i, j] is the root that achieves it. Empty ranges C[i, i − 1] cost 0.
- The tables fill diagonal by diagonal: first single keys (d = 0), then pairs (d = 1), triples, … up to all n keys in the top-right corner C[1, n].
- For each cell, every key k in i..j is tried as the root. The two yellow cells are the optimal left subtree C[i, k − 1] and right subtree C[k + 1, j]. Putting them under a new root pushes every key one level deeper, which adds P[i] + … + P[j].
- The candidate table on the left-bottom shows each k's total; the green row is the current minimum.
- After the tables, the tree is rebuilt from R: the root of 1..n is R[1, n], its left child is R[1, k − 1], and so on.
Try this
- Run the textbook example (A, B, C, D with 0.1, 0.2, 0.4, 0.3). Check the corner: C[1, 4] = 1.7 with root C, left child B (whose left child is A) and right child D.
- Make the probabilities equal (0.25 each). Does the tree become as balanced as possible? What is C[1, 4] now?
- Give one key almost all the weight (e.g. 0.01, 0.01, 0.01, 0.97). Predict the root before playing.
- Count the candidates for n = 4: Σ (n − d)(d + 1) over d = 1..3 = 6 + 6 + 4 = 16. Watch the “k tried” counter. For n = 8 the count grows like n³/6 — the algorithm is Θ(n³).
- Turn on 🤔 Predict. Levitin notes R[i, j] always lies between R[i, j − 1] and R[i + 1, j]. Use that to guess the root faster.