Generating binary trees at random. (English) Zbl 0742.68012
Summary: We give a new constructive proof of the K. L. Chung and W. Feller [Fluctuations in coin-tossing, Proc. Nat. Acad. Sci. USA 35, 605- 608 (1949)] theorem. Our proof provides a new and simple linear-time algorithm for generting random binary trees on \(n\) nodes; the algorithm uses integers no larger than \(2n\).
References:
| [1] | Arnold, D. B.; Sleep, M. R., Uniform random number generation of \(n\) balanced parenthesis strings, ACM Trans. Programming Languages Systems, 2, 122-128 (1980) |
| [2] | Chung, K. L.; Feller, W., Fluctuations in coin-tossing, Proc. Nat. Acad. Sci. U.S.A., 35, 605-608 (1949) · Zbl 0037.36310 |
| [3] | Feller, W., (An Introduction to Probability Theory and its Applications, Vol. 1 (1968), Wiley: Wiley New York) · Zbl 0155.23101 |
| [4] | Knott, G. D., A numbering system for binary trees, Comm. ACM, 20, 113-115 (1977) · Zbl 0345.68025 |
| [5] | Knuth, D. E., (Semi-numerical Algorithms, The Art of Computer Programming, Vol. 2 (1981), Addison-Wesley: Addison-Wesley Reading, MA) · Zbl 0477.65002 |
| [6] | Martin, H. W.; Orr, B. J., A random binary tree generator, (Computing Trends in the 1990’s, ACM Seventeenth Computer Science Conf. (1989), ACM: ACM New York), 33-38, Louisville, KY |
| [7] | Reingold, E. M.; Nievergelt, J.; Deo, N., Combinatorial Algorithms: Theory and Practice (1977), Prentice Hall: Prentice Hall Englewood Cliffs, NJ · Zbl 0367.68032 |
| [8] | Solomon, M.; Finkel, R. A., A note on enumerating binary trees, J. ACM, 27, 3-5 (1980) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
