估计一棵树的大小

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

如果您可以对树进行一些安全的假设（例如：它是否平衡？）及其用法（是否有关于同一节点的子节点有多少叶子的安全假设？），这可能是可能的。如果每次添加/删除叶节点时都维护一个运行计数（计数器），那就更好了。然后您只需在一次操作中访问计数器变量即可。