A random binary tree generator

ABSTRACT

Let B(N) denote the set of all binary trees that have N nodes. A procedure for randomly generating the trees in B(N) such that each tree is equally likely to occur, that is an unbiased random generator, is given which runs in O(N) time, requires very little storage, and uses a system of arithmetic no larger than is required to represent the number U itself. Previous unbiased random binary tree generators, based on inverse rank functions, ran in O(N log N) time and required multiple precision arithmetic capable of handling numbers of the order of magnitude of the cardinality of B(N).

REFERENCES

• 1: Beyer, Terry and Hedetniemi, Sandra Mitchell, Constant time generation of rooted trees, SlAM Journal on Computing, 9 (1980), 706-712.
• 2: Er, M. C., A note on generating well-formed parenthesis strings lexicographically, The Computer Journal, 26 (1983), 205-207.
• 3: 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]
• 4: Donald E. Knuth, The art of computer programming, volume 1 (3rd ed.): fundamental algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1997
• 5: Martin, H. W., Linear time recognition and transformation algorithms for binary tree representations, in preparation.
• 6: Martin, H. W., Kiltinen, J. O. and McNeill, R. B., The representation and enumeration of ordered K-ary trees, submitted for publication.
• 7: Pallo, J. M., Enumerating, ranking and unranking binary trees, The Computer Journal, 29 (1986), 171-175.
• 8: 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]
• 9: 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]
• 10: Ruskey, F. and Hu, T. C., Generating binary trees lexicographically, SlAM Journal on Computing, 6 (1978), 745-758.
• 11: Harry F. Smith, Data structures: form and function, Harcourt Brace & Co., Orlando, FL, 1987
• 12: 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]
• 13: Trojanowski, Anthony E., Ranking and listing algorithms for k-ary trees, SlAM Journal on Computing, 7 (1978), 492-509.
• 14: Zaks, S., Lexicographic generation of ordered trees, Theoretical Computer Science, i0 (1980), 63-82.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

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.2 Graph Theory
          Subjects: Trees

General Terms:
Algorithms, Theory