Segment-Based Dynamic Programming for Optimal Two-Way Comparison Search Trees: Hierarchical Weight Partitioning with Provable Pruning

A binary search tree built from the comparisons that programming languages actually provide, “q<k” and “q=k”, can be much cheaper than one built from Knuth’s three-way comparisons, but it is also much harder to optimize. After an equality test the remaining queries form a punctured interval. The best exact algorithm (Chrobak, Golin, Munro and Young, 2022) therefore runs in O\left(n^4\right) time and \varTheta \left(n^3\right) space, and the Knuth–Yao speed-up does not apply. We present Hierarchical Weight Partitioning (HWP), a segment-based dynamic program with three provable ingredients. (i) A canonical state space stores each punctured interval exactly once, which cuts memory from n^3/2 to n^3/6+O\left(n^2\right) words and enables a cache-friendly, wavefront-parallel loop order. (ii) A multi-level segment tree (merge-sort tree) answers rank and weight queries on punctured intervals in O\left(\log^2n\right). (iii) Weight-class thresholding admits an equality test only when the tested key carries at least a fraction τ of the subproblem weight. With dyadic weight classes, we show that at most ⌈\left(2-\tau \right)/\tau ⌉-1 keys per class can ever be tested for equality. For successful-query instances this makes HWP with τ=1/4 exact in O\left(n^3\log2R\right) time, where R is the key-weight ratio; the previous bound was O\left(n^3\log\left(nR\right)\right). For the general variant, every \tau \in \left[0,1\right] yields a tree within additive 3 (in normalized weight) of optimal, τ=0 is exact, and an equality test on a key heavier than half the subproblem is always optimal (tight). We also prove that no lower threshold can be exact in the general variant. Experiments on synthetic families and four real workloads (English vocabulary with out-of-vocabulary queries, CPython identifiers, opcodes and lexer characters) certify exactness against brute force and the O\left(n^4\right) baseline on over 4,000 instances. They also measure scaling up to n=3200, ablations, skew sensitivity and compiled-lookup deployment. We do not claim a sub-cubic exact algorithm for the general problem, and we explain why the recurrence rules one out.