algorithm - 平衡二叉树底层的节点数

Question

我想知道在研究二叉搜索树时出现的两个问题。它们是:

What is the maximum number of nodes in the bottom level of a balanced binary search tree with n nodes?

What is the minimum number of nodes in the bottom level of a balanced binary search tree with n nodes?

我在教科书中找不到任何与此相关的公式。有什么办法可以回答这些问题吗？请告诉我。

Answer 1

使用符号:

• 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 为真。将高度增加一 (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

对于 Big O 分析，常量被丢弃，因此二叉搜索树查找时间复杂度(即 H 相对于输入大小 N)为 O(log2(N))。另外，请记住更改对数底数的公式:

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

并丢弃常数因子 1/log10(2)，其中 10 可以具有任意对数底，时间复杂度仅为 O (log(N)) 无论选择的对数底常数如何。