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

N1 - Copyright:
Copyright 2016 Elsevier B.V., All rights reserved.

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

VL - 2

SP - 145

EP - 156

JO - Combinatorics Probability and Computing

JF - Combinatorics Probability and Computing

SN - 0963-5483

IS - 2

ER -