Efficient Construction of Near-Optimal Binary and Multiway Search Trees
作者： Prosenjit Bose , Karim Douïeb
DOI: 10.1007/978-3-642-03367-4_21
关键词: Optimal binary search tree 、 Binary search tree 、 Self-balancing binary search tree 、 Random binary tree 、 Weight-balanced tree 、 Ternary search tree 、 Mathematics 、 Geometry of binary search trees 、 Beam search 、 Combinatorics
摘要: We present a new linear-time algorithm for constructing multiway search trees with near-optimal cost whose running time is independent of the size node in tree. With analysis our construction method, we provide upper bound on average that nearly matches lower bound. In fact, it tight infinitely many probability distributions. This problem well-studied literature case binary trees. Using are able to tightest an optimal
springer.com
acm.org
sci-hub.st 参考文章(21)
Kurt Mehlhorn, Sorting and Searching (Eatcs Monographs on Theoretical Computer Science) Springer-Verlag New York, Inc.. ,(1984)
Feifeng Zheng, Stanley P. Y. Fung, Wun-Tat Chan, Francis Y. L. Chin, Chung Keung Poon, Prudence W. H. Wong, Improved on-line broadcast scheduling with deadlines computing and combinatorics conference. pp. 320- 329 ,(2006) , 10.1007/11809678_34
Peter Becker, Construction of Nearly Optimal Multiway Trees computing and combinatorics conference. pp. 294- 303 ,(1997) , 10.1007/BFB0045096
Samuel W. Bent, Daniel D. Sleator, Robert E. Tarjan, Biased Search Trees SIAM Journal on Computing. ,vol. 14, pp. 545- 568 ,(1985) , 10.1137/0214041
Adriano M. Garsia, Michelle L. Wachs, A New Algorithm for Minimum Cost Binary Trees SIAM Journal on Computing. ,vol. 6, pp. 622- 642 ,(1977) , 10.1137/0206045
J. Feigenbaum, R. E. Tarjan, Two New Kinds of Biased Search Trees Bell System Technical Journal. ,vol. 62, pp. 3139- 3158 ,(1983) , 10.1002/J.1538-7305.1983.TB03469.X
L. Gotlieb, Optimal multi-way search trees. SIAM Journal on Computing. ,vol. 10, pp. 422- 433 ,(1978) , 10.1137/0210031
CE Shennon, Warren Weaver, A mathematical theory of communication Bell System Technical Journal. ,vol. 27, pp. 379- 423 ,(1948) , 10.1002/J.1538-7305.1948.TB01338.X
Kurt Mehlhorn, A Best Possible Bound for The Weighted Path Length of Binary Search Trees SIAM Journal on Computing. ,vol. 6, pp. 235- 239 ,(1977) , 10.1137/0206017
Donald E. Knuth, Top-down syntax analysis Acta Informatica. ,vol. 1, pp. 79- 110 ,(1971) , 10.1007/BF00289517