Random Tree Generator
Laurent OGET
In article <199806111929...@ladder01.news.aol.com>,
jd...@aol.com (JDPeh) writes:
>
>>
>>I am seeking a program for generating random binary trees and
>>please give me a pointer if you know where I can download one.
>>
>>
>>Thanks
>>
>
> For trees with N total nodes (leafs + interior nodes) you can
> make one at random as follows:
>
> Start at the root with N, subtract 1; then randomly split
> the remaining N-1, to make the two random subtrees
> with appropriate sizes.
>
> In pseudo-code, genRandomTree returns a pointer
> to a tree with N total nodes:
>
> tree* genRandomTree( int N )
> {
> if ( N > 0 )
> {
> int left = random( N ); // random returns a number from 0..N-1;
> return(
> new tree(
> genRandomTree( left ),
> genRandomTree( N-1 - left )));
> }
> else
> return NULL;
> }
>
> ( I hope this is not homework :)
>
> -jdp
apply that algorithm with 3 nodes
0 0
/ /
0 has probability 1/8 0 has probability 1/8
/ \
0 0
0
/ \ has probability 1/4
0 0
and the symmetrics of the first two have probability 1/8.
i thought one of the requirements for a random generator was 'you cannot predict the output'...
just my .02
laurent
PS:it does not tell you how you choose the number of nodes either..but i guess you can be interested in an algorithm that generates random trees with a fixed number of nodes.
PPS:the answer to the problem i point is to choose the number not with an uniform number generator but with a generator that gives to each number k the probability
Cat(k)(Cat(n-k)
---------------
Cat(n)
where Cat(k) is the catalan number
Louxin Zhang
I am seeking a program for generating random binary trees and
please give me a pointer if you know where I can download one.
Thanks
Louxin
JDPeh
>
>I am seeking a program for generating random binary trees and
>please give me a pointer if you know where I can download one.
>
>
>Thanks
>
For trees with N total nodes (leafs + interior nodes) you can
Laurent OGET
[Posted and mailed]
In article <EuDM1...@undergrad.math.uwaterloo.ca>,
lzh...@wh.math.uwaterloo.ca (Louxin Zhang) writes:
>
> I am seeking a program for generating random binary trees and
> please give me a pointer if you know where I can download one.
>
>
> Thanks
>
>
>
>
> Louxin
>
random would mean you have a nice notion of what measure theory on a tree domain would be..i'd be interested in that..
laurent
--
Laurent Oget- http://liafa.jussieu.fr/~oget/
LIAFA-01 44 27 61 33
17 rue Civiale 75010- 01 42 40 08 86
Niall Graham
>
> Start at the root with N, subtract 1; then randomly split
> the remaining N-1, to make the two random subtrees
> with appropriate sizes.
>
> In pseudo-code, genRandomTree returns a pointer
> to a tree with N total nodes:
>
> tree* genRandomTree( int N )
> {
> if ( N > 0 )
> {
> int left = random( N ); // random returns a number from 0..N-1;
> return(
> new tree(
> genRandomTree( left ),
> genRandomTree( N-1 - left )));
> }
> else
> return NULL;
> }
>
> ( I hope this is not homework :)
>
> -jdp
apply that algorithm with 3 nodes
0 0
/ /
0 has probability 1/8 0 has probability 1/8
/ \
0 0
0
/ \ has probability 1/4
0 0
and the symmetrics of the first two have probability 1/8.
Your observation is qualitatively correct, and reveals the crux
of the problem. The probabilities are
1/6,1/6, 1/3, 1/6,1/6.
This becomes clear if we consider the following process.
Start with a random permutation of {1,2,...,n}.
Select the min value as the root and cut the permutation
at that position putting the left sub-permutation in the left subtree
and the right fragment in the right subtree proceed recursively etc.
This process is equivalent to the one describe above.
We are in effect selecting from a sample space of size n! (3! = 6)
even though the number of distinct trees is cat(n) (cat(3)=5).
Thus, some permutations generate the same tree ( T(213) = T(312) ).
Depending on what it is that the original poster is modeling,
it may turn out that this weighted process is actually what
is warranted. For instance it models the generation of random
binary search trees.
Niall Graham
Kris De Waele
Remy's recursive algorithm :
This algorithm generates all binary trees with labeled
leaves of size 2n+1 with probability n!/(2n)!
Given a binary tree T of size 2n-1 (n-1 internal nodes and n leaves
arbitrarily numbered 1,2,...n) the algorithm constructs a
binary tree of size 2n+1
(i)choose a node v of T with probability 1/(2n-1)
(ii)choose a direction "right" or "left" with probability 1/2
(iii)replace the node v with a new node w so that
if direction==left
w.rightchild =v
w.leftchild=new leaf with number n+1
if direction==right
w.leftchild=v
w.rightchild=new leaf with number n+1
(I hope you understand my pseudo-code)
If you start out with a tree with 1 leaf labelled 1 then
you will become a tree of size 2n-1 after n steps.
Ignore the labels and you have a non-labeled binary tree
More information and a C source code for Remy's algorithm
can be found in :
Random generation of trees
Laurent Alonso and Rene Schott
Kluwer Academic Publishers 1995
Another method for generating binary trees is using the
bijection between binary trees with n internal nodes
and the Dyck words of length 2n. This takes O(n) time.
A Dyck word is a word made out of x's and y's (or parentheses)
w is a Dyck word iff w is the empty word or w=xuyv with u and v Dyck
words.
e.g. xxxyyy xyxyxy xxyyxy
I'll sketch the algorithm (I forgot the details, but I'll look them up
on request):
(i)generate a permutation of 1,...,2n+1
(ii)convert the permutation into a word with n+1 x's and n y's
(iii)cycle this word into a 1-dominated word
(iv)remove the first x and you have a Dyck word
(v) a Dyck word is of the form w=xuyv
this codes a binary three with a root and two subtrees : u is the Dyck
word
that codes the left sub-tree and v codes the right sub-tree
Kris De Waele