Bruce Reed
Abstract
Let Hn be the height of a random binary search tree on n nodes. We show that there exist constants α = 4.311… and β = 1.953… such that E(Hn) = αln n − βln ln n + O(1), We also show that Var(Hn) = O(1).
- Aho, A. V., Hopcroft, J. E., and Ullman, J. D. 1975. The Design and Analysis of Computer Algorithms. Addison-Wesley, Reading, Mass. Google Scholar
- Aho, A. V., Hopcroft, J. E., and Ullman, J. D. 1983. Data Structures and Algorithms, Addison-Wesley, Reading, Mass. Google Scholar
- Chernoff, H. 1952. A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations. Ann. Math. Stat. 23, 493--507.Google Scholar
- Devroye, L. 1986. A note on the height of binary search trees. J. ACM 33, 489--498. Google Scholar
- Devroye, L. 1987. Branching processes in the analysis of the heights of trees. Acta Inf. 24, 277--298. Google Scholar
- Devroye, L. 1990. On the height of random m-ary search trees. Rand. Struct. Algorithms 1, 191--203.Google Scholar
- Devroye, L., and Reed, B. 1995. On the variance of the height of random binary search trees. SIAM J. Comput. 24, 1107--1112. Google Scholar
- Drmota, M. 2003. An analytic approach to the height of binary search trees II. J. ACM 50, 3 (May), 333--374. Google Scholar
- Knuth, D. E. 1973a. The Art of Computer Programming, Vol. 1: Fundamental Algorithms. Addison-Wesley, Reading, Mass., 2nd ed. Google Scholar
- Knuth, D. E. 1973b. The Art of Computer Programming, Vol. 3: Sorting and Searching. Addison-Wesley, Reading, Mass. Google Scholar
- Mahmoud, H. M. 1992. Evolution of Random Search Trees. John Wiley, New York.Google Scholar
- Mahmoud, H., and Pittel, B. 1994. On the most probable shape of a search tree grown from a random permutation. SIAM J. Algeb. Disc. Meth. 5, 69--81.Google Scholar
- Pittel, B. 1984. On growing random binary trees. J. Math. Anal. Appl. 103, 461--480.Google Scholar
- Pittel, B. 1994. Note on the heights of random recursive trees and random m-ary search trees. Rand. Struct. Algorithms 5, 337--347.Google Scholar
- Pyke, R. 1965. Spacings. J. Roy. Stat. Soc., Ser., B 7, 395--445.Google Scholar
- Robson, J. M. 1979. The height of binary search trees. Austral. Comput. J. 11, 151--153.Google Scholar
- Robson, J. M. 1982. The asymptotic behaviour of the height of binary search trees. Austral. Comput. Sci. Commun. p. 88.Google Scholar
- Shorack, G., and Wellner, J. 1986. Empirical Processes with Applications to Statistics. Wiley, New York.Google Scholar
Index Terms
- The height of a random binary search tree
Recommendations
On the Variance of the Height of Random Binary Search Trees
Let $H_n$ be the height of a random binary search tree on $n$ nodes. We show that there exists a constant $\alpha = 4.31107\ldots$ such that ${\rm P} \{ |H_n - \alpha \log n | > \beta \log \log n \} \to 0$, where $\beta>15 \alpha / \ln 2 = 93.2933\...
The height of increasing trees
We extend results about heights of random trees (Devroye, JACM [33 (1986) 489–498], SIAM J COMP [28 (1998) 409–432)]. In this paper, a general split tree model is considered in which the normalized subtree sizes of nodes converge in distribution. The ...
Split Trees – A Unifying Model for Many Important Random Trees of Logarithmic Height: A Brief Survey
Discrete Geometry and Mathematical MorphologyAbstractSplit trees were introduced by Devroye [28] as a novel approach for unifying many important random trees of logarithmic height. They are interesting not least because of their usefulness as models of sorting algorithms in computer science; for ...
Comments