Binary Tree Algorithms: Generating Random Trees

[ytoruno]

Does anybody know where i can get info on generating random binary trees? I've been checking a lot of publications and have come across the yule process and uniform method. The trees they are being applied to, however, are speciation trees and most of the stuff is incomprehensible to me. Can anybody help and point me in some good direction?

 

[BarkingMad]

Isnt the problem of producing a random binary tree the same as producing random binary digits piped into a binary tree?

I mean, binary trees are available for most languages and in most introductory texts, so i guess your problem is one of generating sufficiently "random" numbers?

 

[davee123]

Isnt the problem of producing a random binary tree the same as producing random binary digits piped into a binary tree?

Not quite-- if you create your list of random numbers first, sort it, and then create a binary tree from that data, you are basically assured that your tree is more-or-less uniformly distributed. The size of the right branch is going to be nearly equal to the size of the left branch.

However, in the real world, you might not know your numbers beforehand. Hence, you either need to reconstruct your tree each time a new number comes in (big pain!), or you simply put the new number into the tree wherever it goes. The first option is more time consuming for inserts, but assures you that you'll get an evenly distributed tree (faster retrieval time). The second option is pretty fast for inserts, but might result in a really lopsided tree. For instance, if you got the numbers:

5, 46, 8, 44, 12, 37, 14, 33, 15, 26, 19, 24, 22, 23

You'd get a really deep tree that would be more time consuming to traverse, because it was built poorly. I assume there are plenty of algorithms to build trees more intelligently, or to "prune" trees quickly once they get this ugly (which is I think what's being discussed). Sadly, I'm too long out of college to remember which algorithms were out there for doing this sort of thing...

DaveE

 

[ytoruno]

thanks for the replies fellas. Well piping random numbers into a binary tree (assuming we have an insert function that inserts as if its a binary search tree) would indeed create a more or less balanced tree. To explain more fully I want to create a method like this:

start with a root, fill it randomly
roll a random int number from 1 to 2
if 1 create left child
else create a right child

and so forth- it would probably need an array somewhere in there for randomly picking nodes to expand, but that's the gist

while i can build an algorithm like this, I am merely looking for alternate methods for generating random trees, because i figure there has to be a better way. Creating random numbers and feeding them into an insert function would not solve this. Its more about randomizing topology of the tree than numbers. Also while I am on the subject, does anybody know a good way to print a binary tree to a console. I made one that becomes hard to read accurately if the tree is too unbalanced.
- yasser toruno

 

[davee123]

start with a root, fill it randomly
roll a random int number from 1 to 2
if 1 create left child
else create a right child

I dunno-- I think I'd opt for something like a recursive function-- pseudocode:

function set_child_nodes(parent_node,depth,max) {
  rand = random number 0 to max
  if(rand < depth) {
    #this node has no children
  } else if(rand < depth+(max-depth)/3)) {
    create left_child
    set_child_nodes(left_child,depth+1,max)
  } else if(rand < depth+2*(max-depth)/3) {
    create right_child
    set_child_nodes(right_child,depth+1,max)
  } else {
    create left_child
    set_child_nodes(left_child,depth+1,max)
    create right_child
    set_child_nodes(right_child,depth+1,max)
  }
}

Basically, this algorithm makes a random tree, with an increasingly large chance that no children will get created. Hence, your root node will never be empty, and its children will probably have 1 or more children, and so on down the line, getting progressively more likely that a node will have no children as you progress down the tree.

Of course, you could take out that probability completely, and make it just a random number (0 = no children, 1 = left child, 2 = right child, 3 = both children). You could also change it so that it picks a random number for each child-- that is 0 = no left child, 1 = left child, then pick another random number, 0 = no right child, 1 = right child.

Ultimately, I suppose the "totally random" method (rather than the probability one) would yield more truly random results-- it just has the potential to get REALLY large. I guess you could keep the "truly random" element and just cut it off regardless at a maximum depth, too-- but that depends on what you want.

Anyway, building in probability like that would likely have a similar effect to building up a tree based on a random series of numbers-- it's a little closer to what you might expect in "reality". But if you're looking for genuine randomness of the tree's topology, I'd probably skip it and go for the straight random approach.

DaveE

 

[shoehorn]

On a more practical level, trees are used extensively in financial modelling to price various types of derivative instruments. A good account of some of the practicalities involved in implementing trees for this purpose can be found in Joshi's C++ Design Patterns and Derivatives Pricing.

If you're interested in looking at some actual code in which tree algorithms are used you could do an awful lot worse than studying the QuantLib source, which is available at sourceforge.