HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Reports

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 metadata

https://hal.inria.fr/inria-00076989
Contributor : Rapport de Recherche Inria Connect in order to contact the contributor
Submitted on : Monday, May 29, 2006 - 11:47:01 AM
Last modification on : Thursday, February 3, 2022 - 11:18:11 AM
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

81

Files downloads

130