The generation of binary trees as a numerical problem

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 On , occupying an extra space in the order of On .

REFERENCES

• 1: ABRAMOWn'Z, M., AND STEGUN, I.A. Handbook of Mathemattcal Functtons. National Institute of Standards and Technology, Washington, D.C., i964.
• 2: BAYER, T., AND MITCHEL HEDEYNIEMI, S. Constant time generation of rooted trees. SIAMJ. Comput. 9 (1980), 706-712.
• 3: ER, M.C. Enumerating ordered trees le~icographically. CornputerJ. 28 (1985), 538-542.
• 4: M. C. Er, Lexicographic listing and ranking of t-ary trees, The Computer Journal, v.30 n.6, p.569-572, Dec. 1987
• 5: M. C. Er, A simple algorithm for generating non-regular trees in lexicographic order, The Computer Journal, v.31 n.1, p.61-64, Feb., 1988 [doi>10.1093/comjnl/31.1.61]
• 6: FLAJOLET, PH., AND ODLYZKO, A. The average height of binary trees and other simple trees. J. Comput. Syst. Sci. 25 (1982), 171-213.
• 7: G. H. Gonnet , R. Baeza-Yates, Handbook of algorithms and data structures: in Pascal and C (2nd ed.), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1991
• 8: GOSPER, R. W., JR. Decision procedure for indefinite hypergeometric summation. Proc. NationaI Academy of Sciences USA 75 (1978), 40-42.
• 9: Gary D. Knott, A numbering system for binary trees, Communications of the ACM, v.20 n.2, p.113-115, Feb. 1977 [doi>10.1145/359423.359434]
• 10: Donald E. Knuth, The art of computer programming, volume 1 (3rd ed.): fundamental algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1997
• 11: C. C. Lee , D. T. Lee , C. K. Wong, Generating binary trees of bounded height, Acta Informatica, v.23 n.5, p.529-544, Sept. 1986 [doi>10.1007/BF00288468]
• 12: NIJENHUIS, A., AND WILF, H.S. CombinatoriaIAlgorithms. Academic Press, New York, 1975.
• 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.
• 14: Andrzej Proskurowski, On the Generation of Binary Trees, Journal of the ACM (JACM), v.27 n.1, p.1-2, Jan. 1980 [doi>10.1145/322169.322170]
• 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.
• 16: D. Roelants van Baronaigien , Frank Ruskey, Generating t-ary trees in A-order, Information Processing Letters, v.27 n.4, p.205-213, April 8, 1988 [doi>10.1016/0020-0190(88)90027-0]
• 17: ROTEM, D. On a correspondence between binary trees and a certain type of permutations. Inf. Proc. Letters 4 (1975), 58-61.
• 18: Doron Rotem , Y. L. Varol, Generation of Binary Trees from Ballot Sequences, Journal of the ACM (JACM), v.25 n.3, p.396-404, July 1978 [doi>10.1145/322077.322082]
• 19: Rusr~Y, F. Generating t-ary trees lexicographically. SIAM J. Comput. 7 (1978), 424-439.
• 20: RusI~Y, F., AND HU, T.C. Generating binary trees lexicographically. SIAM J. Comput. 6 (1977), 745-758.
• 21: SCOINS, H. Placing trees in lexicographic order. Mach. Intell. 3 (1969), 41-60.
• 22: W. Skarbek, Generating ordered trees, Theoretical Computer Science, v.57 n.1, p.153-159, April 1988 [doi>10.1016/0304-3975(88)90169-7 ]
• 23: Marvin Solomon , Raphael A. Finkel, A Note on Enumerating Binary Trees, Journal of the ACM (JACM), v.27 n.1, p.3-5, Jan. 1980 [doi>10.1145/322169.322171]
• 24: R. Sprugnoli, Counting labels in binary trees, BIT, v.30 n.1, p.62-69, 1990 [doi>10.1007/BF01932132]
• 25: TROJANOWSKI, A. Ranking and listing algorithms for k-ary trees. SlAM J. Comput. 7 (1978), 492-509.
• 26: ZAKS, S. Lexicographic generation of ordered trees. Theor. Comput. Sci. 10 (1980), 63-82.
• 27: ZAKS, S., AND RICHARDS, D. Generating trees and other combinatorial objects lexicographically. SIAM J. Cornput. 8 (1979), 73-81.
• 28: David Zerling, Generating binary trees using rotations, Journal of the ACM (JACM), v.32 n.3, p.694-701, July 1985 [doi>10.1145/3828.214141]

INDEX TERMS

Primary Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Trees

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Combinatorial algorithms

General Terms:
Algorithms, Performance, Theory

Keywords:
binary trees, generation of binary trees