Optimal Binary Search Trees

1Expected cost is frequency times depth plus one

Fix sorted keys k_1 < \cdots < k_n and a frequency p_i for each. Any BST on those keys is legal — the in-order is already fixed — but the depths change with the shape. The cost of a tree is \sum_i p_i \cdot (\mathrm{depth}(k_i)+1), counting the comparison at the node itself as one. An optimal BST is a shape that minimises that sum.

A perfectly balanced tree can lose. If one key is requested far more than the others, it belongs near the root even if the two sides then have different sizes. Balance minimises worst-case depth; this DP minimises weighted external path.

Figure. Optimal tree on frequencies 3, 1, 2: A at the root, C to its right, B left of C. Cost 3*1 + 1*3 + 2*2 = 10.

Score one tree

1. DepthsRoot has depth 0, so it is charged p once. A child is charged 2p.
2. SumAdd p_i \cdot (\mathrm{depth}_i+1) over every key.
3. Compare shapesThe legal BSTs on the same keys; pick the cheapest sum.

2e[i,j] = w[i,j] plus the best split

Let e[i,j] be the minimum cost of a BST on the contiguous key range k_i,\ldots,k_j, and let w[i,j] = p_i+\cdots+p_j. Choose a root k_r in that range. The left keys k_i,\ldots,k_{r-1} and the right keys k_{r+1},\ldots,k_j must themselves be optimal BSTs — optimal substructure — and every search in the range pays one comparison at k_r, which is exactly w[i,j].

So e[i,j] = w[i,j] + \min_{i \le r \le j}\bigl(e[i,r-1] + e[r+1,j]\bigr). Empty sides are e[i,i-1] = 0. A single key is e[i,i] = p_i. The w[i,j] addend is the charge: every search in the range pays one comparison at the chosen root.

Figure. e[i,j] = w[i,j] plus the min over roots r of e[i,r−1] + e[r+1,j]. On range A,B,C with w=6 and root A, the empty left side is 0 and e[B,C]=4, so e[A,C]=10. The 6 charges one comparison at A for every search in the range.

One cell

1. Weightw[i,j] = sum of frequencies in the range.
2. Try each rootFor each r, add the two already-optimal sides.
3. Charge the rootAdd w[i,j] once. That is the +1 on every depth in the range.

3Fill by increasing span

A cell e[i,j] reads only strictly smaller ranges, so the table is filled by increasing j-i. Fill order is increasing span. Span 0 is the diagonal e[i,i]=p_i. Span 1 tries two roots. Span n-1 is the full instance.

On frequencies 3, 1, 2 the span-1 cells are e[A,B]=5 (root A) and e[B,C]=4 (root C). The span-2 cell is e[A,C]=10 (root A), because the three candidate sums are 10, 11 and 11.

Figure. Fill order: diagonal 3,1,2 then span-1 cells 5 and 4 then the full-range 10. Not a BST drawing — a dependence triangle.

Three spans

1. Span 0e[A]=3, e[B]=1, e[C]=2.
2. Span 1e[A,B]=4+\min(1,3)=5; e[B,C]=3+\min(2,1)=4.
3. Span 2e[A,C]=6+\min(4,5,5)=10.

Optimal BST table

def optimal_bst(p):
    n = len(p)
    e = [[0] * (n + 1) for _ in range(n + 2)]
    w = [[0] * (n + 1) for _ in range(n + 2)]
    root = [[0] * (n + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        e[i][i] = w[i][i] = p[i - 1]
        root[i][i] = i
    for span in range(1, n):
        for i in range(1, n - span + 1):
            j = i + span
            w[i][j] = w[i][j - 1] + p[j - 1]
            e[i][j] = min(
                e[i][r - 1] + e[r + 1][j] + w[i][j]
                for r in range(i, j + 1)
            )
            root[i][j] = min(
                range(i, j + 1),
                key=lambda r: e[i][r - 1] + e[r + 1][j] + w[i][j],
            )
    return e[1][n], root

Coding lab. Fill the three-key cost table runs in the app, with checks on your output.

4O(n³) cells, O(n) roots each

There are O(n^2) ranges (i,j) and each tries O(n) candidate roots, so the straightforward fill is O(n^3) time and O(n^2) space. Storing \mathrm{root}[i,j] lets you rebuild the tree in O(n) after the table exists.

Knuth observed that the optimal roots are monotonic — \mathrm{root}[i,j-1] \le \mathrm{root}[i,j] \le \mathrm{root}[i+1,j] — which cuts the inner search to amortised O(1) per cell and the time to O(n^2). That speedup is a named remark, not a proof this topic invents. For n=3 the cubic and quadratic algorithms do the same six useful cells.

The span triangle already shows the six cells. The new content is the O(n^3) versus O(n^2) row.