The generation of binary trees as a numerical problem
- 1 April 1992
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 39 (2) , 317-327
- https://doi.org/10.1145/128749.128753
Abstract
The problem of generating random, uniformly distributed, binary trees is considered. A closed formula that counts the number of trees having a left subtee with k -1 nodes ( k =1,2,..., n ) is found. By inverting the formula, random trees with n nodes are generated according to the appropriate probability distribution, determining the number of nodes in the left and right subtrees that can be generated recursively. The procedure is shown to run in time O(n) , occupying an extra space in the order of O(√n)Keywords
This publication has 21 references indexed in Scilit:
- A Simple Algorithm for Generating Non-regular Trees in Lexicographic OrderThe Computer Journal, 1988
- Lexicographic Listing and Ranking of t-ary TreesThe Computer Journal, 1987
- Generating binary trees of bounded heightActa Informatica, 1986
- Un procédé itératif de dénombrement d'arbres binaires et son application à leur génération aléatoireRAIRO. Informatique théorique, 1985
- A note on generating binary trees inA-order andB-orderInternational Journal of Computer Mathematics, 1985
- The average height of binary trees and other simple treesJournal of Computer and System Sciences, 1982
- Constant Time Generation of Rooted TreesSIAM Journal on Computing, 1980
- On the Generation of Binary TreesJournal of the ACM, 1980
- Decision procedure for indefinite hypergeometric summationProceedings of the National Academy of Sciences, 1978
- A numbering system for binary treesCommunications of the ACM, 1977