The distribution of height and diameter in random non-plane binary trees

DOI10.1002/RSA.20393MaRDI QIDQ3165458zbMATH OpenOpenAlexFDO

Authors Nicolas Broutin, Philippe Flajolet

Publication date 26 October 2012

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1009.1515

zbMATH Keywords

generating functionheightlimiting distributionnon-plane unlabelled binary treesOtter treesrandom treesingularity analysis

Mathematics Subject Classification ID

Trees (05C05) Random graphs (graph-theoretic aspects) (05C80)

Abstract: This study is dedicated to precise distributional analyses of the height of non-plane unlabelled binary trees ("Otter trees"), when trees of a given size are taken with equal likelihood. The height of a rooted tree of size $n$ is proved to admit a limiting theta distribution, both in a central and local sense, as well as obey moderate as well as large deviations estimates. The approximations obtained for height also yield the limiting distribution of the diameter of unrooted trees. The proofs rely on a precise analysis, in the complex plane and near singularities, of generating functions associated with trees of bounded height.

Recommendations

• The Distribution of Heights of Binary Trees and Other Simple Trees
• scientific article; zbMATH DE number 2197876
• On the total heights of random rooted binary trees
• The height of random binary unlabelled trees
• scientific article; zbMATH DE number 515653
• On the asymptotic joint distribution of height and width in random trees
• The asymptotic distribution of leaf heights in binary trees
• The height of random k‐trees and related branching processes

Cites work

• And/Or Trees Revisited
• Asymptotic densities in logic and type theory
• Functionals of Brownian meander and Brownian excursion
• scientific article; zbMATH DE number 3886512 (Why is no real title available?)
• scientific article; zbMATH DE number 1338133 (Why is no real title available?)
• scientific article; zbMATH DE number 1111371 (Why is no real title available?)
• Isomorphism and symmetries in random phylogenetic trees
• Mellin transforms and asymptotics: Harmonic sums
• On Ramanujan's Q-function
• On the Altitude of Nodes in Random Trees
• On the height of trees
• Parking functions, empirical processes, and the width of rooted labeled trees
• Random Trees
• Random trees and applications
• Scaling limits of Markov branching trees with applications to Galton-Watson and random unordered trees
• Some typical properties of large AND/OR Boolean formulas
• The average height of binary trees and other simple trees
• The continuum random tree. I
• The continuum random tree. III
• The CRT is the scaling limit of unordered binary trees
• The Distribution of Heights of Binary Trees and Other Simple Trees
• The distribution of the maximum Brownian excursion
• The Enumeration of Trees by Height and Diameter
• The Galton-Watson process conditioned on the total progeny
• The height of random binary unlabelled trees
• The number of trees
• The Random Walk Construction of Uniform Spanning Trees and Uniform Labelled Trees

Cited in

(17)

• A strong law for the height of random binary pyramids
• Normal limiting distribution of the size of binary interval trees
• Two results about the Sackin and Colless indices for phylogenetic trees and their shapes
• Model spaces of regularity structures for space-fractional SPDEs
• Extremal statistics on non-crossing configurations
• Asymptotic properties of random unlabelled block-weighted graphs
• The height of random binary unlabelled trees
• On the asymptotic joint distribution of height and width in random trees
• The Distribution of Heights of Binary Trees and Other Simple Trees
• The degree profile of random Pólya trees
• The metric space of limit laws for \(q\)-hook formulas
• On the limiting distributions of the total height on families of trees
• scientific article; zbMATH DE number 2197876 (Why is no real title available?)
• Scaling Limits of Markov-Branching Trees and Applications
• Tree height and the asymptotic mean of the Colijn-Plazzotta rank of unlabeled binary rooted trees
• Scaling limits of Markov branching trees with applications to Galton-Watson and random unordered trees
• Height and diameter of Brownian tree

Describes a project that uses

Uses Software

• OEIS

This page was built for publication: The distribution of height and diameter in random non-plane binary trees

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