5
$\begingroup$

Could someone please provide a reference giving an algorithm to generate uniformly random binary trees?

$\endgroup$
  • 2
    $\begingroup$ If you are familiar with generating functions, have a look at Boltzmann sampling. It is a very powerful method of sampling discrete objects, such as binary trees. $\endgroup$ – Juho May 7 '13 at 19:41
  • $\begingroup$ What exactly are you looking for? Trees are different if their "structure" is different? Trees are labelelled trees? You want tress restricted to a specific number of nodes $n$? If not restricted to a specific number of nodes, what exactly do you mean by uniformly random? $\endgroup$ – Aryabhata May 7 '13 at 23:56
  • $\begingroup$ You could aslo start with any binary tree and the perform randomly rotations. However the mixing time (or to be more precise the best bounds that are known) for this process is bad. (I cant recall the papers, but if you want to go in this direction I can look it up for you.) $\endgroup$ – A.Schulz May 8 '13 at 7:57
  • $\begingroup$ I mean, if I have the ensemble of all trees satisfying a certain condition (here binary and having n terminal nodes), I could pick one of them randomly. (I am not sure whether it is practically meaningful to consider all trees with node numbers unlimited, i.e. up to infinity.) $\endgroup$ – Mok-Kong Shen May 8 '13 at 9:01
2
$\begingroup$

There is a article available here and survey available here

But desipte that its very easy to generate such tree, it all depends on random generator, it must be uniform.

There are two simple approaches:

  • Generate full tree up to some height and randomly cut edges
  • Start from root and make decision about each child on lower level

Both of them are guarantee to end, fist one is obvious, second one needs some induction proof which is quite simple to do.

Taking into account Juho's hint take a look at Boltzmann sampling, it is indeed a powerfull tool which you can use. And here's a working example.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Would it be feasible to additionally require that there be n terminal nodes? $\endgroup$ – Mok-Kong Shen May 7 '13 at 20:09
  • $\begingroup$ Its not a must because according to laws of probability tree will terminate sooner or later (unless vertice probability is 1), it just might be very deep. But you might add restriction on number of nodes. $\endgroup$ – Bartosz Przybylski May 7 '13 at 21:22
  • $\begingroup$ The survey seems to have bit-rotted a little (or at least my viewer did not like the .ps inside the tarball). There is an alternative version at sis.uta.fi/cs/reports/pdf/A-1998-3.pdf $\endgroup$ – Andrew Mar 2 '17 at 11:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.