Optimal Search Trees with 2-Way Comparisons

DOI10.1007/978-3-662-48971-0_7MaRDI QIDQ3459851zbMATH OpenOpenAlexFDO

Authors J. Ian Munro, Neal E. Young, Marek Chrobak, Mordecai J. Golin

Publication date 11 January 2016

Published in Algorithms and Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1505.00357

Mathematics Subject Classification ID

Data structures (68P05) Nonnumerical algorithms (68W05) Approximation algorithms (68W25) Analysis of algorithms (68W40)

Abstract: In 1971, Knuth gave an $O(n^2)$-time algorithm for the classic problem of finding an optimal binary search tree. Knuth's algorithm works only for search trees based on 3-way comparisons, while most modern computers support only 2-way comparisons (e.g., $<,le,=,ge$, and $>$). Until 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(n^4)$-time algorithm and (ii) an $O(nlogn)$-time additive-3 approximation algorithm. Also, for finding optimal binary split trees, we (iii) obtain a linear speedup and (iv) prove some previous work incorrect.

Recommendations

• A Simple Algorithm for Optimal Search Trees with Two-way Comparisons
• Optimal search trees using two-way key comparisons
• Optimal Search in Trees
• Optimal binary search trees
• Optimal binary search trees
• Reflections on Optimal and Nearly Optimal Binary Search Trees
• Constructing optimal search trees in optimal time
• scientific article; zbMATH DE number 2011834
• Efficient Construction of Near-Optimal Binary and Multiway Search Trees
• On the cost of unsuccessful searches in search trees with two-way comparisons

Cited in

(9)

• Almost optimal dynamic 2-3 trees
• Optimal search trees using two-way key comparisons
• On the cost of unsuccessful searches in search trees with two-way comparisons
• On Huang and Wong's algorithm for generalized binary split trees
• Reflections on Optimal and Nearly Optimal Binary Search Trees
• Binary Search on a Tape
• scientific article; zbMATH DE number 2081096 (Why is no real title available?)
• Thresholds and optimal binary comparison search trees
• A Simple Algorithm for Optimal Search Trees with Two-way Comparisons

This page was built for publication: Optimal Search Trees with 2-Way Comparisons

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3459851)