The Distribution of heights of binary trees and other simple trees

Abstract : The number of binary trees of fixed size and given height is estimated asymptotically near the peak of the distribution. There, a local limit theorem with convergence to a theta law is established. Large deviation bounds corresponding to large heights and small heights are also derived. The methods based on the analysis of singular iterations apply to any simple family of trees.
Type de document :
Rapport
[Research Report] RR-1749, INRIA. 1992
Liste complète des métadonnées

https://hal.inria.fr/inria-00076989
Contributeur : Rapport de Recherche Inria <>
Soumis le : lundi 29 mai 2006 - 11:47:01
Dernière modification le : samedi 17 septembre 2016 - 01:36:11
Document(s) archivé(s) le : vendredi 13 mai 2011 - 22:23:21

Fichiers

Identifiants

  • HAL Id : inria-00076989, version 1

Collections

Citation

Philippe Flajolet, Zhicheng Gao, Andrew M. Odlyzko, Bruce Richmond. The Distribution of heights of binary trees and other simple trees. [Research Report] RR-1749, INRIA. 1992. 〈inria-00076989〉

Partager

Métriques

Consultations de la notice

123

Téléchargements de fichiers

74