On Random Binary Trees
Loading...
Authors
Brown, Gerald G.
Shubert, Bruno O.
Subjects
Advisors
Date of Issue
1984-02
Date
1984-02
Publisher
Language
Abstract
A widely used class of binary trees is studied in order to provide information useful in
evaluating algorithms based on this storage structure. A closed form counting formula for the
number of binary trees with n nodes and height k is developed and restated as a recursion
more useful computationally . A generating function for the number of nodes given height is
developed and used to find the asymptotic distribution of binary trees. An asymptotic
probab ility distribution for height given the number of nodes is derived based on equally likely
binary trees. This is compared with a similar result for general trees.
Type
Article
Description
Mathematics of Operations Research, 9, pp. 43-65.
Series/Report No
Department
Operations Research (OR)
Organization
Identifiers
NPS Report Number
Sponsors
Funder
Format
Citation
Brown, G.G. and Shubert, B., 1984, “On Random Binary Trees,” Mathematics of Operations Research, 9, pp. 43-65.
Distribution Statement
Rights
defined in Title 17, United States Code, Section 101. Copyright protection is not available for this work in the United States.