Optimal BST, in depth: from access logs to a deployed lookup tree, with smoothed weights, root reconstruction, weight-balanced approximation and drift-based rebuilds

The cost model, and the floor no tree can beat

Number the sorted keys k1 to kn. Every lookup either hits a key, with probability p_i, or misses and lands in one of the n + 1 gaps between keys, with probability q_j: gap 0 is everything smaller than k1, gap n is everything larger than kn. Each internal node does one three-way comparison (less, equal, greater). A hit on a node at depth d costs d + 1 comparisons; a miss costs the number of nodes on the path to the empty slot it falls into.

The objective is the expected cost, the sum of p_i times (depth + 1) plus the sum of q_j times the miss path length. Two consequences follow. Misses are not free: a hot gap pulls its neighbouring keys towards the root just as a hot key does. And the cost is linear in the weights, so scaling all counts leaves the optimal shape unchanged.

There is also a floor. Each comparison has three outcomes, so it yields at most log2(3), about 1.585 bits, of information. Identifying which of the 2n + 1 outcomes occurred needs H bits on average, where H is the entropy of the p and q distribution. No comparison tree can beat H / log2(3) expected comparisons, which gives you a quick sanity check on any result.

Turning access logs into weights

Weights come from production probes, not from guesses. Log every key that is looked up, including the ones that are not in the set, then map each probe to either a key index or a gap index with one binary search over the sorted keys. A probe that is not present lands in the gap where it would be inserted, which is exactly what bisect_left returns.

from bisect import bisect_left

def weights(keys, probes, alpha=0.5):
    """keys must be sorted. Returns hit probabilities p[0..n-1] and gap probabilities q[0..n]."""
    hits = [0] * len(keys)
    gaps = [0] * (len(keys) + 1)
    for probe in probes:
        i = bisect_left(keys, probe)
        if i < len(keys) and keys[i] == probe:
            hits[i] += 1
        else:
            gaps[i] += 1          # gap i lies between keys[i-1] and keys[i]
    total = sum(hits) + sum(gaps) + alpha * (2 * len(keys) + 1)
    p = [(h + alpha) / total for h in hits]
    q = [(g + alpha) / total for g in gaps]
    return p, q

The alpha term is additive smoothing. Without it, a key that was never probed in the window gets weight zero and the DP is free to bury it at the bottom of a long chain; the first time it is looked up after deployment, it costs the maximum depth. Half a count per outcome is enough to keep shapes sensible without distorting the hot keys. Three further rules keep the weights honest:

• Sample the log with a fixed per-request hash, not the first N requests of the day, so the window is not biased towards one time zone.
• Normalise case and encoding exactly as the lookup will, or the counts describe a different key space from the one being searched.
• Store the counts, the window dates and alpha next to the tree. A tree without its weights cannot be reproduced or audited.

The DP, with the shape kept

The DP below works on half-open ranges of keys: e[i][j] is the minimum expected cost of a subtree holding keys i to j - 1 and gaps i to j, and w[i][j] is the total weight of that range. Making key r the root pushes every outcome in the range one level deeper, so the cost is the two children plus the whole range weight. An empty range costs zero comparisons, which makes the result directly the expected comparison count. The inner loop is restricted to Knuth's window, root[i][j-1] to root[i+1][j], which brings the total work from cubic down to quadratic.

def optimal_bst(p, q):
    n = len(p)
    e = [[0.0] * (n + 1) for _ in range(n + 1)]
    w = [[0.0] * (n + 1) for _ in range(n + 1)]
    root = [[0] * (n + 1) for _ in range(n + 1)]
    for i in range(n + 1):
        w[i][i] = q[i]
    for length in range(1, n + 1):
        for i in range(0, n - length + 1):
            j = i + length
            w[i][j] = w[i][j - 1] + p[j - 1] + q[j]
            lo = root[i][j - 1] if length > 1 else i
            hi = root[i + 1][j] if length > 1 else i
            best, arg = float("inf"), lo
            for r in range(lo, hi + 1):
                cost = e[i][r] + e[r + 1][j]
                if cost < best:
                    best, arg = cost, r
            e[i][j] = best + w[i][j]
            root[i][j] = arg
    return e[0][n], root

def build(root, keys, i, j):
    if i == j:
        return None
    r = root[i][j]
    return (keys[r], build(root, keys, i, r), build(root, keys, r + 1, j))

Keep the root table: the cost alone is useless without the shape, and build recovers the shape in linear time by following it. Memory is quadratic, three tables of (n + 1) squared entries, which is the practical limit: 10,000 keys means about 300 million table cells.

Worked example: eight header names

The proxy logged 9,000 lookups. Hits per key and misses per gap were:

Running optimal_bst on these weights gives an expected cost of 2.326 comparisons per lookup with host at the root, content-type and user-agent below it, and origin and cache-control at depth 3. A perfectly balanced tree over the same keys, rooted at cookie, costs 2.814: about 21 percent more comparisons, because it puts user-agent, the second hottest key, at depth 3. The entropy of the 17 outcomes is 3.14 bits, so the floor is 3.14 / 1.585 = 1.98 comparisons; the optimum sits about 0.35 above it, which is typical for small key sets.

Near-optimal trees for large key sets

Quadratic time and memory stop being comfortable somewhere in the tens of thousands of keys. The standard escape is to give up exact optimality. The simplest approximation, in the spirit of Mehlhorn's nearly optimal trees, chooses as root the key that best balances total weight (hits and gaps) on its two sides, then recurses:

def weight_balanced(p, q, i=0, j=None):
    if j is None:
        j = len(p)
    if i == j:
        return None
    def imbalance(r):
        left = sum(p[i:r]) + sum(q[i:r + 1])
        right = sum(p[r + 1:j]) + sum(q[r + 1:j + 1])
        return abs(left - right)
    r = min(range(i, j), key=imbalance)
    return (r, weight_balanced(p, q, i, r), weight_balanced(p, q, r + 1, j))

Written this way it is simple but slow; with prefix sums and a binary search for the balance point it runs in O(n log n). Mehlhorn proved that a closely related bisection rule stays within a small additive constant of the entropy bound. On the header example it finds exactly the optimal tree. Over 2,000 random instances with 5 to 40 keys and skewed weights (each a uniform random number cubed), its median cost was 1.10 times the optimum and its worst 1.46 times; a balanced tree had a median of 1.24 and a worst of 1.90. That is one scratch experiment, not a theorem, but it shows the usual picture: weight balancing captures most of the gain.

Two other options are worth knowing precisely, because they are often cited for the wrong problem. Hu-Tucker and Garsia-Wachs build optimal alphabetic trees in O(n log n), but only when all the weight is on the leaves, as in an order-preserving prefix code; they do not handle the general case where internal keys carry hit weight. And if you do not know the distribution at all, splay trees adapt online and are within a constant factor of the best static tree over long sequences, at the cost of writes on every read.

Deploying the tree as flat arrays

A pointer-based tree throws away much of the gain: each comparison becomes a cache miss. Flatten it into parallel arrays in preorder. The root lands at index 0, each left child directly follows its parent, and the hottest paths occupy the first few cache lines.

def flatten(tree):
    keys, left, right = [], [], []
    def emit(node):
        if node is None:
            return -1
        idx = len(keys)
        keys.append(node[0]); left.append(-1); right.append(-1)
        left[idx] = emit(node[1])
        right[idx] = emit(node[2])
        return idx
    emit(tree)
    return keys, left, right

def lookup(keys, left, right, probe):
    i = 0 if keys else -1
    while i != -1:
        k = keys[i]
        if probe == k:
            return i
        i = left[i] if probe < k else right[i]
    return -1

For the header tree this produces the key order host, content-type, accept, cache-control, cookie, user-agent, referer, origin. For tiny sets you can instead generate nested if statements from the same structure. Either way, test lookup against plain set membership for every key, every gap and random strings; reconstruction bugs show up as silent misses, not crashes.

Detecting drift and deciding when to rebuild

An optimal tree is optimal for one distribution. To decide whether to rebuild, score the current tree on a new window of weights and compare it with the new optimum, using the same cost function in both cases. Suppose a new client integration lifts origin to 2,100 of 9,550 lookups, about 22 percent, while cookie falls to 200. The deployed tree now costs 2.558 comparisons per lookup on the new traffic; the new optimum, which lifts origin to the root of the right subtree, costs 2.336. The old tree is paying about 9.5 percent more than it needs to.

A good rebuild policy has three parts: a margin (rebuild only when the old tree is at least, say, 5 percent worse), hysteresis (require the margin on two consecutive windows so weekly seasonality does not cause flapping), and a guard (the new tree must not lose to the old one on the previous window either, which catches a single anomalous day). Logging the live tree's expected cost daily also tells you when the client mix changed.

Failure modes

• Zero weights. An unsmoothed key that never appeared in the window is buried at maximum depth and becomes the slowest lookup the day it gets popular.
• Ignoring misses. Building from hit counts only puts gap traffic in the wrong place; for header or keyword sets, misses are often a large share of probes.
• Key-space mismatch. Counting raw strings but looking up normalised ones means the weights describe keys the tree never sees.
• Comparing different cost models. Scoring one tree with hit-only cost and another with hits plus misses produces confident, wrong rebuild decisions.
• Reconstruction off by one. Mixing closed and half-open ranges between the DP and build yields a valid-looking tree that misses keys.

Trade-offs

The interval structure here is the same one behind matrix chain multiplication, and the entropy argument is the one that bounds Huffman codes.

What to do next

1. Log every probe, hits and misses, for a week, with a stable sampling hash.
2. Compute smoothed p and q with weights and store them with the window dates.
3. Run optimal_bst and the balanced tree on the same weights and record both expected costs and the entropy floor.
4. Flatten the winner in preorder and test it against set membership on every key, every gap and random strings.
5. Benchmark real lookups: expected comparisons only matter if comparisons dominate.
6. Score the live tree on each new window and rebuild only past a fixed margin held for two windows.
7. If n grows past what quadratic memory allows, switch to weight_balanced and measure its ratio to the optimum on a sample of the keys.