The Distribution of Heights of Binary Trees and Other Simple Trees

DOI10.1017/S0963548300000560zbMATH Open0795.05042OpenAlexW1996039969MaRDI QIDQ4290085FDOQ4290085

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

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

zbMATH Keywords

distributionbinary treesheightlimit theorem

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (33)

• 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
• The shape of random tanglegrams
• Title not available (Why is that?)
• 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
• Title not available (Why is that?)
• Canonical Trees, Compact Prefix-Free Codes, and Sums of Unit Fractions: A Probabilistic Analysis
• Analytic methods in asymptotic enumeration
• Title not available (Why is that?)
• Random trees have height \(O(\sqrt{n})\)
• Normal limiting distribution of the size of binary interval trees
• Power-law behavior in geometric characteristics of full binary trees
• Sub-Gaussian tail bounds for the width and height of conditioned Galton-Watson trees
• Title not available (Why is that?)
• Title not available (Why is that?)
• Limit distributions for coefficients of iterates of polynomials with applications to combinatorial enumerations
• A stochastically quasi-optimal search algorithm for the maximum of the simple random walk
• 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
• Pareto quantiles of unlabeled tree objects
• Precise logarithmic asymptotics for the right tails of some limit random variables for random trees
• The density of the ISE and local limit laws for embedded trees
• The Wiener Index of simply generated random trees
• The height of random binary unlabelled trees
• Title not available (Why is that?)
• The distribution of height and diameter in random non-plane binary trees
• The continuum limit of critical random graphs
• Critical random graphs and the structure of a minimum spanning tree

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)