Nearly optimal heuristics for binary search trees with geometric generalizations

Abstract

Heuristics for optimal binary search trees with zero key access probabilities (with applications eg. in code theory and in point location) are considered. It is shown that for an arbitrarily small positive constant ∈, there exists a linear-time heuristic for such search trees, producing solutions within the factor of 1+∈ from the optimum. Also, by using an interesting amortization argument, we give a simple and practical, linear-time implementation of a known greedy heuristic for such trees. The above results are obtained in a more general setting, namely in the context of minimum length triangulations of so-called semi-circular polygons. They are carried over to binary search trees by proving a duality between minimum weight partitions of infinitely-flat semi-circular polygons into m-gons and optimal (m−1)-way search trees. Our results can be extended to the case with non-zero key access probabilities, and to multi-way search trees.