Exploring binary trees and other simple trees
- 1 October 1980
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 02725428,p. 207-216
- https://doi.org/10.1109/sfcs.1980.19
Abstract
The average height of a binary tree With n internal nodes is shown to be asymptotic to 2√πn. More generally, the average height of a tree in a simple family S with n nodes is asymptotic to c(S) √πn where c(S) is a number (usually algebraic) which can be explicitly determined from S. These results are achieved by means of a detailed singularity analysis of corresponding generating functions.Keywords
This publication has 6 references indexed in Scilit:
- On the analysis of tree-matching algorithmsLecture Notes in Computer Science, 1980
- On the average stack size of regularly distributed binary treesPublished by Springer Nature ,1979
- On the Altitude of Nodes in Random TreesCanadian Journal of Mathematics, 1978
- THE AVERAGE HEIGHT OF PLANTED PLANE TREESPublished by Elsevier ,1972
- On the height of treesJournal of the Australian Mathematical Society, 1967
- Kombinatorische Anzahlbestimmungen für Gruppen, Graphen und chemische VerbindungenActa Mathematica, 1937