A Simple Algorithm for Optimal Search Trees with Two-Way Comparisons

Autor:	Chrobak, Marek, Golin, Mordecai, Munro, J. Ian, Young, Neal E.
Rok vydání:	2021
Předmět:	Computer Science - Data Structures and Algorithms 68P10 68P30 68W25 94A45 E.4 G.1.6 G.2.2 H.3.1 I.4.2
Zdroj:	ACM Transactions on Algorithms 18(1) (2022) 1-11
Druh dokumentu:	Working Paper
DOI:	10.1145/3477910
Popis:	We present a simple $O(n^4)$-time algorithm for computing optimal search trees with two-way comparisons. The only previous solution to this problem, by Anderson et al., has the same running time, but is significantly more complicated and is restricted to the variant where only successful queries are allowed. Our algorithm extends directly to solve the standard full variant of the problem, which also allows unsuccessful queries and for which no polynomial-time algorithm was previously known. The correctness proof of our algorithm relies on a new structural theorem for two-way-comparison search trees. Comment: v3 adds Appendix B, with a stronger alternative to Theorem 1
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/2103.01084 View this record from Arxiv