The Distribution of Heights of Binary Trees and Other Simple Trees

DOI10.1017/S0963548300000560zbMath0795.05042OpenAlexW1996039969MaRDI QIDQ4290085

Bruce Richmond, Andrew M. Odlyzko, Zhi-Cheng Gao, Philippe Flajolet

Publication date: 14 September 1994

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1017/s0963548300000560

zbMATH Keywords

heightdistributionlimit theorembinary trees

Mathematics Subject Classification ID

Trees (05C05) Enumeration in graph theory (05C30) Limit theorems in probability theory (60F99)

Related Items (16)

The shape of random tanglegrams ⋮ The distribution of height and diameter in random non-plane binary trees ⋮ Tail bounds for the height and width of a random tree with a given degree sequence ⋮ The height of multiple edge plane trees ⋮ Analytic methods in asymptotic enumeration ⋮ Canonical Trees, Compact Prefix-Free Codes, and Sums of Unit Fractions: A Probabilistic Analysis ⋮ Pareto quantiles of unlabeled tree objects ⋮ Finite size percolation in regular trees ⋮ The continuum limit of critical random graphs ⋮ On the Diameter of Random Planar Graphs ⋮ Sub-Gaussian tail bounds for the width and height of conditioned Galton-Watson trees ⋮ A stochastically quasi-optimal search algorithm for the maximum of the simple random walk ⋮ Precise logarithmic asymptotics for the right tails of some limit random variables for random trees ⋮ The shape of unlabeled rooted random trees ⋮ Critical random graphs and the structure of a minimum spanning tree ⋮ The Wiener Index of simply generated random trees

Cites Work

• Periodic oscillations of coefficients of power series that satisfy functional equations
• The average height of binary trees and other simple trees
• Central and local limit theorems applied to asymptotic enumeration. II: Multivariate generating functions
• Regular iteration of real and complex functions
• Current trends in asymptotics: Some problems and some solutions
• On Random Binary Trees
• On the Altitude of Nodes in Random Trees
• Constant Time Generation of Free Trees
• On the height of trees

This page was built for publication: The Distribution of Heights of Binary Trees and Other Simple Trees