Estimating the size of a tree

Posted by Full Decent on Stack Overflow See other posts from Stack Overflow or by Full Decent
Published on 2010-05-07T14:48:05Z Indexed on 2010/05/07 15:08 UTC
Read the original article Hit count: 140

Filed under:
|
|

I'd like to estimate the number of leaves in a large tree structure for which I can't visit every node exhaustively. Is this algorithm appropriate? Does it have a name? Also, please pedant if I am using any terms improperly.

sum_trials = 0
num_trials = 0
WHILE time_is_not_up
    bits = 0
    ptr = tree.root
    WHILE count(ptr.children) > 0
         bits += log2(count(ptr.children))
         ptr = ptr.children[rand()%count(ptr.children)]
    sum_trials += bits
    num_trials++
estimated_tree_size = 2^(sum_trials/num_trials)

© Stack Overflow or respective owner

Related posts about graph

Related posts about tree