Premium
Profiles of random trees: Plane‐oriented recursive trees
Author(s) -
Hwang HsienKuei
Publication year - 2007
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20139
Subject(s) - mathematics , binary tree , limit (mathematics) , logarithm , random tree , random binary tree , tree (set theory) , plane (geometry) , binary search tree , asymptotic distribution , mathematical proof , combinatorics , statistical physics , mathematical analysis , statistics , geometry , computer science , physics , robot , motion planning , artificial intelligence , estimator
We derive 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 approximation to the expected width, and the correlation coefficients of two level sizes. Most of our proofs are based on a method of moments. We also discover 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). © 2006 Wiley Periodicals, Inc. Random Struct. Alg., 2007