Motivation
A balanced search tree minimizes worst-case depth up to constants, but not every key may be requested equally often. If one key is queried much more frequently than the others, placing it near the root can lower the expected number of comparisons. Unsuccessful searches matter too: different gaps between keys can have different query probabilities.
We derive an interval dynamic program that chooses the best tree for known query weights. The state accounts for the ordered keys and the gaps surrounding them, and the recurrence charges one comparison to every query reaching the root of a nonempty subtree. A root table then reconstructs an optimal tree.
Definitions and cost convention
Definition 2.11.1
(Keys, query weights and the comparison cost)
Let be distinct ordered keys. A successful query asks for with weight . An unsuccessful query falls into one of gaps: is the weight below , for is the weight strictly between and , and is the weight above . If the weights sum to one, the objective below is an expected number of key comparisons. The recurrence also works for arbitrary nonnegative weights without normalization.
A search compares the query against a key at each visited internal node. An unsuccessful search ends upon reaching an empty child; that empty child does not itself make a key comparison. Thus, in an empty tree, a failed search costs zero comparisons. The one comparison at a nonempty root is charged to every successful or unsuccessful query reaching that root.
Definition 2.11.2
(Interval cost and total weight)
For , let be the least weighted comparison cost of a tree containing exactly keys , for their successful weights and the surrounding gap weights . The cost is measured with the subtree root at comparison depth one, ignoring any ancestors outside that subtree. For an empty interval set .
Define the total weight of a nonempty subproblem by
Theorem 2.11.3
(Optimal-search-tree recurrence)
For every nonempty interval,
The value is the minimum weighted comparison cost, and stored minimizing roots reconstruct an optimal tree. For , the empty tree has cost zero under the stated convention.
Theorem 2.11.4
(Dynamic-programming complexity)
Using prefix sums for and evaluating intervals in increasing length gives an -time, -space algorithm in the arithmetic/comparison model. No faster root-search optimization is assumed.
Proof: condition on the root
Proof
(Conditioning on the root)
Consider any search tree on and let its root be . The binary-search property forces the left subtree to contain exactly and the right subtree to contain exactly . The corresponding gap weights split into and ; the successful query for ends at the root.
Every query in the subproblem makes one comparison at that root, contributing . Its further comparisons occur entirely in the appropriate child subtree. Thus the tree's cost is
For this fixed root, neither child can cost less than the optimum for its interval, and choosing optimal children attains their sum. Minimizing over all possible roots proves the recurrence. Induction on interval length establishes every state, including empty child intervals. The root that attains the minimum is stored along with the value; recursively using stored roots yields an ordered tree attaining the optimum.
Proof X-ray
Charge every query once at the root
Successful key weights and unsuccessful gap weights all pay one comparison when they enter a nonempty subtree. After that comparison, only the chosen child incurs further cost. This separates the root charge from the two independent smaller interval problems. The one non-obvious point is that the left and right interval problems are independent: the binary-search property fixes which keys and gaps lie on each side, so no weight is shared, and the cost inside one child does not depend on the shape of the other. The induction on interval length closes because both children are strictly shorter, with the empty interval as the base; ties in the minimum do not affect its value.
The empty-interval base is zero because reaching an empty child requires no additional key comparison. Some presentations count an external dummy node as an extra operation and therefore use a different base and objective. Both conventions can be consistent, but mixing their recurrence and base values changes the answer.
Evaluation and reconstruction
Proof
(Counting intervals and candidate roots)
Precompute prefix sums of the and weights, so can be evaluated in constant arithmetic time. There are intervals. For an interval of length , try its possible roots; summing over all lengths gives candidate evaluations. Store each cost and one minimizing root in two tables.
To reconstruct, start with the stored root for . Recursively reconstruct its left and right intervals; an empty interval gives an empty child. Each key becomes one node, so reconstruction uses output nodes and additional traversal work. If several roots tie, any recorded minimizer gives an optimal tree.
The stated cost model treats additions and comparisons as constant-time operations. With rational weights encoded in binary, exact arithmetic and the bit lengths of intermediate sums require separate accounting. The analysis does not assume that query probabilities are known exactly in an application; it says what tree is optimal for the supplied weights.
A direct cost check
A complete candidate tree can be evaluated independently of the dynamic program. For each successful key , count the number of key nodes on the root-to- path and multiply by . For each gap, count the key nodes on the path to the corresponding empty child and multiply by that gap's weight. Summing these terms gives the same objective charged by the recurrence. This direct computation is useful for checking a reconstructed tree on a small example.
For instance, with keys and root , the first and third keys are its left and right children. Each successful query for or pays two comparisons, while a query for pays one. All four unsuccessful gaps reach an empty child below one of the two children and therefore pay two comparisons. The weighted cost is
The recurrence yields the same expression: it charges the total weight once at the root and then charges the left and right subtree weights once more. If a missing child is reached directly from the root instead, the corresponding gap pays only the root comparison.
Concept lensStructural
Cost as a sum of subtree weights
Each key node of a candidate tree is compared against exactly those queries whose search path passes through it, and these are exactly the queries whose key or gap lies in the interval covered by that node's subtree. So the weighted cost of a tree equals the sum, over its key nodes , of the total weight of the interval below , that is, the sum of over the intervals of its subtrees. This is the depth-based count above written node by node instead of query by query. For the three-key tree with root the three intervals are , and , and equals ; the recurrence is this sum with the minimization carried out interval by interval.
Prefix sums implement the weight calculation without repeatedly summing an interval. Set with , and with the convenient convention . Then . The index occurs when ; the convention includes the leftmost gap correctly. Explicitly checking a one-key interval is a useful way to catch an off-by-one error in this formula.
An interval table also avoids recomputing the same subproblem in many candidate trees. The interval to the left of a proposed root depends only on its endpoints, not on the particular ancestors above it; their comparisons were already charged outside the subproblem. This is the optimal-substructure reason a single stored value can represent many different larger candidate trees. The cubic running-time bound is a worst-case count for trying every candidate root. The number of comparisons used by a search in the final tree is a different quantity: it depends on that tree's shape and the query. A more efficient preprocessing algorithm would not change the definition of an optimal search cost, and an optimal expected cost does not imply that every query uses logarithmically many comparisons.
Why gaps change the answer
Consider two keys with no successful queries: , and gap weights , . The total weight is one. If is the root, queries below it stop after one comparison; the right subtree has weight , so the cost is . If is the root, the left subtree carries weight , so the cost is . The most common failed-search gap affects which key should be near the root even though no successful key has positive weight.
This is why treating unsuccessful queries as a single undifferentiated probability is insufficient. A failed query below all keys follows a different path from one above all keys. The gaps are exactly the leaves of the search decision structure and must be distributed among the correct subproblems.
Counterexample mode
A balanced root need not minimize expected cost
With three keys, successful weights and all gap weights zero, choosing the middle key as root gives cost . Choosing the first key as root and placing the other two below it gives cost . Balancing by key count alone ignores the workload.
Worked examples
Worked example 2.11.5
(One key)
With one key of weight and two gap weights , every query makes exactly one comparison. The recurrence gives . Both child intervals have cost zero, even though their gap weights still contribute to the root charge.
Worked example 2.11.6
(Two keys with mixed queries)
Take , , and . The full weight is one. Root leaves a right subproblem of weight , giving cost . Root leaves a left subproblem of weight , giving cost . The optimal root is .
Worked example 2.11.7
(A zero-weight query class)
If every and is zero, every tree has weighted cost zero. The recurrence allows arbitrary ties and can record any root. A zero weight does not remove a key from the tree; it only means that its query contributes no cost to this objective.
Worked example 2.11.8
(The empty tree)
If , there are no key comparisons. Even when the sole unsuccessful-query weight is one, the cost is zero under our convention because the search immediately reaches the empty tree. A different convention that charges for inspecting a dummy leaf would count a different quantity.
Common mistakes
Common mistake
(Assigning a gap to the wrong child)
The gap belongs to the right child when is the root; the gap belongs to the left child. They describe different ranges of query values. Carefully partitioning the gaps prevents a weight from being omitted or counted in both children. For two keys with root , the left subproblem is with gaps , and the right subproblem is empty with its gap .
Common mistake
(Charging only the root key's weight at the root)
The root charge is the weight of all queries reaching that subproblem, not just the successful weight of the root key. An unsuccessful query also compares with every key on its search path. The base for an empty child is zero only because that child adds no further key comparison. In the two-key example with root , the root charge is the whole weight , not .
Common mistake
(Reading the optimum as a guarantee)
Finally, an optimal tree depends on the supplied weights and cost convention. It is not a claim that those weights will accurately predict future traffic, or that minimizing expected comparisons also minimizes worst-case depth. A balanced tree and a weighted-optimal tree solve different objectives. If the workload changes over time, the supplied weights and the cost of rebuilding the tree should be reconsidered.
Summary
For each key interval, try every possible root. All query weight in that interval pays one root comparison, then the two child intervals contribute independent optimal costs. Prefix sums and increasing-length evaluation give a cubic-time dynamic program, and stored roots recover a witness. Gap weights and the empty-child convention are essential to the result.
Exercises
Quick check
(Compute the optimal cost for one key with and .)
Every query reaches the only node.
Solution · Answer
Every query visits the single key, so the cost is comparison on average.
Quick check
(For two keys with , and all three gaps of weight , compute the cost of each root.)
Add the weight of the subtree left below each root to the total weight.
Solution · Answer
The full weight is one. Root has a right-subtree weight of , giving ; root has a left-subtree weight of , giving .
Quick check
(Explain why even when the corresponding gap weight is positive.)
Ask which comparisons a failed query makes before reaching an empty child.
Solution · Answer
The unsuccessful query has already paid for each ancestor key comparison before reaching this empty child. An empty subtree contains no key to compare against and contributes zero additional comparisons under the stated convention.
Quick check
(For three keys with successful weights and zero gap weights, compare the middle-root cost with the tree rooted at the first key and then the second.)
Compute the depth of each key in the two trees.
Solution · Answer
The middle-root cost is . The first-root, second-child tree costs . This example shows that balanced by key count need not be optimal for the supplied weights.