TY - JOUR
T1 - The Distribution of Heights of Binary Trees and Other Simple Trees
AU - Flajolet, Philippe
AU - Gao, Zhicheng
AU - Odlyzko, Andrew
AU - Richmond, Bruce
PY - 1993/6
Y1 - 1993/6
N2 - The number, [formula omitted], of rooted plane binary trees of height ≤ h with n internal nodes is shown to satisfy [formula omitted] uniformly for δ−1(log n)−1/2 ≤ β ≤ δ(log n)1/2, where [formula omitted] and δ is a positive constant. An asymptotic formula for [formula omitted] is derived for h = cn, where 0 < c < 1. Bounds for [formula omitted] are also derived for large and small heights. The methods apply to any simple family of trees, and the general asymptotic results are stated.
AB - The number, [formula omitted], of rooted plane binary trees of height ≤ h with n internal nodes is shown to satisfy [formula omitted] uniformly for δ−1(log n)−1/2 ≤ β ≤ δ(log n)1/2, where [formula omitted] and δ is a positive constant. An asymptotic formula for [formula omitted] is derived for h = cn, where 0 < c < 1. Bounds for [formula omitted] are also derived for large and small heights. The methods apply to any simple family of trees, and the general asymptotic results are stated.
UR - http://www.scopus.com/inward/record.url?scp=84971768690&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84971768690&partnerID=8YFLogxK
U2 - 10.1017/S0963548300000560
DO - 10.1017/S0963548300000560
M3 - Article
AN - SCOPUS:84971768690
SN - 0963-5483
VL - 2
SP - 145
EP - 156
JO - Combinatorics, Probability and Computing
JF - Combinatorics, Probability and Computing
IS - 2
ER -