平衡二叉树底层的节点数

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

二叉树中第 L 层节点的最大数量 为 2^L（如果您假设顶点为第 0 层）。这很容易看出，因为在每个级别上，您都会从之前的每个叶子生成 2 children。它是 balanced/search 树这一事实是无关紧要的。所以你必须找到最大的 L 使得 2^L < n 并从 n 中减去它。在数学语言中是：

节点的最小数量 取决于您平衡树的方式。可以有 height-balanced 棵树，weight-balanced 棵树，我假设其他平衡树。即使是高度平衡的树，您也可以定义平衡树的含义。因为从技术上讲，具有 2^N 个节点且高度为 N + 2 的树仍然是一棵平衡树。

Answer 2

假设它是一棵满二叉树，叶子中的节点数将始终等于(n/2)+1。

对于最少的节点数，总节点数可以是1（满足应该是平衡树的条件）

Answer 3

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

1) Maximum number of nodes at the last level: ⌈n/2⌉

If there is a balanced binary search tree with 7 nodes, then the answer would be ⌈7/2⌉ = 4 and for a tree with 15 nodes, the answer would be ⌈15/2⌉ = 8. But what is troubling is the fact that this formula gives the right answer only when the last level of a balanced tree is completely filled from left to right. For example, a balanced binary search tree with 5 nodes, the above formula gives an answer of 3 which is not true because a tree with 5 nodes can contain a maximum nodes of 4 nodes at the last level. So I am guessing he meant full balanced binary search tree.

2) Minimum number of nodes at the last level: 1

Answer 4

使用符号：

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))。

平衡二叉树底层的节点数

Number of nodes in the bottom level of a balanced binary tree

algorithm

nodes

binary-search-tree

data-structures