Heuristics for optimum binary search trees and minimum weight triangulation problems

In this paper we establish new bounds on the problem of constructing optimum binary search trees with zero-key access probabilities (with applications e. g. to point location problems). We present a linear-time heuristic for constructing such search trees so that their cost is within a factor of 1 + ε from the optimum cost, where ε is an arbitrary small positive constant. Furthermore, by using an interesting amortization argument, we give a simple and practical, linear-time implementation of a known greedy heuristics 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 optimum (m − 1)-way search trees and minimum weight partitions of infinitely-flat semi-circular polygons into m-gons. With this duality we can also obtain better heuristics for minimum length partitions of polygons by using known algorithms for optimum search trees.

Authors

• Christos Levcopoulos
• Andrzej Lingas
• Jörg-R. Sack

Keywords

No keywords are indexed for this paper.