The profile of binary search trees. (English) Zbl 1012.60038
Summary: We characterize the limiting behavior of the number of nodes in level \(k\) of binary search trees \(T_n\) in the central region \(1.2\log n\leq k\leq 2.8\log n\). Especially we show that the width \(\overline V_n\) (the maximal number of internal nodes at the same level) satisfies \(\overline V_n \sim(n/ \sqrt{4\pi\log n})\) as \(n\to\infty\) a.s.
Keywords:
repartition of nodes for binary search trees; martingales; asymptotic series expansion; complex analysisReferences:
| [1] | Biggins, J.D. (1997). How fast does a general branching random walk spread? In Classical and Modern Branching Processes 19-39. Springer, New York. · Zbl 0873.60061 |
| [2] | Devroye, L. (1987). Branching processes in the analysis of the height of trees. Acta Inform. 24 277-298. · Zbl 0643.60065 · doi:10.1007/BF00265991 |
| [3] | Drmota, M. and Hwang, H.K. (2001). Asymptotic expansions for second moments of the profile of binary search trees. Unpublished manuscript. |
| [4] | Flajolet, P. and Odlyzko, A.M. (1990). Singularity analysis of generating functions. SIAM J. Discrete Math. 3 216-240. · Zbl 0712.05004 · doi:10.1137/0403019 |
| [5] | Jabbour-Hattab, J. (2001). Martingales and large deviations for the binary search trees. Random Structure Algorithms 19, 112-127. · Zbl 0983.60034 · doi:10.1002/rsa.1023 |
| [6] | Joffe, A. Le Cam, L, and Neveu, J. (1973). Sur la loi des grands nombres pour des variables aléatoires attachées a un arbre dyadique. C. R. Acad. Sci. Paris. Ser. A 277 963-964. · Zbl 0292.60078 |
| [7] | Lynch, W. (1965). More combinatorial problems on certain trees.Computer J. 7 299-302. · Zbl 0136.38801 |
| [8] | Mahmoud, H.M. (1992). Evolution of Random Search Trees. Wiley, New York. · Zbl 0762.68033 |
| [9] | Moser, L. and Wyman, M. (1958). Asymptotic development of the Stirling numbers of the first kind. J. London Math. Soc. 33 133-146. · Zbl 0081.28202 · doi:10.1112/jlms/s1-33.2.133 |
| [10] | Neveu, J. (1972). Martingales á temps discret. Masson and Cie, Paris. · Zbl 0235.60010 |
| [11] | Revuz, D. and Yor, M. (1990). Continuous Martingales and Brownian Motion. Springer, New York. · Zbl 1087.60040 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
