Publication:
On Random Binary Trees

Loading...
Thumbnail Image
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.
Collections