Skip to Main content Skip to Navigation
Conference papers

Profiles of random trees: plane-oriented recursive trees

Abstract : 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).
Complete list of metadata

Cited literature [19 references]  Display  Hide  Download

https://hal.inria.fr/hal-01184033
Contributor : Coordination Episciences Iam <>
Submitted on : Wednesday, August 12, 2015 - 3:51:57 PM
Last modification on : Wednesday, January 24, 2018 - 10:46:02 AM
Long-term archiving on: : Friday, November 13, 2015 - 11:40:18 AM

File

dmAD0119.pdf
Publisher files allowed on an open archive

Identifiers

  • HAL Id : hal-01184033, version 1

Collections

Citation

Hsien-Kuei Hwang. Profiles of random trees: plane-oriented recursive trees. 2005 International Conference on Analysis of Algorithms, 2005, Barcelona, Spain. pp.193-200. ⟨hal-01184033⟩

Share

Metrics

Record views

150

Files downloads

750