树系列第 9 篇：AVL 树——旋转与插入

欢迎来到“树系列”第 9 篇。第 7 篇我们认识了二叉搜索树（BST），第 8 篇则亲手把它推上了手术台：升序插入会让 BST 退化成一根链，查找从 O(log n) 崩坏成 O(n)，百万节点的差距从“20 次比较”膨胀到“100 万次比较”。这一篇，我们要给 BST 装上第一个“自我矫正”的装置——AVL 树。它用一句极简的规则——任意节点的左右子树高度差不超过 1——彻底终结了退化问题，并让查找、插入、删除在最坏情况下都稳定在 O(log n)。这也是计算机科学史上第一棵被正式提出来的自平衡二叉搜索树，1962 年由苏联数学家 Adelson-Velsky 和 Landis 发表，“AVL”正是两位作者姓氏的缩写。

本篇的重心是插入，因为插入是平衡问题最集中、最经典的战场：一次插入如何打破平衡？如何定位“最小的失衡子树”？四种旋转（LL、RR、LR、RL）分别怎么转、三个子树怎么搬家？代码怎么写、高度和平衡因子什么时候更新？最后用一个具体序列从头到尾走一遍完整流程。全篇配了十几张 SVG 示意图，旋转部分特意“宁多勿少”，希望你合上文章后能自己画出每一次旋转。第 10 篇我们会继续讲删除——删除的修复比插入更棘手，因为一次删除可能触发多次旋转，复杂度分析也完全不同，但本篇先打地基，把旋转这个“万能扳手”彻底练熟。

正文路线图：先回顾第 7、8 篇的核心结论，并给出 AVL 的答案；然后定义平衡因子，看它如何随插入逐层更新；接着讲失衡的发现机制与“最小失衡子树”定理；再用四节篇幅分别图解 LL、RR、LR、RL 四种旋转；之后给出完整的 TypeScript 实现并逐行解释；随后用序列 [10, 20, 30, 40, 50, 25] 完整走一遍插入与修复；再证明 AVL 树高度为什么被锁死在 O(log n)，推导斐波那契式的最少节点递推；然后与普通 BST 全面对比，客观评估“旋转频繁”的代价；最后附上四种旋转速查表、七道自测题（含答案）和下一篇文章的预告。

0 先回顾：退化问题，以及 AVL 给出的答案

出发前的行囊：本篇会频繁使用第 7、8 篇的四个概念，先列出来对表。第一，BST 的递归定义（左小右大）与“中序遍历严格递增”的等价关系；第二，“高度”的口径——空子树 -1、叶子 0、节点 1 + max(左右孩子高度)；第三，退化机制——有序插入制造链，树高从 O(log n) 恶化成 O(n)；第四，复杂度心智——O(log n) 与 O(n) 在百万级数据上，是 20 步与 100 万步的差距。这四个概念里任何一个不清楚，读到旋转部分都会卡壳，建议先花十分钟回顾第 7、8 篇再继续。

0.1 第 7、8 篇的结论捡回来

第 7 篇的主角是二叉搜索树：任意节点的左子树所有值小于它，右子树所有值大于它；中序遍历严格递增；查找、插入、删除都沿着从根到目标的一条路径进行，因此时间复杂度是 O(h)，其中 h 是树的高度。这些结论本身没有问题，问题出在“h 到底是多大”这个变量上。

第 8 篇把这个变量彻底放大了一遍：从空树开始按升序插入 1、2、3、…、n，每一个新节点都比树里所有节点大，于是每次插入都一路向右走到最右下角，新节点永远挂在当前链的末端。n 次插入之后，树的高度是 n - 1，查找最坏要比较 n 次，插入最坏也要走 n 步。降序插入是对称的灾难，交替的“折线插入”也能造出各种奇形怪状的高树。更令人不安的是，这种输入并不罕见：数据库按主键导入存量数据、日志系统按时间戳追加、排行榜按分数批量录入，全都天然带有“有序性”。第 8 篇的结论可以浓缩成一句话：裸 BST 只保证了“内容正确”，不保证“形状健康”；而性能恰恰由形状决定。

那么，能不能在插入的同时主动“矫正”形状？思路看起来简单：每次插入之后检查一下树有没有长歪，歪了就把它掰回来。可“歪”怎么定义？“掰”又怎么掰？掰完之后会不会把 BST 性质破坏掉？会不会“按下葫芦浮起瓢”——修好了这棵子树，又弄坏了上面的结构？这一连串问题，正是本篇要逐个攻克的。

0.2 AVL 的答案：高度差不超过 1

AVL 树给出的矫正标准是：对于树中的任意节点，它的左子树高度与右子树高度之差（取绝对值）不超过 1。高度怎么算？约定：空子树的高度是 -1，叶子节点的高度是 0，一般节点的高度是“左右孩子高度较大者 + 1”。在这个约定下，“左右子树高度差不超过 1”对叶子也成立：叶子左右都是空子树，高度都是 -1，差是 0，完全合格。

为什么这个标准能治退化？直觉是这样的：一棵 AVL 树里，任何节点都不能“一头特别高、一头特别矮”，所以树不可能长成一条链。链上每个节点只有一个孩子，另一个子树是空的，高度差恰好等于“唯一孩子的子树高度 + 1”，随着链变长，这个差值会不断增大，迟早超过 1，触发矫正。反过来，如果每个节点都被限制在高度差 1 以内，那么树的高度就只能按对数量级增长——这个结论我们会在第 6 节严格证明，这里先记住结论：AVL 树的高度大约是 1.44 log₂(n + 2) - 1.33，也就是 O(log n)。

用同一组键 1 到 7 来感受一下这个标准：普通 BST 可以长成一根向右倒的链，也可以长成 AVL 允许的“矮胖”形状。下面两棵树存的内容完全一样，中序遍历都是 1、2、3、4、5、6、7，但左边高度为 6，右边高度为 2：

右边这棵树每个节点都满足“左右子树高度差不超过 1”：根 4 的左右子树高度都是 1，差 0；节点 2 的左右子树都是叶子，差 0；节点 6 同理。它不但好看，而且所有操作都被限制在 3 次比较以内。AVL 树的全部工作，就是在每次插入或删除之后，检查这个“高度差不超 1”的规则有没有被违反；一旦违反，立刻用旋转把违规的子树修回原状。

0.3 一个关键伏笔：旋转为什么“只修一处”？

在展开细节之前，先剧透一个贯穿全篇的事实：一次插入最多只需要修一棵子树。插入只可能让某些祖先节点的高度增加 1，因此一个节点的平衡因子最多从“合格”变成“不合格”，而且是从 ±1 变成 ±2，绝不会从 ±1 直接跳成 ±3。找到第一个失衡的节点之后，对它所在的那棵子树做一次旋转（单旋或双旋），这棵子树的高度会恢复成插入之前的高度，于是它上面的所有祖先根本感知不到变化，自然也不用修。这个“只需修一处”的性质，是 AVL 插入 O(log n) 的基石：回溯是 O(log n)，但旋转永远只有常数次。详细论证在第 2、3 节展开。

1 平衡因子：给每个节点配一个“水平仪”

1.1 定义：左高减右高

“左右子树高度差不超过 1”说起来容易，但每次检查都去重新递归求两棵子树的高度太浪费了。工程上的做法是：每个节点额外存一个整数，叫作平衡因子（balance factor，简称 bf），表示它的失衡倾向。本文采用“左高减右高”的约定：

bf(节点) = 左子树高度 - 右子树高度

这个约定下，bf 为正数表示左子树更高（左重），为负数表示右子树更高（右重）。注意有些教材用相反的约定（右高减左高），符号会全部反过来，旋转的判断条件也会跟着变，但只要始终如一，两种约定完全等价。本文所有代码、口诀、图例都统一采用“左减右”。有了平衡因子，AVL 规则就变成一句非常容易检查的话：每个节点的平衡因子只能是 -1、0、+1 三者之一。出现 ±2 就说明失衡了，必须修复。

为了算平衡因子，还需要一套统一的高度口径。本文约定：

空子树的高度 = -1
叶子节点的高度 = 0
任意节点的高度 = 1 + max(左子树高度, 右子树高度)

为什么要让空子树是 -1 而不是 0？因为这样“只有一个左孩子的节点”的高度差才能被正确度量。比如一个节点只有左孩子（右孩子为空），左子树高 0、右子树高 -1，bf = 0 - (-1) = +1，恰好表示“左重 1”，符合直觉；如果空子树算 0，bf 就会变成 0，把明显偏斜的节点误判成平衡。一个“只有左孩子的链节点”正是退化树的典型零件，口径错了，AVL 的警报系统就会失灵。

1.2 例子：给一棵树的每个节点贴标签

来看一棵具体的树，把每个节点的“高度 h”和“平衡因子 bf”都标出来。这棵树有 7 个节点：

从下往上验算：10 和 25 是叶子，h = 0，左右孩子都是空（-1），bf = (-1) - (-1) = 0；20 的左孩子 10 高 0、右孩子 25 高 0，所以 h(20) = 1，bf = 0 - 0 = 0；40 是叶子，h = 0，bf = 0；30 的左子树以 20 为根，高度 1，右子树以 40 为根，高度 0，所以 h(30) = 2，bf = 1 - 0 = +1。所有节点 bf ∈ {-1, 0, +1}，这是一棵合格的 AVL 树。注意节点 30 的 bf 是 +1：它允许“左比右高一格”，这正是 AVL 的宽容之处——它不要求左右一般齐，只要求差距不超过 1。

1.3 插入之后，平衡因子怎么更新？

插入一个节点，受影响的范围只有“从新节点一路到根”的这条祖先链，因为只有这些节点的高度可能变化；兄弟子树、侄子子树完全没动，高度不变。更新的方向必须是自底向上：先更新新节点父节点的高度，再往上更新祖父，直到根。每到一个节点，做四件事：

1. 用 h = 1 + max(h(左), h(右)) 重新计算高度；
2. 用 bf = h(左) - h(右) 重新计算平衡因子；
3. 如果 |bf| = 2，此节点失衡，立即停止向上——它就是最小失衡子树的根（第 2 节详述）；
4. 如果该节点高度没有变化，也可以提前停止——它上面的祖先高度一定也没变，平衡因子自然也没变。

举一个具体例子。在 1.2 那棵树里插入 5：5 比 10 小，成为 10 的左孩子。10 的高度从 0 变成 1，bf 从 0 变成 +1；20 的左子树（以 10 为根）高度从 0 变成 1，右子树 25 还是 0，所以 20 的高度从 1 变成 2，bf 从 0 变成 +1；30 的左子树（以 20 为根）高度从 1 变成 2，右子树 40 还是 0，于是 30 的高度从 2 变成 3，bf 从 0 变成 +2——失衡了！

沿插入路径向上，每个祖先的 bf 都只改变 1：插入发生在左子树就 +1、发生在右子树就 -1，所以第一次失衡必然是 ±2，绝不可能是 ±3 或更大。

注意一个细节：这个例子里，沿着插入路径向上，每个祖先的 bf 都朝着同一方向变了 +1，因为插入发生在每个祖先的左子树里；如果插入发生在某个祖先的右子树里，那个祖先的 bf 就会 -1。也就是说，一次插入不会让 bf 跳跃式变化，每个祖先的 bf 至多改变 1。这保证失衡节点第一次出现时 bf 只能是 ±2，不可能是 ±3 或更大——这个事实大大简化了旋转的分类，也是下一节“只需修一处”的数学基础。

1.4 更完整的视角：插入如何改变每个祖先的 bf

把“插入会怎样影响祖先的平衡因子”完整地总结成一张表，比零散举例更清楚。设某祖先 A 在插入前的 bf 为 b，插入发生的位置是 A 的左子树：

插入前 A 的 bf	插入左子树后	结论
+1（左重）	+2	失衡候选，需要旋转
0	+1	合格，只是变左重
-1（右重）	0	合格，而且更平衡了

插入发生在 A 的右子树时完全对称：-1 变 -2（失衡候选）、0 变 -1（合格）、+1 变 0（合格且更平衡）。

这张表藏了三个重要推论。第一，只有“插在本来就重的那一侧”的祖先才可能失衡：左重节点只有往左插才可能变成 +2，右重节点只有往右插才可能变成 -2。回想 5.6 的折返插入为什么总触发双旋，就是因为折返意味着新节点先后落在祖先的两侧，把平衡方向反复拉扯。第二，插入有时会让树“更平衡”：当新节点落在轻的一侧，bf 从 ±1 回到 0。所以“插入必然让树更歪”是错觉，AVL 真正检查的是“有没有歪过头”。第三，bf 从 0 变成 ±1 的节点是“预备失衡者”：下一次再往同一侧插，它就会升到 ±2；下一次插到另一侧，它又回到 0。连续的有序插入之所以危险，正是因为它们每次都往同一个方向“攒”预备失衡者，攒到某一层就一起爆发出 ±2——第 5 节走查时你会亲眼看到这个“攒”的过程。

2 失衡的发现：找到“最小失衡子树”

2.1 自底向上：沿插入路径回查

插入完成、高度和平衡因子逐层更新之后，AVL 树的下一个动作是发现失衡。做法非常朴素：从新插入的节点出发，沿着父指针一路向上，逐个检查祖先的平衡因子，找到第一个 |bf| = 2 的节点。这个节点就是整棵树上失衡最深、位置最低的那个失衡者，我们把它叫作“最小失衡子树的根”。

为什么是“第一个”？因为在它下面的所有节点，平衡因子都还是 {-1, 0, +1}——它们要么根本没受插入影响，要么虽然高度变了但还在合格范围内。而在它上面的祖先，插入导致的高度变化在到达它这里时已经被发现并截停：我们从下往上检查，遇到第一个失衡者就停下，所以它的祖先还没来得及被检查，也根本不需要被检查。一句话：最小失衡子树是“插入引发的失衡风波”波及到的最高节点以下、最靠近新节点的那个失衡区域。

用一张图把“回查路径”画出来。下面的树里，我们插入 5 后，从 5 的父节点 10 开始向上检查：

检查顺序是 5 → 10 → 20 → 30：5、10、20 都合格，到 30 发现 bf = +2，立刻停下。注意，我们不会继续检查 30 的父节点——并不是“上面没检查过所以可能还有问题”，而是根据第 1.3 节的单调性，30 是插入路径上第一个高度发生“超限”变化的节点，只要把以 30 为根的子树修好，上面就恢复原状。这个断言不是侥幸，下一小节给出严谨论证。

2.2 为什么只需要修这一处？

这是 AVL 插入里最容易被忽略、却最值得深挖的一个问题：为什么修好最小失衡子树，整棵树就平衡了？ 我们分三步证明。

第一步，旋转前的高度关系。 设最小失衡子树根为 X，插入前 X 的高度为 h+1，它是合格的（bf = ±1，左右子树高度分别为 h 和 h+1 或相反，较大者是 h+1）。插入发生在 X 的较矮一侧，使那侧子树高度从 h 变成 h+1，于是 X 的 bf 变成 ±2，X 的高度变成 h+2。在 X 之下的所有子树仍然合格，因为它们没有被破坏或已经被更新正确。

第二步，旋转后的高度关系。 第 3 节会详细展示四种旋转，但这里先给出共同结论：一次旋转（或双旋）之后，以 X 为根的子树的“新根”高度恰好是 h+1，等于插入前 X 的高度，而且整棵子树内部的每个节点都重新合格。这个“高度恢复”不是巧合，而是旋转设计的核心目标——旋转在本质上就是“把过高的那一侧抬起来、把过矮的那一侧放下去”，让整棵子树缩回原来的高度。

第三步，向上传播为零。 X 上面的祖先只关心“我的这个孩子子树高度是多少”。插入前它是 h+1，插入后旋转完它又是 h+1，所以祖先们看到的子树高度和插入前一模一样，它们的高度、平衡因子全部保持不变，自然全部合格。于是整棵树恢复平衡。

这三步合起来，就是 AVL 插入最优雅的地方：问题被局部化了。BST 插入沿着一条 O(log n) 的路径向下，回溯更新也沿着同一条路径向上，但真正的“手术”只发生在路径上的一个节点，且旋转次数是 O(1)。对比一下第 10 篇会讲的删除：删除会让子树高度减小，旋转后高度未必恢复，所以失衡可能“向上传染”，一次删除最多需要 O(log n) 次旋转——到那时你会更加珍惜插入的这份“一次就够”。

2.3 先看形状，再定旋转：失衡节点与孩子的 bf

找到失衡节点 X 后，光知道“X 失衡了”还不够，还要看失衡方向和插入落在哪一侧，才能决定用哪种旋转。判断依据是 X 的 bf 符号，以及 X 的那个“较重的孩子”自己的 bf 符号。约定记号：

• X 为最小失衡子树的根；
• Y 为 X 较重的那个孩子（bf 为 +2 时是左孩子，bf 为 -2 时是右孩子）；
• 根据插入发生在 Y 的哪一侧，总共有四种组合。

先给出总览表，后面四节逐一展开：

失衡类型	X 的 bf	Y 的 bf	形状描述	修复动作
LL	+2	+1（或 0）	插入在左孩子的左子树	右单旋
RR	-2	-1（或 0）	插入在右孩子的右子树	左单旋
LR	+2	-1	插入在左孩子的右子树	先左旋，再右旋
RL	-2	+1	插入在右孩子的左子树	先右旋，再左旋

字母缩写 LL、RR、LR、RL 的含义：第一个字母表示“X 的哪一侧重”，第二个字母表示“Y 的哪一侧重”。LL 就是 Left-Left：左孩子的左子树太高；LR 就是 Left-Right：左孩子的右子树太高。这个命名法是所有教材通用的，记熟之后，看到树形就能脱口而出对应的旋转。有一种常见的困惑：“为什么 LR 不叫 RL？”因为命名看的是“重的一侧”，不是旋转的顺序；LR 的修复顺序是先左旋后右旋，恰好和名字相反，别被绕进去。

一个补充细节：LL 型里 Y 的 bf 可以是 +1 也可以是 0。Y 的 bf 为 0 的情形通常出现在删除后的修复（第 10 篇），插入场景里 Y 的 bf 一般是 +1；但代码层面两种都按同一套旋转处理，所以实现时不需要区分。RR 型同理，Y 的 bf 可以是 -1 或 0。

命名看的是“重的一侧”而不是旋转顺序：LR 是先左旋后右旋，与名字相反；RL 则先右旋后左旋。记住 X 与 Y 的符号，就能一眼判断该走哪条分支。

这张总览图把四种失衡的形状并排放在一起，方便对比。接下来的第 3 节，我们一节一组，把每种失衡的“前、后、修好”三张图全部画出来，并仔细交代三个子树怎么搬家。

2.4 为什么“非祖先节点”永远不可能失衡

还有一个经常被忽略、但值得讲透的事实：插入 5 之后，为什么只需检查 5 的祖先链，而 5 的兄弟、堂兄弟、以及整棵树的另一侧都能直接跳过？因为插入操作只改变了插入路径上的指针：递归向下时，路径上的每个祖先都把左或右孩子指针指向递归返回的新子树；路径之外的节点，指针一个都没动。指针没动，子树内容就没变，高度和平衡因子自然不变。换句话说，失衡风波只可能沿着插入路径传播，路径之外的节点连“被波及”的资格都没有。这不是约定俗成的习惯，而是二叉树指针结构决定的必然。

由此还能推出一个工程上的好结论：回溯检查的代价与树高同阶，而 AVL 树高是 O(log n)，所以插入的“体检”开销天然是 O(log n)。如果有一天看到某份代码在插入后对整个树重新算一遍所有节点的高度，那它要么是教学演示，要么是没想清楚局部性——正确的做法永远只回溯一条路径。

2.5 发现失衡的复杂度

把“发现”这一步的成本也算清楚：插入本身沿路径向下走 O(h) 步；回溯时从新节点向根逐个检查，最多也是 O(h) 个祖先，每个祖先做两次高度读取、一次减法、一次比较，全是 O(1)。所以“发现失衡”的总代价是 O(h)。在 AVL 树里 h = O(log n)，于是发现过程是 O(log n)。再叠加修复阶段的常数次旋转，插入整体就是 O(log n)。这个结论值得记住一个不等式：回溯的成本 = 树高 = O(log n)，旋转的成本 = O(1)。前者来自“必须检查所有可能受影响的祖先”，后者来自“只需修最小失衡子树”。两句话合在一起，就是 AVL 插入复杂度分析的完整骨架。

3 四种失衡与旋转：左旋、右旋、双旋

3.1 LL 失衡：右单旋

形状。 LL 型失衡长这样：失衡节点 X 的 bf = +2，它的左孩子 Y 的 bf = +1，插入发生在 Y 的左子树里。也就是说，从 X 出发，往左走一步、再往左走一步，就到了新节点所在的区域。X 的左侧“叠了两层高”，像一根向左倾斜的竹竿。识别口诀：“插在左子的左子树 → LL → 右单旋”。

三个子树。 为了讲清楚旋转，我们给这棵子树里的三棵独立子树编号：

• T1：Y 的左子树，插入发生在这里，它是三者中最高的，高度为 h；
• T2：Y 的右子树，高度为 h-1；
• T3：X 的右子树，高度为 h-1。

插入前 X 的高度是 h+2（因为 T1 高度 h，加上 Y、X 两层），平衡因子 +2。Y 的平衡因子是 +1（T1 比 T2 高 1）。下面这张图是失衡时的完整样子：

右单旋怎么做。 右单旋（rotateRight）的物理动作是：把 Y 提起来当这棵子树的新根，让 X 降级成为 Y 的右孩子，同时把 Y 原来的右子树 T2 过继给 X 当左孩子。T1 继续挂在 Y 的左边，T3 继续挂在 X 的右边。三个关键移动：

1. Y 的右指针指向 X；
2. X 的左指针指向 T2（Y 原来的右子树）；
3. T1、T3 原封不动。

旋转后这棵子树的根变成了 Y，高度变成 h+1，正好等于插入前 X 的高度——这就是 2.2 节说的“高度恢复”。为什么 T2 要过继给 X 当左孩子，而不是丢掉或者挂到别处？因为 BST 性质要求：T2 里的所有值都大于 Y（它在 Y 的右子树里）且小于 X（它在 X 的左子树里）。旋转后 Y 成了 X 的左孩子，T2 恰好是“大于 Y、小于 X”的那一段，挂到 X 的左边完美保持“左小右大”。这恰恰是旋转最精妙的地方：它只改变节点间的父子关系，不改变中序遍历序列，所以 BST 性质自动成立。

旋转后 Y 的平衡因子：左 T1（h）对右 X（h），差 0；X 的平衡因子：左 T2（h-1）对右 T3（h-1），差 0。整棵子树高度为 h+1，与插入前一致，所有祖先无需任何处理。如果 T1、T2、T3 再矮一些（比如它们不是完整子树而是叶子或空），计算方式完全一样，只是 h 的取值不同。

为什么叫“右单旋”？ 因为从视觉上看，整棵子树绕着一个轴“向右倒”了一下：原来在左边的 Y 升到顶部，原来在顶部的 X 被甩到右下。也可以理解为“顺时针旋转”。与之对称的左单旋就是逆时针，下一小节登场。

3.2 RR 失衡：左单旋

形状。 RR 型是 LL 的镜像：失衡节点 X 的 bf = -2，它的右孩子 Y 的 bf = -1，插入发生在 Y 的右子树里。从 X 出发，往右走一步、再往右走一步，就到插入区域。识别口诀：“插在右子的右子树 → RR → 左单旋”。

三个子树。 编号与 LL 对称：

• T3：Y 的右子树，插入发生在这里，高度为 h；
• T2：Y 的左子树，高度为 h-1；
• T1：X 的左子树，高度为 h-1。

失衡时 X 的 bf = -2，Y 的 bf = -1，X 的高度为 h+2：

左单旋怎么做。 左单旋（rotateLeft）与右单旋完全对称：把 Y 提起来当新根，让 X 降级成为 Y 的左孩子，把 Y 原来的左子树 T2 过继给 X 当右孩子；T1 留在 X 左边，T3 留在 Y 右边。三个关键移动：

1. Y 的左指针指向 X；
2. X 的右指针指向 T2（Y 原来的左子树）；
3. T1、T3 原封不动。

T2 里的值都小于 Y（在 Y 左子树里）且大于 X（在 X 右子树里），旋转后它挂在 X 的右边，恰好填进“大于 X、小于 Y”的区间，BST 性质继续成立。旋转后子树高度恢复为 h+1：

旋转后 Y 的左子树 X 高 h、右子树 T3 高 h，bf = 0；X 的左 T1 与右 T2 都是 h-1，bf = 0。整棵子树高度 h+1，恢复原状。LL 和 RR 是“单旋”家族，各自只动一次父子关系；而接下来要讲的 LR、RL 则需要两次旋转才能摆平。

3.3 LR 失衡：先左旋，再右旋

形状。 LR 型失衡是 LL 的“变种陷阱”：失衡节点 X 的 bf = +2，它的左孩子 Y 的 bf 却是 -1，插入发生在 Y 的右子树里。从 X 出发往左走一步，再往右走一步，到达插入区域——所以它叫 Left-Right。识别口诀：“插在左子的右子树 → LR → 先左旋后右旋”。

为什么单旋救不了 LR？ 有人会想：X 左重，直接右单旋不就行了？我们来试一试。X 左重的原因是 Y 的右子树 Z 太高。如果直接对 X 做右单旋，Y 会升到顶部，X 变成 Y 的右孩子，Z 变成 X 的左孩子。可 Z 恰恰是最高的一棵子树（高度 h），X 的右子树 T4 只有 h-1，于是 X 变成“左高右低”，bf = +1；再看新根 Y：左子树 T1 高 h-1，右子树 X 高 h+1，bf = -2——失衡没有消失，只是从 X 转移到了 Y！这正是 LR 被称为“陷阱”的原因：只做单旋，问题会原地打转。必须先化解 Y 的“右重”，把它变成标准的 LL 形状，再对 X 右单旋。

三个主角与四棵子树。 记 Z = Y 的右孩子，也就是插入所在子树的根。四棵独立子树：

• T1：Y 的左子树，高度 h-1；
• T2：Z 的左子树；
• T3：Z 的右子树；
• T4：X 的右子树，高度 h-1。

Z 的高度为 h，T2、T3 中至少有一棵高度为 h-1（另一棵可能矮一格，取决于插入落在 Z 的哪一侧）。为便于画图，下面的示意图把 T2、T3 画成等高 h-1，真实插入时其中一个会矮一格，但这不影响旋转的机械步骤，只影响旋转后个别节点的 bf 是 0 还是 ±1——两者都合格。

第一步：对 Y 做左单旋。 把 Y 看成“RR 失衡的根”，对它执行左单旋：Z 被提起来，Y 降为 Z 的左孩子，Z 原来的左子树 T2 过继给 Y 当右子树。旋转后 Z 的左孩子是 Y（高度 h），右孩子是 T3（h-1），所以 Z 的 bf = +1，整棵子树变成标准的 LL 形状——X 的左孩子现在是 Z，而 Z 左重。这一步的实质是：先把“左子树的右重”熨平，让失衡方向统一为 LL。

第二步：对 X 做右单旋。 现在形状已经是 LL，套用 3.1 节的标准流程：把 Z 提起来当新根，X 降为 Z 的右孩子，Z 原来的右子树 T3 过继给 X 当左子树。最终形态：Z 是根，左孩子是 Y（Y 带着 T1、T2），右孩子是 X（X 带着 T3、T4）。

验算最终高度：Y = 1 + max(T1, T2) = h，X = 1 + max(T3, T4) = h，Z = 1 + max(Y, X) = h + 1，正好等于插入前 X 的高度。中序遍历的检查也交给读者：旋转前后序列都是 T1、Y、T2、Z、T3、X、T4，一个字都没变。LR 双旋的名字和动作顺序相反（名字说 LR，动作是先左后右），这是初学者最容易记混的地方，务必用口诀“先左后右”锁死动作顺序。

3.4 RL 失衡：先右旋，再左旋

形状。 RL 是 LR 的镜像：失衡节点 X 的 bf = -2，它的右孩子 Y 的 bf = +1，插入发生在 Y 的左子树里。从 X 出发往右走一步，再往左走一步，到达插入区域。识别口诀：“插在右子的左子树 → RL → 先右旋后左旋”。

同理，直接对 X 左单旋也救不了 RL：Y 会升顶、X 降为 Y 的左孩子、Z 过继给 X 当右孩子，结果 X 变成右重（bf = -1），Y 变成左重（bf = +2），失衡从 X 转移到 Y。必须先对 Y 右旋，把形状熨成 RR，再对 X 左旋。

主角与子树。 记 Z = Y 的左孩子，T1 = X 的左子树（h-1），T2 = Z 的左子树，T3 = Z 的右子树，T4 = Y 的右子树（h-1），Z 高度为 h。失衡时：

第一步：对 Y 做右单旋。 把 Y 看成“LL 失衡的根”，对 Y 右旋：Z 升顶，Y 降为 Z 的右孩子，Z 原来的右子树 T3 过继给 Y 当左子树。旋转后 Z 的右孩子是 Y（高度 h），左孩子是 T2（h-1），bf = -1，变成标准 RR 形状——X 的右孩子现在是 Z，Z 右重。

第二步：对 X 做左单旋。 形状已经是 RR，套用 3.2 节标准流程：Z 升顶当新根，X 降为 Z 的左孩子，Z 原来的左子树 T2 过继给 X 当右子树。最终形态：Z 是根，左孩子是 X（带着 T1、T2），右孩子是 Y（带着 T3、T4）。

至此四种旋转全部登场。把它们放到一张“识别决策树”里，代码只需要四个分支：

把这张决策树背下来，旋转的选择就不再是玄学：先看 X 往哪边歪，再看 X 那个“壮孩子”往哪边歪，两笔一画，类型立现。

把这棵决策树背下来，旋转的选择就不再是玄学：先看 X 往哪边歪，再看 X 那个“壮孩子”往哪边歪，两笔一画，类型立现。

3.5 旋转为什么永远安全：中序不变原理

旋转里最让人不放心的问题，是“搬来搬去会不会把 BST 性质弄坏”。答案是不会，而且可以给出一个非常漂亮的证明：旋转不改变中序遍历序列。以 LL 右单旋为例。旋转前，以 X 为根的子树的访问顺序是 T1 → Y → T2 → X → T3：先进入 Y 的左子树 T1，访问 Y，再访问 Y 的右子树 T2，回到 X，最后访问 X 的右子树 T3。旋转后，Y 是根、X 是 Y 的右孩子、T2 从 Y 的右子树搬到了 X 的左子树，中序变成：T1（还是 Y 的左子树）→ Y → T2（现在挂在 X 的左子树，访问完 T2 才轮到 X）→ X → T3。两种形态的序列逐项完全相同。而“中序严格递增”是 BST 的充要条件（第 7 篇的结论），所以只要旋转前后中序序列一致，BST 性质就自动保持。RR、LR、RL 同理可证：单旋保持中序，双旋是两次单旋的组合，自然也保持。

用一个具体数字例子把 LL 完整走一遍。设 X = 50、Y = 30，T1 是一棵以 20 为根、左孩子 10 的小树，T2 = 40，T3 = 60。失衡前：

中序遍历：10、20、30、40、50、60。右单旋之后，30 成为新根，50 降为 30 的右孩子，40 过继给 50 当左孩子：

再验一遍中序：进入 20 子树，得到 10、20；访问 30；进入 50 的左子树 40，访问 40；访问 50；最后 60。序列还是 10、20、30、40、50、60。键没有多、没有少、顺序没有变，只是骨架换了——这就是“旋转安全”的完整含义。日后无论遇到多复杂的双旋，只要记住“旋转 = 重新挂接，不改变中序”，就可以放心推导每一种子树搬家方案。

3.6 另一种理解：旋转就是把“中间值”抬上来

如果觉得“先左后右”“先右后左”容易记混，这里提供一个更高层的视角：旋转的实质，是把失衡子树中序序列的“中间值”抬升为根。以最简单的情形看：X、Y、插入的新节点，三个值按中序排列是“新节点、Y、X”（LL 时新节点在 Y 左侧）。Y 恰好是三个值里的中位数，右单旋把 Y 提为根，X 落到右侧，整棵子树立刻在“值域”上左右均衡。RR 同理，Y 也是中位数。再看 LR：中序序列是 T1、Y、T2、Z、T3、X、T4，Z 才是真正的中间值——所以第一步左旋先把 Z 抬到 Y 的位置，第二步右旋再把 Z 抬到根。RL 完全对称。把“抬中位数”和“先整队再正骨”两个画面叠加起来，双旋就不再是死记硬背的两步，而是“先让中位数就位，再让它登顶”的自然过程。

这个视角还有一个实际用途：面试或写文章画图时，如果想快速验证某种旋转方案是否正确，不需要逐指针追踪，只需要检查“新根的键是不是整个子树中序序列的中间值”。如果是，树形大概率正确；如果不是，一定哪里画错了。旋转的所有细节都会在“中位数登顶”这个目标下变得有条理。

4 旋转的代码：TypeScript 实现与逐行解释

4.1 节点与三个基础函数

原理讲透了，代码其实非常短。AVL 节点只需要在 BST 节点的基础上多一个 height 字段；平衡因子不单独存储，需要时用“左高减右高”现算，省内存也避免两处数据不一致。先看节点定义和三个基础函数：

type MaybeNode = TreeNode | null;

class TreeNode {
  key: number;
  left: MaybeNode = null;
  right: MaybeNode = null;
  height = 0; // 叶子高度为 0，空子树高度约定为 -1

  constructor(key: number) {
    this.key = key;
  }
}

// 空子树高度是 -1，这是全文统一的口径
function getHeight(node: MaybeNode): number {
  return node === null ? -1 : node.height;
}

// 用左右孩子的高度重算当前节点的高度
function updateHeight(node: TreeNode): void {
  node.height = 1 + Math.max(getHeight(node.left), getHeight(node.right));
}

// 平衡因子：左高减右高，正数表示左重
function balanceFactor(node: TreeNode): number {
  return getHeight(node.left) - getHeight(node.right);
}

逐行解释：

1. MaybeNode 是一个类型别名：树里的指针要么指向节点，要么是 null。在 TypeScript 里把它写清楚，getHeight 才能安全地处理空指针。
2. TreeNode 有四个字段：key 存键值，left、right 存左右孩子，height 存“以该节点为根的子树高度”。构造函数里 height 初始化为 0，因为新节点一定是叶子。
3. getHeight 是唯一的“读高度”入口：空节点返回 -1，非空节点返回它记录的 height。所有需要高度的代码都必须走这个函数，直接读 node.height 会在节点为 null 时崩溃，也会忘记 -1 的约定。
4. updateHeight 用公式 1 + max(左高, 右高) 重算高度。它依赖两个孩子的高度是“新鲜”的——所以调用顺序很关键，详见 4.3。
5. balanceFactor 就是第 1 节的定义：左高减右高。返回 +2 表示严重左重，返回 -2 表示严重右重。

4.2 两个旋转函数

// 右单旋：以左孩子为轴，把当前节点“甩”到右下
function rotateRight(y: TreeNode): TreeNode {
  const x = y.left;           // x 是 y 的左孩子，旋转后成为新根
  const t2 = x!.right;        // t2 是 x 的右子树，需要搬家
  x!.right = y;               // y 变成 x 的右孩子
  y.left = t2;                // t2 过继给 y 当左孩子
  updateHeight(y);            // 先更新“下沉”的 y
  updateHeight(x!);           // 再更新“上升”的 x
  return x!;                  // 返回新根，让上层接住
}

// 左单旋：以右孩子为轴，把当前节点“甩”到左下
function rotateLeft(x: TreeNode): TreeNode {
  const y = x.right;          // y 是 x 的右孩子，旋转后成为新根
  const t2 = y!.left;         // t2 是 y 的左子树，需要搬家
  y!.left = x;                // x 变成 y 的左孩子
  x.right = t2;               // t2 过继给 x 当右孩子
  updateHeight(x);            // 先更新“下沉”的 x
  updateHeight(y!);           // 再更新“上升”的 y
  return y!;                  // 返回新根
}

逐行解释：

1. rotateRight(y) 的参数名为什么叫 y？因为调用场景里，被旋转的节点正是 3.1 节那个“失衡节点 X”——但在代码里，我们传入的是将要降级的旧根，也就是 X。为了让代码和图示一一对应，可以把参数名直接写成 x，然后把左孩子取名 y；这里用 y 当参数名只是为了强调“右旋发生在 y 与其左孩子 x 之间”，两种命名读起来都能理解。重点是记住指针改动的三行：x.right = y、y.left = t2、t2 = x.right 的取值要在改写之前完成。
2. const x = y.left 和 const t2 = x!.right 必须先取值再改指针。如果先执行 y.left = ...，x 的引用就找不到了。! 是非空断言：既然走到了旋转分支，y 一定有左孩子 x，TypeScript 编译器不知道这一点，我们用 ! 告诉它“这里不会是 null”。
3. x.right = y 把旧根变成新根的右孩子；y.left = t2 把 t2 过继给 y。这两行做完，父子关系反转，但 BST 性质仍然成立——T2 里所有键大于 y 且小于 x，挂在 x 的左子树下正好。
4. 高度更新顺序绝不能错：先更新 y（现在它变成孩子了），再更新 x（现在它变成根了）。如果先更新 x，x 用的还是 y 的旧高度，算出来的高度是错的。这是一个非常隐蔽的 bug 源：代码逻辑看着没问题，但树里某些节点的高度永远差 1，导致后续平衡因子判断全盘错乱。记住口诀：先更新沉下去的孩子，再更新浮上来的根。左旋同理，先 updateHeight(x) 再 updateHeight(y)。
5. 函数返回新根。为什么必须返回？因为树的指针是单向的，旋转改变了子树的根，父节点必须知道“我的孩子换人了”。递归插入里，这个返回值被父节点的 left = insert(...) 或 right = insert(...) 接住，见 4.4。

4.3 失衡检查与四种旋转的分发：rebalance

// 对以 node 为根的子树做一次“体检 + 修复”，返回修复后的新根
function rebalance(node: TreeNode): TreeNode {
  updateHeight(node); // 先刷新自己的高度
  const bf = balanceFactor(node);

  if (bf > 1) {
    // 左重：要么 LL（左孩子不右倾），要么 LR（左孩子右倾）
    if (balanceFactor(node.left!) < 0) {
      node.left = rotateLeft(node.left!); // LR：先对左孩子左旋
    }
    return rotateRight(node); // LL（或 LR 第二步）：再对当前节点右旋
  }

  if (bf < -1) {
    // 右重：要么 RR（右孩子不左倾），要么 RL（右孩子左倾）
    if (balanceFactor(node.right!) > 0) {
      node.right = rotateRight(node.right!); // RL：先对右孩子右旋
    }
    return rotateLeft(node); // RR（或 RL 第二步）：再对当前节点左旋
  }

  return node; // 合格，原样返回
}

逐行解释：

1. rebalance 的开头先 updateHeight(node)。调用它时，node 的两个孩子刚刚被递归处理完，高度都是最新的，所以这里刷新出的高度是可信的。这行代码也让 rebalance 成为“插入回溯的唯一入口”：无论 node 是否失衡，它的高度都被修正了。
2. bf > 1 是左重。此时要看左孩子的倾向：如果左孩子右倾（bf < 0），说明是 LR，先对左孩子 rotateLeft，把它熨成 LL；如果左孩子不右倾（bf ≥ 0，即 +1 或 0），说明是 LL，直接进入右旋。无论哪种，最后一行 return rotateRight(node) 都会执行——LR 走的是“先左后右”，LL 走的是“只右”。
3. bf < -1 是右重，完全对称：右孩子左倾（bf > 0）就是 RL，先对右孩子 rotateRight，再对当前节点 rotateLeft；右孩子不左倾就是 RR，只左旋一次。
4. 注意四个分支里，对孩子的旋转结果都赋回给了 node.left / node.right。这一步不能省：LR 第一步旋转后，子树的根从 Y 变成了 Z，如果只调用不赋值，node 的左指针还指着旧的 Y，第二步右旋就找错了对象。
5. 最后返回“处理后的新根”。合格时返回原 node；发生旋转时返回新根。这个返回值一路上交给上层的赋值语句，保证整棵树的指针链完整。

4.4 完整插入：BST 插入 + 回溯修复

function insert(root: MaybeNode, key: number): MaybeNode {
  // 第一步：标准 BST 查找并插入
  if (root === null) {
    return new TreeNode(key); // 找到空位，创建叶子节点
  }
  if (key < root.key) {
    root.left = insert(root.left, key); // 去左子树，接住可能的新根
  } else if (key > root.key) {
    root.right = insert(root.right, key); // 去右子树，接住可能的新根
  } else {
    return root; // 键已存在：不插入重复值，原样返回
  }
  // 第二步：回溯路上对每个祖先做“高度更新 + 失衡修复”
  return rebalance(root);
}

整个插入函数只有十行左右，却完成了第 5 节要手绘一整条流程的所有工作。逐行解释：

1. root === null 是递归基：我们顺着 BST 的查找路径走到了空位，在这里创建新叶子并返回。新节点高度为 0，左右孩子为 null。
2. key < root.key 走左子树。关键在赋值：root.left = insert(root.left, key)。内层递归返回的可能是原来的左孩子，也可能是旋转后的新根，必须赋回来，否则旋转结果会丢。右子树同理。
3. key === root.key 时直接返回 root，不插入重复值。这是 AVL 的常见约定（和 BST 一样）；如果业务需要支持重复键，一般会在节点里加计数器或允许一侧相等，而不是真的插入两份。
4. 递归返回时，每一层都执行 rebalance(root)。这天然实现了第 2 节的“自底向上回溯”：最深处的调用最先返回，所以最靠近新节点的祖先最先被 rebalance；一旦某一层旋转后高度恢复原状，更上层的 rebalance 会发现 bf 合格、高度不变，直接原样返回——但这并不会提前终止递归，只是额外做了几次 O(1) 检查。整体开销依然是 O(log n)。
5. 如果你把 rebalance 改成 updateHeight 之后直接 return node，这段代码就退化成了第 7 篇的普通 BST 插入——这正是理解 AVL 的另一个视角：AVL 插入 = 普通 BST 插入 + 回溯路上的自动体检。

4.5 常见坑位清单

写 AVL 代码时，最容易翻车的不是旋转本身，而是围绕旋转的细节。把四个高频坑位列在这里，调试时可以逐条排查：

1. 空子树高度算错：把 null 的高度当 0，而不是 -1。后果是“只有一个孩子的节点”被误判为平衡，树悄悄退化。检查 getHeight 是否对 null 返回 -1。
2. 旋转后更新高度的顺序反了：先更新新根，再更新旧根。后果是高度差 1，平衡因子连续出错，树越修越歪。记住“先孩子、后根”。
3. 忘了把旋转结果赋回父指针：rotateLeft(node.right) 写成了裸调用。后果是树的结构在局部变了，但父节点还指着旧根，整棵树从那里断开。检查所有 left =、right = 赋值。
4. LR/RL 只做单旋：看到左重就右旋，忽略左孩子的 bf 符号。后果是失衡从 X 转移到 Y，问题原地打转。检查 rebalance 里是否先看了孩子的 bf。

4.6 递归实现的边界与迭代实现

上面的代码是递归写法，递归深度等于树的高度，而 AVL 高度是 O(log n)，所以调用栈深度不会超过大约 1.44 log₂n 层——在 n 为百万时也就二三十层，完全不用担心爆栈。这也是平衡树的一个隐性好处：递归深度本身就受平衡保证，不会像退化 BST 那样在插入 n 个节点时递归 n 层。

如果出于性能或规避递归的考虑，也可以改成迭代：先用循环完成 BST 插入（显式维护一个路径栈，记录经过的所有节点），插入后从栈顶开始逆序弹出，逐个执行 updateHeight 和 rebalance，并把每个节点的孩子指针更新为子问题返回的新根。迭代版与递归版在逻辑上完全等价，只是把“系统调用栈”换成了“显式栈”。代价是代码更长、更容易在指针更新上出错；收益是避免了函数调用开销，在极高频的插入场景下可能快几个百分点。工程上多数语言（C++、Java、Go、TypeScript）的平衡树实现反而更常写迭代版，因为可以省掉递归调用并更精细地控制内存；教学场景用递归版更直观，因为“先递归插入、后回溯修复”和算法描述一一对应。

另外提一个泛化问题：本文的 key 是 number，比较用 < 和 >。如果键是字符串或自定义对象，只要把比较抽象成一个函数 compare(a, b) 返回负数、零、正数，插入、查找、旋转的逻辑一行都不用改。AVL 只关心“比较结果”，不关心键的具体类型——这正是二叉树结构独立于数据类型的体现。遇到重复键时，除了“直接返回”的写法，还可以在节点里加一个 count 字段记录重复次数，查询时按计数处理；只要不真正插入两份，平衡性就不受影响。

4.7 怎么验证写对了：三条不变式与随机测试

AVL 代码的 bug 很难靠肉眼一次看清，好在它有非常强的“不变式”可以用来自动验证。写完实现后，建议先写三个检查函数，再跑随机测试。

不变式一：BST 性质。 中序遍历结果必须严格递增。实现一个 inOrder(root) 收集所有键，断言每个相邻对都满足前一个小于后一个。这个检查能抓住大部分“旋转后指针挂错”的问题——只要中序乱了，树肯定错了。

不变式二：高度一致。 对每个节点，node.height 必须等于 1 + max(getHeight(left), getHeight(right))。递归检查整棵树，任何一处不满足，说明某个 updateHeight 漏调或顺序错了。这个检查尤其擅长发现“旋转后先更新了新根”的隐蔽错误。

不变式三：平衡因子合法。 对每个节点，balanceFactor(node) 必须落在 {-1, 0, +1}。这个检查最直接地验证 AVL 规则本身；一旦失败，把当时插入的键序列打印出来，就能复现出问题路径。

随机测试的经典写法是：循环几万次，每次随机生成一个键插入，插入后立刻跑一遍三条不变式；再随机删除（第 10 篇实现后），同样验证。再进一步，可以维护一个参考容器（比如语言标准库的有序集合）或简单数组，每轮操作后比较“AVL 树中序”和“参考排序结果”是否一致。这套“性质验证 + 对照验证”的组合，能把旋转类的实现错误压缩到几分钟内定位。很多教材只讲怎么写，不讲怎么验，但工程上“写得快、验得狠”才是真实需求。

代码已经齐了。接下来我们用一组真实数字把整个流程走一遍，看看插入、失衡、旋转是如何一环扣一环发生的。

5 完整插入流程：把 [10, 20, 30, 40, 50, 25] 走一遍

理论、图、代码都有了，现在把它们拧成一股绳。我们从空树开始，依次插入 10、20、30、40、50、25，每一轮都执行“标准 BST 插入 → 沿路径更新高度 → 遇到失衡就旋转”。每一步的状态图都画出来，特别标出每个节点的平衡因子，失衡节点用红色语义强调。

5.1 第 1、2 步：插入 10 和 20

插入 10：树为空，10 直接成为根，高度 0，bf = 0。插入 20：20 比 10 大，成为 10 的右孩子；10 的高度从 0 更新为 1，bf = 0 - 1 = -1，合格。此时树是“单边右倾”的，但 AVL 允许 bf = -1，所以无需旋转：

这一阶段最容易产生错觉：树已经“歪”了，为什么不动手修？因为 AVL 的规则从来不是“不允许歪”，而是“不允许歪超过 1”。10 的右子树比左子树高 1，完全合法。真正的警报要等第三个数。

5.2 第 3 步：插入 30，触发第一次旋转（RR）

插入 30：30 比 20 大，成为 20 的右孩子。回溯更新：20 的高度从 0 变 1，bf = -1，合格；10 的高度从 1 变 2，bf = 0 - 2 = -2，失衡！沿路径检查 10 的右孩子 20：bf = -1，右重。根据 3.2 节，这是标准的 RR 型——插在右孩子的右子树，执行左单旋：

（图中 20 的左孩子为空，用“空”占位，帮助看清三棵子树的关系。）对 10 执行 rotateLeft(10)：20 升为新根，10 成为 20 的左孩子，20 原来的左子树（空）过继给 10 当右子树。旋转后：

10 的 bf 从 -2 回到 0，20 的 bf 也是 0，子树高度从 2 恢复到 1（以 20 为根的子树高度：左右都是 0，h=1），与插入前 10 的高度一致，上面的祖先（此时没有）无需处理。

5.3 第 4、5 步：插入 40 和 50，第二次旋转（RR）

插入 40：40 比 30 大，成为 30 的右孩子。30 高度变 1，bf = -1；20 高度变 2，bf = -1（左 10 高 0，右 30 高 1）。全部合格，无需旋转。树变成：

插入 50：50 比 40 大，成为 40 的右孩子。回溯：40 高度变 1，bf = -1，合格；30 的左孩子是空（-1）、右孩子 40 高 1，高度变 2，bf = 0 - 1 = -2，失衡！30 的右孩子 40 的 bf = -1，右重，又是 RR 型，对 30 左单旋：

rotateLeft(30)：40 升为这棵子树的新根，30 成为 40 的左孩子，40 原来的左子树（空）过继给 30 当右子树。旋转后 20 的右孩子从 30 变成 40：

现在整棵树高度为 2，节点数 5，所有 bf 都在 {-1, 0, +1} 内。细心的读者会发现：到这里，插入顺序 10、20、30、40、50 已经“制造”了两次 RR 旋转，每一次都是把新插入的那段链条折回树里。如果没有 AVL，这五个数已经是一根 4 层高的链了。

5.4 第 6 步：插入 25，触发最复杂的 RL 双旋

插入 25：25 比 20 大、比 40 小、比 30 小，成为 30 的左孩子。回溯更新：25 高度 0，bf = 0；30 的左孩子从空变为 25，高度从 0 变 1，bf = 1 - 0 = +1，合格；40 的左子树（以 30 为根）高度从 0 变 1，右子树 50 高 0，40 高度从 1 变 2，bf = +1，合格；20 的左子树 10 高 0、右子树（以 40 为根）高度从 1 变 2，20 高度从 2 变 3，bf = 0 - 2 = -2，失衡！这次失衡点不是 40 而是 20——注意最小失衡子树根是 20，尽管 40、30 也都“参与”了高度变化，但它们自己还合格。

判断旋转类型：失衡节点 20 右重（bf = -2），它的右孩子 40 左重（bf = +1），根据 3.4 节，这是 RL 型——插在右孩子的左子树，需要先对 40 右旋，再对 20 左旋。第一步，把 40 看成“LL 失衡的根”，对 40 执行右单旋：30 升为这棵子树的新根，40 降为 30 的右孩子，30 原来的右子树（空）过继给 40 当左子树；再把结果赋回 20.right：

这时 20 的右孩子变成了 30，而 30 右重（bf = -1），形状已经被熨成标准的 RR。第二步，对 20 左单旋：30 升为整棵树的新根，20 降为 30 的左孩子，30 原来的左子树 25 过继给 20 当右子树：

最终树的中序遍历仍是 10、20、25、30、40、50；两次 RR 单旋和一次 RL 双旋后，子树高度每次都恰好恢复，因此没有引发任何祖先的连锁失衡——这正是插入“只修一处”的直观体现。

最终树的形态是：根 30，左子树以 20 为根（左 10、右 25），右子树以 40 为根（右 50）。中序遍历验证：10、20、25、30、40、50，严格递增，BST 性质完好。所有节点 bf ∈ {-1, 0, +1}，整棵树高度 2。六个数字，两次 RR 单旋、一次 RL 双旋，每次旋转后子树高度都恰好恢复，祖先节点零连锁反应——这就是 AVL 插入的全貌。

5.5 如果插入顺序换成 [10, 20, 30] 会怎样？

走完上面六步，值得做一个对比实验：只插 10、20、30 三个数。第三步就会触发一次 RR 左旋，树变成 20 为根、10 和 30 分居左右。也就是说，同样是三个有序数字，裸 BST 长成三层的链，AVL 树把它折成了两层的完美二叉。这正是自平衡的意义：树不关心输入顺序，只关心自己是否健康。插入 25 那一步还揭示了一个更微妙的点：失衡的判定依据不是“插入位置离根有多远”，而是“插入路径上哪个祖先的 bf 先越界”——20 是最小失衡子树根，而 40、30 只是“帮凶”，这和第 2 节的局部化定理完全吻合。

想亲手拖拽、插入、观察旋转过程？下面的可视化实验室支持搜索算法的动态演示，可以把上面这组序列输进去，看着树一步步长成最终形态：

动手玩过之后，我们再从数学上回答最后一个大问题：为什么 AVL 树的高度一定是 O(log n)？

5.6 三个对照小实验：LL、LR、RL

主流程里出现的是 RR 和 RL。为了把四种旋转都练一遍，这里再加三个“三个数就能触发”的小实验——它们也揭示一个漂亮的规律：插入方向单调时触发单旋，插入方向折返时触发双旋。

实验一：插入 30、20、10，触发 LL。 30 先当根；20 成为左孩子，30 的 bf = +1；10 成为 20 的左孩子后，20 的 bf = +1，30 的 bf = +2，左孩子 20 左倾——LL，右单旋。旋转后 20 升根，10 和 30 分居左右：

实验二：插入 30、20、25，触发 LR。 前两步和实验一相同；25 插入后成为 20 的右孩子（因为它大于 20 小于 30）。此时 20 的 bf = -1，30 的 bf = +2，而左孩子 20 是右倾的——LR。第一步对 20 左旋，25 升为 30 的左孩子；第二步对 30 右旋，25 升根：

实验三：插入 10、30、20，触发 RL。 这是实验二的镜像：10 先当根，30 成为右孩子；20 插入后成为 30 的左孩子（大于 10 小于 30），30 的 bf = +1，10 的 bf = -2，右孩子 30 左倾——RL。第一步对 30 右旋，20 升为 10 的右孩子；第二步对 10 左旋，20 升根：

三个实验放在一起看，规律非常清晰：三个数按单调方向插入（升序 10、20、30 或降序 30、20、10），中间那个数最终成为根，触发的是单旋；三个数按折返方向插入（30、20、25 或 10、30、20），也是中间那个数成为根，但触发的是双旋。为什么折返一定要双旋？因为折返让“壮孩子”的重心朝向和 X 相反，单旋会把失衡从 X 推到 Y，只有先反向转一次把重心统一，再转一次才能根治。把“单调单旋、折返双旋”和“外折单旋、内折双旋”这两句口诀记在一起，四种旋转就齐了。

5.7 最终形态验算，以及和裸 BST 的逐轮对比

先给主流程 [10, 20, 30, 40, 50, 25] 的最终树做一次“全身体检”，把每个节点的高度和平衡因子都算一遍：

节点	左子树高度	右子树高度	节点高度	bf	是否合格
30（根）	1（以 20 为根）	1（以 40 为根）	2	0	是
20	0（10）	0（25）	1	0	是
40	-1（左孩子为空）	0（50）	1	-1	是
10	-1	-1	0	0	是
25	-1	-1	0	0	是
50	-1	-1	0	0	是

等一下，表里“40 的左子树高度”是 -1，因为最终树里 40 的左孩子为空——这正是 RL 双旋后 30 被“抽走”的结果。检查表的正确性本身也在练习读树：每读一棵子树，先问“它的根是谁、两个孩子是谁”，再套高度公式。

再把同样的插入序列分别喂给裸 BST 和 AVL 树，逐轮记录高度：

轮次	插入的键	裸 BST 高度	AVL 树高度	是否触发旋转
1	10	0	0	否
2	20	1	1	否
3	30	2	1	是（RR 左旋）
4	40	3	2	否
5	50	4	2	是（RR 左旋）
6	25	4	2	是（RL 双旋）

这张对照表是全文最浓缩的“为什么需要 AVL”的证据：同样的六个键，裸 BST 一路涨到高度 4，AVL 树始终被按在高度 2；裸 BST 的高度等于“当前最大链长”，AVL 的高度等于“当前数据量的对数”。如果数据继续按这个节奏插入一万个键，裸 BST 会退化成万层高塔，AVL 树依旧只有十几层。所谓自平衡，就是每一轮插入后都主动“按下去”，而不是等树长歪了再后悔。

5.8 第 6 步的插入路径复盘：RL 形状是怎么“攒”出来的

最后把第 6 步（插入 25）单独复盘一遍，因为它同时展示了“查找路径”和“失衡积累”两条线。插入 25 时，从根 20 出发：25 比 20 大，向右走到 40；25 比 40 小，向左走到 30；25 比 30 小，向左走到空位，成为 30 的左孩子。路径是 20 → 40 → 30，最终挂在 30 的左边。回溯时从下往上看：30 的左子树从空变成 25，bf 从 0 变 +1，合格；40 的左子树（以 30 为根）变高，bf 从 0 变 +1，合格；20 的右子树（以 40 为根）变高，bf 从 -1 变 -2，失衡。可以看到，25 不是直接“压垮”20 的，而是先在 30 和 40 身上各“存”了一份左重（+1），再通过 40 把第二份左重传到 20 的右子树，最终让 20 的右重从 -1 越界成 -2。这份“层层积累”正是 RL 形状的来历：失衡节点右重，但重孩子内部左重，因为插入方向在第二层拐了一个弯。以后遇到任何双旋，都可以用同样的复盘方法：把插入路径写出来，逐层看 bf 的变化，看“拐弯”发生在哪一层。

6 复杂度：高度被斐波那契锁死

6.1 最坏情况的构造：高度为 h 的“最瘪” AVL 树

要证明 AVL 树的高度是 O(log n)，一个自然的思路是反着问：给定高度 h，一棵 AVL 树至少要有多少个节点？ 如果“高度 h 至少需要 n(h) 个节点”，那么反过来，“n 个节点的高度至多是某个关于 n 的对数函数”。

设 n(h) 为一棵高度为 h 的 AVL 树的最少节点数。高度为 0 时，树只有一个节点，所以 n(0) = 1。高度为 1 时，至少要有根和一层孩子，两个节点就够（一个孩子高度 0，另一个为空），所以 n(1) = 2。现在看高度 h ≥ 2 的情况。根的两棵子树中，较高的一棵高度必须是 h-1，否则整棵树到不了 h；而 AVL 规则要求另一棵子树的高度至少是 h-2——它可以是 h-2、h-1 或更高，但不能再矮，再矮根的平衡因子就会超过 1。为了让节点数最少，较高的子树要取“高度 h-1 的最少节点树”，较矮的子树要取“高度 h-2 的最少节点树”。于是得到递推：

n(0) = 1
n(1) = 2
n(h) = n(h-1) + n(h-2) + 1   （h ≥ 2）

这里的“+1”是根节点自己。这个递推长得几乎和斐波那契数列一模一样，只是每一项都多加了 1。把它展开：

插一句常见疑问：较矮的那一侧为什么不能更低，比如 h-3？因为如果一侧是 h-1、另一侧是 h-3，根的平衡因子就是 (h-1) - (h-3) = 2，已经超过 AVL 允许的 1，根本不构成一棵合法的 AVL 树。所以 h-2 是矮侧的底线，“贴着底线构造”才能让节点数最少；任何比底线更矮的尝试，都会先违反平衡规则。反过来，如果两侧都取 h-1，节点数会更多（n(h-1) ≥ n(h-2)），那不是“最少构造”。这正是一个典型的“最坏情况分析”姿势：先画清合法区间，再在区间的边界上找极值。

h	0	1	2	3	4	5	6	7
n(h)	1	2	4	7	12	20	33	54

验证 n(2)：根加两棵单节点子树，共 3 个？不对——n(2) = n(1) + n(0) + 1 = 2 + 1 + 1 = 4。高度 2 的最少节点树长这样：根的两个孩子各带一个叶子，四个节点，正好是四层棋盘里的“漏斗”。（写表格时容易犯的错：以为高度 2 只要 3 个节点——根、左孩子、右孩子——但那棵树的左右子树高度都是 0，根的高度是 1，不是 2。）高度 3 需要 7 个节点：根的一侧是高度 2 的 4 节点树，另一侧是高度 1 的 2 节点树，再加根。把前几棵“最瘪 AVL 树”画出来：

这组树的节点数严格满足 n(h) = n(h-1) + n(h-2) + 1，与斐波那契数列只有“+1”之差，解出 n(h) = F(h+3) - 1，正是高度上界 1.44 log₂(n+2) 的由来。

这组树被称为“斐波那契树”，因为它们的节点数严格走斐波那契数列的变形。事实上可以证明 n(h) = F(h+3) - 1，其中 F 是标准斐波那契数列（F₀ = 0，F₁ = 1）。验算：h = 0 时 F₃ - 1 = 2 - 1 = 1；h = 1 时 F₄ - 1 = 3 - 1 = 2；h = 2 时 F₅ - 1 = 5 - 1 = 4；h = 3 时 F₆ - 1 = 8 - 1 = 7。全部吻合。

如果还想看一遍严格归纳：假设对一切 k < h 都有 n(k) = F(k+3) - 1，那么 n(h) = n(h-1) + n(h-2) + 1 = [F(h+2) - 1] + [F(h+1) - 1] + 1 = F(h+2) + F(h+1) - 1。斐波那契数列的核心恒等式是 F(m) + F(m-1) = F(m+1)，取 m = h+2 就得到 F(h+2) + F(h+1) = F(h+3)，于是 n(h) = F(h+3) - 1。基例 h = 0、h = 1 已经验过，归纳完成。这个证明的价值不只是“算出了一个公式”，而是确认了递推式与斐波那契的对应关系：AVL 树的最坏形态，就是一棵按斐波那契节奏生长的树。

6.2 从递推解出高度上界

斐波那契数列的增长速率是黄金分割比 φ ≈ 1.618 的指数函数：F_k ≈ φᵏ / √5。于是 n(h) ≈ φ^(h+3) / √5 - 1。两边取对数解出 h：

h ≈ log_φ(√5 (n + 1)) - 3
  ≈ 1.44 log₂(n + 2) - 1.33

系数 1.44 来自 1 / log₂φ。这个公式告诉我们两件事。第一，AVL 树的高度永远不超过约 1.44 倍的 log₂n——和满二叉树相比，它最多“浪费”不到一半的高度余量。第二，常数系数 1.44 是理论最坏值，实际插入随机数据时，树的高度往往更接近 log₂n 甚至更低，因为“每层都贴着最少节点数”的斐波那契树非常难遇到。

用具体数字感受一下：当 n = 1,000,000 时，log₂n ≈ 19.9，AVL 高度上界 ≈ 27.4，即最坏 28 层；而普通 BST 最坏高度是 999,999。同样是“最坏情况”，一个是 28 次比较，一个是 100 万次比较，这就是自平衡的全部价值。再对照一张表：

节点数 n	满二叉树高度	AVL 最坏高度（约）	退化 BST 最坏高度
1,000	10	14	999
10,000	14	19	9,999
100,000	17	24	99,999
1,000,000	20	28	999,999

6.3 三个操作的最坏复杂度

有了高度上界，AVL 的复杂度分析水到渠成：

查找。 查找与 BST 完全一样，从根沿一条路径向下，比较次数不超过高度。AVL 高度 ≤ 1.44 log₂(n+2)，所以查找最坏是 O(log n)。注意 AVL 的查找不需要任何旋转或平衡操作——它只在插入、删除后维护平衡，查询时树已经是合格的，直接走 BST 路径即可。

插入。 三步：第一步标准 BST 插入，沿路径向下，O(log n)；第二步沿同一路径回溯，逐层更新高度、检查 bf，O(log n)；第三步一旦发现失衡，做一次单旋或双旋，而旋转本身只改动常数个指针，是 O(1)。合起来，插入最坏是 O(log n)。这里要强调一个容易误解的点：回溯确实访问了 O(log n) 个祖先，但旋转只发生一次（至多两次指针操作，LR/RL 的双旋也按常数计），不是每个祖先都转一遍。

删除。 删除的标准流程是 BST 删除（第 7 篇的三种情况），之后同样沿路径回溯修复。但删除有一个和插入本质不同的地方：插入把子树“垫高”，旋转后高度恢复原状，问题不向上传播；删除把子树“削矮”，旋转后高度未必恢复，失衡可能继续向上传染。因此删除最坏需要 O(log n) 次旋转，复杂度仍是 O(log n)，但常数更大、实现更繁琐。这一点的完整展开放在第 10 篇。

空间。 AVL 只比普通 BST 多一个 height 整数（以及递归回溯时的调用栈），所以空间复杂度是 O(n)。高度可以压缩成 2 bit 的平衡因子（-1、0、+1 只有三种状态），工程实现里有时会这么省；本文的代码直接存高度，逻辑更直白。

6.4 一个直觉类比

如果觉得“1.44 log₂n”太抽象，可以这样想：AVL 树允许的最差形状，是一棵“处处都比满二叉树矮一层”的树。想象一个仓库管理员，规则是“任何货架两侧的高度差不能超过 1”——这个规则把最坏的仓库限制成了斐波那契螺旋的形状：每一层都比上一层多出“前两层之和”的格子。斐波那契数列虽然增长很快，但它的对数依然很小，于是仓库的高度永远停留在几十层以内，哪怕格子上百万。AVL 的工程含义是：无论输入多么恶意，查找永远不会超过大约 1.44 log₂n 步——这比“平均很快”强得多，因为它把最坏情况也变成了对数时间。

6.5 一个更简单的证明：为什么至少是“每两层翻一倍”

如果觉得斐波那契推导太绕，这里还有一个只用到初中数学的简化版。递推式 n(h) = n(h-1) + n(h-2) + 1 里，n(h-1) 一定不小于 n(h-2)（高度越高，最少节点数只会越多，这是显然的单调性），所以：

n(h) = n(h-1) + n(h-2) + 1 ≥ 2 · n(h-2) + 1

这意味着，高度每增加 2，最少节点数至少翻一倍（再加 1）。于是 n(h) ≥ 2^(h/2)，两边取对数得到 h ≤ 2 log₂n。这个证明的结论“h = O(log n)”已经成立，只是常数是 2，比斐波那契分析给出的 1.44 宽松。两个证明的关系是：简化版负责“看懂”，斐波那契版负责“精确”。面试或工程里，能说出“最少节点数满足斐波那契式递推，所以高度约 1.44 log₂n”已经足够惊艳；如果只想快速论证 AVL 为什么是对数，2 log₂n 这个上界也完全够用。

6.6 “旋转频繁”到底有多频繁？

第 7 节会提到 AVL“旋转频繁”这个代价，这里先给它一个准确的坐标系。插入的每一次回溯都要检查 O(log n) 个祖先的高度和平衡因子，这是每轮都发生的固定开销；但真正执行旋转的次数，平均来说远小于检查次数。直觉来自平衡因子的分布：一棵健康的 AVL 树里，bf = 0 的节点通常占相当比例（所有叶子都是 0，很多内部节点也是 0），插入若落在 bf = 0 节点的某一侧，该节点只是从 0 变成 ±1，根本不会失衡。只有当插入路径上恰好有一个 bf = ±1 的节点，并且插入落在它“本来就高”的那一侧，它才可能升级成 ±2。也就是说，旋转不是“每插入一次就转一次”，而是“路径上有合适条件才触发一次”，且最多一次。

当然，可以刻意构造出“每次插入都触发旋转”的序列——比如反复按斐波那契树的结构补节点，让树一直处于临界状态。这也是“最坏情况每次插入都旋转，但每次旋转都是 O(1)”这句复杂度结论的来源：单次插入最坏 O(log n)，旋转次数恒为 O(1)。真正让“旋转频繁”成为工程痛点的是删除（第 10 篇主角）：删除后子树高度可能不恢复，失衡沿路径向上传播，最坏每一层都要转一次，写密集型负载的常数立刻变大。所以在读多写少、尤其是插入多删除少的场景，AVL 的旋转成本相当可控。

6.7 查找为什么不需要修改树

还有一个值得点明的细节：查找在 AVL 里是“纯只读”的，它不修改任何指针，也不更新任何高度，更不会触发旋转。原因很简单——AVL 的不变式在每次插入、删除之后就已经被维护好了，查找面对的一定是一棵合格的树，直接复用第 7 篇的 BST 查找即可。这个“只读”特性带来两个工程红利。第一，查找可以安全地与插入并发：只要写操作不破坏读者正在经过的路径（通常用锁或版本号协调），多个查找可以同时进行，共享同一棵树；第二，查找的开销可以被精确预测，它永远是“树高次比较 + 常数次分支”，没有任何隐藏的修复成本。有些资料会把“查找 O(log n)”写得像 AVL 的默认值，其实这个结论完全建立在“写操作已经把树维护好”的前提上——写的时候偷懒，读的时候就要还债。

7 与普通 BST 对比：AVL 的得与失

7.1 一张表看清差距

把普通 BST 和 AVL 树放在同一张表里，最坏情况下的差异一目了然：

维度	普通 BST	AVL 树
平衡规则	无	任意节点左右子树高度差 ≤ 1
高度上界	最坏 n - 1	≤ 1.44 log₂(n + 2) - 1.33
查找最坏	O(n)	O(log n)
插入最坏	O(n)	O(log n)
删除最坏	O(n)	O(log n)
插入后的修复	无	回溯检查 + 至多一次旋转
删除后的修复	无	回溯检查 + 可能多次旋转
额外空间	无	每节点一个 height 字段
实现难度	简单	中等（旋转 + 高度维护）
对输入顺序的敏感度	高（有序输入即灾难）	低（任何顺序都保持对数高度）

这张表最值得记住的一行是“对输入顺序的敏感度”。普通 BST 的快是“运气好才快”：随机输入通常不错，但有序输入、恶意输入直接打回 O(n)。AVL 的快是“保证的快”：它不赌输入，而是每次插入、删除后主动检查并修复形状。数据库索引、编译器符号表这类系统之所以选择平衡树而不是裸 BST，正是因为它们无法假设用户输入“恰好随机”。

7.2 AVL 的优点

AVL 最大的优点可以概括为三个“确定”：最坏情况确定——无论插入顺序如何，树高始终 ≤ 1.44 log₂(n+2)，查找、插入、删除全部 O(log n)；结构确定——平衡规则简单、可验证，任何节点都能现场检查是否合格；查询友好——AVL 是平衡树里“平衡得最严格”的几种结构之一，树高通常比红黑树还要矮一些，所以纯查找场景（读多写少）它往往更快。对于查找密集型负载，比如内存数据库的索引、路由器里的查找表、字符串键的字典，AVL 的严格平衡能换来实实在在的缓存命中率和更少的比较次数。

另一个常被忽略的优点是可预测性。普通 BST 的深度取决于历史输入，同样的键集合，不同到达顺序会产生不同深度的树，深度本身又影响后续所有操作；AVL 把这种“历史依赖”几乎抹平了，树的形状只由键集合决定（近似），这让性能分析、容量规划、最坏时延估算都变得简单。在实时系统或需要严格延迟上界的场景里，“可预测”本身就是一种需求。

7.3 AVL 的代价

天下没有免费的午餐，AVL 的平衡也付了三笔账。

第一笔：空间。 每个节点多存一个高度整数（或压缩成 2 bit 平衡因子）。对百万、千万级节点，这是几 MB 到几十 MB 的额外内存；在嵌入式环境或缓存敏感的系统里，这笔开销需要认真评估。相比之下，跳表每个节点平均多存约两个指针，红黑树多存一个颜色位，各有各的账。

第二笔：写操作的开销。 每次插入都要沿路径回溯更新高度、检查平衡因子，虽然总复杂度还是 O(log n)，但常数比裸 BST 大：裸 BST 插入只做一次向下查找，AVL 插入还要做一次向上“体检”。删除更甚，一次删除最多可能触发 O(log n) 次旋转，每个旋转都要改写若干指针并更新高度。如果你的负载是“写入极多、查询很少”，AVL 的维护成本可能超过它带来的查询收益。

第三笔：实现与调试的复杂度。 旋转本身不难，但高度更新顺序、指针赋值、递归返回值这些细节很容易出 bug，而且 bug 往往不立刻暴露——树会在几百次插入后才悄悄失衡，表现为“偶尔慢一下”或“某次遍历顺序错乱”。这也是为什么很多工程团队直接选用现成的红黑树实现（比如 Java 的 TreeMap、C++ 的 std::map），而不是自己写 AVL。

7.4 什么时候选 AVL？

选型建议可以浓缩成三句话：查找远多于插入删除、需要严格的最坏情况保证、希望树形尽量矮时，AVL 是很好的选择；写入频繁、删除频繁、树形稍微高一点也能接受时，红黑树通常更划算；数据量巨大且需要磁盘友好访问时，B 树、B+ 树才是主角；并发环境需要简单实现时，跳表也值得考虑。第 10 篇我们会把 AVL 和红黑树做一次正面比较，这里先记住：没有“永远最好”的数据结构，只有“在特定负载下最合适”的数据结构。

7.5 AVL 在真实世界的使用

有人会问：既然标准库的 sorted map 大多是红黑树，AVL 是不是只活在教科书里？并非如此。AVL 的严格平衡在“查询密集、写入稀疏”的场景里依然是实打实的优势。早期 Linux 内核就用 AVL 树管理进程的虚拟内存区域，后来因为写操作频繁、需要更少旋转才切换到了红黑树——这个历史案例恰恰说明两种结构的定位差异：内核要处理海量、高频的映射增删，红黑树更划算；而查找型负载，AVL 更矮的树高意味着更少的比较和更好的局部性。内存数据库的索引、嵌入式设备里的符号表、路由器控制面的查找结构、以及一些对最坏时延敏感的实时系统，都能看到 AVL 的身影。很多语言的标准库在“有序集合”上选择红黑树，主要原因是删除性能更稳、实现经验更成熟，而不是 AVL 在数学上差——两者最坏都是 O(log n)，差距只在常数和旋转次数。

对学习者和面试者来说，AVL 还有一层不可替代的价值：它是理解一切自平衡结构的最佳入门教材。旋转、回溯、局部修复、高度守恒，这些思想原封不动地出现在红黑树、B 树、跳表以及各种“自我修复”的数据结构里。把 AVL 的四种旋转练到“闭眼能画”，再看红黑树的颜色翻转、B 树的节点分裂，会发现全是同一个故事的不同讲法。

7.6 AVL 的工程变体：为了降低维护成本

针对 AVL“写操作维护成本高”的短板，工程上有几种常见变体。第一种是压缩平衡因子：不存完整高度，只存 2 bit 的 bf（-1、0、+1），把每个节点的内存开销压到最低；旋转时需要根据左右子树临时推算高度，代码略复杂，但内存收益在千万级节点上很明显。第二种是放宽平衡条件：红黑树把“高度差 ≤ 1”放宽成“任意路径长度差不超过两倍”，旋转频率随之下降；AA 树再进一步，把红黑树的五条规则简化成单一的水平链接限制，实现更短但树形略高。第三种是懒删除（lazy deletion）：删除时只做标记不真正摘节点，树的结构暂不修复，等标记节点积累到一定比例再统一重建或清理。懒删除把删除成本从“每次都要回溯修复”摊薄成“偶尔大扫除”，适合“删得少但每次都要快”的场景，代价是查询时要跳过已标记节点，且树的高度可能略高于理论值。理解这些变体之后回头看 AVL，会发现它不是一个“过时结构”，而是一张平衡树的坐标系：所有自平衡方案都在“平衡的严格程度”和“维护的成本”之间取一个点，AVL 只是把平衡推到最严格那一端。

8 四种旋转速查表

把本篇最核心的内容压缩成一张表，方便日后复习：

类型	失衡节点 X 的 bf	重孩子 Y 的 bf	识别口诀	修复动作	三个关键子树去向
LL	+2	+1（或 0）	插在左子的左子树	右单旋	T1 留 Y 左；T2 过继 X 左；T3 留 X 右
RR	-2	-1（或 0）	插在右子的右子树	左单旋	T1 留 X 左；T2 过继 X 右；T3 留 Y 右
LR	+2	-1	插在左子的右子树	先左旋 Y，再右旋 X	T1 留 Y 左；T2 过继 Y 右；T3 过继 X 左；T4 留 X 右
RL	-2	+1	插在右子的左子树	先右旋 Y，再左旋 X	T1 留 X 左；T2 过继 X 右；T3 过继 Y 左；T4 留 Y 右

补充三条总纲：第一，所有旋转都不改变中序遍历，所以 BST 性质永远成立；第二，旋转后子树高度恢复为插入前的高度，所以最小失衡子树以上的祖先无需处理；第三，高度更新顺序是先孩子后根，写代码时永远不要颠倒。

8.1 常见误区与答疑

误区一：AVL 要求左右子树一样高。 不对。AVL 只要求高度差不超过 1，允许 ±1 的倾斜。要求“完全一样高”只会让维护成本剧增，而且节点数不是 2ᵏ - 1 时根本做不到。bf = ±1 是合法的，这是 AVL 与“完全平衡二叉树”的本质区别。

误区二：LR 双旋是“两个独立的旋转”，可以只做第二个。 不对。双旋的第一步不是可选项：它把 Y 的右重熨平成左重，让失衡方向统一；跳过第一步直接对 X 右旋，失衡会转移到 Y，树依然不合格。两步是“先整队、再正骨”的关系。

误区三：旋转会改变键的顺序或丢失节点。 不对。旋转只改写指针，不创建、不删除节点；中序遍历序列在旋转前后逐项相同。它甚至比“把节点取出来重新插入”更安全——后者在极端情况下可能触发新的失衡，而旋转在数学上保证不破坏 BST 性质。

误区四：每次插入都会旋转。 不对。回溯时每个祖先都要检查，但只有遇到第一个 |bf| = 2 的节点才旋转，而且一次插入最多一次（双旋算一次）。大多数插入根本不会触发旋转，只是把某些节点的 bf 从 0 改成 ±1。

误区五：平衡因子必须存在节点里。 不必。本文的代码用高度现算 bf，节点里只有 height 一个字段；更省内存的做法是只存 2 bit 的 bf（-1、0、+1 三种状态）。两种方案各有取舍：存高度便于调试、逻辑直观；存 bf 省空间但旋转时要额外推算高度。没有哪种“必然正确”，关键是口径统一。

误区六：AVL 一定比红黑树快。 不能一概而论。纯查找场景 AVL 树高更矮，通常占优；但插入、删除场景红黑树的旋转更少（删除时尤其明显），总耗时可能反超。第 10 篇会用数据和场景对比细说，这里先破除“AVL 全面优于红黑树”的迷思。

误区七：AVL 树不允许出现任何失衡。 不对。插入或删除过程中，树会“临时”失衡——先完成标准 BST 操作，再回溯检查并修复，修复完成之后才恢复“处处合格”。旋转处理的正是这些临时失衡，而不是“永远不出事”。判断一棵树是否是 AVL，看的是操作完成后的静止状态，不是操作过程中的中间状态。

8.2 术语速查

术语	含义
高度	空子树为 -1，叶子为 0，节点为 1 + max(左右孩子高度)
平衡因子 bf	左子树高度 - 右子树高度；允许 -1、0、+1，±2 即失衡
最小失衡子树	插入路径上第一个 bf = ±2 的节点为根的子树，只需修这里
回溯	插入后从新节点向根逐层更新高度、检查平衡因子的过程
单旋	LL 右单旋 / RR 左单旋，一次改变两个节点的高低关系
双旋	LR 先左后右 / RL 先右后左，两步各改变一次父子关系
中序不变	旋转前后中序遍历序列相同，因此 BST 性质自动保持
高度恢复	旋转后子树高度回到插入前，祖先平衡因子不受影响

8.3 一句话总结

把全文压缩成一句话：AVL 树用“任意节点左右子树高度差不超过 1”的规则，把 BST 的高度锁死在 O(log n)；插入后沿路径回溯，找到最小失衡子树，用 LL/RR 单旋或 LR/RL 双旋一次性修复；旋转不改变中序、恢复原高度，所以只需修一处，所有操作最坏都是 O(log n)。这句话里包含的四个要素——规则、回溯、旋转、高度恢复——正是 AVL 的全部骨架，也是下一篇删除故事的地基。

8.4 面试常见追问

AVL 是数据结构面试的高频话题，把最常见的五个追问连同答案列在这里，当作全篇的“压力测试”。

追问一：为什么 AVL 不需要存父指针？ 因为递归实现用“返回值 + 赋值”天然完成了自底向上的回溯：root.left = insert(root.left, key) 把子问题的结果（可能是旋转后的新根）写回父节点，父节点再调用 rebalance 处理自己。存父指针会让旋转代码多出大量“改爹”操作，反而更容易错；迭代实现用显式路径栈也能做到同样的效果。

追问二：旋转后，最小失衡子树的祖先为什么不需要动？ 因为旋转把子树高度恢复到了插入前的值，祖先看到的“孩子高度”没有变化，它们的高度和平衡因子自然不变。这是“一次插入只需一次旋转”的核心论据，也是 AVL 插入与删除最本质的区别。

追问三：如何一眼区分 LR 和 RL？ 看两个符号：失衡节点 X 的 bf 和它“壮孩子”Y 的 bf。X 左重（+2）而 Y 右倾（-1）是 LR；X 右重（-2）而 Y 左倾（+1）是 RL。或者直接画插入路径：路径在第二层“拐弯”向里就是双旋，拐向里左就是 LR，拐向里右就是 RL。

追问四：高度上界 1.44 是怎么来的？ 从最少节点递推 n(h) = n(h-1) + n(h-2) + 1 出发，解出 n(h) = F(h+3) - 1，再用斐波那契的指数增长 F(k) ≈ φᵏ/√5 反解 h，得到 h ≈ 1.44 log₂(n + 2) - 1.33。如果记不住 1.44，能说出“斐波那契式递推，高度是 O(log n)”也足够。

追问五：AVL 和红黑树怎么选？ 简短版答案：查找密集选 AVL（树更矮、比较更少），写入密集选红黑树（旋转更少、删除更稳），两者最坏都是 O(log n)。完整版要讲清楚红黑树的“最长路径不超过最短路径两倍”规则为什么换来更少旋转，这正是第 10 篇的内容。

9 自测题

10 下一篇预告：AVL 树的删除

插入的故事讲完了，但 AVL 的完整版图还差最后一块拼图——删除。第 10 篇《树系列第 10 篇：AVL 树的删除、复杂度与对比》将把删除的三种情况（叶子、单孩子、双孩子）与平衡修复结合起来，回答几个插入里不会遇到的问题：为什么删除后的旋转不一定能恢复高度？为什么一次删除可能引发“连环旋转”？删除时用前驱还是后继替换，会影响后续修复吗？然后我们会把 AVL 与红黑树放在同一张工作台上：同样保证 O(log n)，为什么红黑树允许“最长路径不超过最短路径两倍”？写密集负载下谁的旋转更少？标准库为什么偏爱红黑树而数据库却偏爱 B 树？最终给你一张“什么时候选谁”的决策地图。

下一站，我们继续把这棵会自我修复的树，推向它完整的一生。