The height of a random binary search tree

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

REFERENCES

• 1: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 2: Alfred V. Aho , John E. Hopcroft , Jeffrey Ullman , J. D. Ullman , J. E. Hopcroft, Data Structures and Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1983
• 3: 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.
• 4: Luc Devroye, A note on the height of binary search trees, Journal of the ACM (JACM), v.33 n.3, p.489-498, July 1986 [doi>10.1145/5925.5930]
• 5: L Devroye, Branching processes in the analysis of the heights of trees, Acta Informatica, v.24 n.3, p.277-298, June 1987
• 6: Devroye, L. 1990. On the height of random m-ary search trees. Rand. Struct. Algorithms 1, 191--203.
• 7: Luc Devroye , Bruce Reed, On the Variance of the Height of Random Binary Search Trees, SIAM Journal on Computing, v.24 n.6, p.1157-1162, Dec. 1995 [doi>10.1137/S0097539792237541]
• 8: Michael Drmota, An analytic approach to the height of binary search trees II, Journal of the ACM (JACM), v.50 n.3, p.333-374, May 2003 [doi>10.1145/765568.765572]
• 9: Donald E. Knuth, The art of computer programming, volume 1 (3rd ed.): fundamental algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1997
• 10: Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
• 11: Mahmoud, H. M. 1992. Evolution of Random Search Trees. John Wiley, New York.
• 12: 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.
• 13: Pittel, B. 1984. On growing random binary trees. J. Math. Anal. Appl. 103, 461--480.
• 14: Pittel, B. 1994. Note on the heights of random recursive trees and random m-ary search trees. Rand. Struct. Algorithms 5, 337--347.
• 15: Pyke, R. 1965. Spacings. J. Roy. Stat. Soc., Ser., B 7, 395--445.
• 16: Robson, J. M. 1979. The height of binary search trees. Austral. Comput. J. 11, 151--153.
• 17: Robson, J. M. 1982. The asymptotic behaviour of the height of binary search trees. Austral. Comput. Sci. Commun. p. 88.
• 18: Shorack, G., and Wellner, J. 1986. Empirical Processes with Applications to Statistics. Wiley, New York.

INDEX TERMS

Primary Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Trees

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
  G.3 PROBABILITY AND STATISTICS

General Terms:
Algorithms, Theory

Keywords:
Binary search tree, asymptotics, height, probabilistic analysis, random tree, second moment method