The generation of random, binary unordered trees (Q1068492)

This article is devoted to random generation of binary trees. All the considered trees are fully binary with unordered edges. There are introduced five general strategies for generating uniform random combinatorial objects. Three of these strategies are adopted for the generation of binary trees. According to labeling are investigated unlabelled, terminally labelled and completely labelled trees. As unrooted and rooted trees are distinguished, six types of trees are generated. All the algorithms are presented in exact form with the analysis of the computational complexity. Each method of random generation is introduced with a formal proof. The presented results can be used in Monte Carlo simulations where random binary trees are needed.