你如果刷过二叉树相关的题目大概率会遇到同一个坎插入逻辑写好了几个用例也过了但只要按顺序丢一串拍好序的数据进去整棵树直接歪成一根棍儿查找复杂度从 log n 崩到 n跟链表一个尿性。AVL 树就是为了治这个病出现的。它给每个节点立了一条规矩左右子树的高度差不能超过 1一旦越过这个线立刻通过旋转修正。AVL 树最绕的部分就是这个旋转机制而今天想跟你把这个东西掰开揉碎聊明白失衡是怎么发生的四种失衡形态怎么分辨左右旋的指针到底怎么搬双旋为什么非得转两次。把这套东西真正撕透了后面再碰红黑树那些旋转操作你会觉得它们全在吃 AVL 这套老本。这篇文章适合那种 BST 基础还算熟、递归也能看懂但一看到旋转就头晕、只能靠背代码续命的读者。我会配合代码实现、ASCII 示意和踩坑记录来讲不搞虚的。1. 先搞懂“平衡”到底在保什么1.1 一棵退化的 BST 有多离谱先做个小实验。你往一棵空的二叉搜索树里依次插入 1、2、3、4、5、6、7中规中矩地插入结果会长成下面这样1 \ 2 \ 3 \ 4 \ 5 \ 6 \ 7严格来说这还是一棵合法的二叉搜索树左小右大的性质完全没被破坏。但你想想查找一个 7 要走几步——整整七步。如果插入 n 个有序数据树高就是 n所有操作都是 O(n)那还要它干嘛直接用链表不香吗所以 AVL 树的基本思路非常直白在每次插入或删除之后检查每个节点的左右子树高度差一旦超过阈值就通过局部调整把树“扶正”让整棵树的高度始终维持在 O(log n) 级别。树一矮查找、插入、删除的成本全跟着下来。1.2 平衡因子到底是什么要把“失衡”量化就得引入一个指标。每个节点都有一个高度叶节点高度为 1往上累加。我们定义平衡因子balance factor为左子树高度减右子树高度bf height(left) - height(right)AVL 树要求每个节点的 bf 只能是 -1、0、1 三者之一。bf 1 表示左边比右边高一层bf -1 表示右边比左边高一层bf 0 表示两边等高。这个尺度很宽松——它并没有要求树是完美二叉只要求两侧不能差两层以上。打个比方这就好比跷跷板坐两个人可以一边高一边低但不允许一边直接翘到天上。等到某次插入把一个节点的 bf 顶到 2 或 -2就意味着这里“失衡”了需要立刻旋转修正。这里要明确一个很关键的点失衡是一个局部概念。整棵树上可能只有一个节点不满足条件也可能是回溯路径上的多个节点同时越界。你真正需要关注的是第一次出现失衡的那个节点——也就是从插入点向上回溯时遇到的第一个 bf 绝对值等于 2 的节点。所有旋转都围绕它展开搞定它局部就稳了。2. 失衡四态LL、RR、LR、RL 是怎么判出来的2.1 失衡的方向组合只有四种失衡听起来情况很多其实只有四种形态。因为失衡节点 bf 的符号和它“高出来的那一侧孩子”的 bf 符号组合起来就那么几种组合。我直接给结论再逐个拆。失衡节点 bf高侧孩子的 bf形态处理方式21LL一次右旋-2-1RR一次左旋2-1LR先左旋孩子再右旋自己-21RL先右旋孩子再左旋自己注意看第一列和第二列符号不一致的情况就是需要双旋的 LR 和 RL。这两类是最容易让人翻车的形态后面专门讲。2.2 四种形态的图示与插入序列先说 LL。按顺序插入 30、20、10插入完长这样30 / 20 / 1030 的 bf 2左孩子 20 的 bf 1两个都是正的方向和位置一致这叫 LL 型意思是“左孩子的左子树长高了”。处理方式是在 30 上做一次右旋把树抬正。再说 RR完全镜像。按顺序插入 10、20、3010 \ 20 \ 3010 的 bf -2右孩子 20 的 bf -1方向和位置也一致这叫 RR 型。处理方式是在 10 上做一次左旋。接下来是 LR最容易看错的一种。按顺序插入 30、10、2030 / 10 \ 20节点 30 的 bf 2说明左边高。但左孩子 10 的 bf -1说明 10 自身是右边高。整体看下去路径是左、再右所以叫 LR 型。你如果在 30 上直接右旋会发现根本压不平。RL 就是 LR 的镜像。按顺序插入 10、30、2010 \ 30 / 2010 的 bf -2右孩子 30 的 bf 1路径是右、再左叫 RL 型。2.3 用“倾斜方向一致性”快速判断这么多符号容易记混我有一套自己的判断口诀先看失衡节点本身往哪边歪再看它高的那个孩子往哪边歪。两根筷子往同一个方向歪就是单旋往相反方向歪就是双旋。具体地说失衡节点 bf 为正说明左边高往左上斜bf 为负说明右边高往右上斜。然后看它高出来的那个孩子的 bf 符号正负一致就是 LL/RR不一致就是 LR/RL。判断准了后面代码怎么写都顺手。3. 左旋、右旋的实现细节——拆链、换根、重接3.1 节点结构怎么设计写 AVL 树第一步是把节点的结构定好。我建议在节点里直接存高度而不是每次现算。height 字段的初始值设为 1表示叶子高度为 1空节点高度为 0。struct TreeNode { int val; int height; TreeNode* left; TreeNode* right; TreeNode(int x) : val(x), height(1), left(nullptr), right(nullptr) {} }; int getHeight(TreeNode* node) { return node ? node-height : 0; } int getBalance(TreeNode* node) { return node ? getHeight(node-left) - getHeight(node-right) : 0; } void updateHeight(TreeNode* node) { node-height 1 max(getHeight(node-left), getHeight(node-right)); }为什么叶子高度要从 1 开始而不是 0因为这样空节点高度就是 0叶子高度 1一层子树的高度差能直接用 1 表示平衡因子的判断边界非常干净。这只是约定你从 0 开始也行但所有代码都得跟着改容易出 bug不如从一开始就统一。3.2 右旋的指针搬运动作分解右旋作用于一个“左边高”的节点假设失衡节点叫 y它的左孩子叫 xx 的右孩子叫 T2。旋转前树长这样y / \ x C / \ A T2右旋要达到的目的x 成为新根y 退位变成 x 的右孩子而 T2 这个“中间子树”必须挂到 y 的左孩子位置上。关键问题来了为什么 T2 要挂到 y 左边而不是别的地方因为 BST 的中序顺序是 A x T2 y C。旋转后 x 成了根那么 y 的中序位置一定在 x 右边而 T2 的值介于 x 和 y 之间所以 T2 必须留在 x 的右子树、且作为 y 的左孩子。这一下就明确了指针怎么搬TreeNode* rightRotate(TreeNode* y) { TreeNode* x y-left; // 左孩子要上位 TreeNode* T2 x-right; // 先把“中间子树”留住 x-right y; // y 变成新根的右孩子 y-left T2; // T2 挂回 y 的左侧 updateHeight(y); // 先更新原根的 height updateHeight(x); // 再更新新根的 height return x; // 新的子树根要交还给上一层 }这个函数返回的不是 void而是旋转后的新根。因为一旦旋转原失衡节点不再是这个子树的根了你的插入递归必须拿到新根才能正确接到上一层的某个指针上。这是初学最容易漏的点旋转完忘了 return或者返回了旧的 y。3.3 左旋就是右旋的镜像左旋不用单独死记完全镜像过来就行。失衡节点叫 x右孩子叫 yy 的左孩子叫 T2。旋转前x / \ A y / \ T2 C中间顺序是 A x T2 y C所以 T2 必须成为 x 的右孩子y 成为新根x 变成 y 的左孩子TreeNode* leftRotate(TreeNode* x) { TreeNode* y x-right; TreeNode* T2 y-left; y-left x; // x 降级为左孩子 x-right T2; // T2 接给 x 当右孩子 updateHeight(x); updateHeight(y); return y; }我自己记这两个函数的诀窍是只记“中间那棵子树往哪边挪”。右旋时T2 是从左孩子的右边挪到原根的左边左旋时T2 是从右孩子的左边挪到原根的右边。方向反了代码必错。3.4 这里的三个隐形坑第一个坑更新高度的顺序。旋转之后y 变成了 x 的孩子x 变成了新根。必须先更新 y 的高度再更新 x 的高度。因为你 updateHeight 依赖孩子的 height如果你先算 xx 可能读到的还是旧高度算完也是错的。顺序反了平衡因子全乱后面判断全按错的来。第二个坑T2 可能为空。比如一棵只有两个节点的左偏树做右旋x-right 就是空指针。空指针没关系getHeight 返回 0整个公式依然成立所以没必要对空分支做特判。但如果你用 node-height 直接取而不经过 getHeight空指针访问就直接崩溃了。第三个坑旋转后必须把新根返回给调用方。因为递归插入时父节点的左或右指针需要重新指向旋转后的根。如果没有这一步树的结构还是旧的旋转等于白做。4. 双旋的真相——为什么 LR 需要先左后右4.1 单旋为什么压不住 LR很多入门文章直接甩给你结论LR 型要先对左孩子做左旋再对自己做右旋。但如果不解释为什么你永远只能背代码。我们拿前面的例子在失衡节点 30 上直接右旋试试30 直接右旋 10 / \ 10 30 \ / 20 20旋转完变成10 的 bf -2右孩子 30 的 bf 1。我丢失衡只是从“左边高”变成了“右边高”问题并没有解决只是换了个姿势继续歪。为什么会这样因为失衡的根源是“中间拐弯”的形态。左孩子的右子树长高了但真正插入的那个节点在 10 和 30 之间。这一层“折线”结构如果不先掰直直接右旋等于把一段弯着的钢筋硬压根本压不平。4.2 双旋拆开看先掰直后扶正LR 型的正确动作分两步。第一步对左孩子 10 做左旋把折线变成直线30 先对10左旋 30 / / 10 20 \ / 20 10左旋完成之后原来的 LR 型就变成了 LL 型。此时失衡节点 30 的左孩子是 2020 的 bf 是 1方向和 30 一致了。这时候再用一次右旋把整棵树扶正30 再对30右旋 20 / / \ 20 10 30 / 10所以双旋本质上就是“先把它变成好处理的形态再单旋处理”。这也解释了为什么代码里 LR 分支要写成先 leftRotate(node-left)再 rightRotate(node)。4.3 完整插入函数与四种分支判定下面是一份完整可跑通的插入实现。我故意把四种分支放在一起方便对照TreeNode* insert(TreeNode* node, int key) { // 1. 标准 BST 插入 if (!node) return new TreeNode(key); if (key node-val) { node-left insert(node-left, key); } else if (key node-val) { node-right insert(node-right, key); } else { return node; // 重复键按需处理这里直接忽略 } // 2. 更新当前节点高度 updateHeight(node); // 3. 计算平衡因子 int balance getBalance(node); // 4. 四种失衡形态 if (balance 1 key node-left-val) { return rightRotate(node); // LL } if (balance -1 key node-right-val) { return leftRotate(node); // RR } if (balance 1 key node-left-val) { node-left leftRotate(node-left); // 左孩子先左旋 return rightRotate(node); // 自己再右旋 } if (balance -1 key node-right-val) { node-right rightRotate(node-right); // 右孩子先右旋 return leftRotate(node); // 自己再左旋 } return node; // 无需旋转 }判断 LL 还是 LR我不能只看 balance 1 就拍板还得知道新插入的 key 是落在左孩子的左边还是右边。因为递归回溯时当前节点的左孩子已经完成了插入和可能的内部旋转这时 key 与 node-left-val 的大小关系能直接告诉你是哪种路径。这个判断思路非常顺比传方向标志位干净得多。注意递归的流向插入往深走回来的路上每层都先 updateHeight再判断 balance。如果当前层不需要旋转就把 node 原样返回如果需要旋转就返回新根。上层拿到返回值后重新指向继续更新自己的高度继续判断。整个过程一直回溯到根节点。有一个经验之谈插入操作里一旦某个节点发生了旋转更高层的祖先多半不会再失衡。因为旋转后的子树高度和旋转前一模一样甚至可能更低。所以你经常能看到递归一路回溯只在某一个节点完成旋转上层全是“白检查”。删除才不一样删除后可能需要在多个祖先处连续旋转。这就是为什么 AVL 删除比插入麻烦也是很多实现里删除和插入共用一套旋转却经常出 bug 的根源。5. 我写 AVL 树踩过的坑和一套好用的排查流程5.1 四个高频 bug按发生率排序第一个 bug忘了在双旋里接收孩子旋转后的新根。很多人写leftRotate(node-left);然后接着rightRotate(node);调了半天发现树还是歪的。原因很简单leftRotate(node-left)不会修改node-left它返回的是新根你必须把这个返回值重新赋给 node-left。第二个 bug旋转之后更新高度的顺序错了。这个我前面提过但值得再强调一遍不要把updateHeight(x); updateHeight(y);写成updateHeight(y); updateHeight(x);。谁当孩子就先更新谁这跟“先算下层结果再汇总给上层”是一个逻辑。第三个 bug平衡因子的正负号搞反。getBalance 定义成左减右之后2 一定是左边高。如果你写旋转时把符号搞反就会出现该右旋的时候去左旋越旋越歪。我的排查办法是拿到一棵失衡树后手动把关键节点的 bf 用笔算一遍确认定义再改代码。第四个 bug在删除操作里复用了插入的判断逻辑。寻找“需要旋转的节点”的方向在删除里更复杂因为你删掉节点后真正失衡的节点不一定在递归路径的最深处。直接用插入那套balance 1的分支逻辑经常会漏判。AVL 删除的正确姿势是正常递归删除完成回溯时每层都更新高度、检查平衡可以在同一层旋转多次直到回到根。这跟插入“旋转一次就好”的心态完全不同操作要谨慎。5.2 用层序遍历把树“打印”出来调树这种代码光看变量是很痛苦的最直接的办法是把它画出来。我习惯写一个层序遍历打印函数空节点打#这样树的形状一目了然。void printLevel(TreeNode* root) { if (!root) return; vectorTreeNode* cur {root}; while (!cur.empty()) { vectorTreeNode* next; for (auto node : cur) { cout (node ? to_string(node-val) : #) ; if (node) { next.push_back(node-left); next.push_back(node-right); } } cout endl; cur next; } }打印结果你会看到类似这样的分层20 10 30一眼就知道树长什么样比盯着一堆指针变量强一百倍。如果层数太多显示乱也可以输出(val, height, bf)三元组比如(20,3,0)这样高度和平衡因子也一起检查。5.3 写一个验证函数让程序自报故障人肉查树总有看漏的时候尤其树一大。我在调完基本功能后一定会写一个验证函数检查两件事第一BST 的中序有序性第二每个节点的平衡因子是否都满足要求。bool isValidBST(TreeNode* node, int minVal, int maxVal) { if (!node) return true; if (node-val minVal || node-val maxVal) return false; return isValidBST(node-left, minVal, node-val) isValidBST(node-right, node-val, maxVal); } bool isBalanced(TreeNode* node) { if (!node) return true; int bf getBalance(node); if (abs(bf) 1) return false; return isBalanced(node-left) isBalanced(node-right); }写完之后做随机测试随机插入几千个不重复的数每插一批就调用 isValidBST 和 isBalanced再随机删除一批再验证。只要有一次验证失败马上把当时的插入序列记录下来用最小复现的方式一步步追。这套组合拳下来AVL 树的逻辑基本可以做到滴水不漏。我个人在这套流程里最受益的一个小技巧是不要只在出问题的时候打日志要让验证函数反复跑。因为树结构的 bug 往往是“偶发”的你用固定用例测永远测不出来只有随机大规模数据才能把隐藏的失衡形态逼出来。AVL 树撕到现在你会发现它根本没那么多神秘可言。旋转就是一套固定的指针搬运动作保存中间子树、拆链、换根、重接、更新高度。四种失衡形态本质上是这套动作的两种单旋和两种组合。真正让你卡住的不是代码而是脑子里能不能预演指针从哪里来、到哪里去。把这个想顺了后面再去写红黑树你会觉得旋转全是老熟人心态完全不一样。