The optimal binary search tree for Andersson's search algorithm (Q1323348)

\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)].