平衡二叉树：为什么需要平衡？旋转操作简单讲

我们先从最常见的数据结构之一——二叉搜索树（BST）说起。二叉搜索树是一种按特定规则排列的二叉树：对于任意节点，左子树的所有节点值都小于它，右子树的所有节点值都大于它。这种结构在理想情况下，查找、插入、删除的时间复杂度都是 O(log n)，看起来很高效。

但如果我们插入节点的顺序比较“极端”，比如一直往右边插入（或一直往左边插入），BST 就会退化成一个链表。例如，连续插入 1, 2, 3, 4, 5，最终树会变成一条长长的右链，查找时需要从根节点一路走到叶子，时间复杂度变成 O(n)，这就失去了 BST 的优势。

什么是“平衡”？¶

平衡二叉树（比如 AVL 树）的核心是 “平衡因子”。每个节点的平衡因子定义为：左子树高度 - 右子树高度。对于平衡二叉树，每个节点的平衡因子必须是 -1、0 或 1（即左右子树高度差不超过 1）。

举个例子：如果一个节点的左子树高度是 3，右子树高度是 1，那么平衡因子是 2，这棵树就“不平衡”了。

为什么需要平衡？¶

想象你在图书馆找书：如果书架是“平衡”的（每一层书的数量差不多），你很快就能找到目标；但如果书架是倾斜的（左边堆了 100 本，右边只有 1 本），你可能需要花更多时间爬过去。

树的高度直接影响操作效率。平衡的树高度近似为 log n（比如 n=1000 时，高度约 10），而不平衡的树可能退化成 O(n) 高度。平衡二叉树通过调整结构，让树的高度始终保持在 log n 级别，从而保证查询、插入、删除的高效性。

旋转操作：如何让树“平衡”？¶

当树不平衡时（平衡因子绝对值 >1），需要通过 旋转操作 调整结构。旋转有四种基本类型：LL 型、RR 型、LR 型、RL 型，本质是通过“调整支点”让树恢复平衡。

1. LL 型：左左失衡（右旋）¶

场景：节点 A 的左子树高度比右子树高 2，且左子树的左子树也高。
例子：
插入顺序：10, 5, 3, 1（连续插入左子树），形成树结构：

    10
   /
  5
 /
3
 /
1

此时，节点 10 的平衡因子为 2（左高右低），需要右旋。

右旋步骤：
- 以节点 5 为新根，原来的根 10 变成 5 的右孩子；
- 5 原来的右子树（如果有的话），变成 10 的左孩子（这里 5 没有右子树，所以 10 的左孩子为空）。

旋转后结构：

  5
 / \
3   10
 \
  1  // 注意：3 的右孩子是 1（原 3 的右子树为空，这里 3 原来只有左孩子 1？哦，原结构是 5 的左孩子是 3，3 的左孩子是 1，所以右旋后 3 是 5 的左孩子，10 是 5 的右孩子，3 的右子树为空，所以 10 的左孩子为空。正确结构：

  5
 / \
3   10
 \
  1

（更准确的描述：右旋后，原根节点 10 变成新根 5 的右孩子，原根的左子树（5 的左子树）保持不变，原根的右子树（空）变成 10 的左子树。）

2. RR 型：右右失衡（左旋）¶

场景：节点 A 的右子树高度比左子树高 2，且右子树的右子树也高。
例子：
插入顺序：1, 3, 5, 7（连续插入右子树），形成树结构：

1
 \
  3
   \
    5
     \
      7

此时，节点 1 的平衡因子为 -2（右高左低），需要左旋。

左旋步骤：
- 以节点 5 为新根，原来的根 1 变成 5 的左孩子；
- 5 原来的左子树（如果有的话），变成 1 的右孩子（这里 5 没有左子树，所以 1 的右孩子为空）。

旋转后结构：

    5
   / \
  1   7
   \
    3

（原根 1 变成 5 的左孩子，原根的右子树（3）变成 1 的右孩子。）

3. LR 型：左右失衡（先左旋再右旋）¶

场景：节点 A 的左子树高度比右子树高 2，但左子树的右子树更高。
例子：
插入顺序：10, 5, 7, 3（先插左 5，再插右 7，再插左 3），形成树结构：

    10
   /
  5
   \
    7
   /
  3

此时，节点 10 的平衡因子为 2（左高），但左子树 5 的平衡因子为 -1（右高），属于 LR 型。

调整步骤：
1. 先左旋：对左子树 5 进行左旋，将 7 变成 5 的父节点（即 5 和 7 交换位置）：

      10
     /
    7
   / \
  5   （原 5 的右子树）
 /
3

2. 再右旋：对根节点 10 进行右旋，将 7 变成新根，10 变成 7 的右孩子：

     7
    / \
   5   10
  /
 3

旋转后，所有节点的平衡因子均为 -1、0 或 1，树恢复平衡。

4. RL 型：右左失衡（先右旋再左旋）¶

场景：节点 A 的右子树高度比左子树高 2，但右子树的左子树更高。
例子：
插入顺序：10, 15, 12, 20（先插右 15，再插左 12，再插右 20），形成树结构：

    10
     \
      15
     /
    12
     \
      20

此时，节点 10 的平衡因子为 -2（右高），右子树 15 的平衡因子为 1（左高），属于 RL 型。

调整步骤：
1. 先右旋：对右子树 15 进行右旋，将 12 变成 15 的父节点：

      10
       \
        12
         \
          15
           \
            20

2. 再左旋：对根节点 10 进行左旋，将 12 变成新根，10 变成 12 的左孩子：

      12
     / \
    10  15
         \
          20

旋转后树恢复平衡。

总结¶

平衡二叉树通过 平衡因子 监控树的结构，当树不平衡时，通过 旋转操作（LL/RR/LR/RL）调整节点位置，让树的高度始终保持在 log n 级别，从而保证操作效率。旋转的本质是“调整支点”，让树的左右子树高度差不超过 1，最终实现“高效查找”。

记住：平衡的核心是“让树不倾斜”，旋转是“扶正倾斜树”的关键动作。

（如果需要更直观的旋转效果，可以想象一个“跷跷板”：当左边过重时，右边的支点需要向上抬，把重的部分调回中间。树的旋转就像这样，通过调整子树的“位置”让整体结构平衡。）