2

我正在研究 Robert Sedgewick 的 C++ 算法，并遇到了以下声明：

具有内部节点的二叉树的高度N至少lg N 为 ，最多为N-1。最好的情况发生在平衡树中，2^i 除了可能的底层之外，每一层都有内部节点。如果高度是“h”那么我们必须有

         2^(h-1) < N+1 <= 2^h

因为有 N+1 个外部节点。

围绕不等式没有太多解释，所以我的问题是：作者是如何推断不等式的，它究竟显示了什么？

谢谢！

4

2 回答 2

2

不等式2^(h-1) < N + 1 <= 2^h表明，对于给定的 height h，存在一系列节点数量，它们将具有h共同的最小高度。这表明了一个属性：所有包含N个节点的二叉树的高度至少为 log( N )，四舍五入到下一个整数。

例如，具有任一4, 5, 6 or 7节点的树的最小高度最多为3. 比这个范围少一个，你就可以有一棵高度的树2；还有一个，你能做的最好的就是高度4。如果我们使用N的以 2 为底的对数绘制出从3节点到节点增长的树的最小高度并向上取整，则不等式变得清晰：8

log(3) = 1.58 -> 2  [lower bound]

log(4) = 2    -> 3  [2^(h-1)]
log(5) = 2.32 -> 3
log(6) = 2.58 -> 3
log(7) = 2.81 -> 3

log(8) = 3    -> 4  [2^h | upper bound]

注意到范围（由N+1不同的数量组成）与给定树的外部节点数直接相关可能很有用。取一棵具有3节点且高度为的树2：

     *
    / \
   *   *

向这棵树添加一个节点，

    *          *          *          *
   / \        / \        / \        / \
  *   *  or  *   *  or  *   *  or  *   *
 /            \            /            \
*              *          *              *

不管你把它放在哪里，高度都会增加1。然后我们可以在不改变高度的情况下继续创建叶节点，直到树总共包含7个节点，此时，任何进一步的添加都将再次增加最小可能高度：

    *
   / \
  *   *
 / \ / \
*  * *  *

最初，N等于3节点，这意味着N+1 = 4我们看到存在4具有共同最小高度的数量。

如果您需要更多信息，我建议您查看完整和平衡二叉树的属性。

于 2012-09-21T19:25:33.660 回答
0

N让我们称在二叉树中适合节点所需的最小高度minheight(N)。

为给定数量的节点导出树高度下限的一种方法N是从另一个方向工作：给定高度树h，可以打包到其中的最大节点数是多少？

我们称这个函数为 height maxnodes(h)。显然，给定高度的二叉树上的节点数在树满时最大化，即当每个内部节点有 2 个子节点时。感应很快就会显示出来maxnodes(h) = 2^h - 1。

因此，如果我们有节点N，每个节点h都是maxnodes(h) >= N的上限：也就是说，您可以将所有节点都放在该高度的树上。在所有这些上限中，最好的（最严格的）一个将是最小值。所以我们想要找到的是最小的，使得minheight(N)Nh

N <= maxnodes(h) = 2^h - 1

那么如何找到这个最小的令人满意的值h呢？

的重要属性maxnodes(h)是它是非递减h的（实际上它是严格递增的，但非递减就足够了）。这意味着您永远无法通过降低其高度来将更多节点放入完整的二叉树中。h（很明显，但有时它有助于将事情拼写出来！）这使得重新排列上述等式以找到容易的最小值：

2^h - 1 >= N
2^h >= N+1        # This is the RHS of your inequality, just flipped around
h >= log2(N+1)    # This step is only allowed because log(x) is nondecreasing

hh必须是整数，所以满足的最小值h >= log2(N+1)是RoundUp(log2(N+1))。

我发现这是描述下限的最有用的方法，但它可用于导出您所询问的不等式的 LHS。从上一个块中的第二个等式开始：

2^h >= N+1

h满足这个不等式的一组值从正无穷开始h = log2(N+1)并延伸到正无穷大。由于h = log2(N+1)是这个集合中的最小满足值，任何更低的都不能满足不等式，所以特别是h-1不会满足它。如果>=不等式在两个实数（非无限）之间不成立，则相应的<不等式必须成立，因此：

2^(h-1) < N+1
于 2012-09-22T07:24:56.413 回答