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,.
|Original language||English (US)|
|Number of pages||10|
|Journal||Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS|
|State||Published - Jan 1 1980|
|Event||21st Annual Symposium on Foundations of Computer Science, FOCS 1980 - Syracuse, United States|
Duration: Oct 13 1980 → Oct 15 1980