Skip to main contentSkip to search
Episciences
Open Access Journals
Sign in(new window)
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Sign in(new window)
Articles & Issues
All articlesAll accepted articlesAll volumesLast volumeSectionsSpecial issuesAuthors
About
The journalIndexing
Boards
Publish
For authorsEthical charter
Submit
Discrete Mathematics & Theoretical Computer Science logo
Contact
|
Credits
eISSN 1365-8050
|
RSS
|
Atom
Episciences
Documentation
|
Acknowledgements
|
Publishing policy
Accessibility: non-compliant
|
Legal mentions
|
Privacy statement
|
Terms of use
  1. Home > Articles & Issues >
  2. Articles >
  3. The height of random ...
Conference paper

The height of random binary unlabelled trees

Nicolas Broutin (1), Philippe Flajolet (1)
(1) Algorithms
Download article
Open on HAL
Imported on
May 10, 2017
Published on
December 31, 2007
Last modified on
March 31, 2025
Volume
DMTCS Proceedings vol. AI, Fifth Colloquium on Mathematics and Computer Science
Proceedings
DOI
10.46298/dmtcs.3559
License
https://about.hal.science/hal-authorisation-v1
Indicators
615
Views
496
Downloads

The height of random binary unlabelled trees

Nicolas Broutin (1), Philippe Flajolet (1)
(1) Algorithms
Abstract
This extended abstract is dedicated to the analysis of the height of non-plane unlabelled rooted binary trees. The height of such a tree chosen uniformly among those of size $n$ is proved to have a limiting theta distribution, both in a central and local sense. Moderate as well as large deviations estimates are also derived. The proofs rely on the analysis (in the complex plane) of generating functions associated with trees of bounded height.
Keywords
  • [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
  • [MATH.MATH-DS]Mathematics [math]/Dynamical Systems [math.DS]
  • [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO]
  • Average case analysis
  • height
  • limit distribution
  • local limit theorem
  • generating functions
Cited by

Source: OpenCitations

  • The shape of unlabeled rooted random trees

    European Journal of Combinatorics

    Authors : Michael Drmota ORCID, Bernhard Gittenberger ORCID

    Journal reference : Volume 31, 2010, pp. 2028-2063

    DOI : 10.1016/j.ejc.2010.05.011

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

    arXiv (Cornell University)

    Authors : Nicolas Broutin, Philippe Flajolet

    Journal reference : Volume 41, 2011, pp. 215-252

    DOI : 10.1002/rsa.20393

  • Tree Height and the Asymptotic Mean of the Colijn–Plazzotta Rank of Unlabeled Binary Rooted Trees

    Bulletin of Mathematical Biology

    Authors : Luc Devroye ORCID, Michael R. Doboli, Noah A. Rosenberg ORCID, Stephan Wagner ORCID

    Journal reference : Volume 87, 2025, pp. 172

    DOI : 10.1007/s11538-025-01538-7

  • Scaling limits of Markov branching trees with applications to Galton–Watson and random unordered trees

    The Annals of Probability

    Authors : Bénédicte Haas ORCID, Grégory Miermont ORCID

    Journal reference : Volume 40, 2012, pp.

    DOI : 10.1214/11-aop686

  • The CRT is the scaling limit of unordered binary trees

    arXiv (Cornell University)

    Authors : Jean‐François Marckert ORCID, Grégory Miermont ORCID

    Journal reference : Volume 38, 2010, pp. 467-501

    DOI : 10.1002/rsa.20332
Preview
Loading PDF preview...