Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
NCTM or The Math Forum.


Math Forum
»
Discussions
»
sci.math.*
»
sci.stat.math
Notice: We are no longer accepting new posts, but the forums will continue to be readable.
Topic:
Generation of random binary trees
Replies:
10
Last Post:
Mar 20, 2014 10:30 AM




Generation of random binary trees
Posted:
Feb 26, 2014 3:34 PM


Given n, I want to randomly generate a binary tree (unlabelled) that has n end nodes. Could someone kindly provide a reference containing an algorithm for doing that?
I attempted to do as follows: From a PRNG obtain n PRNs in [O.0, 1.0) as (relative) frequencies of n symbols for generating a Huffman tree (commonly known in the field of data compression). But, if the PRNs used are uniform, then I think this would highly favour generation of those Huffman trees that are more flat and Huffman trees corresponding to widely different frequencies of the symbolss would be highly suppressed in the generation process. If this is correct, how could one do better? Thanks in advance.
M. K. Shen



