Renzo Sprugnoli
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)
- 1 ABRAMOWn'Z, M., AND STEGUN, I.A. Handbook of Mathemattcal Functtons. National Institute of Standards and Technology, Washington, D.C., i964.Google Scholar
- 2 BAYER, T., AND MITCHEL HEDEYNIEMI, S. Constant time generation of rooted trees. SIAMJ. Comput. 9 (1980), 706-712.Google Scholar
- 3 ER, M.C. Enumerating ordered trees le~icographically. CornputerJ. 28 (1985), 538-542.Google Scholar
- 4 ER, M.C. Lexicographic listing and ranking of t-ary trees. ComputerJ., 30 (1987), 569-572. Google Scholar
- 5 ER, M. C. A simple algorithm for generating non-regular trees in lexicographic order. Computer J. 31 (1988), 61-64. Google Scholar
- 6 FLAJOLET, PH., AND ODLYZKO, A. The average height of binary trees and other simple trees. J. Comput. Syst. Sci. 25 (1982), 171-213.Google Scholar
- 7 GONNET, G. H. Handbook of Algorithms and Data Structures. Addison-Wesley, Reading, Mass., 1984. Google Scholar
- 8 GOSPER, R. W., JR. Decision procedure for indefinite hypergeometric summation. Proc. NationaI Academy of Sciences USA 75 (1978), 40-42.Google Scholar
- 9 KNOTT, G. D. A numbering system for binary trees. Commun. ACM 20, 2 (Feb. 1977), 113-115. Google Scholar
- 10 KNUTH, D.E. The Art of Computer Programming, Vol. 1-3. Addison-Wesley, Reading, Mass., 1968-1973. Google Scholar
- 11 LEE, C. C., LEE, D. T., AND WONG, C.K. Generating binary trees of bounded height. Acta Inf. 23 (1986), 529-544. Google Scholar
- 12 NIJENHUIS, A., AND WILF, H.S. CombinatoriaIAlgorithms. Academic Press, New York, 1975.Google Scholar
- 13 PALLO, J., AND RACCA, R. A note on generating binary trees in A-order and B-order. Int. J. Comput. Math. 18 (1985), 27-39.Google Scholar
- 14 PROSKUROWSKI, A. On the generation of binary trees. J. ACM 27, 1 (Jan. 1980), 1-2. Google Scholar
- 15 REMY, J.-L. Un proc~d~ it6ratif de d6nombrement d'arbres binaires et son application a leur g6n6ration al~atoire. RAIRO Informatique Thdorique 19 (1985), 179-195.Google Scholar
- 16 ROELANTS VAN BARONEIGIEN, D., AND RUSKEY, F. Generating t-ary trees in A-order. bzf. Proc. Letters 27 (1988), 205-213. Google Scholar
- 17 ROTEM, D. On a correspondence between binary trees and a certain type of permutations. Inf. Proc. Letters 4 (1975), 58-61.Google Scholar
- 18 ROTEM, D., AND VAROL, Y. Generation of binary trees from ballot sequences. J. A CM 25, 3 (July 1978), 396-404. Google Scholar
- 19 Rusr~Y, F. Generating t-ary trees lexicographically. SIAM J. Comput. 7 (1978), 424-439.Google Scholar
- 20 RusI~Y, F., AND HU, T.C. Generating binary trees lexicographically. SIAM J. Comput. 6 (1977), 745-758.Google Scholar
- 21 SCOINS, H. Placing trees in lexicographic order. Mach. Intell. 3 (1969), 41-60.Google Scholar
- 22 Sr~ARBEK, W. Generating ordered trees. Theor. Comput. Sci. 57 (1988), 153-159. Google Scholar
- 23 SOLOMON, M., AND FINKEL, R.A. A note on enumerating binary trees. J. ACM 27 1 (Jan. 1980), 3-5. Google Scholar
- 24 SeRUGNOLI, R. Counting labels in binary trees. BIT (CopenhagetO 30 (1990), 62-69. Google Scholar
- 25 TROJANOWSKI, A. Ranking and listing algorithms for k-ary trees. SlAM J. Comput. 7 (1978), 492-509.Google Scholar
- 26 ZAKS, S. Lexicographic generation of ordered trees. Theor. Comput. Sci. 10 (1980), 63-82.Google Scholar
- 27 ZAKS, S., AND RICHARDS, D. Generating trees and other combinatorial objects lexicographically. SIAM J. Cornput. 8 (1979), 73-81.Google Scholar
- 28 ZeRLING, D. Generating binary trees using rotations. J. ACM 32, 3 (July 1985), 694-701. Google Scholar
Index Terms
- The generation of binary trees as a numerical problem
Recommendations
On Random Binary Trees
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 ...
An optimal insertion algorithm for one-sided height-balanced binary search trees
An algorithm for inserting an element into a one-sided height-balanced (OSHB) binary search tree is presented. The algorithm operates in time O(log n), where n is the number of nodes in the tree. This represents an improvement over the best previously ...
Parallel generation of binary trees in A-order
We present a new parallel algorithm for generating binary trees; it generates trees in A-order using A-sequences representation. This algorithm is adaptive and cost-optimal and is executed on a shared memory multiprocessor. We know of no other parallel ...
Reviews
Linda Pagli
The random generation of binary trees has been widely studied both as a theoretical problem and for its practical relevance. In fact, random trees have to be generated in a uniform way whenever the performance of algorithms on binary trees has to be studied or verified by means of statistical evaluation. This paper presents a new algorithm for the problem, requiring O n time and O n extra space for the generation of a random tree of n nodes. The algorithm matches the time complexity of the best previous strategy, but reduces the extra space from O n to O n . The algorithm can also be applied for the generation of binary search trees, still in O n time against the O n log n time complexity of previous methods. The algorithm is based on a novel technique that generates the random tree recursively. More precisely, first a closed formula that counts the number of tree s that have k-1 nodes k=1,&ldots;,n in the left subtree is derived; then the formula is inverted to determine, according to the probability distribution, the number of nodes in the left and right subtrees that can be generated recursively. The merit of the proposed approach is that the theoretical investigation is completed with a number of practical observations that yield an efficient implementation of the method.
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments