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.
Document type :
Reports
Complete list of metadatas

https://hal.inria.fr/inria-00076989
Contributor : Rapport de Recherche Inria <>
Submitted on : Monday, May 29, 2006 - 11:47:01 AM
Last modification on : Friday, May 25, 2018 - 12:02:02 PM
Long-term archiving on : Friday, May 13, 2011 - 10:23:21 PM

Identifiers

  • 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⟩

Share

Metrics

Record views

159

Files downloads

159