平衡二叉树底层的节点数

Question

我想知道在研究二进制搜索树时出现的两个问题。它们如下：

有n个节点的平衡二叉树底层的最大节点数是多少？ 有n个节点的平衡二叉树底层的最小节点数是多少？

关于这一点，我在课本上找不到任何公式。有没有办法回答这些问题？请让我知道。

Answer 1

假设它是一个完整的二叉树，叶子中的节点数总是等于(n/2)+1。

对于最小节点数，节点总数可以是1 (满足它应该是一棵平衡树的条件)。

Answer 2

使用符号：

• H =平衡二叉树高
• L =高度为H的完整二叉树中的总叶数
• N =高度为H的完整二叉树中的节点总数

这个关系是L = (N + 1) / 2，如下所示。这将是给定树高H的最大叶节点数。给定高度的最小节点数为1 (不能为零，因为这样树的高度就会减少一个)。

随着树高的增加，人们可以看到：

H = 1, L = 1, N = 1
H = 2, L = 2, N = 3
H = 3, L = 4, N = 7
H = 4, L = 8, N = 15
...

树高(H)与树叶总数(L)和节点总数(N)之间的关系变得明显：

L = 2^(H-1)
N = (2^H) - 1

用数学归纳法很容易地证明了该方法的正确性。

上面的例子表明，对于小型H来说是正确的。简单地用H (例如，H=1)的值来计算L和N。假设公式对某些H是正确的，就可以证明它们对于HH=H+1也是正确的

对于L来说，假设L=2^(H-1)是真的。由于每个节点都有两个子节点，增加一个节点的高度将以两个新的叶子代替每个叶节点，从而有效地使叶片总数翻一番。因此，就HH=H+1而言，叶子总数(LL)将增加一倍：

LL = L * 2
   = 2^(H-1) * 2
   = 2^(H)
   = 2^(HH-1)

对于N来说，假设N=(2^H)-1是真的。增加高度1 (HH=H+1)，使节点总数增加，增加叶节点总数。因此，

NN = N + LL
   = (2^H) - 1 + 2^(HH-1)
   = 2^(HH-1) - 1 + 2^(HH-1)
   = 2 * 2^(HH-1) - 1
   = (2^HH) - 1

应用数学归纳法，证明了该方法的正确性。

H可以用N表示

N = (2^H) - 1        // +1 to both sides
N + 1 = 2^H          // apply log2 monotone function to both sides
log2(N+1) = log2(2^H)
          = H * log2(2)
          = H

L与N之间的直接关系(对所提问题的回答)是：

L = 2^(H - 1)                 // replace H = log2(N + 1)
  = 2^(log2(N + 1) - 1)
  = 2^(log2(N + 1) - log2(2))
  = 2^(log2( (N + 1) / 2 ))
  = (N + 1) / 2

对于大O分析，常量被丢弃，因此二进制搜索树查找时间复杂度(即H相对于输入大小N)是O(log2(N))。此外，请记住改变对数基数的公式：

log2(N) = log10(N) / log10(2)

而抛开常数因子1/log10(2)，这里的10可以有任意的对数基，不管选择的对数基是什么，时间复杂度都是O(log(N))。

Answer 3

我从我的教授那里得到了答案。

1)最后一层的最大节点数：⌈n/2⌉ 如果有一个有7个节点的平衡二叉树，那么答案是⌈7/2⌉=4，对于一个有15个节点的树，答案将是⌈15 /2⌉= 8。但麻烦的是，只有当平衡树的最后一层是从左到右完全填充的⌈时，这个公式才能给出正确的答案。例如，一个有5个节点的平衡二叉树，上面的公式给出了一个3的答案，这是不正确的，因为一棵有5个节点的树在最后一级可以包含4个节点的最大节点。，所以我猜他指的是完全平衡的二叉树. 2)最后一层的最小节点数：1