Nicolas Broutin ; Philippe Flajolet
-
The height of random binary unlabelled trees
dmtcs:3559 -
Discrete Mathematics & Theoretical Computer Science,
January 1, 2008,
DMTCS Proceedings vol. AI, Fifth Colloquium on Mathematics and Computer Science
-
https://doi.org/10.46298/dmtcs.3559
The height of random binary unlabelled trees
Authors: Nicolas Broutin 1; Philippe Flajolet 1
NULL##NULL
Nicolas Broutin;Philippe Flajolet
1 Algorithms
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.
The Distribution of heights of binary trees and other simple trees
3 Documents citing this article
Source : OpenCitations
Broutin, Nicolas; Flajolet, Philippe, 2011, The Distribution Of Height And Diameter In Random Non-Plane Binary Trees, Random Structures And Algorithms, 41, 2, pp. 215-252, 10.1002/rsa.20393.
Haas, Bénédicte; Miermont, Grégory, 2012, Scaling Limits Of Markov Branching Trees With Applications To Galton–Watson And Random Unordered Trees, The Annals Of Probability, 40, 6, 10.1214/11-aop686.
Marckert, Jean-François; Miermont, GrĂŠgory, 2010, The CRT Is The Scaling Limit Of Unordered Binary Trees, Random Structures And Algorithms, 38, 4, pp. 467-501, 10.1002/rsa.20332.