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

2 ALGORITHMS - Algorithms
Inria Paris-Rocquencourt
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.
Type de document :
Article dans une revue
Random Structures and Algorithms, Wiley, 2011, 41 (2), pp.215-252. 〈10.1002/rsa.20393〉
Domaine :

https://hal.inria.fr/hal-00773369
Contributeur : Nicolas Broutin <>
Soumis le : dimanche 13 janvier 2013 - 16:08:44
Dernière modification le : vendredi 25 mai 2018 - 12:02:05

### Citation

Nicolas Broutin, Philippe Flajolet. The distribution of height and diameter in random non-plane binary trees. Random Structures and Algorithms, Wiley, 2011, 41 (2), pp.215-252. 〈10.1002/rsa.20393〉. 〈hal-00773369〉

### Métriques

Consultations de la notice