Optimal search trees with 2-way comparisons?
Marek Chrobak1?? , Mordecai Golin2? ? ? , J. Ian Munro3† , and Neal E. Young1
1

arXiv:1505.00357v4 [cs.DS] 3 Oct 2015

2

University of California — Riverside, Riverside, California, USA
Hong Kong University of Science and Technology, Hong Kong, China
3
University of Waterloo, Waterloo, Canada

Abstract. In 1971, Knuth gave an O(n2 )-time algorithm for the classic problem of finding an optimal binary search tree. Knuth’s algorithm
works only for search trees based on 3-way comparisons, but most modern
computers support only 2-way comparisons (<, ≤, =, ≥, and >). Until this paper, the problem of finding an optimal search tree using 2-way
comparisons remained open — poly-time algorithms were known only for
restricted variants. We solve the general case, giving (i) an O(n4 )-time algorithm and (ii) an O(n log n)-time additive-3 approximation algorithm.
For finding optimal binary split trees, we (iii) obtain a linear speedup
and (iv) prove some previous work incorrect.

1

Background and statement of results

In 1971, Knuth [10] gave an O(n2 )-time dynamic-programming algorithm for a
classic problem: given a set K of keys and a probability distribution on queries,
find an optimal binary-search tree T . As shown in Fig. 1, a search in such a tree
for a given value v compares v to the root key, then (i) recurses left if v is smaller,
(ii) stops if v equals the key, or (iii) recurses right if v is larger, halting at a leaf.
The comparisons made in the search must suffice to determine the relation of
v to all keys in K. (Hence, T must have 2|K| + 1 leaves.) T is optimal if it has
minimum cost, defined as the expected number of comparisons assuming the
query v is chosen randomly from the specified probability distribution.
Knuth assumed three-way comparisons at each node. With the rise of higherlevel programming languages, most computers began supporting only two-way
comparisons (<, ≤, =, ≥, >). In the 2nd edition of Volume 3 of The Art of Computer Programming [11, §6.2.2 ex. 33], Knuth commented
. . . machines that cannot make three-way comparisons at once. . . will have to
make two comparisons. . . it may well be best to have a binary tree whose internal nodes specify either an equality test or a less-than test but not both.

But Knuth gave no algorithm to find a tree built from two-way comparisons (a
2wcst, as in Fig. 2(a)), and, prior to the current paper, poly-time algorithms
?
??
???
†

This is the full version of an extended abstract that appeared in ISAAC [2].
Research funded by NSF grants CCF-1217314 and CCF-1536026.
Research funded by HKUST/RGC grant FSGRF14EG28.
Research funded by NSERC and the Canada Research Chairs Programme.

2
v

<
v?H

v<H

v=H

>

=

v=O

>

< =

v?O

H<v<O

<

O<v<W

v?W

=
v=W

>
W<v

Fig. 1. A binary search tree T using 3-way comparisons, for K = {H, O, W }.
(a)

(b)

v
yes
y

v=H

v < O?

no

v = H?
v < H?
y

v<H

n

H<v<O

yes
y

n
y

v = O?
n

v

v < W?
y

v < O?

v=H

n

v = W?

no
y

v=O

v = O?
n

v=W

n

v=O O<v<W v=W W<v

Fig. 2. Two 2wcsts for K = {H, O, W }; tree (b) only handles successful queries.

were known only for restricted variants. Most notably, in 2002 Anderson et al. [1]
gave an O(n4 )-time algorithm for the successful-queries variant of 2wcst, in
which each query v must be a key in K, so only |K| leaves are needed (Fig. 2(b)).
The standard problem allows arbitrary queries, so 2|K| + 1 leaves are needed
(Fig. 2(a)). For the standard problem, no polynomial-time algorithm was previously known. We give one for a more general problem that we call 2wcst:
Theorem 1. 2wcst has an O(n4 )-time algorithm.
We specify an instance I of 2wcst as a tuple I = (K = {K1 , . . . , Kn }, Q, C, α, β).
The set C of allowed comparison operators can be any subset of {<, ≤, =, ≥, >}.
The set Q specifies the queries. A solution is an optimal 2wcst T among those
using operators in C and handling all queries in Q. This definition generalizes
both standard 2wcst (let Q contain each key and a value between each pair
of keys), and the successful-queries variant (take Q = K and α ≡ 0). It further
allows any query set Q between these two extremes, even allowing K 6⊆ Q. As
usual, βi is the probability that v equals Ki ; αi is the probability that v falls
between keys Ki and Ki+1 (except α0 = Pr[v < K1 ] and αn = Pr[v > Kn ]). 4
To prove Thm. 1, we prove Spuler’s 1994 “maximum-likelihood” conjecture: in
any optimal 2wcst tree, each equality comparison is to a key in K of maximum
likelihood, given the comparisons so far [14, §6.4 Conj. 1]. As Spuler observed,
the conjecture implies an O(n5 )-time algorithm; we reduce this to O(n4 ) using
4

As defined here, a 2wcst T must determine the relation of the query v to every
key in K. More generally, one could specify any partition P of Q, and only require
T to determine, if at all possible using keys in K, which set S ∈ P contains v. For
example, if P = {K, Q \ K}, then T would only need to determine whether v ∈ K.
We note without proof that Thm. 1 extends to this more general formulation.

3

standard techniques and a new perturbation argument. Anderson et al. proved
the conjecture for their special case [1, Cor. 3]. We were unable to extend their
proof directly; our proof uses a different local-exchange argument.
We also give a fast additive-3 approximation algorithm:
Theorem 2. Given any instance I = (K, Q, C, α, β) of 2wcst, one can compute
a tree of cost at most the optimum plus 3, in O(n log n) time.
Comparable results were known for the successful-queries variant (Q = K) [16,1].
We approximately reduce the general case to that case.
Binary split trees “split” each 3-way comparison in Knuth’s 3-way-comparison
model into two 2-way comparisons within the same node: an equality comparison (which, by definition, must be to the maximum-likelihood key) and a “<”
comparison (to any key) [13,3,8,12,6]. The fastest algorithms to find an optimal
binary split tree take O(n5 )-time: from 1984 for the successful-queries-only variant (Q = K) [8]; from 1986 for the standard problem (Q contains queries in all
possible relations to the keys in K) [6]. We obtain a linear speedup:
Theorem 3. Given any instance I = (K = {K1 , . . . , Kn }, α, β) of the standard
binary-split-tree problem, an optimal tree can be computed in O(n4 ) time.
The proof uses our new perturbation argument (Sec. 3.1) to reduce to the case
when all βi ’s are distinct, then applies a known algorithm [6]. The perturbation
argument can also be used to simplify Anderson et al.’s algorithm [1].
Generalized binary split trees (gbsts) are binary split trees without the maximumlikelihood constraint. Huang and Wong [9] (1984) observe that relaxing this constraint allows cheaper trees — the maximum-likelihood conjecture fails here —
and propose an algorithm to find optimal gbsts. We prove it incorrect!
Theorem 4. Lemma 4 of [9] is incorrect: there exists an instance — a query
distribution β — for which it does not hold, and on which their algorithm fails.
This flaw also invalidates two algorithms, proposed in Spuler’s thesis [15], that
are based on Huang and Wong’s algorithm. We know of no poly-time algorithm
to find optimal gbsts. Of course, optimal 2wcsts are at least as good.
2wcst without equality tests. Finding an optimal alphabetical encoding has
several poly-time algorithms: by Gilbert and Moore — O(n3 ) time, 1959 [5];
by Hu and Tucker — O(n log n) time, 1971 [7]; and by Garsia and Wachs
— O(n log n) time but simpler, 1979 [4]. The problem is equivalent to finding an optimal 3-way-comparison search tree when the probability of querying
any key is zero (β ≡ 0) [11, §6.2.2]. It is also equivalent to finding an optimal 2wcst in the successful-queries variant with only “<” comparisons allowed
(C = {<}, Q = K) [1, §5.2]. We generalize this observation to prove Thm. 5:
Theorem 5. Any 2wcst instance I = (K = {K1 , . . . , Kn }, Q, C, α, β) where =
is not in C (equality tests are not allowed), can be solved in O(n log n) time.

4

Definitions 1 Fix an arbitrary instance I = (K, Q, C, α, β).
For any node N in any 2wcst T for I, N ’s query subset, QN , contains
queries v ∈ Q such that the search for v reaches N . The weight ω(N ) of N is
the probability that a random query v (from distribution (α, β)) is in QN . The
weight ω(T 0 ) of any subtree T 0 of T is ω(N ) where N is the root of T 0 .
Let hv < Ki i denote an internal node having key Ki and comparison operator
< (define hv ≤ Ki i and hv = Ki i similarly). Let hKi i denote the leaf N such that
QN = {Ki }. Abusing notation, ω(Ki ) is a synonym for ω(hKi i), that is, βi .
Say T is irreducible if, for every node N with parent N 0 , QN 6= QN 0 .
In the remainder of the paper, we assume that only comparisons in {<, ≤, =}
are allowed (i.e., C ⊆ {<, ≤, =}). This is without loss of generality, as “v > Ki ”
and “v ≥ Ki ” can be replaced, respectively, by “v ≤ Ki ” and “v < Ki .”

2

Proof of Spuler’s conjecture

Fix any irreducible, optimal 2wcst T for any instance I = (K, Q, C, α, β).
Theorem 6 (Spuler’s conjecture). The key Ka in any equality-comparison
node N = hv = Ka i is a maximum-likelihood key: βa = maxi {βi : Ki ∈ QN }.
The theorem will follow easily from Lemma 1:
Lemma 1. Let internal node hv = Ka i be the ancestor of internal node hv = Kz i.
Then ω(Ka ) ≥ ω(Kz ). That is, βa ≥ βz .
Proof. (Lemma 1) Throughout, “hv ≺ Ki i” denotes a node in T that does an
inequality comparison (≤ or <, not =) to key Ki . Abusing notation, in that
context, “x ≺ Ki ” (or “x 6≺ Ki ”) denotes that x passes (or fails) that comparison.
Assumption 1 (i) All nodes on the path from hv = Ka i to hv = Kz i do inequality comparisons. (ii) Along the path, some other node hv ≺ Ks i separates
key Ka from Kz : either Ka ≺ Ks but Kz 6≺ Ks , or Kz ≺ Ks but Ka 6≺ Ks .
It suffices to prove the lemma assuming (i) and (ii) above. (Indeed, if the lemma
holds given (i), then, by transitivity, the lemma holds in general. Given (i), if
(ii) doesn’t hold, then exchanging the two nodes preserves correctness, changing
the cost by (ω(Ka ) − ω(Kz )) × d for d ≥ 1, so ω(Ka ) ≥ ω(Kz ) and we are done.)
By Assumption 1, the subtree rooted at hv = Ka i, call it T 0 , is as in Fig. 3(a):
Let child hv ≺ Kb i, with subtrees T0 and T1 , be as in Fig. 3.
Lemma 2. If Ka ≺ Kb , then ω(Ka ) ≥ ω(T1 ), else ω(Ka ) ≥ ω(T0 ).
(This and subsequent lemmas in this section are proved in Appendix 7.2. The
idea behind this one is that correctness is preserved by replacing T 0 by subtree
(b) if Ka ≺ Kb or (c) otherwise, implying the lemma by the optimality of T .)
Case 1: Child hv ≺ Kb i separates Ka from Kz . If Ka ≺ Kb , then Kz 6≺ Kb , so descendant hv = Kz i is in T1 , and, by this and Lemma 2, ω(Ka ) ≥ ω(T1 ) ≥ ω(Kz ),

5
(a)

(b)

v = Ka

y

(c)
v

n

Ka

v

y

Kb

y

T0

v = Ka

y

n

v

Kb

y

n

T0

T1

n

Ka

T1

Kb

y

n

v = Ka
n

Ka

T0

T1

Fig. 3. (a) The subtree T 0 rooted at hv = Ka i and possible replacements (b), (c).

and we’re done. Otherwise Ka 6≺ Kb , so Kz ≺ Kb , so descendant hv = Kz i is in
T0 , and, by this and Lemma 2, ω(Ka ) ≥ ω(T0 ) ≥ ω(Kz ), and we’re done.
Case 2: Child hv ≺ Kb i does not separate Ka from Kz . Assume also that descendant hv = Kz i is in T1 . (If descendant hv = Kz i is in T0 , the proof is symmetric,
exchanging the roles of T0 and T1 .) Since descendant hv = Kz i is in T1 , and child
hv ≺ Kb i does not separate Ka from Kz , we have Ka 6≺ Kb and two facts:
Fact A: ω(Ka ) ≥ ω(T0 ) (by Lemma 2), and
Fact B: the root of T1 does an inequality comparison (by Assumption 1).
By Fact B, subtree T 0 rooted at hv = Ka i is as in Fig. 4(a):

(a)
y

Ka

y

T0

(b)

v = Ka
n

v

Kb
y

T10

y
y

n

v

T1

Kc

n

T11

T0

v

Kb

v

n

T10

Kc
y

Ka

(c)

v = Ka

y

n

Ka

v = Ka
n

T11

y

T0

v

y

Kb

v
n

Kc

n

T11

T10

Fig. 4. (a) The subtree T 0 in Case 2, two possible replacements (b), (c).

As in Fig. 4(a), let the root of T1 be hv ≺ Kc i, with subtrees T10 and T11 .
Lemma 3. (i) ω(T0 ) ≥ ω(T11 ). (ii) If Ka 6≺ Kc , then ω(Ka ) ≥ ω(T1 ).

(As replacing T 0 by (b) or (c) preserves correctness; proof in Appendix 7.2.)
Case 2.1: Ka 6≺ Kc . By Lemma 3(ii), ω(Ka ) ≥ ω(T1 ). Descendant hv = Kz i is
in T1 , so ω(T1 ) ≥ ω(Kz ). Transitively, ω(Ka ) ≥ ω(Kz ), and we are done.
Case 2.2: Ka ≺ Kc . By Lemma 3(i), ω(T0 ) ≥ ω(T11 ). By Fact A, ω(Ka ) ≥
ω(T11 ).
If hv = Kz i is in T11 , then ω(T11 ) ≥ ω(Kz ) and transitively we are done.
In the remaining case, hv = Kz i is in T10 . T ’s irreducibility implies Kz ≺ Kc .
Since Ka ≺ Kc also (Case 2.2), grandchild hv ≺ Kc i does not separate Ka from
Kz , and by Assumption 1 the root of subtree T10 does an inequality comparison.
Hence, the subtree rooted at hv ≺ Kb i is as in Fig. 5(a):

6
(a)
y

v

Kb

(b)
y

n

v

T0

Kc

y
y

T100

v

Kd

T10

n

n

T11

y

T0

v

v

Kb

n

T100

Kd
y

n

v

T101

Kc

n

T11

T101

Fig. 5. (a) The subtree rooted at hv ≺ Kb i in Case 2.2. (b) A possible replacement.

Lemma 4. ω(T0 ) ≥ ω(T10 ).
(Because replacing (a) by (b) preserves correctness; proof in Appendix 7.2.)
Since descendant hv = Kz i is in T10 , Lemma 4 implies ω(T0 ) ≥ ω(T10 ) ≥
ω(Kz ). This and Fact A imply ω(Ka ) ≥ ω(Kz ). This proves Lemma 1.

Proposition 1. If any leaf node hK` i’s parent P does not do an equality comparison against key K` , then changing P so that it does so gives an irreducible
2wcst T 0 of the same cost.
Proof. Since QhK` i = {K` } and P ’s comparison operator is in C ⊆ {<, ≤, =}, it
must be that K` = max QP or K` = min QP . So changing P to hv = K` i (with
hK` i as the“yes” child and the other child the “no” child) maintains correctness,
cost, and irreducibility.

Proof. (Thm. 6) Consider any equality-testing node N = hv = Ka i and any key
Kz ∈ QN . Since Kz ∈ QN , node N has descendant leaf hKz i. Without loss of
generality (by Proposition 1), leaf hKz i’s parent is hv = Kz i. That parent is a
descendant of hv = Ka i, so ω(Ka ) ≥ ω(Kz ) by Lemma 1.


3

Proofs of Thm. 1 (algorithm for 2wcst) and Thm. 3

First we prove Thm. 1. Fix an instance I = (K, Q, C, α, β). Assume for now that
all probabilities in β are distinct. For any query subset S ⊆ Q, let opt(S) denote
the minimum cost of any 2wcst that correctly determines all queries in subset S
(using keys in K, comparisons in C, and weights from the appropriate restriction
of α and β to S). Let ω(S) be the probability that a random query v is in S.
The cost of any tree for S is the weight of the root (= ω(S)) plus the cost of its
two subtrees, yielding the following dynamic-programming recurrence:
Lemma 5. For any query set S ⊆ Q not handled by a single-node tree,

min opt(S \ {k}) (if “=” is in C, else ∞) (i)
k
opt(S) = ω(S) + min
min opt(Sk≺ ) + opt(S \ Sk≺ ),
(ii)
k,≺

where k ranges over K, and ≺ ranges over the allowed inequality operators (if
any), and Sk≺ = {v ∈ S : v ≺ k}.

7

Using the recurrence naively to compute opt(Q) yields exponentially many query
subsets S, because of line (i). But, by Thm. 6, we can restrict k in line (i) to be
the maximum-likelihood key in S. With this restriction, the only subsets S that
arise are intervals within Q, minus some most-likely keys. Formally, for each of
O(n2 ) key pairs {k1 , k2 } ⊆ K ∪ {−∞, ∞} with k1 < k2 , define four key intervals
(k1 , k2 ) = {v ∈ Q : k1 < v < k2 },
(k1 , k2 ] = {v ∈ Q : k1 < v ≤ k2 },

[k1 , k2 ] = {v ∈ Q : k1 ≤ v ≤ k2 },
[k1 , k2 ) = {v ∈ Q : k1 ≤ v < k2 }.

For each of these O(n2 ) key intervals I, and each integer h ≤ n, define top(I, h)
to contain the h keys in I with the h largest βi ’s. Define S(I, h) = I \ top(I, h).
Applying the restricted recurrence to S(I, h) gives a simpler recurrence:
Lemma 6. If S(I, h) is not handled by a one-node tree, then opt(S(I, h)) equals

opt(S(I, h + 1)) (if equality is in C, else ∞) (i)
ω(S(I, h)) + min
≺
≺
≺
≺
min opt(S(Ik , hk )) + opt(S(I \ Ik , h − hk )), (ii)
k,≺

≺
where key interval Ik≺ = {v ∈ I : v ≺ k}, and h≺
k = | top(I, h) ∩ Ik |.

Now, to compute opt(Q), each query subset that arises is of the form S(I, h)
where I is a key interval and 0 ≤ h ≤ n. With care, each of these O(n3 )
subproblems can be solved in O(n) time, giving an O(n4 )-time algorithm. In
particular, represent each key-interval I by its two endpoints. For each keyinterval I and integer h ≤ n, precompute ω(S(I, h)), and top(I, h), and the h’th
largest key in I. Given these O(n3 ) values (computed in O(n3 log n) time), the
recurrence for opt(S(I, h)) can be evaluated in O(n) time. In particular, for line
(ii), one can enumerate all O(n) pairs (k, h≺
k ) in O(n) time total, and, for each,
compute Ik≺ and I \ Ik≺ in O(1) time. Each base case can be recognized and
handled (by a cost-0 leaf) in O(1) time, giving total time O(n4 ). This proves
Thm. 1 when all probabilities in β are distinct; Sec. 3.1 finishes the proof.
3.1

Perturbation argument; proofs of Theorems 1 and 3

Here we show that, without loss of generality, in looking for an optimal search
tree, one can assume that the key probabilities (the βi ’s) are all distinct. Given
any instance I = (K, Q, C, α, β), construct instance I 0 = (K, Q, C, α, β 0 ), where
βj0 = βj + jε and ε is a positive infinitesimal (or ε can be understood as a
sufficiently small positive rational). To compute (and compare) costs of trees
with respect to I 0 , maintain the infinitesimal part of each value separately and
extend linear arithmetic component-wise in the natural way:
1. Compute z × (x1 + x2 ε) as (zx1 ) + (zx2 )ε, where z, x1 , x2 are any rationals,
2. compute (x1 + εx2 ) + (y1 + εy2 ) as (x1 + x2 ) + (y1 + y2 )ε,
3. and say x1 + εx2 < y1 + εy2 iff x1 < y1 , or x1 = y1 ∧ x2 < y2 .
Lemma 7. In the instance I 0 , all key probabilities βi0 are distinct. If a tree T is
optimal w.r.t. I 0 , then it is also optimal with respect to I.

8

Proof. Let A be a tree that is optimal w.r.t. I 0 . Let B be any other tree, and
let the costs of A and B under I 0 be, respectively, a1 + a2 ε and b1 + b2 ε. Then
their respective costs under I are a1 and b1 . Since A has minimum cost under
I 0 , a1 + a2 ε ≤ b1 + b2 ε. That is, either a1 < b1 , or a1 = b1 (and a2 ≤ b2 ). Hence
a1 ≤ b1 : that is, A costs no more than B w.r.t. I. Hence A is optimal w.r.t. I. 

Doing arithmetic this way increases running time by a constant factor.5 This
completes the proof of Thm. 1. The reduction can also be used to avoid the
significant effort that Anderson et al. [1] devote to non-distinct key probabilities.
For computing optimal binary split trees for unrestricted queries, the fastest
known time is O(n5 ), due to [6]. But [6] also gives an O(n4 )-time algorithm
for the case of distinct key probabilities. With the above reduction, the latter
algorithm gives O(n4 ) time for the general case, proving Thm. 3.

4

Proof of Thm. 2 (additive-3 approximation algorithm)

Fix any instance I = (K, Q, C, α, β). If C is {=} then the optimal tree can be
found in O(n log n) time, so assume otherwise. In particular, < and/or ≤ are in
C. Assume that < is in CP
(the other case
Pis symmetric).
The entropy HI = − i βi log2 βi − i αi log2 αi is a lower bound on opt(I).
For the case K = Q and C = {<}, Yeung’s O(n)-time algorithm [16] constructs
a 2wcst that uses only <-comparisons whose cost is at most HI + 2 − β1 − βn .
We reduce the general case to that one, adding roughly one extra comparison.
Construct I 0 = (K0 = K, Q0 = K, C 0 = {<}, α0 , β 0 ) where each αi0 = 0 and
each βi0 = βi + αi (except β10 = α0 + β1 + α1 ). Use Yeung’s algorithm [16] to
construct tree T 0 for I 0 . Tree T 0 uses only the < operator, so any query v ∈ Q
that reaches a leaf hKi i in T 0 must satisfy Ki ≤ v < Ki+1 (or v < K2 if i = 1).
To distinguish Ki = v from Ki < v < Ki+1 , we need only add one additional
comparison at each leaf (except, if i = 1, we need two).6 By Yeung’s guarantee,
T 0 costs at most HI 0 + 2 − β10 − βn0 . The modifications can be done so as to
increase the cost by at most 1 + α0 + α1 , so the final tree costs at most HI 0 + 3.
By standard properties of entropy, HI 0 ≤ HI ≤ opt(I), proving Thm. 2.

5

Proof of Thm. 4 (errors in work on binary split trees)

A generalized binary split tree (gbst) is a rooted binary tree where each node
N has an equality key eN and a split key sN . A search for query v ∈ Q starts
at the root r. If v = er , the search halts. Otherwise, the search recurses on the
left subtree (if v < sr ) or the right subtree (if v ≥ sr ). The cost of the tree
is the expected number of nodes (including, by convention, leaves) visited for a
random query v. Fig. 6 shows two gbsts for a single instance.
5
6

For an algorithm that works with linear (or O(1)-degree polynomial) functions of β.
If it is possible to distinguish v = Ki from Ki < v < Ki+1 , then C must have at
least one operator other than <, so we can add either hv = Ki i or hv ≤ Ki i.

9

(a)

B0
10

A1
20

A2
20
C0
5

D0
10

D1
22

A3
20
E0
10

(b)

B0
10

A1
20

A2
20
D0
10
C0
5

B4
20

N0
10

A3
20
E0
10

N0
10

N1
20

N1
20

P2
20
P0
10

Q0
10

P2
20
P0
10

Q0
10

B4
20
Q1
20

R0
10

S0
10

S1
20

T2
20
T0
10

D1
22
Q1
20

R0
10

S0
10

S1
20

U0
10

T2
20
T0
10

U0
10

U1
20

U1
20

V3
20
V0
10

W0
10

V3
20
V0
10

W0
10

W1
20

W1
20

X2
20
X0
10

Y0
10

X2
20
X0
10

Y0
10

Y1
20

Y1
20

Z0
10

Z0
10

Fig. 6. Two gbsts for an instance. Keys are ordered alphabetically (A0 < A1 < A2 <
A3 < B0 < · · · ). Each node shows its equality key and the frequency of that key; split
keys are not shown. The algorithm of [9] gives (a), of cost 1763, but (b) costs 1762.

To prove Thm. 4, we observe that [9]’s Lemma 4 and algorithm fail on the
instance in Fig. 6. There is a solution of cost only 1762 (in Fig. 6(b)), but the
algorithm gives cost 1763 for the instance (as in Fig. 6(a)), as can be verified by
executing the Python code for the algorithm in Appendix 7.1. The intuition is
that the optimal substructure property fails for the subproblems defined by [9]:
the circled subtree in (a) (with root A2) is cheaper than the corresponding
subtree in (b), but leads to larger global cost. For more intuition and the full
proof, see Appendix 7.3.

6

Proof of Thm. 5 (O(n log n) time without equality)

Fix any 2wcst instance I = (K, Q, C, α, β) with C ⊆ {<, ≤}. Let n = |K|. We
show that, in O(n log n) time, one can compute an equivalent instance I 0 =
(K0 , Q0 , C 0 , α0 , β 0 ) with K0 = Q0 , C 0 = {<}, and |K0 | ≤ 2n + 1. (Equivalent means
that, given an optimal 2wcst T 0 for I 0 , one can compute in O(n log n) time an
optimal 2wcst T for I.) The idea is that, when C ⊆ {<, ≤}, open intervals are
functionally equivalent to keys.
Assume without loss of generality that C = {<, ≤}. (Otherwise no correct
tree exists unless K = Q, and we are done.) Assume without loss of generality
that no two elements in Q are equivalent (in that they relate to all keys in K
in the same way; otherwise, remove all but one query from each equivalence
class). Hence, at most one query lies between any two consecutive keys, and
|Q| ≤ 2|K| + 1.
Let instance I 0 = (K0 , Q, C 0 , α0 , β 0 ) be obtained by taking the key set K0 =
Q to be the key set, but restricting comparisons to C 0 = {<} (and adjusting
the probability distribution appropriately — take α0 ≡= 0, take βi to be the
probability associated with the ith query — the appropriate αj or βj ).

10

Given any irreducible 2wcst T for I, one can construct a tree T 0 for I 0 of
the same cost as follows. Replace each node hv ≤ ki with a node hv < qi, where
q is the least query value larger than k (there must be one, since hv ≤ ki is in T
and T is irreducible). Likewise, replace each node hv < ki with a node hv < qi,
where q is the least query value greater than or equal to k (there must be one,
since hv < ki is in T and T is irreducible). T 0 is correct because T is.
Conversely, given any irreducible 2wcst T 0 for I 0 , one can construct an
equivalent 2wcst T for I as follows. Replace each node N 0 = hv < qi as follows.
If q ∈ K, replace N 0 by hv < ki. Otherwise, replace N 0 by hv ≤ ki, where key k
is the largest key less than q. (There must be such a key k. Node hv < qi is in
T 0 but T 0 is irreducible, so there is a query, and hence a key k, smaller than q.)
Since T 0 correctly classifies each query in Q, so does T .
To finish, we note that the instance I 0 can be computed from I in O(n log n)
time (by sorting the keys, under reasonable assumptions about Q), and the
second mapping (from T 0 to T ) can be computed in O(n log n) time. Since I 0
has K0 = Q0 and C = {<}, it is known [10] to be equivalent to an instance of
alphabetic encoding, which can be solved in O(n log n) time [7,4].

References
1. R. Anderson, S. Kannan, H. Karloff, and R. E. Ladner. Thresholds and optimal
binary comparison search trees. Journal of Algorithms, 44:338–358, 2002.
2. M. Chrobak, M. Golin, J. I. Munro, and N. E. Young. Optimal search trees with
2-way comparisons. In Proceedings of International Symposium on Algorithms and
Computation, 2015.
3. D. Comer. A note on median split trees. ACM Transactions on Programming
Languages and Systems, 2(1):129–133, 1980.
4. A. M. Garsia and M. L. Wachs. A new algorithm for minimum cost binary trees.
SIAM Journal on Computing, 6(4):622–642, 1977.
5. E. Gilbert and E. Moore. Variable-length binary encodings. Bell System Technical
Journal, 38(4):933–967, 1959.
6. J. H. Hester, D. S. Hirschberg, S. H. Huang, and C. K. Wong. Faster construction
of optimal binary split trees. Journal of Algorithms, 7(3):412–424, 1986.
7. T. C. Hu and A. C. Tucker. Optimal computer search trees and variable-length
alphabetical codes. SIAM Journal on Applied Mathematics, 21(4):514–532, 1971.
8. S. Huang and C. Wong. Optimal binary split trees. Journal of Algorithms, 5(1):69–
79, 1984.
9. S.-H. Huang and C. K. Wong. Generalized binary split trees. Acta Informatica,
21(1):113–123, 1984.
10. D. E. Knuth. Optimum binary search trees. Acta Informatica, 1(1):14–25, 1971.
11. D. E. Knuth. The Art of Computer Programming, Volume 3: Sorting and Searching.
Addison-Wesley Publishing Company, 2nd edition, 1998.
12. Y. Perl. Optimum split trees. Journal of Algorithms, 5:367–374, 1984.
13. B. A. Sheil. Median split trees: a fast lookup technique for frequently occuring
keys. Communications of the ACM, 21(11):947–958, 1978.
14. D. Spuler. Optimal search trees using two-way key comparisons. Acta Informatica,
740:729–740, 1994.

11
15. D. A. Spuler. Optimal Search Trees Using Two-Way Key Comparisons. PhD thesis,
James Cook University, 1994.
16. R. Yeung. Alphabetic codes revisited. IEEE Transactions on Information Theory,
37(3):564–572, 1991.

7

Appendix

7.1
1
2
3

Python code for Thm. 4 (gbst algorithm of [9])

#!/usr/bin/env python3.4
import functools
memoize = functools.lru_cache(maxsize=None)

4
5
6

def huang1984(weights):
"Returns cost as computed by Huang and Wong's GBST algorithm (1984)."

7
8
9

n = len(weights)
beta = {i+1 : weights[key] for i, key in enumerate(sorted(weights.keys()))}

10
11

def is_legal(i, j, d): return 0 <= i <= j <= n and 0 <= d <= j -i

12
13
14
15

@memoize
def p_w_t(i, j, d):
"Returns triple: (cost p[i,j,d], weight w[i,j,d], deleted keys for t[i,j,d])."

16
17

interval = set(range(i+1, j+1))

18
19
20

if d == j-i: # base case
return (0, 0, interval)

21
22
23
24
25
26
27
28
29
30
31
32

def candidates(): # Lemma 4 recurrence from Huang et al
for k in interval: # k = index of split key
for m in range(d+2): # m = num. deletions from left subtree
if is_legal(i, k-1, m) and is_legal(k-1, j, d-m+1):
cost_l, weight_l, deleted_l = p_w_t(i, k-1, m)
cost_r, weight_r, deleted_r = p_w_t(k-1, j, d-m+1)
deleted = deleted_l .union( deleted_r )
x = min(deleted, key = lambda h : beta[h])
weight = beta[x] + weight_l + weight_r
cost = weight + cost_l + cost_r
yield cost, weight, deleted -set([x])

33
34

return min(candidates())

35
36
37

cost, weight, keys = p_w_t(0, n, 0)
return cost

38
39
40
41
42
43
44

weights = dict(b4=20,
a3=20, v3=20,
a2=20, p2=20, t2=20, x2=20,
a1=20, d1=22, n1=20, q1=20, s1=20, u1=20, w1=20, y1=20,
b0=10, c0= 5, d0=10, e0=10, n0=10, p0=10, q0=10, r0=10,
s0=10, t0=10, u0=10, v0=10, w0=10, x0=10, y0=10, z0=10)

45
46

assert huang1984(weights) == 1763 # Both assertions pass. The first is used in our Thm. 4.

47
48
49

weights['d1'] += 0.99 # Increasing a weight cannot decrease the optimal cost, but
assert huang1984(weights) < 1763 # in this case decreases the cost computed by the algorithm.

The extended abstract [2] is essentially the body of this paper minus the remainder of this appendix. The remainder of this appendix contains all proofs omitted
from the extended abstract.

12

7.2

Proof of Lemmas 2–4 (in the proof of Spuler’s conjecture)

We prove some slightly stronger lemmas that imply Lemmas 2–4.
Let T be any irreducible, optimal 2wcst as in the proof of Lemma 1.
Lemma 8 (implies Lemma 2). Assume T has a subtree as in Fig. 3(a) with
nodes hv = Ka i and hv ≺ Kb i. (i) Replacing that subtree the one in Fig. 3(b) (if
Ka ≺ Kb ) or the one in Fig. 3(c) (if Ka 6≺ Kb ) preserves correctness. (ii) If
Ka ≺ Kb , then ω(Ka ) ≥ ω(T1 ); otherwise ω(Ka ) ≥ ω(T0 ).
Proof. Assume that Ka ≺ Kb (the other case is symmetric). By inspection of
each case (Q = Ka or Q 6= Ka ), subtree (b) classifies each query Q the same
way subtree (a) does, so the modified tree is correct. The modification changes
the cost by ω(Ka ) − ω(T1 ), so (since T has minimum cost) ω(Ka ) ≥ ω(T1 ). 

(a)

(b)

y

T0

v

Kb
y

T10

(c)
v
y

n

v

Kc

T1

v
n

T11

y

T0

Kb

Kc

v
n

y

v
n

y

T10

T0

Kb

v
n

T11

y

T0

Kb

n

Kc

n

T11

T10

Fig. 7. Lemma 9 — “Rotating” subtree (a) yields (c); the subtrees are interchangeable.

Lemma 9 (implies Lemma 3(i)). (i) If T has either of the two subtrees in
Fig. 7(a) or (c), then exchanging one for the other preserves correctness. (ii) If
T has the subtree in Fig. 7(a), then ω(T0 ) ≥ ω(T11 ).
Proof. Part (i). The transformation from (a) to (c) is a standard rotation operation on binary search trees, but, since the comparison operators can be either
< or ≤ in our context, we verify correctness carefully.
By inspection, replacing subtree (a) by subtree (b) (in Fig. 7) gives a tree
that classifies all queries as T does, and so is correct.
Next we observe that, in subtree (b), replacing the right subtree by just T11
(to obtain subtree (c)), maintains correctness. Indeed, since T is irreducible,
replacing (in (a)) the subtree T1 by just T11 would give an incorrect tree.
Equivalently, ∃Q. Q 6≺ Kb ∧ Q ≺ Kc . Equivalently, the right-bounded interval {Q ∈ R : Q ≺ Kc } overlaps the left-bounded interval {Q ∈ R : Q 6≺ Kb }.
Equivalently, the complements of these intervals, namely {Q ∈ R : Q 6≺ Kc } and
{Q ∈ R : Q ≺ Kb }, are disjoint. Equivalently, ∀Q. Q 6≺ Kc → Q 6≺ Kb . Hence,
replacing the right subtree of (b) by T11 (yielding (c)) maintains correctness.
In sum, replacing subtree (a) by subtree (c) maintains correctness. This shows
part (i). This replacement changes the cost by ω(T0 )−ω(T11 ), so ω(T0 ) ≥ ω(T11 ).
This proves part (iii). The proof of (ii) is symmetric to the proof of (i).


13

(a)
y

Ka

y

v = Ka
n

v

Kb

T0

y

T10

(b)
Ka

n

v

Kc

T1

v

y

n

y

(c)

y

n

v

Kb

T0

T11

v = Ka

y

Kc

y

n

Kb

T0

T11

n

v

v

n

T10

Kc
y

n

v = Ka
n

Ka

T11

T10

Fig. 8. Lemma 10 — Subtrees (a) and (c) are interchangeable if Ka 6≺ Kc .

Lemma 10 (implies Lemma 3(ii)). If T has a subtree as in Fig. 8(a), and
Ka 6≺ Kc , then (i) replacing the subtree by Fig. 8(c) preserves correctness, and
(ii) ω(Ka ) ≥ ω(T1 ).
Proof. (i) Assume T has the subtree in Fig. 7(a) (the other case is symmetric).
By Lemma 9(i) (applied to the subtree of (a) with root hv ≺ Kb i), replacing
subtree (a) by subtree (b) gives a correct tree. Then, by Lemma 8(i) (applied to
subtree (b), but note that node hv ≺ Kc i in (b) takes the role of node hv ≺ Kb i
in Fig. 3(a)!) replacing (b) by (c) gives a correct tree. This proves part (i). Part
(ii) follows because replacing (a) by (c) changes the cost of T by ω(Ka ) − ω(T1 ),
and T has minimum cost, so ω(Ka ) ≥ ω(T1 ).


(a)
y

v

Kb

(b)
y

n

v

T0

Kc

y

v

y

T100

T10

Kd

n

n

T11

T101

T0

v

(c)

Kb

y

n

v

Kd

T100

v

y

y

T101

y

n

Kc

n

T0

v

v

Kb

n

T100

Kd
y

n

v

T101

Kc

n

T11

T11

Fig. 9. Lemma 11 — Subtrees (a) and (c) are interchangeable.

Lemma 11 (implies Lemma 4). If T has a subtree as in Fig. 9(a), then (i)
replacing that subtree by the one in Fig. 9(c) preserves correctness, and (ii)
ω(T0 ) ≥ ω(T10 ).
Proof. Applying Lemma 9(i) to the subtree of (a) with root hv ≺ Kc i, replacing
subtree (a) by subtree (b) gives a correct tree.7 Then, applying Lemma 9(i) to
the subtree of (b) with root hv ≺ Kb i, replacing subtree (b) by subtree (c) gives
7

Technically, to apply Lemma 9(i), we need (b) to be correct and irreducible. The
overall argument remains valid though as long as the tree from Fig. 9(a) is optimal.

14

a correct tree. This shows part (i). Part (ii) follows, because replacing (a) by (c)
changes the cost of T by ω(T0 ) − ω(T10 ), so ω(T0 ) ≥ ω(T10 ).

7.3

Proof of Thm. 4 — Huang and Wong’s error

A generalized binary split tree (gbst) is a rooted binary tree where each node
N has an equality key eN and a split key sN . A search for query v ∈ Q starts
at the root r. If v = er , the search halts. Otherwise, the search recurses on the
left subtree (if v < sr ) or the right subtree (if v ≥ sr ). The cost of the tree
is the expected number of nodes (including, by convention, leaves) visited for a
random query v.

(a)

E
20
D

B
22
B
A
10

C
10

(b)

F
20
F
D
5

G
10

A
10

E
20
C

B
22
G
C
10
E

G
10

F
20
H

D
5

Fig. 10. In a gbst, each node has equality key, frequency, and (if internal) split key.

Huang and Wong demonstrate that equality keys in optimal gbsts do not
have the maximum-likelihood property [9]. Fig. 10 shows their counterexample:
in the optimal gbst (a), the root equality key is E (frequency 20), not B (frequency 22). The cheapest tree with B at the root is (b), and is more expensive.
Having B at the root increases the cost because then the other two high-frequency
keys E and F have to be the children, so the split key of the root has to split E
and F, and low-frequency keys A, C, and D all must be in the left subtree.
Following [9], restrict to successful queries (K = Q). Fix any instance I =
(K, β). For any query interval I = {Ki , Ki+1 , . . . , Kj } and any subset D ⊆ I of
“deleted” keys, let opt(I, D) denote the minimum cost of any gbst that handles
the keys in I \ D. This recurrence follows directly from the definition of gbsts:
Lemma 12. For any query set I \ D not handled by a single-node tree,
opt(I, D) = ω(I \ D) + min opt(I<s , De ∩ I<s ) + opt(I≥s , De ∩ I≥s )
e,s∈K

where De = D \ {e}, and I<s = {v ∈ I : v < s} and I≥s = {v ∈ I : v ≥ s}.
The goal is to compute opt(K, ∅). Using the recurrence above, exponentially
many subsets D arise. This motivates the following lemma. For any node N in
an optimal gbst, define N ’s key interval, IN , and deleted-key set, DN , according
to the recurrence in the natural way. Then the set QN of queries reaching N is
IN \ DN , and DN contains those keys in IN that are in equality tests above N ,
and IN contains the key values that, if searched for in T with the equality tests
removed, would reach node N .

15

Lemma 13 ([9, Lemma 2]). For any node N in an optimal gbst, N ’s equality
key is a least-frequent key among those in IN that aren’t equality keys in any of
N ’s subtrees: if eN = Ki , then βi = min{βj : Kj ∈ DN }.
The proof is the same exchange argument that shows our Assumption 1(ii).
[9] claims (incorrectly) that, by Lemma 13, the desired value opt(Q, ∅) can
be computed as follows. For any key interval I = {Ki+1 , . . . , Kj } and d ≤ n, let
p[i, j, d] = min{opt(I \ D) : D ⊆ I, |D| = d}

(1)

be the minimum cost of any gbst for any query set I \ D consisting of I minus
any d deleted keys. Let t[i, j, d] be a corresponding subtree of cost p[i, j, d], and
let w[i, j, d] be the weight of the root of t[i, j, d].
Their algorithm uses the following (incorrect) recurrence (their Lemma 4):
p[i, j, d] = min(w[i, j, d] + p[i, k − 1, m] + p[k − 1, j, d − m − 1])
where the minimum is taken over all legal combinations of k’s and m’s [and]
w[i, j, d] = w[i, k − 1, m] + w[k − 1, j, d − m − 1] + βx
where x is the index of the key of minimum frequency among those in range
{Ki+1 , . . . , Kj } but outside t[i, k − 1, m] and t[k − 1, j, d − m + 1]. . . ”

Next we describe their error. Recall that p[i, j, d] chooses a subtree of minimum cost (among trees with any d keys deleted). But this choice might not lead
to minimum overall cost! The reason is that the subtree’s cost does not suffice
to determine the contribution to the overall cost: the weight of the subtree, and
the weights of the deleted keys and their eventual locations, also matter.

(a)

T
B0
10

A3
20
A2
20

A1
20
C0
5

B4
20

A3
20

T’ A1

D1
22
D0
10

(b)

E0
10

B0
10

20

A2
20
D0
10
C0
5

D1
22

B4
20

E0
10

Fig. 11. Trees T , T 0 for 9-key interval I with d = 2. (Split keys not shown.)

For example, consider p[i, j, d] for the subproblem where d = 2 and interval
I consists of the nine keys I = {A1, A2, A3, B0, B4, C0, D0, D1, E0}, with the
following weights:
key: A1 A2 A3 B0 B4 C0 D0 D1 E0
weight: 20 20 20 10 20 5 10 22 10

Fig. 11 shows two 7-node subtrees (circled and shaded), called T and T 0 , involving these keys. These subtrees will be used in our counter-example, described
below. (The split key of each node is not shown in the diagram.)

16

Partition the set of possible trees t[i, j, d] into two classes: (i) those that
contain D1 and (ii) those that don’t (that is, D1 is a “deleted” key). By a careful
case analysis,8 subtree T in Fig. 11(a) is a cheapest (although not unique) tree in
class (i), while the 7-node subtree T 0 in Fig. 11(b) is a cheapest tree in class (ii).
Further, the subtree T 0 costs 1 more than the subtree T . Hence, the algorithm
of [9] will choose T , not T 0 , for this subproblem.
However, this choice is incorrect. Consider not just the cost of tree, but also
the effects of the choice on the deleted keys’ costs. For definiteness, suppose the
two deleted nodes become, respectively, the parent and grandparent of the root
of the subtree, as in (a) and (b) of the figure. In (b), C0 is one level deeper than
it is in (a), which increases the cost by 5, but D1 is three levels higher, which
decreases the overall cost by 2 × 3 = 6, for a net decrease of 1 unit. Hence, using
T instead of T 0 ends up costing the overall solution 1 unit more.
This observation is the basis of the complete counterexample shown in Fig. 6.
The counterexample extends the smaller example above by appending two “neutral” subintervals, with 7 and 15 keys, respectively, each of which (without any
deletions) admits a self-contained balanced tree. Keys are ordered alphabetically.
On this instance, the algorithm of [9] (and their Lemma 4) fail, as they choose
T instead of T 0 for the subproblem. Fig. 6(a) shows the tree computed by their
recurrence, of cost 1763. (This can be verified by executing the Python code for
the algorithm in Appendix 7.1.) Fig. 6(b) shows a tree that costs 1 less. This
proves Thm. 4.
Spuler’s thesis. In addition to Spuler’s conjecture (and 2wcst algorithms that
rely on his conjecture), Spuler’s thesis [15, §6.4.1 Conj. 1] also presents code
for two additional algorithms that he claims, without proof, compute optimal
2wcsts independently of his conjecture.
First, [15, §6.4.1] gives code for the problem restricted to successful queries
(Q = K), which it describes as a “straightforward” modification of Huang et
al.’s algorithm [9] for generalized split trees (an algorithm that we now know is
incorrect, per our Thm. 4). Correctness is addressed only by the remark that
“The changes to the optimal generalized binary split tree algorithm of Huang and
Wong [9] to produce optimal generalized two-way comparison trees 9 are quite
straight forward.”
Secondly, [15, §6.5] gives code for the case of unrestricted queries, which it
describes as a “not difficult” modification of the preceding algorithm in §6.4.1.
Correctness is addressed only by the following remark: “The algorithm of the
previous section assumes that αi = 0 for all i. However, the improvement of
8

9

In case (i), to minimize cost, the top two levels of the tree must contain D1 and two
other heavy keys from {A1, A2, A3, B4}. D1 has to be the right child of the root,
because otherwise a key no larger than B4 is, so the split key at the root has to be
no larger than B4, so the three light keys {C0, D0, E0} have to all be in the right
subtree, so that one of them has to be at level four instead of level three, increasing
the cost by at least 5. In case (ii), when D1 is deleted (not in the subtree), by a
similar argument, one of the light keys has to be at level four, so T 0 is best possible.
Spuler’s generalized two-way comparison trees are exactly 2wcsts as defined herein.

17

the algorithm to allow non-zero values of α is not difficult.” In contrast, Huang
et al. explicitly mention that they were unable to generalize their algorithm to
unrestricted queries [9].
Neither of Spuler’s two proposed algorithms is published in a peer-reviewed
venue (although they are referred to in [14]). They have no correctness proofs,
and are based on [9], which we now know is incorrect. Given these considerations,
we judge that Anderson et al. [1] give the first correct proof of a poly-time
algorithm to find optimal 2wcsts when only successful queries are allowed (K =
Q), and that this paper gives the first correct proof for the general case.

