Exploring binary trees and other simple trees

Philippe Flajolet; Andrew Odlyzko

doi:10.1109/SFCS.1980.4567821

Exploring binary trees and other simple trees

Philippe Flajolet
, Andrew Odlyzko

Research output: Contribution to journal › Conference article › peer-review

8 Scopus citations

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,.

Original language	English (US)
Article number	4567821
Pages (from-to)	207-216
Number of pages	10
Journal	Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
DOIs	https://doi.org/10.1109/SFCS.1980.4567821
State	Published - 1980
Externally published	Yes
Event	21st Annual Symposium on Foundations of Computer Science, FOCS 1980 - Syracuse, United States Duration: Oct 13 1980 → Oct 15 1980

Bibliographical note

Publisher Copyright:
© 1980 IEEE Computer Society. All rights reserved.

Publisher link

10.1109/SFCS.1980.4567821

Find It

Find It at U of M Libraries

Cite this

@article{fda761b39f89405baa31f515bbb4f481,

title = "Exploring binary trees and other simple trees",

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,.",

author = "Philippe Flajolet and Andrew Odlyzko",

note = "Publisher Copyright: {\textcopyright} 1980 IEEE Computer Society. All rights reserved.; 21st Annual Symposium on Foundations of Computer Science, FOCS 1980 ; Conference date: 13-10-1980 Through 15-10-1980",

year = "1980",

doi = "10.1109/SFCS.1980.4567821",

language = "English (US)",

pages = "207--216",

journal = "Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS",

issn = "0272-5428",

publisher = "IEEE Computer Society",

}

TY - JOUR

T1 - Exploring binary trees and other simple trees

AU - Flajolet, Philippe

AU - Odlyzko, Andrew

PY - 1980

Y1 - 1980

N2 - 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,.

AB - 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,.

UR - https://www.scopus.com/pages/publications/19544390609

UR - https://www.scopus.com/pages/publications/19544390609#tab=citedBy

U2 - 10.1109/SFCS.1980.4567821

DO - 10.1109/SFCS.1980.4567821

M3 - Conference article

AN - SCOPUS:19544390609

SN - 0272-5428

SP - 207

EP - 216

JO - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS

JF - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS

M1 - 4567821

T2 - 21st Annual Symposium on Foundations of Computer Science, FOCS 1980

Y2 - 13 October 1980 through 15 October 1980

ER -

Exploring binary trees and other simple trees

Abstract

Bibliographical note

Publisher link

Find It

Other files and links

Fingerprint

Cite this