Optimal Binary Search Tree

6.20

Pattern · interval + split point (CMM-style) 2-D table O(n³) 8difficulty

Question — exam style

Suppose we know the frequency with which keywords occur in programs of a certain language, and we want to organize them in a binary search tree (in-order = sorted key order). When a keyword is looked up, its cost is the number of comparisons, i.e. its depth in the tree plus one. Weighting by frequency, the cost of a tree is the expected number of comparisons to look up a word. Give an efficient algorithm for the following.

Input:n words in sorted order; their frequencies (probabilities) p[1], p[2], …, p[n].

Output:The cost of the lowest-cost BST (expected number of comparisons to look up a word).

Model answer

4-part format

aSubproblem in words

C(i, j) = the cost of the optimal BST built on the contiguous block of keys i, i+1, …, j, for 1 ≤ i ≤ j ≤ n.

Let P(i, j) = p[i] + p[i+1] + … + p[j] be the total frequency of the block (precompute prefix sums so this is O(1)).

bRecurrence math only, with base cases + bounds

C(i, i-1) = 0 for 1 ≤ i ≤ n+1 (empty block) C(i, j) = P(i, j) + min{ C(i, r-1) + C(r+1, j) : i ≤ r ≤ j } for 1 ≤ i ≤ j ≤ n

Choose a root r in the block. Its two children are the optimal BSTs on the left block [i..r−1] and right block [r+1..j]. Making r the root pushes every key in the block one level deeper, adding exactly P(i, j) to the cost. Try all roots; take the best. Same "pick a split point in a window" engine as Chain Matrix Multiply.

cImplementation analysis

(1) # of subproblems

O(n²)

(2) Time to fill table

O(n³) — O(n) roots per entry

(3) Where answer is extracted

C(1, n)

(4) Time to extract

O(1)

The O(n³) signature

Two window indices give O(n²) cells; a split/root loop inside each gives the extra factor of n. Whenever you see "choose where to split / parenthesize / root a range," expect a 2-D window table filled in O(n³). Only CMM, Optimal BST, and Floyd–Warshall hit O(n³) in this course.

Optional pseudocode not required by Ed #9

A mechanical translation. Outer loop over block length; inner loop over the root r — that's the O(n³).

function OptimalBST(p[1..n]):
    # P(i,j) via prefix sums, O(1) lookup
    for i = 1 to n+1: C[i][i-1] = 0        # empty blocks
    for len = 1 to n:                    # block length
        for i = 1 to n-len+1:
            j = i + len - 1
            C[i][j] = ∞
            for r = i to j:              # choose root
                C[i][j] = min(C[i][j], C[i][r-1] + C[r+1][j])
            C[i][j] = C[i][j] + P(i,j)
    return C[1][n]

✎

Try it yourself

worked example + self-test

C(i,j)=P(i,j)+min_r{C(i,r−1)+C(r+1,j)}. Answer C(1,n). (Integer freqs → cost = Σ freq·(depth+1).)

Worked P and C tables shown

4 keys k1..k4, frequencies p = [34, 8, 50, 8] (Σ = 100)

P(i,j) block sums: C(i,j) costs (fill by block length): j1 j2 j3 j4 j1 j2 j3 j4 i1 34 42 92 100 i1 34 50 142 158 ← answer i2 8 58 66 i2 8 66 82 i3 50 58 i3 50 66 i4 8 i4 8 C(1,4): try roots r=1..4 → r=3 best: C(1,2)+C(4,4)=50+8=58 ; +P(1,4)=100 → 158

Answer: C(1,4) = 158. Optimal tree: root k3, left subtree {k1→k2}, right child k4. Check: 50·1 + 34·2 + 8·3 + 8·2 = 158. ✓

Self-test build P then C, then reveal

4 keys, frequencies p = [25, 10, 40, 15]

Reveal answer

Optimal cost = 150. (Spares to practice on: [10,20,30,40] → 180; [5,60,5] → 80.)