
Re: Generation of random binary trees
Posted:
Feb 28, 2014 12:37 PM


On 20140227, MokKong Shen <mokkong.shen@tonline.de> wrote: > Am 27.02.2014 20:11, schrieb Herman Rubin:
>> Can you describe the probability model you want to use? This >> is necessary to answer your question.
> I simply want to be able to pick any of the total number of > different binary trees with n end nodes with equal probability. > As I wrote, the method I employed seems to be biased towards > favouring those trees that are comparatively flat (of lower > height).
> M. K. Shen
Do you want equally likely labelled trees or equally likely unlabelled ones? For the labelled trees, the method is fairly easy; there are 2^(n1)! labelled trees with n nodes, and going from n1 to n can be done by selecting a node at random and branching there. For unlabelled trees, the problem is much harder.
 This address is for information only. I do not claim that these views are those of the Statistics Department or of Purdue University. Herman Rubin, Department of Statistics, Purdue University hrubin@stat.purdue.edu Phone: (765)4946054 FAX: (765)4940558

