A note on the height of binary search trees

ABSTRACT

Let Hn be the height of a binary search tree with n nodes constructed by standard insertions from a random permutation of 1, … , n. It is shown that Hn/log n → c = 4.31107 … in probability as n → ∞, where c is the unique solution of c log((2e)/c) = 1, c ≥ 2. Also, for all p > 0, limn→∞E(Hpn)/ logpn = cp. Finally, it is proved that Sn/log n → c* = 0.3733 … , in probability, where c* is defined by c log((2e)/c) = 1, c ≤ 1, and Sn is the saturation level of the same tree, that is, the number of full levels in the tree.

REFERENCES

• 1: BIGGINS, J.D. The first and last-birth problems for a multitype age-dependent branching process. Adv. Appl. Probab. 8 (1976), 446-459.
• 2: BIGGINS, J.D. Chernoff's theorem in the branching random walk. J. Appl. Probab. 14 (1977), 630-636.
• 3: DE BRUIJN, N., KNUTH, D. E., AND RICE, O. The average height of planted plane trees. In Graph Theory and Computing, R.-C. Read, Ed. Academic Press, Orlando, Fla., 1972, pp. 15-22.
• 4: DEVROYE, L. A probabilistic analysis of the height of tries and of the complexity of triesort. Acta Inf. 21 (1984), 229-237.
• 5: FLAJOLET, P. AND ODLYZKO, A. The average height of binary trees and other simple trees. J. Comput. Syst. Sci. 25 (1982), 171-213.
• 6: HAMMERSLEY, J.M. Postulates for subadditive processes. Ann. Probab. 2 (1974), 652-680.
• 7: Rainer Kemp, On the Average Stack Size of Regularly Distributed Binary Trees, Proceedings of the 6th Colloquium, on Automata, Languages and Programming, p.340-355, July 16-20, 1979
• 8: KINGMAN, J. F.C. The first-birth problem for an age-dependent branching process. Ann. Probab. 3 (1975), 790-801.
• 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: MAHMOUD, H., AND PITTEL, B. On the most probable shape of a binary search tree grown from a random permutation. SIAM J. Algebraic Discrete Meth. 5 (1984), 69-81.
• 11: PITTEL, B. On growing random binary trees. J. Math. Anal. Appl. 103 (1984), 461-480.
• 12: RENYI, A., SZEKERES, G. On the height oftrees. Aust. J. Math. 7 (1967), 497-507.
• 13: ROBSON, J.M. The height of binary search trees. Aust. Comput. J. 11 (1979), 151-153.
• 14: ROBSON, J.M. The asymptotic behaviour of the height of binary search trees. Aust. Comput. S~i. Commun. (1982), p. 88 (Also: Tech. Rep. TR-CS-81-15, Dept. of Computer Science, Australian National Univ., Canberra, Australia, 1981).
• 15: ROBSON, J. M. On the height of binary search trees. Tech. Rep. Dept. of Computer Science, Australian National Univ. Canberra, 1983.
• 16: STEPANOV, V.E. On the distribution of the number of vertices in strata of a random tree. Theor. Probab. Appl. 14 (1969), 65-78.
• 17: YAO, A.C. A note on the analysis of extendible hashing. Inf. Process. Lett. 11 (1980), 84-86.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Graph and tree search strategies

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sorting and searching

General Terms:
Algorithms, Performance, Theory, Verification