The optimal binary search tree for Andersson's search algorithm
\textit{A. Andersson} [Software, Pract. Exper. 21, No. 10, 1125-1128 (1991)] has presented a search algorithm for binary search trees that uses only two-way key comparisons by deferring equality comparisons until the leaves are reached. The use of a different search algorithm means that the optimal tree for the traditional search algorithm, which has been shown to be computable in \(O(n^ 2)\) time by \textit{D. E. Knuth} [Acta Inf. 1, No. 1, 14-25 (1971; Zbl 0233.68010)] is not optimal with respect to of the different search algorithm. This paper shows that the optimal binary search tree for Andersson's search algorithm can be simply computed in \(O(n\log n)\) time using existing algorithms for the special case of zero successful access frequencies, such as the Hu-Tucker algorithm [\textit{T. C. Hu} and \textit{A. C. Tucker}, SIAM J. Appl. Math. 21, 514-532 (1971; Zbl 0228.94002)].
- Optimal binary search trees
- Optimal binary search trees
- Optimal alphabetic trees for binary search
- An Approximation Algorithm for Binary Searching in Trees
- An approximation algorithm for binary searching in trees
- Optimal Search in Trees
- Binary search trees of almost optimal height
- Reflections on Optimal and Nearly Optimal Binary Search Trees
- DYNAMIC OPTIMAL BINARY SEARCH TREE
- scientific article; zbMATH DE number 5237331
- The optimal binary search tree for Andersson's search algorithm
- Operations research applications of dichotomous search
- Optimal alphabetic trees for binary search
- scientific article; zbMATH DE number 2081096 (Why is no real title available?)
- Thresholds and optimal binary comparison search trees
- Optimal binary search trees
- A Simple Algorithm for Optimal Search Trees with Two-way Comparisons
This page was built for publication: The optimal binary search tree for Andersson's search algorithm
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1323348)
