scientific article; zbMATH DE number 4047146
[For the entire collection see Zbl 0616.00013.] Heuristics for optimal binary search trees with zero key access probabilities (with applications e.g. in code theory and in point location) are considered. It is shown that for an arbitrarily small positive constant \(\epsilon\), there exists a linear-time heuristic for such search trees, producing solutions within the factor of \(1+\epsilon\) 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.
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3783595)