How would one go about choosing a random element from a tree? Is it necessary to know the depth/size of the tree beforehand?
A:
Just do for each node a random call in the range 0 up to (number of childs)-1 and select the next child after that number.
Repeat this until you are in a leaf.
Quonux
2010-07-17 17:15:06
+2
A:
It is not. To choose a node uniformly at random, simply iterate through the tree in any order you like. Let the nth node examined be the chosen one with probability 1/n. That is, keep a record of the node you would return in a variable, and when you look at the nth node, replace the current node with the nth one with probability 1/n. You can show by induction that this returns a node uniformly at random without needing to know how many there are beforehand.
Jeffrey
2010-07-17 17:16:08
This a nice use of the idea in http://stackoverflow.com/questions/1133942.
momeara
2010-07-17 18:33:37
To put a name on it: This is a well-known algorithm, known as [Reservoir sampling](http://en.wikipedia.org/wiki/Reservoir_sampling).
Joey
2010-07-17 22:53:24
A:
If you've structured your leaves to be stored themselves within an index-able data type, like an array, then you can easily (pseudocode):
random_leaf = leaf_pile[ random( size of leaf pile ) ]
That's a nice, refreshing O(1) :-)
Of course, there may be holes, so you may have to iterate from there. If it's stored as a linked list, then you can iterate though.
Just providing an alternative to the obvious. It really depends on your data structure and your commonest-use-case.
eruciform
2010-07-17 17:56:39