写 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它的左孩子是 yy 的右孩子是 x且 x 是那个让高度增加的节点。第一步对 y 做左旋x 就升上来变成了 z 的左孩子y 降到 x 的左边此时 z 的左子树变成了一条向左下的直线形状是 LL。第二步对 z 做右旋x 顶上来成为新的子树根z 变成 x 的右孩子y 留在 x 的左边。整个过程中 x 原来的两棵子树会自动被分配到 y 的右边和 z 的左边不需要你手工处理因为这两次旋转内部各自都做了正确的 T2 传递。代码写起来其实特别短因为可以直接复用两个单旋函数// LR 型z 失衡z-left 是 yy-right 是 x // 第一步把左孩子掰直对 y 左旋 node-left rotateLeft(node-left); // 第二步按 LL 型处理对 z 右旋 return rotateRight(node);就这么两行。RL 型同理镜像过来先对右孩子右旋再对当前节点左旋。这四行代码几乎是整个 AVL 里最有性价比的部分但前提是你真的理解“掰直”这个动作在干什么。如果只是背遇到删除操作里那种“孩子的孩子在哪边不确定”的情况就会立刻蒙住。2.3 四种旋转的对照关系与易错点失衡类型形状特征第一步第二步一句话记忆LL一直向左下对失衡节点右旋无左歪了往右扳RR一直向右下对失衡节点左旋无右歪了往左扳LR先左后右折线对左孩子左旋对失衡节点右旋先掰直再扳RL先右后左折线对右孩子右旋对失衡节点左旋先掰直再扳这张表我建议贴在显示器旁边看几天。表里最容易出错的是 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 用四个最小序列把四种失衡逼出来写完代码别急着跑随机数据先用四个只有三个节点的序列把四种形态各触发一次。这三个节点的插入顺序决定了你会走到哪条分支是最干净的手动验证手段插入顺序触发的失衡类型旋转后根节点中序结果30, 20, 10LL2010, 20, 3010, 20, 30RR2010, 20, 3030, 10, 20LR2010, 20, 3010, 30, 20RL2010, 20, 30这张表的价值在于四个序列的中序结果完全一样但走的是四条完全不同的代码路径。你可以在这个阶段直接打断点看每一次旋转被调用时的那几个指针值。我在调试自己实现的时候就干过这事把 rotateRight 和 rotateLeft 各加了一行打印输出“旋转前后节点 key 和高度”四个序列跑一遍哪个分支的打印次数不对、哪个高度值突然变得离谱一眼就能看出来。三节点跑通之后升级到七节点的完整用例。七节点能覆盖“旋转后还要继续向上回溯”的情况比如插入 1 到 7 的升序序列会连续触发多次 RR最终生成的是一棵完全平衡的树每个节点的 BF 都在 -1 到 1 之间。这个用例跑通基本可以认为插入逻辑是对的。4.2 三重校验不只是看它没崩“没崩”不叫正确。我自己写的校验函数检查四件事缺一不可中序有序中序遍历结果必须严格递增。这一条能抓出所有“指针接错但恰好没形成环”的错误。高度自洽每个节点的height必须等于1 max(左高, 右高)。这一条专抓高度更新顺序写反的 bug也是我认为最值得加的一条。BF 合法每个节点的 BF 必须在 -1 到 1 之间。这一条能抓出“该旋没旋”和“旋错方向”的问题。父子指针互指对每个节点检查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 常见问题速查表现象最可能的原因排查动作插入三个节点就崩或死循环旋转时没保存 T2形成自环检查旋转函数第一行是否存了临时变量树形状对但后续插入莫名旋歪高度更新顺序写反断言height(n) 1 max(左高, 右高)中序有序但查不到某个键旋转返回值没接住检查所有rotateXxx调用处是否赋值BF 断言偶发失败空节点高度约定不统一全工程只保留一个height()函数删除后仍然报失衡删除只向上回溯了一层确认删除路径每层都做了平衡检查LR 型旋完更歪第一步旋错了对象确认旋的是左孩子不是失衡节点大量数据后性能骤降等号情况丢失导致误判检查bf(child) 0里的等号最后分享一个我自己养成的习惯每写完一个旋转函数先在纸上用三节点把指针变化全部画一遍再上机。听起来很笨但纸上画一遍只要两分钟上机调一个指针 bug 平均要半小时。而且纸上画的时候你会被迫想清楚“T2 挂哪边”这个问题而这个问题的答案就是旋转的全部本质。我甚至觉得AVL 树的四种旋转真正要理解的只有两条一条是直线情形单旋、折线情形先掰直再单旋另一条是旋转不改变中序序列所以夹在中间的子树必须挂到正确的那一侧。这两条理解透了代码只是把它翻译出来而已不需要背。