平衡二叉树

平衡二叉树是为了堵住 BST 那个「输入有序就退化成链表」的洞而设的。

做法很直接：在插入和删除时，规定任意结点的左、右子树高度差的绝对值不超过 1，一旦超了就地转回来。代价是每次插入删除都要检查、可能要旋转；收益是树高被锁死在。

这一节要理解的其实只有两件事：哪棵子树需要调（最小不平衡子树），和往哪个方向调（LL / RR / LR / RL 四选一）。旋转本身是机械的。下一节的红黑树正是嫌这个代价太高才把「高度平衡」放宽成「适度平衡」——先把 AVL 的代价看清楚，才知道红黑树在省什么。

机制

定义与平衡因子

为了避免树的高度增长过快、降低二叉排序树的性能，规定在插入和删除结点时，要保证任意结点的左、右子树高度差的绝对值不超过 1，将这样的二叉树称为平衡二叉树（Balanced Binary Tree），也称 AVL 树。

定义结点左子树与右子树的高度差为该结点的平衡因子，则平衡二叉树结点的平衡因子的值只可能是 −1、0 或 1。

平 衡 因 子 左 右

也可以递归定义：平衡二叉树或者是一棵空树，或者是具有下列性质的二叉树——它的左子树和右子树都是平衡二叉树，且左子树和右子树的高度差的绝对值不超过 1。

边界辨析：

平衡因子 = 左减右，符号不能反。 LL 情况下 A 的平衡因子由 1 增至 2（左边更高）， RR 情况下由 −1 减至 −2（右边更高）。记反了四种旋转会全部左右颠倒。另外，平衡二叉树首先必须是二叉排序树——只满足高度条件、不满足 BST 序的树不是 AVL 树。

插入：只调最小不平衡子树

基本思想：每当在 BST 中插入（或删除）一个结点时，首先检查其插入路径上的结点是否因为此次操作而导致了不平衡。若导致了不平衡，则先找到插入路径上离插入结点最近的平衡因子的绝对值大于 1 的结点 ，再对以为根的子树，在保持二叉排序树特性的前提下，调整各结点的位置关系，使之重新达到平衡。

注意，每次调整的对象都是最小不平衡子树，即以插入路径上离插入结点最近的平衡因子的绝对值大于 1 的结点作为根的子树。

「最近」是关键词。 从插入点往根走，遇到的第一个失衡结点就是，不要继续往上找更高的失衡结点。

四种旋转

四种情况按插入位置相对于的两步路径命名。第一个字母是「的哪个孩子」，第二个字母是「那个孩子的哪棵子树」：

情况	插入位置	旋转
LL	的左孩子的左子树	右单旋转
RR	的右孩子的右子树	左单旋转
LR	的左孩子的右子树	先左后右双旋转
RL	的右孩子的左子树	先右后左双旋转

LL（右单旋转）：将的左孩子向右上旋转代替成为根结点，将向右下旋转成为的右子树，而 的原右子树则作为的左子树。

flowchart LR
    subgraph BEFORE["失衡（A 的平衡因子 = 2）"]
        A1(("A")) --- B1(("B"))
        A1 --- AR1["AR<br/>H"]
        B1 --- BL1["BL<br/>H+1"]
        B1 --- BR1["BR<br/>H"]
    end
    subgraph AFTER["LL 右单旋转后"]
        B2(("B")) --- BL2["BL<br/>H+1"]
        B2 --- A2(("A"))
        A2 --- BR2["BR<br/>H"]
        A2 --- AR2["AR<br/>H"]
    end
    BEFORE ==>|"B 上升，A 右下沉<br/>BR 改挂到 A 的左边"| AFTER

    classDef bad fill:#ffcdd2,stroke:#b71c1c,stroke-width:2px
    classDef good fill:#c8e6c9,stroke:#1b5e20,stroke-width:2px
    classDef sub fill:#e3f2fd,stroke:#1565c0
    class A1 bad
    class B2 good
    class B1,A2 sub
    class AR1,BL1,BR1,BL2,BR2,AR2 sub

RR（左单旋转） 与 LL 完全对称：的右孩子向左上旋转代替，向左下旋转成为的左子树， 的原左子树作为的右子树。

LR（先左后右双旋转）：先将的左孩子的右子树的根结点 向左上旋转提升到的位置，然后把向右上旋转提升到的位置。RL 对称。

flowchart LR
    subgraph S1["失衡：C 在 A→B 的右子树上"]
        A3(("A")) --- B3(("B"))
        A3 --- AR3["AR"]
        B3 --- BL3["BL"]
        B3 --- C3(("C"))
    end
    subgraph S2["第一步：C 左旋提升到 B 的位置"]
        A4(("A")) --- C4(("C"))
        A4 --- AR4["AR"]
        C4 --- B4(("B"))
        B4 --- BL4["BL"]
    end
    subgraph S3["第二步：C 右旋提升到 A 的位置"]
        C5(("C")) --- B5(("B"))
        C5 --- A5(("A"))
        B5 --- BL5["BL"]
        A5 --- AR5["AR"]
    end
    S1 ==> S2 ==> S3

    classDef bad fill:#ffcdd2,stroke:#b71c1c,stroke-width:2px
    classDef good fill:#c8e6c9,stroke:#1b5e20,stroke-width:2px
    classDef sub fill:#e3f2fd,stroke:#1565c0
    class A3 bad
    class C5 good
    class B3,C3,A4,C4,B4,B5,A5 sub
    class AR3,BL3,AR4,BL4,BL5,AR5 sub

双旋转最终坐上根位置的是，不是。 单旋转是上位，双旋转是上位——这是区分单双旋的最快标志。

边界辨析：

教材的注意框：LR 和 RL 旋转时，新结点究竟是插入的左子树还是插入的右子树，不影响旋转过程。 图 7.13 和 7.14 只是以插入的左子树为例。所以做题时看到下面挂了新结点， 不必纠结挂在哪一边，直接按 LR / RL 走。

删除：可能一路回溯到根

以删除结点为例：

用二叉排序树的方法对结点执行删除操作。
若导致了不平衡，则从结点开始向上回溯，找到第一个不平衡的结点 （最小不平衡子树）； 为结点的高度最高的孩子； 是结点的高度最高的孩子。
然后对以为根的子树进行平衡调整，、、可能的位置有 4 种情况——与插入时的 LL / LR / RR / RL 一一对应。

与插入最重要的区别（教材原文加了着重）：

插入操作仅需要对以为根的子树进行平衡调整；而删除操作就不一样，先对以为根的子树进行平衡调整，若调整后子树的高度减 1，则可能需要对的祖先结点进行平衡调整，甚至回溯到根结点（导致树高减 1）。

flowchart TD
    I["插入导致失衡"] --> I1["找最小不平衡子树 A"]
    I1 --> I2["按插入路径判 LL/RR/LR/RL"]
    I2 --> I3["旋转一次<br/>结束"]

    D["删除导致失衡"] --> D1["从 w 向上回溯<br/>找第一个失衡结点 z"]
    D1 --> D2["y = z 的最高孩子<br/>x = y 的最高孩子"]
    D2 --> D3["按 x,y,z 位置判 LL/RR/LR/RL"]
    D3 --> D4{"调整后子树高度减 1？"}
    D4 -->|"是"| D1
    D4 -->|"否"| D5["结束"]

    classDef once fill:#c8e6c9,stroke:#1b5e20
    classDef loop fill:#ffcdd2,stroke:#b71c1c,stroke-width:3px
    classDef norm fill:#e3f2fd,stroke:#1565c0
    class I3 once
    class D4,D1 loop
    class I,I1,I2,D,D2,D3,D5 norm

边界辨析：

插入的分支判据是「插入位置的路径」，删除的分支判据是「高度最高的孩子」。 这两个判据不一样，因为删除时根本没有「插入路径」可言。若的两个孩子等高，通常取与同方向的那个（即优先走单旋）。

查找效率与递推

在平衡二叉树上进行查找的过程与二叉排序树的相同，因此比较关键字的次数不超过树的深度。

设表示深度为的平衡二叉树中含有的最少结点数，则

	0	1	2	3	4	5	6	7	8	9	10
	0	1	2	4	7	12	20	33	54	88	143

含有个结点的平衡二叉树的最大深度为，因此平均查找效率为。

关联对照：

教材的注意框给了这个递推的唯一用法：「该结论可用于求解给定结点数的平衡二叉树的查找所需的最多比较次数（或树的最大高度）。如在含有 12 个结点的平衡二叉树中查找某个结点的最多比较次数？」 查表：，所以最多 5 次。 反过来问「深度为最少几个结点」也是同一张表。 深度为的平衡二叉树含有的最多结点数显然是满二叉树的情况，即。

手算模板

构造 AVL 树（教材例：）：

按 BST 规则插入一个结点。
从新结点往根走，标出沿途每个结点的平衡因子。
遇到第一个 $平衡因子$ 的结点，记作，停。
看新结点在的哪个孩子的哪棵子树里 → 定 LL / RR / LR / RL。
旋转：单旋上位，双旋上位。旋完这一棵子树就结束，不再往上。
回到第 1 步插下一个。

删除：多两步——旋完之后看子树高度有没有减 1，减了就继续往上找下一个失衡结点，直到根。

判定树复用：折半查找的判定树就是一棵平衡二叉树（7.2.2），所以那一节数的方法在这里原样可用。

边界

说法	判断	说明
「平衡因子 = 右子树高 − 左子树高」	❌	是左减右
「平衡因子只能是 0 或 ±1」	✅	出现 ±2 就说明失衡，需要调整
「高度差不超过 1 的二叉树就是 AVL 树」	❌	还必须首先是二叉排序树
「失衡时要调整整棵树」	❌	只调最小不平衡子树
「是从根往下找的第一个失衡结点」	❌	是从插入点往上找的第一个
「LR 旋转后成为根」	❌	成为根。单旋上位，双旋上位
「LR 时新结点插在的左边还是右边会影响旋转」	❌	不影响（教材注意框）
「插入一次最多旋转一次」	✅	插入只调一棵最小不平衡子树
「删除一次最多旋转一次」	❌	可能一路回溯到根，这是插入与删除最重要的区别
「深度为的 AVL 树最少有个结点」	❌	是，而非 16
「AVL 树的查找一定比 BST 快」	⚠️	最坏情况下快（ vs ）；单次比较平均差别不大，代价在插入删除

口径差异：

算法竞赛几乎不写 AVL——要平衡就上 Treap、Splay 或者直接 std::set，因为竞赛只关心复杂度量级，不关心具体转了几次。 408 恰恰只考「转了几次、转成什么形状」：给一个插入序列画出最终的 AVL 树，或问「插入某个值后最小不平衡子树的根是谁」。 这一节要练的是手上的动作，不是渐进分析。

对照速查

	插入	删除
找谁	插入路径上最近的失衡结点	从上溯的第一个失衡结点
判据	插入位置的两步路径	、取「高度最高的孩子」
旋转次数	最多 1 次调整	可能一路回溯到根
旋转种类	LL / RR / LR / RL	同上，4 种

旋转	别名	关键改挂
LL	右单旋转	的原右子树 → 的左子树
RR	左单旋转	的原左子树 → 的右子树
LR	先左后右双旋转	的两棵子树分给和
RL	先右后左双旋转	同上，方向相反

	3	4	5	6	7
最少结点	4	7	12	20	33
最多结点	7	15	31	63	127

考点

平衡因子 = 左 − 右，取值只能是 −1 / 0 / 1。
最小不平衡子树的定位（从插入点往上找第一个）。
四种旋转的命名与结果，单旋上位、双旋上位。
LR / RL 时新结点挂哪边不影响。
插入最多调一次，删除可能回溯到根——插入与删除的核心差异。
，用于「个结点最多比较几次」（2012 命题追踪）。
判定树是平衡二叉树（7.2.2 原文）。

链接

🏠 返回总览：数据结构第 7 章：查找总览
⬅️ 上一节：7.3.1 二叉排序树
➡️ 下一节：7.3.3 红黑树
🔗 放宽平衡条件的后继者：7.3.3 红黑树
🔗 判定树就是平衡二叉树：7.2.2 折半查找
🔗 树高与结点数的基本关系：5.2.1 二叉树的定义及其主要特性
📖 名词库：第 7 章名词库

考研笔记

平衡二叉树

机制

定义与平衡因子

插入：只调最小不平衡子树

四种旋转

删除：可能一路回溯到根

查找效率与递推

手算模板

边界

对照速查

考点

链接

目录

反向链接

考研笔记

平衡二叉树

机制

定义与平衡因子

插入：只调最小不平衡子树

四种旋转

删除：可能一路回溯到根

查找效率与 递推

手算模板

边界

对照速查

考点

链接

目录

反向链接

查找效率与递推