18

我有一个深度为 L 级的树数据结构，每个节点大约有N 个节点。我想计算出树中节点的总数。要做到这一点（我认为），我需要知道将有孩子的节点的百分比。

N 中叶节点与非叶节点的比例的正确术语是什么？

计算三个节点总数的公式是什么？

更新有人在其中一个答案中提到了分支因素，但随后消失了。我想这是我一直在寻找的术语。那么公式不应该考虑分支因素吗？

更新我应该对假设的数据结构进行估计，而不是确切的数字！

4

6 回答 6

29

好的，每个节点都有大约 N 个子节点，树的深度为 L 级。

With 1 level, the tree has 1 node.
With 2 levels, the tree has 1 + N nodes.
With 3 levels, the tree has 1 + N + N^2 nodes.
With L levels, the tree has 1 + N + N^2 + ... + N^(L-1) nodes.

节点总数为 (N^L-1) / (N-1)。

好的，只是一个小例子，为什么它是指数的：

                    [NODE]
                      |
                     /|\
                    / | \
                   /  |  \
                  /   |   \
            [NODE]  [NODE] [NODE]
              |
             /|\
            / | \
于 2009-02-05T10:17:31.220 回答
14

只是为了纠正第一个答案中的错字：深度为 L 的树的节点总数为 (N^(L+1)-1) / (N-1)...（即幂 L +1 而不仅仅是 L）。

这可以如下所示。首先，我们的定理：

1 + N^1 + N^2 + ... + N^L = (N^(L+1)-1)/(N-1)

两边乘以 (N-1)：

(N-1)(1 + N^1 + N^2 + ... + N^L) = N^(L+1)-1。

展开左侧：

N^1 + N^2 + N^3 + ... + N^(L+1) - 1 - N^1 - N^2 - ... - N^L。

所有项 N^1 到 N^L 都被取消，剩下 N^(L+1) - 1。这是我们的右手边，所以初始等式是正确的。

于 2009-05-01T01:44:05.137 回答
1

深度L的节点数计算公式为：（假设有N个根节点）

NL _

要计算所有节点的数量，需要对每一层执行此操作：

for depth in (1..L)
    nodeCount += N ** depth

如果只有 1 个根节点，则从 L 中减去 1 并将总节点数加 1。

请注意，如果在一个节点中的叶子数量与平均情况不同，这可能会对您的数量产生很大影响。树的位置越高，影响越大。

     * * * N ** 1
    *** *** *** N ** 2
*** *** *** *** *** *** *** *** *** N ** 3

这是社区 wiki，所以请随意更改我令人震惊的代数。

于 2009-02-05T10:00:29.210 回答
1

如果您的树大约是完整的，即除了最后两个之外，每个级别都有其完整的子节点，那么您的叶子节点介于 N^(L-2) 和 N^(L-1) 之间，并且介于 N^(L -1) 和 N^L 个节点总数。

如果你的树没有满，那么知道叶节点的数量并没有帮助，因为一棵完全不平衡的树将有一个叶节点，但有任意多个父节点。

我想知道你的陈述“每个节点大约有 N 个节点”有多精确——如果你知道平均分支因子，也许你可以计算出树的预期大小。

如果您能够找到叶子与内部节点的比率，并且您知道平均子节点数，则可以将其近似为 (n*ratio)^N = n。这不会给你答案，但我想知道数学比我更好的人是否能想出一种方法将 L 插入这个方程并给你一些可解的东西。

尽管如此，如果您想准确地知道，您必须遍历树的结构并随时计算节点。

于 2009-02-05T10:20:27.593 回答
1

Knuth 的估计器 [1],[2] 是一个点估计，它以任意有限树中的节点数为目标，无需遍历所有节点，即使树不平衡。Knuth 的估计器是无偏估计器的一个例子；Knuth 估计器的期望值将是树中的节点数。话虽如此，如果所讨论的树不平衡，Knuth 的估计量可能会有很大的差异，但在你的情况下，由于每个节点都会有大约 N 个子节点，我认为 Knuth 的估计量的方差应该不会太大。当人们试图测量执行蛮力搜索所需的时间时，这个估计器特别有用。

对于以下函数，我们将假设所有树都表示为列表的列表。例如，[]表示具有单个节点的树，[[],[[],[]]]将表示具有 5 个节点和 3 个叶子的树（树中的节点与左括号一一对应）。以下函数是用 GAP 语言编写的。

该函数simpleestimate给出了树中节点数的估计值tree。背后的想法simpleestimate是我们随机选择从树的根 x_0 到叶子 x_n 的路径 x_0,x_1,...,x_n。假设 x_i 有 a_i 个后继者。然后simpleestimate将返回 1+a_1+a_1*a_2+...+a_1*a_2*...*a_n。

point:=tree; prod:=1; count:=1; list:=[]; 
while Length(point)>0 do prod:=prod*Length(point); count:=count+prod; point:=Random(point); od;
return count; end;

该函数estimate将简单地给出通过simpleestimate(tree) samplesize多次应用该函数给出的估计值的算术平均值。

estimate:=function(samplesize,tree) local count,i; 
count:=0; 
for i in [1..samplesize] do count:=count+simpleestimate(tree); od; 
return Float(count/samplesize); end;

示例： simpleestimate([[[],[[],[]]],[[[],[]],[]]]);在返回15时 estimate(10000,[[[],[[],[]]],[[[],[]],[]]]);返回10.9608（树实际上确实有 11 个节点）。

  1. 估计搜索树大小。 http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.129.5569&rep=rep1&type=pdf

  2. 估计回溯程序的效率。Donald E. Knuth http://www.ams.org/journals/mcom/1975-29-129/S0025-5718-1975-0373371-6/S0025-5718-1975-0373371-6.pdf

于 2019-04-14T04:08:05.510 回答
0

如果您只知道树的深度，那么您计算总大小的唯一选择就是遍历并计算它们。

于 2009-02-05T09:59:56.857 回答