Optimal search trees with 2-way comparisons?
Marek Chrobák, Mordecai J. Golin, J. Ian Munro, Neal E. Young · 2016
Abstract. In 1971, Knuth gave an O(n2)-time algorithm for the clas-sic 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 (). Un-til 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 al-gorithm and (ii) an O(n logn)-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 higher-level programming languages, most computers began supporting only two-way