Profiles of random trees: plane-oriented recursive treesConference paperAuthors: Hsien-Kuei Hwang
1
0000-0002-9410-6476
Hsien-Kuei Hwang
- 1 Institute of Statistical Science
We summarize several limit results for the profile of random plane-oriented recursive trees. These include the limit distribution of the normalized profile, asymptotic bimodality of the variance, asymptotic approximations of the expected width and the correlation coefficients of two level sizes. We also unveil an unexpected connection between the profile of plane-oriented recursive trees (with logarithmic height) and that of random binary trees (with height proportional to the square root of tree size).
Volume: DMTCS Proceedings vol. AD, International Conference on Analysis of Algorithms
Section: Proceedings
Published on: January 1, 2005
Imported on: May 10, 2017
Keywords: [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], [INFO.INFO-CG]Computer Science [cs]/Computational Geometry [cs.CG], [INFO.INFO-HC]Computer Science [cs]/Human-Computer Interaction [cs.HC], [en] random binary trees, Plane-oriented recursive trees, profile of trees, limit distribution, convergence of all moments, total path length