  Optimal 3-way comparison search trees (3WCST's) can be computed using
standard dynamic programming in time O(n^3), and this can be further improved
to O(n^2) by taking advantage of the Monge property. In contrast, the fastest
algorithm in the literature for computing optimal 2-way comparison search trees
(2WCST's) runs in time O(n^4). To shed light on this discrepancy, we study
structure properties of 2WCST's. On one hand, we show some new threshold bounds
involving key weights that can be helpful in deciding which type of comparison
should be at the root of the optimal tree. On the other hand, we also show that
the standard techniques for speeding up dynamic programming (the Monge property
/ quadrangle inequality) do not apply to 2WCST's.
