algorithm - 估计一棵树的大小

Question

我想估计我无法详尽访问每个节点的大型树结构中的叶子数。这个算法合适吗？它有名字吗？另外，如果我使用任何术语不当，请学究。

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)

Answer 1

如果您可以对您的树做出一些安全假设(例如:它是否平衡？)及其用法(是否有关于有多少叶子将成为同一节点的子节点的安全假设？)，这可能是可能的。更好的是，如果您每次添加/删除叶节点时都保持运行计数(计数器)。然后您只需在一个操作中访问您的计数器变量。