Abstract
Trees, and particularly binary trees, appear frequently in the classification literature. When studying the properties of the procedures that fit trees to sets of data, direct analysis can be too difficult, and Monte Carlo simulations may be necessary, requiring the implementation of algorithms for the generation of certain families of trees at random. In the present paper we use the properties of Prufer's enumeration of the set of completely labeled trees to obtain algorithms for the generation of completely labeled, as well as terminally labeled t-ary (and in particular binary) trees at random, i.e., with uniform distribution. Actually, these algorithms are general in that they can be used to generate random trees from any family that can be characterized in terms of the node degrees. The algorithms presented here are as fast as (in the case of terminally labeled trees) or faster than (in the case of completely labeled trees) any other existing procedure, and the memory requirements are minimal. Another advantage over existing algorithms is that there is no need to store pre-calculated tables.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
CAYLEY, A. (1889), “A Theorem on Trees,”Quarterly Journal of Pure and Applied Mathematics, 23, 376–378.
DE SOETE, G., DESARBO, W. S., FURNAS, G. W., and CARROLL, J. D. (1984), “The Estimation Of Ultrametric And Path Length Trees From Rectangular Proximity Data,”Psychometrika 49, no.3, 289–310.
EVEN, S. (1979),Graph Algorithms, Rockville, MD: Computer Science Press.
FOWLKES, E. B., MALLOWS, C. L., and MCRAE, J. E. (1983), “Some Methods for Studying The Shape of Hierarchical Trees,” Murray Hill, NJ: AT&T Bell Laboratories Technical Memorandum 83-11214-6.
FURNAS, G. W. (1984), “The Generation of Random, Binary Unordered Trees,”Journal of Classification 1, 187–233.
GNANADESIKAN, R., KETTENRING, J. R., and LANDWEHR, J. M. (1977), “Interpreting and Assessing The Results of Cluster Analyses,”Bulletin of the International Statistical Institute, 47, 451–463.
KNUTH, D. E. (1981),The Art of Computer Programming, Second edition, Reading, MA: Addison-Wesley.
MEIR, A., and MOON, J. W. (1970), “The Distance Between Points in Random Trees,”Journal of Combinatorial Theory, 8, 99–103.
MOON, J. W. (1967), “Various Proofs of Cayley's Formula for Counting Trees,” inA Seminar on Graph Theory, ed. F. Harary, New York: Holt, 70–78.
MOON, J. W. (1970), “Counting Labeled Trees,”Canadian Mathematical Monographs, No. 1.
NIJENHUIS, A., and WILF, H. F. (1975),Combinatorial Algorithms, New York: Academic Press.
ODEN, N. L., and SHAO, K-T. (1984), “An Algorithm to Equiprobably Generate all Directed Trees with K Labeled Terminal Nodes and Unlabeled Interior Nodes,”Bulletin of Mathematical Biology, 46(3, 379–387.
PRUFER, H. (1918), “Neuer Beweis eines Satzes uber Permatationen,”Archives of Mathematical Physics, 27, 142–144.
RENYI, A. (1959), “Some Remarks on The Theory of Random Trees,”Publications of the Mathematical Institute of the Hungarian Academy of Sciences, 4, 73–85.
ROBINSON, R. W., and SCHWENK, A. J. (1975), “The Distribution of Degrees in a Large Random Tree,”Discrete Math, 12, 359–372.
RUSKEY, F. (1978), “Generating t-ary Trees Lexicographically,”SIAM Journal on Computing, 7, 424–439.
TROJANOWSKI, A. E. (1978), “Ranking and Listing Algorithm for k-ary Trees,”SIAM Journal on Computing, 7, 492–509.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Quiroz, A.J. Fast random generation of binary, t-ary and other types of trees. Journal of Classification 6, 223–231 (1989). https://doi.org/10.1007/BF01908600
Issue Date:
DOI: https://doi.org/10.1007/BF01908600