企业官网建设流程全解析

写 AVL 树的人，十个里有八个卡在旋转上。不是卡在“不知道有四种旋转”，而是卡在“知道有四种旋转，但一到纸上画指针就开始飘”。我见过太多笔记把 LL、RR、LR、RL 抄了四遍，配图也很工整，可真要让你从零手写一个能跑通插入删除的实现，还是会在这四种数据旋转的指针顺序、高度更新时机、以及“到底该旋哪个节点”上翻车。这篇文章就把 AVL 树的四种旋转从头到尾掰开，重点放在书本上通常一笔带过的地方：最小失衡子树怎么找、双旋转为什么要“反着来”、旋转代码里两个赋值的先后顺序为什么不能换、删除操作里判断条件和插入为什么不一样。不管你是正在准备手写平衡树的同学，还是写业务代码多年、突然想回头把那点数据结构底子补上的开发者，看完至少能做到不查资料写出正确的四种旋转，并且知道错了该怎么查。

1. 旋转这件事，先把约束条件想透

1.1 平衡因子才是 AVL 树的真正主角

很多人一上来就背旋转，其实顺序反了。AVL 树的一切行为都由一个数字驱动：平衡因子（Balance Factor，简称 BF）。它的定义是某个节点左子树高度减去右子树高度，取值范围在合法状态下只有三个：-1、0、1。一旦某个节点的 BF 变成 2 或者 -2，这棵树就不再是 AVL 树，必须立刻修。

这里有个特别容易被忽略的细节：空节点的高度取 0 还是 -1，你必须从第一行代码开始就统一。我见过太多调试到半夜的案例，最后发现是height(nullptr)在某处返回 0、在另一处返回 -1，导致 BF 判定永远差一格，插入三个节点就误触发旋转。我自己的习惯是空节点高度为 0、叶子节点高度为 1，整个工程里只允许出现一个height()函数，任何地方要取高度都必须调它，不准手写node->left->height。这一个习惯能省掉后面八成的调试时间。

另外一个认知上的分水岭是：AVL 树的约束是局部的。一次插入只会让从根到插入点这条路径上的节点高度发生变化，路径之外的所有节点高度纹丝不动。所以插入之后你不需要遍历整棵树去找谁失衡，只要沿着递归返回的路径往上走，遇到的第一个 BF 绝对值为 2 的节点，就是需要动手的地方。这个“第一个”很关键，它叫最小失衡子树，修好它，它上面的所有祖先自动恢复平衡，一次插入最多只需要一到两次旋转，不会连锁。

1.2 四种失衡形态，才是“四种旋转”的来源

教科书上说“四种旋转”，严格讲是四种失衡形态对应四种修复手法。把形态认对了，旋转方式自然就出来了，根本不用背。判定的核心是看失衡节点和它的“肇事孩子”“肇事孙子”连成的折线形状：

• LL 型：失衡节点的左子树的左子树变高了，形状是一条直线往左下走。修复方式是一次右旋。
• RR 型：失衡节点的右子树的右子树变高了，一条直线往右下走。修复方式是一次左旋。
• LR 型：失衡节点的左子树的右子树变高了，形状是折的。修复方式是先左旋再右旋。
• RL 型：失衡节点的右子树的左子树变高了，折线。修复方式是先右旋再左旋。

这里我要强调一个特别反直觉的点，也是我当年栽的第一个坑：LR 型的处理方向，和孩子所在的方向是相反的。左子树出问题，第一步偏偏要做左旋。很多人写出if (bf > 1) rotateRight(node)就以为覆盖了左侧所有情况，结果碰上 LR 型直接旋错，树不但没平衡，反而更歪。判断逻辑必须分成两支：左侧失衡时，先看左孩子的 BF 是正还是负，正的是 LL 直接右旋，负的是 LR 得先给左孩子做左旋把它掰直，再对当前节点右旋。

1.3 为什么非得旋转，不能推倒重建

有人会问，既然失衡了，我把这棵子树的中序序列取出来，重新二分建树不就完了？能，但代价完全不是一个量级。重建一棵大小为 k 的子树需要 O(k) 时间和 O(k) 额外空间，而旋转是常数时间的指针改写，只碰三到四个指针，不动任何节点里的数据。更关键的是，旋转有一个极其优雅的性质：它不改变这棵子树的中序序列。也就是说旋转前后，这棵树作为有序集合的语义完全一致，只是形状变了。这就像你把书架上的书重新挪了一下位置，书还是那些书、顺序还是那个顺序，只是矮的地方被垫高了。

从工程角度还有一层考虑：旋转是局部的，它只影响三四个节点的父子关系，其余部分完全不受打扰。这意味着如果你在节点上挂了别的东西（比如迭代器指向某个节点、或者节点上带引用计数），旋转的影响面是可预测的、可控的。重建则会让所有外部持有的节点指针全部失效。这两种设计哲学的区别，在做缓存、索引、内存池这类需要稳定指针的场景里会被放大得非常明显。我后来做过一个需要“插入过程中保持已有节点地址不变”的小项目，就是因为这个原因必须老老实实用旋转而不能重建。

2. 四种旋转的指针改写，逐行拆开看

2.1 右旋与左旋：一对镜像操作

先看右旋（Right Rotation）。场景是 LL 型，失衡节点记作 y，它的左孩子记作 x。右旋的目标是让 x 升上来顶替 y 的位置，y 降下去当 x 的右孩子，而 x 原来那棵右子树（记作 T2）要挂到 y 的左边去。为什么挂左边？因为 T2 里所有节点都大于 x、小于 y，右旋之后 y 变成了 x 的右孩子，T2 作为“夹在中间”的部分，只能挂在 y 的左子树位置，这样中序序列才保持不变。

这个 T2 就是必须提前保存的临时变量。代码里如果先写x->right = y再想去找 y 的左孩子接谁，已经晚了，因为 y 的左孩子此刻还指着 x，你再去读就是死循环或者自环。正确的顺序只有一种：

// 右旋：y 是失衡节点，x 是 y 的左孩子 Node* rotateRight(Node* y) { Node* x = y->left; Node* t2 = x->right; // 先保存夹在中间的那棵子树 x->right = y; // x 升上来，y 变成它的右孩子 y->left = t2; // 原来夹在中间的挂到 y 的左边 updateHeight(y); // 先更新下降的那个 updateHeight(x); // 再更新上升的那个 return x; // 新的子树根 }

左旋（Left Rotation）完全是镜像：RR 型失衡时，失衡节点 y 的右孩子 x 升上来，y 变成 x 的左孩子，x 原来的左子树挂到 y 的右边。写代码时我建议你直接把右旋的代码复制一份，把left和right全部互换，几乎不可能错。手写的时候千万别凭记忆写，镜像操作凭记忆是最容易把方向写反的。

关于高度更新的两行，我要单独拎出来说，因为这是最隐蔽的 bug 来源。updateHeight(y)必须在updateHeight(x)之前，因为 x 的新高度依赖 y 的新高度。写反了会怎样？树的形状完全正确、中序遍历完全正确、打印出来完全正确，但 BF 值全部偏移，下一次插入就会在错误的地方触发旋转，把一个本来平衡的树旋歪。这种 bug 最难查，因为你的树“看起来是对的”，只有跑大量数据才会偶发崩溃。我自己被这个坑过一次，后来在单元测试里加了一条断言：旋转完成后立刻校验abs(bf(x)) <= 1 && abs(bf(y)) <= 1，如果这条不成立，一定就是高度更新顺序错了。

2.2 LR 与 RL：双旋转是两次单旋转的组合

LR 型的处理，教科书上的标准说法是“先对左孩子左旋，再对当前节点右旋”。这个描述准确但容易让人晕，我用一句话概括它的本质：LR 型是因为折线太歪，先把它掰成直线（LL 型），再按 LL 型处理。

具体走一遍。假设失衡节点是 z，它的左孩子是 y，y 的右孩子是 x，且 x 是那个让高度增加的节点。第一步对 y 做左旋，x 就升上来变成了 z 的左孩子，y 降到 x 的左边，此时 z 的左子树变成了一条向左下的直线，形状是 LL。第二步对 z 做右旋，x 顶上来成为新的子树根，z 变成 x 的右孩子，y 留在 x 的左边。整个过程中 x 原来的两棵子树会自动被分配到 y 的右边和 z 的左边，不需要你手工处理，因为这两次旋转内部各自都做了正确的 T2 传递。

代码写起来其实特别短，因为可以直接复用两个单旋函数：

// LR 型：z 失衡，z->left 是 y，y->right 是 x // 第一步：把左孩子掰直（对 y 左旋） node->left = rotateLeft(node->left); // 第二步：按 LL 型处理（对 z 右旋） return rotateRight(node);

就这么两行。RL 型同理，镜像过来：先对右孩子右旋，再对当前节点左旋。这四行代码几乎是整个 AVL 里最有性价比的部分，但前提是你真的理解“掰直”这个动作在干什么。如果只是背，遇到删除操作里那种“孩子的孩子在哪边不确定”的情况就会立刻蒙住。

2.3 四种旋转的对照关系与易错点

这张表我建议贴在显示器旁边看几天。表里最容易出错的是 LR 和 RL 两行的第一步：对谁做旋转。是“对孩子的孩子所在的子树根”做旋转，也就是对左孩子（或右孩子）本身，而不是对孙子，也不是对失衡节点。很多人在纸面上算得清清楚楚，一写代码就写成rotateLeft(node->left->right)之类，然后调试两小时。

还有一处细节：双旋转之后新的子树根是谁。单旋转后新根是原来的孩子，双旋转后新根是原来的孙子。这一点在递归回溯的写法里会自动处理（因为函数返回新根，上一层直接接住），但如果你写的是非递归的迭代版本，就必须显式记住这个新根并挂回父节点。迭代版 AVL 的复杂度和递归版完全不是一个难度级，除非有特殊需求，我强烈建议先用递归版把逻辑跑通。

3. 完整实现的落地路径

3.1 节点结构与“高度 vs 平衡因子”的取舍

节点里存什么，是个有实际影响的设计选择。两种主流做法：存高度或者存平衡因子。存高度更直观，调试时打印出来一目了然，代价是每次旋转要多做几次减法；存平衡因子省掉了高度查询，但每次旋转都要手工重算两个节点的 BF，推导过程繁琐且极易出错，尤其是删除操作里 BF 的更新规则比插入复杂得多。

我个人的建议是：学习和一般业务场景一律存高度。理由很朴素——AVL 树的性能瓶颈几乎从来不在那几次减法上，而在你的逻辑是否正确。等你把实现跑通、做过大规模压力测试、确认旋转是热点之后再考虑优化，而且到那时候你多半会直接换红黑树或者 B 树，而不是去抠 AVL 的这几个减法。

struct Node { int key; int height; // 空节点高度 0，叶子节点高度 1 Node* left; Node* right; explicit Node(int k) : key(k), height(1), left(nullptr), right(nullptr) {} }; inline int height(Node* n) { return n ? n->height : 0; } inline void updateHeight(Node* n) { if (n) n->height = 1 + std::max(height(n->left), height(n->right)); } inline int balanceFactor(Node* n) { return n ? height(n->left) - height(n->right) : 0; }

注意balanceFactor里我用的是“左减右”，前面 1.2 节的判定表也是按这个约定写的：BF 大于 1 表示左边高。如果你习惯写成“右减左”，那所有判断条件的符号都要反过来，包括> 1变< -1、bf(node->left) >= 0变<= 0。这个约定必须在写第一行判定代码之前定死，中途改符号是灾难。

3.2 插入路径的回溯与旋转触发

插入本身是普通 BST 插入，往左往右递归下去，回到每一层时做三件事：更新高度、算 BF、判断要不要旋。这里有个很实用的写法技巧——用插入的 key 和孩子的大小关系来判断失衡类型，比用 BF 判断更省事，因为插入场景下“新增节点在左子树的哪一侧”直接可以用 key 比出来。

Node* insert(Node* node, int key) { if (!node) return new Node(key); if (key < node->key) node->left = insert(node->left, key); else if (key > node->key) node->right = insert(node->right, key); else return node; // 重复键不插入 updateHeight(node); int bf = balanceFactor(node); // LL：左边高，且新键落在左孩子的左边 if (bf > 1 && key < node->left->key) return rotateRight(node); // RR：右边高，且新键落在右孩子的右边 if (bf < -1 && key > node->right->key) return rotateLeft(node); // LR：左边高，但新键落在左孩子的右边 —— 先掰直 if (bf > 1 && key > node->left->key) { node->left = rotateLeft(node->left); return rotateRight(node); } // RL：右边高，但新键落在右孩子的左边 —— 先掰直 if (bf < -1 && key < node->right->key) { node->right = rotateRight(node->right); return rotateLeft(node); } return node; }

这四段 if 的顺序有讲究：必须先判单旋再判双旋。因为key < node->left->key这个条件只有在左侧失衡成立时才有意义，如果你先写双旋条件key > node->left->key，在 LL 情况下这个条件为假，会漏过去——看起来没问题。但如果键值恰好相等（重复键），两边条件都为假，就不会旋转。所以更稳的写法是先用if (bf > 1)括住左侧所有情况，在里面再分两种。我上面这种写法能跑，但对重复键和相等比较要格外小心，实际项目里我会写成嵌套形式，可读性更好。

3.3 删除操作：判断条件为什么要换成看孩子的 BF

插入用的是“新键在哪边”，删除没法这么干，因为你不知道删除后是哪边变矮了。这时候只能老老实实看孩子的平衡因子，从而区分单旋和双旋：

// 删除后对 node 做平衡修复 if (bf > 1) { // 左子树高。左孩子的 BF >= 0 说明是 LL（或左孩子两边一样高）， // 此时单旋即可；< 0 说明是 LR，要双旋 if (balanceFactor(node->left) >= 0) return rotateRight(node); node->left = rotateLeft(node->left); return rotateRight(node); } if (bf < -1) { if (balanceFactor(node->right) <= 0) return rotateLeft(node); node->right = rotateRight(node->right); return rotateLeft(node); }

这里>= 0和<= 0里的等号非常关键，也是删除比插入难的地方。当孩子节点的 BF 恰好为 0 时（意味着它两边一样高，删除发生在这棵子树的“另一侧”），单旋转之后依然能保持平衡，而且旋转后新子树的高度不变，所以可以停止向上回溯。如果写成> 0，把等号丢掉，碰上 BF 为 0 的左孩子就会误判成 LR 去做双旋，虽然很多情况下树也还能保持“大致平衡”，但高度会算错，后续插入会在错误的位置触发旋转，最终表现为随机数据下偶发的性能劣化或者校验失败。这个坑我踩过，而且因为结果不是崩溃、只是“偶尔有点慢”，查了很久才定位到。

删除还有个差异：删除可能触发多次旋转。因为一次删除会让某棵子树变矮，这个变矮会往上传，祖先节点可能连续失衡。所以删除回溯的时候不能像插入那样“旋一次就收工”，必须一路走到根，每层都检查。这也是为什么 AVL 树的删除平均要旋转的次数比插入多。

4. 怎么验证你的旋转真的写对了

4.1 用四个最小序列把四种失衡逼出来

写完代码别急着跑随机数据，先用四个只有三个节点的序列，把四种形态各触发一次。这三个节点的插入顺序决定了你会走到哪条分支，是最干净的手动验证手段：

这张表的价值在于：四个序列的中序结果完全一样，但走的是四条完全不同的代码路径。你可以在这个阶段直接打断点，看每一次旋转被调用时的那几个指针值。我在调试自己实现的时候就干过这事，把 rotateRight 和 rotateLeft 各加了一行打印，输出“旋转前后节点 key 和高度”，四个序列跑一遍，哪个分支的打印次数不对、哪个高度值突然变得离谱，一眼就能看出来。

三节点跑通之后，升级到七节点的完整用例。七节点能覆盖“旋转后还要继续向上回溯”的情况，比如插入 1 到 7 的升序序列，会连续触发多次 RR，最终生成的是一棵完全平衡的树，每个节点的 BF 都在 -1 到 1 之间。这个用例跑通，基本可以认为插入逻辑是对的。

4.2 三重校验：不只是看它没崩

“没崩”不叫正确。我自己写的校验函数检查四件事，缺一不可：

1. 中序有序：中序遍历结果必须严格递增。这一条能抓出所有“指针接错但恰好没形成环”的错误。
2. 高度自洽：每个节点的height必须等于1 + max(左高, 右高)。这一条专抓高度更新顺序写反的 bug，也是我认为最值得加的一条。
3. BF 合法：每个节点的 BF 必须在 -1 到 1 之间。这一条能抓出“该旋没旋”和“旋错方向”的问题。
4. 父子指针互指：对每个节点检查node->left->parent == node（如果你存了 parent 指针），否则检查左右孩子的 key 大小关系。这一条专抓那些没形成环、但挂错位置的隐蔽错误。

把这四条封装成一个validate(root)函数，在每次插入和删除之后都调一次。性能会很差，但只在测试环境开。我甚至建议你在旋转函数内部、返回之前就断言一次abs(balanceFactor(newRoot)) <= 1，这样一旦出错，崩在事发地点，比等到几百次操作之后再崩好查一万倍。

4.3 一点量级上的直观感受

很多人对 AVL 的收益没概念，觉得平衡不平衡差不多。我做过一个粗糙的对比，在同一台普通笔记本上插入 100 万个随机整数：普通二叉搜索树因为随机性，树高大概在 40 到 50 层之间，勉强能用；但如果数据是升序的（比如从日志里按时间读出来的 ID），普通 BST 直接退化成一条链，树高 100 万层，插入耗时从零点几秒膨胀到几十秒，递归版还会直接爆栈。AVL 在这两种输入下高度都稳定在 20 层左右（因为 1.44 × log₂(10⁶) ≈ 29，实际随机数据会更矮），耗时基本一致。

这个数据我只当量级参考，具体数字跟机器、编译器、是否开优化全都有关系。但它说明了一件事：平衡树的价值不在于随机数据下的那点常数差异，而在于它对恶意输入和有序输入的抗性。你写业务代码时数据可能确实随机，但一旦有人构造了有序的批量请求，退化成链的树就是现成的性能事故。这也是为什么我在需要有序结构的场景里，宁可多写一百行旋转代码，也不愿意赌数据分布。

5. 那些只有踩过才知道的坑

5.1 指针改写的三个经典死法

第一种，先改父再存子。写y->left = x->right之后又去读x->right，此时 x 的右孩子已经被换了，读到的不是原来那棵 T2。所有旋转函数的第一行必须是保存临时变量，这不是代码风格问题，是正确性问题。

第二种，返回值忘了接。旋转函数返回新根，但调用处写成rotateRight(node);而不是node = rotateRight(node);。这种情况下树的结构其实已经被改了（因为函数内部动了指针），但当前层的 node 变量还指着旧根，上一层拿到的就是错的。表现出来是“树看起来是平衡的，但偶尔查不到某个键”。这种错误极其隐蔽，因为旋转的副作用是真实的，只是指针没更新。

第三种，在旋转函数里更新了多余的高度。有些实现图省事，在旋转里把涉及的四个节点高度全刷一遍，结果把某个本来正确的节点高度也算错了。高度更新必须严格只更新“实际改变了的两个节点”，也就是下降的那个和上升的那个，顺序还不能反。

5.2 删除操作为什么比插入难一个数量级

插入时你知道“新节点往哪边走”，失衡类型可以靠比较 key 直接判定；删除时你只知道“某棵子树变矮了”，必须靠孩子的 BF 反推类型。这一个差别带来三个连锁后果：

• 判断条件多出“等号情况”，也就是孩子 BF 为 0 时的处理，这里少写一个=就会导致误判双旋；
• 一次删除可能触发多次旋转，因为高度变化会一路往上传；
• 删除有两个孩子的节点时，通常用后继节点替换，替换完之后要在右子树里继续删那个后继，递归路径比插入长。

这三点叠加，导致删除的代码量大概是插入的两倍，出错概率也差不多是两倍。我的建议是：先只实现插入，把四种旋转彻底跑通、校验函数全绿之后，再动删除。我见过不少人插入和删除一起写，结果出的问题分不清是旋转的锅还是删除逻辑的锅，最后只能全推翻重来。

5.3 常见问题速查表

最后分享一个我自己养成的习惯：每写完一个旋转函数，先在纸上用三节点把指针变化全部画一遍，再上机。听起来很笨，但纸上画一遍只要两分钟，上机调一个指针 bug 平均要半小时。而且纸上画的时候你会被迫想清楚“T2 挂哪边”这个问题，而这个问题的答案就是旋转的全部本质。我甚至觉得，AVL 树的四种旋转真正要理解的只有两条：一条是直线情形单旋、折线情形先掰直再单旋；另一条是旋转不改变中序序列，所以夹在中间的子树必须挂到正确的那一侧。这两条理解透了，代码只是把它翻译出来而已，不需要背。