The Distribution of Heights of Binary Trees and Other Simple Trees

DOI10.1017/S0963548300000560MaRDI QIDQ4290085zbMATH OpenOpenAlexFDO

Authors Philippe Flajolet, Zhicheng Gao, Andrew Odlyzko, Bruce Richmond

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

distributionbinary treesheightlimit theorem

Mathematics Subject Classification ID

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

Recommendations

• The distribution of height and diameter in random non-plane binary trees
• The height of random binary unlabelled trees
• The limiting common distribution of two leaf heights in a random binary tree
• An analytic approach to the height of binary search trees
• The asymptotic distribution of leaf heights in binary trees

Cites work

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

Cited in

(33)

• The continuum limit of critical random graphs
• Critical random graphs and the structure of a minimum spanning tree
• An asymptotic ratio in the complete binary tree
• Tail bounds for the height and width of a random tree with a given degree sequence
• On the diameter of random planar graphs
• The shape of unlabeled rooted random trees
• Canonical trees, compact prefix-free codes, and sums of unit fractions: a probabilistic analysis
• The shape of random tanglegrams
• scientific article; zbMATH DE number 1552322 (Why is no real title available?)
• Returns, hills, and \(t\)-ary trees
• Finite size percolation in regular trees
• The height of multiple edge plane trees
• A diffusion limit for a class of randomly-growing binary trees
• scientific article; zbMATH DE number 2197876 (Why is no real title available?)
• Analytic methods in asymptotic enumeration
• scientific article; zbMATH DE number 3847416 (Why is no real title available?)
• Normal limiting distribution of the size of binary interval trees
• Random trees have height \(O(\sqrt{n})\)
• Power-law behavior in geometric characteristics of full binary trees
• Sub-Gaussian tail bounds for the width and height of conditioned Galton-Watson trees
• scientific article; zbMATH DE number 1552321 (Why is no real title available?)
• scientific article; zbMATH DE number 3904610 (Why is no real title available?)
• A stochastically quasi-optimal search algorithm for the maximum of the simple random walk
• Limit distributions for coefficients of iterates of polynomials with applications to combinatorial enumerations
• The joint distribution of the three types of nodes in uniform binary trees
• Some new results on the average shape of binary trees and other simply generated families
• Precise logarithmic asymptotics for the right tails of some limit random variables for random trees
• Pareto quantiles of unlabeled tree objects
• The density of the ISE and local limit laws for embedded trees
• The height of random binary unlabelled trees
• The Wiener Index of simply generated random trees
• scientific article; zbMATH DE number 1984553 (Why is no real title available?)
• The distribution of height and diameter in random non-plane binary trees

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4290085)