二叉树

E

• 概念定义

  • 满二叉树：除叶子节点外的所有节点都有两个子节点的树（严格二叉树/2-树）。
  • 完全二叉树：除最后一层外，每一层完全填满且节点尽可能靠左排列的二叉树。

• 选项分析
  A) 错误。示例：

      12
     /
    20
   /
  30
  

  此树既不是完全二叉树（最后一层未填满且未靠左），也不是满二叉树（存在单子节点）。

  B) 错误。示例：

      12
     / \
   20  30
   /
  30
  

  此树是完全二叉树（满足完全性），但非满二叉树（根节点右子树缺失）。

  C) 错误。示例：

      12
     / \
   20  30
      / \
    20  40
  

  此树是满二叉树（所有非叶节点有两个子节点），但非完全二叉树（最后一层未靠左填满）。

  D) 错误。示例：

      12
     / \
   20  30
   / \
  10 40
  

  此树同时满足完全二叉树（结构完整且靠左）和满二叉树（所有非叶节点有两个子节点）。

• 结论
  所有选项均存在反例，因此正确答案为 E。

解释：

• 先序（前缀）表示法和后序（后缀）表示法均能通过操作符/操作数的排列顺序隐含运算优先级，无需依赖括号。
• 中缀表示法因需区分运算符优先级和结合性，通常需要括号辅助解析。
• 题干中标准答案标注为 A（a、b 和 c），但严格来说中缀表示法不符合“无需括号”的条件。此答案可能存在矛盾，建议结合具体上下文判断。

对于每个节点恰好有 k 个子节点或没有子节点的 k 叉树，以下关系成立：
叶子节点数量公式
$$ L = (k-1) \times n + 1 $$

其中 $ L $ 表示叶子节点数量，$ n $ 表示内部节点数量。

示例说明
观察下图结构：

        o
      / | \
     o  o  o
   / | \       / | \
  o  o  o     o  o  o
              / | \
             o  o  o

• 参数取值：$ k = 3 $, 内部节点数 $ n = 4 $
• 计算过程： $$ L = (3-1) \times 4 + 1 = 8 + 1 = 9 $$
• 验证结果：图中共有 9 个叶子节点（最底层的 6 个 + 中间层的 3 个）

解析：

• 当节点无标签时，二叉树的形态仅由结构决定
• 可通过卡特兰数（Catalan numbers）计算二叉树数量
• 计算公式如下：

$$ \frac{\binom{2n}{n}}{n+1} = \frac{\binom{6}{3}}{4} = 5 $$

• 因此当 $ n = 3 $ 时，共有 5 种不同形态 的二叉树
• 若节点有标签，则每种结构对应 $ 3! = 6 $ 种排列，总数为 $ 5 \times 6 = 30 $ 棵
• 所以选项 (B) 正确

在节点数为 n 的树中，部分节点有 0 或 3 个子节点：定义如下变量：

• n：总节点数
• L：叶节点数
• I：内部节点数

关键关系是：每个具有 3 个子节点的内部节点会生成 2 个内部节点和 1 个叶节点。根节点不参与此计算，因此可得公式 $ L = 2I + 1 $。同时，总节点数满足 $ n = L + I $。

将第一个公式代入第二个公式：

$$ n = (2I + 1) + I \quad \Rightarrow \quad n = 3I + 1 $$

解得 $ I = \frac{n-1}{3} $。

将其代回 $ L = 2I + 1 $：

$$ L = 2\left(\frac{n-1}{3}\right) + 1 \quad \Rightarrow \quad L = \frac{2n+1}{3} $$

因此，此类树的叶节点数为 $ \frac{2n+1}{3} $。

权重平衡树是一种二叉树，其中每个节点的左子树中的节点数至少是右子树的一半，并且最多是右子树的两倍。为了确定这种树在 $ n $ 个节点下的最大可能高度，我们分析选项：

• a) 表示完全平衡二叉树的高度。在权重平衡树中，左子树最多可以是右子树的两倍，因此它不一定是完全平衡的。此选项未考虑约束条件。
• b) 对数底数 $\log_{4/3} n$ 是非标准选择。该值不符合二叉树高度分析的典型模式。
• c) 表示完全平衡三叉树的高度。与二叉树的权重平衡约束无关，无法反映实际结构特性。
• d) 底数 $\log_{3/2} n$ 反映了左子树与右子树的节点数比例关系。由于左子树规模在右子树的 $[1/2, 2]$ 倍范围内，该对数形式能准确描述树的最大高度增长趋势。

对于每个节点有 n 个子节点或无子节点的 n 叉树，满足以下关系：
$$ L = (n-1) \times I + 1 $$
（其中 $ L $ 为叶子节点数，$ I $ 为内部节点数）

计算过程

1. 代入给定数据： $$ 41 = 10(n - 1) + 1 $$
2. 移项并化简： $$ n - 1 = \frac{41 - 1}{10} = 4 $$
3. 解得： $$ n = 5 $$

节点数最多的将是完全二叉树。
高度为 $ h $ 的完全二叉树的节点数计算如下：

$$ 1 + 2 + 2^2 + 2^3 + \cdots + 2^h = 2^{h+1} - 1 $$

该公式来源于等比数列求和，其中每一层的节点数是前一层的两倍，最终总和为 $ 2^{h+1} - 1 $。

对于右偏二叉树，节点数将是 $2^n - 1$。例如，在下述二叉树中，节点 ‘A’ 将存储在索引 1 处，‘B’ 存储在索引 3 处，‘C’ 存储在索引 7 处，‘D’ 存储在索引 15 处：

A
 \
   \
    B
      \
        \
         C
           \
             \
              D

该存储方式要求数组 X 的大小必须能够容纳最坏情况下的索引位置。当二叉树退化为单链结构（完全右偏）时，第 k 层节点的索引为 $2^k - 1$。若总共有 n 个节点，则最大索引值为 $2^n - 1$，因此数组最小大小需为 $2^n - 1$。其他选项均无法覆盖此类极端情况。

解析

• 二叉搜索树的中序遍历具有严格性质：输出结果必为升序排列
• 对比各选项：
  • 选项 A: 9, 10, 15, 22, 23, 25, 27, 29, 40, 50, 60, 95 → 完全升序 ✅
  • 其他选项均存在逆序元素 ❌
• 因此唯一符合条件的选项是 A

解析

• C 是正确的
  (1 (2 3 4)(5 6 7)) 表示如下二叉树：

    1
   / \
  2   5
  / \ / \
  3 4 6 7
  

• A) (1 2 (4 5 6 7)) 不合法
  括号内包含 4 个元素 (4 5 6 7)，违反了二叉树每个节点最多两个子节点的规则。

• B) (1 (2 3 4) 5 6) 7) 不合法
  存在括号不匹配问题（2 个左括号 vs. 3 个右括号），且根节点有 4 个直接子元素。

• D) (1 (2 3 NULL) (4 5)) 不合法
  右子树 (4 5) 仅有 2 个元素，而根据表示法 (X Y Z) 需要 3 个元素（父节点 + 左子树 + 右子树）。

解析：
在二叉树中，若节点 X 有两个子节点，则其 中序后继 Y 是 X 的右子树中最左侧的节点。

• 根据中序遍历（左 - 根 - 右）的特性，X 的中序后继必然位于其右子树中。
• 最左侧的节点意味着该节点 没有左子节点（否则会继续向左搜索）。

因此，Y 的左子节点必为空，选项 B 正确。

• 最大节点数：当二叉树是完美二叉树时，节点数最大。
  高度为 $ h $ 的完美二叉树的节点数为 $ 2^{h+1} - 1 $。

• 最小节点数：当二叉树是倾斜二叉树时，节点数最小。
  此时节点数为 $ h + 1 $。

根据题意并分析选项可知，选项 (A) 正确。

所有度数之和 = 2 × |边数|。将树视为 k 叉树时：叶子节点度数之和 + 非根内部节点度数之和 + 根节点度数 = 2 × (节点总数 - 1)

推导过程：

1. 代入公式： $$ L + (I-1)(k+1) + k = 2(L + I - 1) $$
2. 展开并化简： $$ \begin{align*} L + kI - k + I - 1 + k &= 2L + 2I - 2 \\ L + kI + I - 1 &= 2L + 2I - 2 \\ (k-1)I + 1 &= L \end{align*} $$
3. 代入已知条件 $k=2$，$L=20$： $$ (2-1)I + 1 = 20 \Rightarrow I = 19 $$

结论：
树中有 19 个具有两个子节点的内部节点。

上述描述实际上是输入数组 A 的堆构建算法。

BUILD-HEAP(A)
    heapsize := size(A);
    for i := floor(heapsize/2) downto 1
        do HEAPIFY(A, i);
    end for
END

该算法的时间复杂度上界为 $O(n)$。

设高度为 h 时的节点数为 $n(h)$。

在完美二叉树（除叶子节点外每个节点都有两个子节点）中，以下递推关系成立：
$$n(h) = 2 \times n(h-1) + 1$$

在本题情况下，节点数少 2 个，因此
$$n(h) = 2 \times n(h-1) + 1 - 2$$
$$= 2 \times n(h-1) - 1$$

将所有选项代入验证，只有选项 (B) 满足上述递推关系。

我们来看选项 (B)：
$$n(h) = 2^{h-1} + 1$$

若代入 $n(h-1) = 2^{h-2} + 1$，应得到 $n(h) = 2^{h-1} + 1$：

$$ \begin{align*} n(h) &= 2 \times n(h-1) - 1 \\ &= 2 \times (2^{h-2} + 1) -1 \\ &= 2^{h-1} + 1 \end{align*} $$

当给定距离为 4 时，节点编号为 31。

分析过程：

• 完全二叉树特性：在 BFS 中，若某层的所有节点均被访问，则下一层的起始位置为当前层末尾 + 1。
• 层级关系：距离根节点为 4 的节点位于第 5 层（根节点为第 0 层）。
• 最大节点数计算：
  完全二叉树的总节点数公式为 $2^{h+1} - 1$，其中 h 为高度。
  当高度为 4 时，总节点数为 $2^{5} - 1 = 31$，即第 5 层最后一个节点为第 31 个节点。

示例说明：
以距离为 2 的情况为例，第 3 层最远节点 G 在 BFS 中的序号为 7：

    A
   / \
  B   C
 / \ / \
 D E F G

结论：
在距离 4 处，最后一个节点的序号为 31。选项 (C)。

解释：
在二叉树中，叶子节点的数量与度为 2 的内部节点之间存在以下关系：

叶子节点数 = 度为 2 的内部节点数 + 1

根据题目条件：

• 度为 2 的内部节点数 = 10
• 度为 1 的内部节点数不影响叶子节点数量

代入公式：
叶子节点数 = 10 + 1 = 11

• 解题思路

  1. 首先找出首尾元素相同的序列：
     • 先序遍历的第一个元素是根节点
     • 后序遍历的最后一个元素是根节点
  2. 观察给出的序列：
     • 先序 = KAMCBYPFH
     • 后序 = MBCAFHPYK
     • 剩余序列 MABCKYFPH 将是中序遍历
  3. 确认三组序列对应关系：
     • I. 后序
     • II. 先序
     • III. 中序

• 结论
  根据上述分析，选项 D 正确描述了序列与遍历方式的对应关系。

解释

对于任意树结构，所有节点的度数之和等于边数的两倍（即 $ \sum \text{度数} = 2(n-1) $）。设总节点数为 $ n = n_1 + n_2 + n_3 $，则：

$$ 1 \cdot n_1 + 2 \cdot n_2 + 3 \cdot n_3 = 2(n - 1) $$

将 $ n = n_1 + n_2 + n_3 $ 代入并化简，可得：

$$ n_3 = n_1 - 2 $$

推导过程：

1. 树的性质：
   任意树的边数为 $ n - 1 $，根据握手定理，所有节点的度数之和等于边数的两倍：

   $$ \sum_{v \in V} \deg(v) = 2(n - 1) $$

2. 度数分类求和：
   设 $ n_1, n_2, n_3 $ 分别表示度数为 1、2、3 的节点数量，则：

   $$ 1 \cdot n_1 + 2 \cdot n_2 + 3 \cdot n_3 = 2(n - 1) $$

3. 总节点数关系：

   $$ n = n_1 + n_2 + n_3 $$

4. 联立方程消元：
   将 $ n $ 代入度数方程，整理后得到： $$ n_3 = n_1 - 2 $$

该结论表明，在仅包含度数为 1、2、3 的树中，度数为 3 的节点数量比度数为 1 的节点少 2。

解析

1. 初始边数计算
   树的边数恒为 $n - 1$，其中 $n = n_1 + n_2 + n_3$。

2. 操作影响分析

   • 每次处理一个度为 2 的节点时：
     • 添加一条边（连接其两个相邻节点），边数增加 1；
     • 移除该节点及其两条原有边，边数减少 2；
     • 净变化：边数减少 1。

3. 操作终止条件
   当无度为 2 的节点时停止。设共执行 $k$ 次操作，则：

   • 最终边数 = 初始边数 $- k$；
   • 初始边数 $= (n_1 + n_2 + n_3) - 1$；
   • 最终边数 $= (n_1 + n_2 + n_3 - 1) - k$。

4. 求解 $k$ 的值

   • 每次操作消除一个度为 2 的节点，因此 $k = n_2$。

5. 代入简化

   • 最终边数 $= (n_1 + n_2 + n_3 - 1) - n_2 = n_1 + n_3 - 1$；
   • 由于树的度数总和公式：$\sum (\text{度}) = 2(n - 1)$，可得 $n_1 + 2n_2 + 3n_3 = 2(n - 1)$；
   • 化简后 $n_1 + n_3 = 2(n - 1) - n_2 - 2n_2 = 2n - 2 - 3n_2$；
   • 代入最终边数表达式：$n_1 + n_3 - 1 = 2n - 3 - 3n_2$；
   • 结合 $n = n_1 + n_2 + n_3$，进一步化简可得 $2n_1 - 3$。

综上，正确答案为 A。

解析：

• 正确性分析

  • 前序遍历特性：根节点 → 左子树 → 右子树
  • 二叉搜索树规则：左子树所有节点 < 根节点 < 右子树所有节点
  • 有效序列特征：任意子序列需满足 BST 的大小约束关系

• 选项 D 分析

  序列：5 3 1 2 4 7 6 8
  

  • 根节点 5 将序列划分为左子树 [1,2,3,4] 和右子树 [6,7,8]
  • 左子树递归验证：
    • 根节点 3 划分左 [1,2] 和右 [4]
    • 节点 1 的右子树为 2（满足 1 < 2 < 3）
    • 节点 4 无子节点
  • 右子树递归验证：
    • 根节点 7 划分左 [6] 和右 [8]
    • 节点 6 无子节点
    • 节点 8 无子节点
  • 所有子树均满足 BST 性质

• 错误选项分析

  • 选项 A (5 3 1 2 4 7 8 6)
    • 在右子树 7 的子序列中，8 出现在 6 前面
    • 8 属于 7 的右子树，6 应该是 7 的左子树
    • 但 6 < 7 且 8 > 7，导致 8 和 6 同属 7 的不同子树却顺序颠倒
  • 选项 B (5 3 1 2 6 4 8 7)
    • 在左子树 3 的子序列中，6 出现在 4 前面
    • 6 属于 3 的右子树，4 应该是 6 的左子树
    • 但 4 < 6 且 4 > 3，导致 4 无法同时满足对父节点 3 和祖父节点 6 的约束
  • 选项 C (5 3 2 4 1 6 7 8)
    • 在左子树 3 的子序列中，2 的右子树出现 4（合法）
    • 但 2 的左子树出现 1（合法），随后又出现 4（合法）
    • 关键问题是 1 出现在 2 的右子树位置，违反 BST 规则（1 < 2 且 1 应该是 2 的左子树）

• 结论：只有选项 D 的序列能构建出符合 BST 性质的二叉搜索树

解释
该问题可通过 卡特兰数（Catalan Number） 公式求解，用于计算具有 n 个不同节点的结构不同的二叉树总数。公式如下：
$$ C(n) = \frac{(2n)!}{n!(n+1)!} $$

当 n = 4 时：

• 分子：$ (2 \times 4)! = 8! = 40320 $
• 分母：$ 4! \times 5! = 24 \times 120 = 2880 $
• 结果：$ \frac{40320}{2880} = 14 $

因此，正确答案为 A. 14。

参考：数据结构与算法 | 第 16 集

解析：
AVL 树的平衡性质要求任意节点的左右子树高度差不超过 1。要确定 7 个节点的 AVL 树的最大高度，需通过递推关系计算最小节点数：

$$ N(h) = N(h-1) + N(h-2) + 1 $$

其中 $N(h)$ 表示高度为 $h$ 的 AVL 树的最小节点数。初始条件为 $N(0) = 1$, $N(1) = 2$。

计算过程如下：

• $h=0$: $N(0) = 1$
• $h=1$: $N(1) = 2$
• $h=2$: $N(2) = N(1) + N(0) + 1 = 2 + 1 + 1 = 4$
• $h=3$: $N(3) = N(2) + N(1) + 1 = 4 + 2 + 1 = 7$

当 $h=3$ 时，最小节点数恰好为 7，因此 7 个节点的 AVL 树的最大高度为 3。

红黑树的性质（总结）：

1. 每个节点是红色或黑色
2. 根节点是黑色
3. 每个叶子节点（NIL，哨兵节点）是黑色
4. 如果一个节点是红色的，则它的两个子节点都是黑色的（即不允许两个红色节点相邻）
5. 从任一节点到其所有后代叶节点的每条路径都包含相同数目的黑色节点

选项分析：

• B 错误。红色节点不能有红色子节点。
• C 错误。红色节点的子节点必须是黑色。
• D 错误。红黑树的所有叶子节点（NIL节点）必须是黑色的。

所以正确答案为 A。

在完全二叉树中，存在以下规律：

1. 叶子节点数量 = 非叶子节点数量 + 1
2. 当非叶子节点数为 $n$ 时，叶子节点数为 $n+1$
3. 总节点数 = 非叶子节点数 + 叶子节点数 = $n + (n+1) = 2n+1$

解析

• 题目描述的是严格二叉树（每个非叶子节点必须有两个子节点）的最大高度问题
• 最大高度出现在最不平衡的二叉树结构中：
  • 每层仅有一个非叶子节点
  • 其余节点均为叶子节点
• 节点数量与高度的关系推导：
  • 根节点为第 1 层
  • 每增加 1 层需新增 2 个叶子节点
  • 总节点数 $ n = 1 + 2(h-1) $
  • 解得最大高度 $ h = \frac{n-1}{2} $
• 因此选项 C 是正确答案

题目问的是“包含 6 个节点的不同二叉树的数量”，这实际上是一个 卡塔兰数（Catalan number） 的问题。

卡塔兰数定义：

卡塔兰数第 $n$ 项的公式为：

$$ C_n = \frac{1}{n+1} \binom{2n}{n} = \frac{(2n)!}{(n+1)! \cdot n!} $$

当 $n = 6$ 时：

$$ C_6 = \frac{1}{7} \binom{12}{6} = \frac{1}{7} \cdot 924 = 132 $$

所以选项 C 正确。

卡塔兰数常用于计算：

• 不同二叉树的数量
• 合法括号组合数
• 栈排序的排列数等结构问题

• 定义：完全二叉树是所有非叶子节点均有两个子节点的二叉树
• 性质：叶子节点数 $ L $ 与内部节点数 $ I $ 满足关系式
  $$ L = I + 1 $$
• 验证过程：
  • 总节点数 $ N = L + I = (I + 1) + I = 2I + 1 $
  • 当 $ N = 15 $ 时，解得 $ I = 7, L = 8 $，满足完全二叉树条件
• 结论：选项 (B) 符合完全二叉树的构造规则

解析：

• 在最大堆（Max Binary Heap）中，每个节点的键值至少不小于其子节点的键值
• 在最小堆（Min Binary Heap）中，根节点的键必须是二叉堆中所有键中的最小值
• 题干描述的"每个节点的值至少不小于其子节点的值"符合最大堆的定义特征
• 因此正确答案为 (D) 堆

• 定义：若每个节点有 0 或 2 个子节点，则称为满二叉树
• 性质：所有非叶子节点均有两个子节点
• 公式推导：
  设叶子节点数为 $ n $，则总节点数为 $ 2n - 1 $
• 结论：选项 (C) 符合该数学关系

在 BFS 情况下，如果绘制完全二叉树，则集合 A 包含第 1 层和第 2 层的所有元素。在 DFS 情况下，集合 B 包含第 1 层、第 2 层和第 3 层的部分元素。

• 第 1 层 = 1 个元素
• 第 2 层 = 2 个元素
• 第 3 层 = 4 个元素

集合 A 构成：

• 第 1 层：第一个元素
• 第 2 层：第二个和第三个元素

集合 B 构成：

• 第 1 层：1 个元素
• 第 2 层：第二个元素
• 第 3 层：第三个元素

交集关系：

• A ∩ B 包含 L1 的 1 个元素与 L2 的 1 个元素
• A - B 包含 L2 剩余的 1 个元素

因此 |A - B| = 1

1. 后序遍历规则：左子树 → 右子树 → 根节点
2. 从最左下角的叶子节点 g 开始遍历：
   • 遍历 g → 回溯到父节点 c → 遍历 c 的右子树 d → 最终输出 g c d
3. 返回到 b 节点时，已遍历完其左右子树，输出 b
4. 继续向上回溯到 a 节点，此时需先处理 a 的右子树：
   • 右子树根节点 e 的左子树 f 先被遍历 → 输出 f e
5. 最后输出根节点 a，完整序列为 g c d b f e a
6. 对比选项发现 C 与推导结果一致

解析：

1. 根据先序遍历首元素确定根节点为 a
2. 中序遍历 d b e a f c g 可划分为左子树 d b e 和右子树 f c g
3. 递归构建左右子树后，后序遍历顺序应为：
   • 左子树后序：d e b
   • 右子树后序：f g c
   • 最终结果：d e b f g c a

选项 (C) 是正确答案。

解析：

• 在二叉堆的数组表示中，每个节点的父节点索引通过 floor(i/2) 计算得到。
• 例如，当 i=2 或 i=3 时，父节点均为索引 1；当 i=4、5 时，父节点为索引 2。
• 因此，正确答案是 B。

解析

1. 算法特性：二分查找每次迭代通过 (low + high) // 2 计算中间索引，涉及一次算术运算。
2. 递归深度：由于每次将搜索区间减半，递归调用最多执行 log₂(n) 层。
3. 结论：总运算次数与递归深度成正比，即 Θ(log₂(n))，对应选项 B。

在二叉树中，高度 h 表示从根节点到任意叶节点的最长路径。
最坏情况分析：

• 当每个父节点只有一个子节点（左或右）而另一个子节点为空时，树的高度将小于 n-1
• 完全二叉树等平衡二叉树包含最大节点数时，其高度可以等于 n-1

结论：

• 树的高度 可能大于或等于 n-1（取决于具体结构）
• 选项 b) 正确描述了这一特性，因为树的高度会随着节点排列方式的不同而变化
• 其他选项均存在绝对化表述（“总是”），与实际情况不符

由于 AVL 树是平衡树，其高度为 $ O(\log n) $。因此，在 AVL 树中最坏情况下插入一个元素的时间复杂度为 $ O(\log n) $。注意：每次插入操作包括以下步骤：

• 查找插入位置 = $ O(\log n) $
• 若插入后性质不满足，则进行旋转调整 = $ O(\log n) $
  因此，AVL 树的单次插入操作总时间为 $ O(\log n) + O(\log n) = O(\log n) $。
  现在需要插入 $ n^2 $ 个元素，因此总时间复杂度为 $ O(n^2 \log n) $。

另一种方法：
最坏情况下，第 1 次插入时间复杂度 = $ O(\log n) $
第 2 次插入时间复杂度 = $ O(\log(n+1)) $
…
第 $ n^2 $ 次插入时间复杂度 = $ O(\log(n + n^2)) $
总时间复杂度为：

$$ \begin{align*} \text{时间复杂度} &= O(\log n) + O(\log(n+1)) + \dots + O(\log(n + n^2)) \\ &= O(\log [n(n+1)(n+2)\dots(n+n^2)]) \\ &= O(\log n^{n^2}) \\ &= O(n^2 \log n) \end{align*} $$

选项 (C) 正确。

AVL 树是二叉树，具有以下限制：

1. 子节点的高度差最多为 1。
2. 两个子树都是 AVL 树。

以下是使用 7 个节点可以得到的最不平衡的 AVL 树：

    a
   / \
  b   c
 / \ /
d  e g
     \
      h

AVL 树的平衡性要求任意节点左右子树高度差不超过 1。当构造最不平衡的合法 AVL 树时，每个节点都尽可能让左右子树高度差为 1。对于 7 个节点的情况，这种递归构造会形成高度为 3 的树（根节点 a → b/c → d/e/g → h）。若继续增加高度会导致违反平衡约束，因此最大高度为 3。

参考以下步骤了解 AVL 插入过程。AVL 树 | 插入部分（第一部分）

平衡过程解析

1. 初始插入状态
   插入 70 后，树变为：

      60
     /   \
   20    100
          / \
        80 120
       /
      70
   

2. 失衡检测

   • 从插入节点向上回溯至根节点
   • 在节点 60 处发现失衡（右左情况）

3. 旋转操作

   • 第一步：右旋 100

         60                          60
        /   \                       /   \
      20    100                   20     80
             / \                      /   / \
           80 120                  70  100 120
          /
         70
     

   • 第二步：左旋 60

         60                            80
        /   \                        /     \
      20     80                    60      100
            / \                 /   \        \
          70 100              20    70       120
               \
               120
     

4. 最终平衡结果
   平衡后的 AVL 树结构与选项 C 完全一致：

         80
        /  \
      60   100
     / \     \
    20 70    120
   

解析

• 红黑树高度特性：包含 n 个节点的红黑树高度 ≤ 2Log₂(n+1)
• AVL 树高度特性：包含 n 个节点的 AVL 树高度 < Logφ(√5(n+2)) - 2
• 平衡性对比：AVL 树比红黑树更平衡
• 旋转操作差异：AVL 树在插入/删除时可能需要更多旋转

解析：

• AVL 树插入操作
  需要两次遍历路径：

  1. 第一次从根节点到插入位置完成节点插入；
  2. 第二次从插入节点向上回溯至根节点，检测并修复平衡性（通过旋转操作）。

• 红黑树插入操作
  仅需一次遍历路径：
  插入完成后，通过自顶向下的修复策略（如变色、旋转）直接沿插入路径向上调整，无需额外回溯。

因此，选项 A 正确，其余选项均存在描述错误。

• 实现步骤

  1. 对 B1 和 B2 分别进行中序遍历，得到两个有序数组 A1（长度 n）和 A2（长度 m）
  2. 使用双指针法在 O(m+n) 时间内合并两个有序数组
  3. 对合并后的有序数组递归构建平衡二叉树：
     • 取中间元素作为根节点
     • 左子数组递归构建左子树
     • 右子数组递归构建右子树

• 时间复杂度分析

  • 中序遍历：O(n + m)
  • 数组合并：O(n + m)
  • 构建新树：O(n + m)
  • 总体时间复杂度为三者之和 → O(n + m)

• 关键结论
  平衡二叉树的性质保证了中序遍历结果严格有序，而线性时间的数组合并与树构建操作共同决定了最优解的时间复杂度上限。

解析：

平衡二叉搜索树特性

• 支持在 $O(\log n)$ 最坏情况时间复杂度下完成查找、插入和删除操作
• 最小元素可通过遍历左子树快速定位（左下角节点）

堆的局限性

• 虽然支持 $O(\log n)$ 的插入与删除最小值操作
• 关键缺陷：无法在 $O(\log n)$ 时间内判断元素是否存在
• 题目要求的"仅当元素不存在时插入"操作需要先执行存在性查询，而堆不支持高效查询

结论对比

因此，选项 (B) 正确。

• AVL 树特性：AVL 树是一种自平衡二叉搜索树，通过旋转操作维持高度平衡
• 时间复杂度对比：
  • AVL 树搜索时间复杂度始终为 θ(log n)
  • 普通二叉搜索树在极端情况下（如完全倾斜）会退化为链表，此时搜索时间复杂度为 θ(n)
• 关键区别：平衡性保障了 AVL 树的最坏情况性能，而普通二叉搜索树的性能依赖于输入数据的分布

• 定义：若二叉搜索树中每个节点的平衡因子均为 -1、0 或 1，则该树为 AVL 树。
  • 节点 X 的平衡因子定义为：左子树高度 - 右子树高度
• 分析：
  • 在树 B 中，值为 50 的节点平衡因子为 2（左子树高度为 2，右子树高度为 0），因此 B 不是 AVL 树。
  • 其他选项中的树均满足所有节点平衡因子在 [-1, 1] 范围内。