如果你写过几年业务代码大概率有过这样的经历数据结构课上听老师讲 AVL 树时觉得“不就是多转几下嘛”等自己真在 C 项目里动手实现、或者面试被问到“手写一棵 AVL 树”时才发现旋转方向、平衡因子更新顺序、删除后怎么修复每一个细节都能把人绕晕。前两年我做一个内存索引模块需要维护大量动态有序数据图省事先用普通二叉搜索树顶了一阵结果插入的数据恰好是单调递增树的形态直接退化成了链表查询从理想的 O(log n) 一路掉到 O(n)几万条记录就把接口拖得肉眼可见地慢。那次踩坑之后我把 AVL 树从头完整实现了一遍踩了不少雷也理顺了它背后“为什么这样转、为什么这样更新”的逻辑。这篇东西面向两类人一类是正在学数据结构、想真正搞懂 AVL 树而不是背代码的学生另一类是工作中要用 C 手写平衡树、或者想通过实现经典结构来提升内功的开发者。我会把原理拆开讲透再给出一份可以直接抄作业的 C 实现最后用我自己调试时踩过的坑帮你少走弯路。1. 为什么要用 AVL 树从二叉搜索树的退化谈起1.1 一棵树是怎么变成链表的二叉搜索树BST的核心优势在于每个结点左子树的所有值都小于它右子树的所有值都大于它所以查找时每次比较都能砍掉一半的搜索范围。这个结论成立的前提是树的形态足够“矮胖”。可一旦插入的数据本身有序先插 1再插 2接着插 3新结点永远挂在右子树整棵树就变成了一条只有右孩子的“斜树”本质就是链表。我对这一点印象极深当时测试数据是时间戳字段天然递增BST 的插入速度还好但查询某个范围内的时间点时要沿着 40 层深的链表一路走下去性能报表直接亮红灯。有人可能会说“那我用 Red-Black 树或者直接用 std::map 不就行了”话是没错但理解 AVL 树的价值不在于它一定比红黑树强而在于它是“严格平衡”的典型代表能把“如何用旋转维持平衡”这件事用最直观的形式讲清楚。红黑树的变色规则比 AVL 复杂理解门槛更高AVL 树用高度差这一个指标就能判断要不要转、怎么转非常适合作为手写平衡树的起点。1.2 AVL 树的解决思路用高度约束换查询稳定性AVL 树由 Adelson-Velsky 和 Landis 在 1962 年提出核心约束非常朴素任意结点的左右子树高度差不超过 1。这个约束保证了任意结点的左右子树都不会“差太多”于是树高始终被控制在 O(log n) 的量级查找可以稳定地跑出对数复杂度不会因为插入顺序的不同而崩坏。AVL 树之所以能在插入和删除后保持平衡靠的是旋转操作。旋转的本质是在不破坏二叉搜索树“左小右大”性质的前提下重新调整局部结点的父子关系把偏高的一侧“掰”回来。后面我会详细拆这四种旋转这里先记住一个结论AVL 树牺牲了一部分插入和删除的性能因为要维护平衡换来了极其稳定的查询性能非常适合“读多写少”或数据分布不可预知的场景。你在选型时如果拿不准可以这样想频繁写、不敏感查询考虑红黑树查询敏感、写操作相对少AVL 树更稳。2. 平衡因子与四种旋转AVL 树的核心机制2.1 平衡因子用一个整数判断健康状况AVL 树判断是否失衡依靠的是平衡因子balance factor定义是左子树高度减去右子树高度。平衡因子为 0 表示左右一样高为 1 表示左子树高一筹为 -1 表示右子树高一筹。只要平衡因子的绝对值不超过 1这棵树就是健康的一旦变成 2 或者 -2就说明当前结点失衡需要立刻修复。这里有一个我在初学时容易混淆的点我们说的是“结点的高度”不是“结点的深度”。高度是从叶子向上数的叶子结点高度为 1空结点高度为 0深度是从根向下数的。判断平衡时用的是左右子树的高度差所以实现中每个结点要维护一个 height 字段每次插入或删除后递归回溯时都要更新路径上每个结点的高度。高度更新必须从叶子向上层层回传这就是递归写法天然适合 AVL 树的原因——递归栈帮我们自动完成了“向上回溯”这件事。来看一个具体例子。依次插入 10、20、30插入 10根结点高度 1平衡因子 0。插入 2020 成为 10 的右孩子10 的高度变成 2平衡因子 0 - 1 -1健康。插入 3030 成为 20 的右孩子20 的高度变成 2平衡因子 -110 的高度变成 3平衡因子 0 - 2 -2失衡了。此时需要对 10 这个结点做旋转。2.2 四种旋转场景的判定失衡情况虽然看起来千变万化但归根结底可以归为四种形态分别对应四种旋转。我建议你不要死记代码而是从“哪个结点高了就往另一个方向压”的角度去理解。失衡形态平衡因子特征旋转方式一句话口诀LL左左当前结点 bf 1且左孩子 bf 0右旋左边太重往右掰RR右右当前结点 bf -1且右孩子 bf 0左旋右边太重往左掰LR左右当前结点 bf 1且左孩子 bf 0先左旋左孩子再右旋当前结点左孩子的右子树捣乱先掰直再右旋RL右左当前结点 bf -1且右孩子 bf 0先右旋右孩子再左旋当前结点右孩子的左子树捣乱先掰直再左旋LL 和 RR 是对称的LR 和 RL 在 LL/RR 基础上多了一步“先把内侧重的那侧转成外侧”。为什么需要先转这一步因为如果失衡结点的左孩子右子树偏高直接右旋会让这个“内侧重心”跑到新树的右子树上依然可能不平衡先左旋左孩子把内侧重心转成外侧重心此时问题就变成了标准的 LL 形态再右旋一次即可。2.3 旋转操作原理解读为什么转完就平衡了我们以右旋为例拆开看它到底做了什么。设 y 是失衡结点x 是 y 的左孩子T2 是 x 的右子树。右旋后x 成为新的子树根y 变成 x 的右孩子T2 从 x 的右子树过继给 y 的左子树。这样调整有两大效果第一中序遍历的顺序完全不变BST 性质被完整保留第二x 和 y 的高度互换过程让左右子树的高度差下降。右旋的核心代码非常短但我强调三个细节必须先保存 x 的右子树指针T2防止覆盖旋转后要先把 y 的高度更新再更新 x 的高度因为 y 现在变成了 x 的孩子x 的高度依赖 y最后返回 x 作为新的子树根上层递归拿到这个返回值后会把树的连接关系修正。很多人的 AVL 树插入后“还是乱的”问题往往就出在“更新高度的顺序”或者“忘记把新根返回给上一层”这两处。template typename T AVLNodeT* rotateRight(AVLNodeT* y) { AVLNodeT* x y-left; AVLNodeT* T2 x-right; // 旋转 x-right y; y-left T2; // 更新高度先更新 y再更新 x updateHeight(y); updateHeight(x); return x; // 新子树根 }左旋完全对称不再单独展开但请你务必亲手写一遍而不是复制粘贴改个名字。我自己带新人时发现一个规律能不看代码独立写出左旋的人对 AVL 的理解基本到位写不出来的人多半是“右旋看懂了但没理解对称性”。3. C 实现从结点设计到插入与平衡修复3.1 结点和类的设计为什么我存 height 而不存 balance实现 AVL 树第一步是定义结点结构。我用的是模板类让树可以装任意可比较类型这样代码的通用性更好。每个结点存储 key键、height高度、left 和 right 两个指针。这里有一个设计选择要解释一下为什么不直接在结点里存 balance 因子而是存 height因为 balance 是一个派生值左子树和右子树的高度变化都会导致当前结点的 balance 改变如果直接存 balance每次旋转后必须重新计算并同步更新大量结点极其容易漏更新。而存 height每次只更新路径上的结点平衡因子用 getBalance(node) 实时算代码清晰且不容易出错。高度字段用 int 就完全够用因为 2^31 的高度对于任何实际程序来说都已经大到不现实了。template typename T struct AVLNode { T key; int height; AVLNode* left; AVLNode* right; explicit AVLNode(const T k) : key(k) , height(1) , left(nullptr) , right(nullptr) {} };三个辅助函数是整棵树的“计量工具”。getHeight 处理空指针返回 0这是必须的因为 C 里对 nullptr 取 height 是未定义行为updateHeight 取左右子树高度的较大者加 1getBalance 返回左子树高度减右子树高度。这三个函数都很短但它们是所有平衡判断的基础写错任何一个后面全都白搭。3.2 插入操作的递归实现BST 插入 回溯平衡AVL 树的插入逻辑可以理解为“普通 BST 插入 回溯时伺机旋转”。递归函数 insert 接收一个结点指针和待插入的 key返回修正后的子树根。第一步是按 BST 规则找到位置key 小于当前结点走左子树大于走右子树相等直接返回本实现不允许重复键如果需要允许重复可以约定插入左子树或右子树但要保持逻辑一致。找到空位后创建新结点插入完成。插入完成后递归在回溯路径上逐层做三件事更新当前结点高度计算平衡因子判断是否失衡并执行对应旋转。这里有个关键点也是新手最容易漏的不是只有“失衡”的那一个结点需要处理而是从插入点到根的整条路径都可能失衡递归回溯的每一层都要检查。不过好消息是在 AVL 树中一次插入最多只需要一次旋转单旋或双旋就能让整棵子树恢复平衡回溯过程中一旦某个结点完成旋转它的祖先结点就不再需要额外的旋转处理了。3.3 插入代码详解平衡判断的四种分支来看 insert 函数的完整实现。我把旋转对应的四种情况直接写在平衡判断里这样读代码时能很自然地对应上理论。template typename T AVLNodeT* insertAVL(AVLNodeT* node, const T key) { // 1. 普通 BST 插入 if (!node) { return new AVLNodeT(key); } if (key node-key) { node-left insertAVL(node-left, key); } else if (key node-key) { node-right insertAVL(node-right, key); } else { return node; // 重复键直接忽略 } // 2. 回溯更新高度 检查平衡 updateHeight(node); int balance getBalance(node); // 3. 失衡修复 // LL左子树高且 key 比左孩子的 key 还小 if (balance 1 key node-left-key) { return rotateRight(node); } // RR右子树高且 key 比右孩子的 key 还大 if (balance -1 key node-right-key) { return rotateLeft(node); } // LR左子树高但 key 落在了左孩子的右子树 if (balance 1 key node-left-key) { node-left rotateLeft(node-left); return rotateRight(node); } // RL右子树高但 key 落在了右孩子的左子树 if (balance -1 key node-right-key) { node-right rotateRight(node-right); return rotateLeft(node); } return node; }注意一个有意思的细节插入时的旋转分支判断用“key 和 node-left-key 比较”来确定 key 落在左孩子的哪一侧。这其实是一种基于路径的判断方式如果当前结点左子树高且插入的 key 小于左孩子的 key那插入点一定在左孩子的左侧对应 LL如果 key 大于左孩子的 key就是 LR。这个判断和用“node-left-balance”判断是等价的。我更推荐用后者即直接看子树的平衡因子因为它在删除操作中更通用逻辑也更直观。下面我先按新手的习惯写插入判断在讲删除时会切换到平衡因子判断法你会发现两种写法在插入场景下等价但后者在删除场景下才是标准做法。3.4 更新高度的顺序旋转里最容易翻车的点旋转操作本身不多但“先更新谁的高度”这个问题我见过无数人栽在这里。以右旋为例旋转后y 变成了 x 的右孩子x 成了新根。此时 x 的高度依赖 y 的高度所以必须先 updateHeight(y)再 updateHeight(x)。如果顺序反了y 会读取到旧 x 的高度导致整棵子树的高度计算错误而高度的错误会直接传染给上层的平衡判断后续所有旋转都可能做出错误决策。还有一个很隐蔽的坑双旋LR 和 RL中第一次旋转后必须把返回值重新赋值给对应的孩子指针。比如 LR 情况下的 node-left rotateLeft(node-left)这一步如果漏了第一次旋转白白做了因为上层根本拿不到旋转后的新子树根。递归写法的每一个“返回值”都是让上层修正指针关系的通信通道少接一个树的形态就是坏的。4. 删除操作AVL 树真正的分水岭4.1 删除流程BST 删除 回溯修复如果你觉得插入理解了就够了那删除会让你重新清醒。删除分两个阶段第一阶段是按 BST 规则删除结点第二阶段是从删除位置向上回溯逐层更新高度、检查平衡、进行旋转。第一阶段有三种情况待删结点是叶子直接删除返回 nullptr 给父结点。待删结点只有一个孩子用这个孩子顶替待删结点位置。待删结点有两个孩子经典做法是找右子树中的最小结点后继或左子树中的最大结点前驱用它的 key 覆盖待删结点然后递归地在子树中删除那个后继结点。我习惯用右子树最小结点因为它一定没有左孩子递归删除时走的是“只有一个孩子或叶子”的分支处理起来最干净。删除和插入最大的不同是插入后最多只需要一次旋转整棵树就恢复平衡了删除后旋转修复完当前结点其祖先结点依然可能处于失衡状态。原因是删除让某一侧子树的高度减 1这个高度变化会沿着路径持续向上传播。因此删除后的回溯中每一个祖先结点都必须完整执行一遍“更新高度、算平衡因子、必要时旋转”的流程不能像插入那样“转了就不管了”。4.2 删除后的平衡判断为什么等号意义重大删除后的平衡判断代码和插入看起来很像但有一个细微而关键的差异单旋条件里多了等号。插入场景中BST 新结点只会加在叶子的左侧或右侧方向性非常明确删除场景中我们只知道左右子树的高度差关系但并不知道“是谁被删掉了”所以当失衡结点的左孩子平衡因子为 0 时右旋依然能让整棵树恢复到合法高度。我直接给出标准写法这也是网上面试题里最常考到的一个区分点template typename T AVLNodeT* removeAVL(AVLNodeT* node, const T key) { if (!node) { return nullptr; } if (key node-key) { node-left removeAVL(node-left, key); } else if (key node-key) { node-right removeAVL(node-right, key); } else { // 找到待删结点 if (!node-left || !node-right) { AVLNodeT* child node-left ? node-left : node-right; delete node; return child; } else { // 找右子树最小结点 AVLNodeT* successor minValueNode(node-right); node-key successor-key; node-right removeAVL(node-right, successor-key); } } if (!node) { return nullptr; } // 回溯更新高度 修复平衡 updateHeight(node); int balance getBalance(node); // 这里和插入不同使用子树的平衡因子判断 // 左子树偏高且左孩子平衡因子 0用右旋 if (balance 1 getBalance(node-left) 0) { return rotateRight(node); } // 左子树偏高但左孩子平衡因子 0先用左旋把左孩子掰直 if (balance 1 getBalance(node-left) 0) { node-left rotateLeft(node-left); return rotateRight(node); } // 右子树偏高且右孩子平衡因子 0用左旋 if (balance -1 getBalance(node-right) 0) { return rotateLeft(node); } // 右子树偏高但右孩子平衡因子 0先用右旋把右孩子掰直 if (balance -1 getBalance(node-right) 0) { node-right rotateRight(node-right); return rotateLeft(node); } return node; }解释一下这两个等号为什么出现在单旋分支里。以balance 1 getBalance(node-left) 0为例它涵盖左孩子平衡因子为 0 的情况。此时左子树的左、右两个子树等高右旋后原来左孩子的右子树 T2 过继到 y 的左子树y 的高度取决于 T2 与 y 原来右子树的高度。由于 T2 和 y 的右子树等高的可能性是存在的旋转后整棵子树高度可能比原来减少 1这个减少要继续向上传播所以即使这层做了右旋上层仍然需要继续平衡检查。这就是删除需要回溯所有祖先结点的根本原因。4.3 寻找最小结点一个被低估的辅助函数minValueNode 函数很短但它决定了删除双孩结点的正确性。它的逻辑是一路往左走直到没有左孩子为止返回当前结点。实现时注意循环的终止条件以及对于空树要返回 nullptr。这个函数在找后继时调用但它只负责“找”不负责“删”真正的删除交给递归完成的 removeAVL。template typename T AVLNodeT* minValueNode(AVLNodeT* node) { AVLNodeT* cur node; while (cur cur-left) { cur cur-left; } return cur; }我自己的一个教训是在删除双孩结点后直接用后继的 key 覆盖当前结点再递归删除后继这时一定要确保把递归的返回值重新赋给 node-right。因为递归删除后继后右子树的高度和结构都可能变化甚至后继所在位置被整体旋转调整过不接住返回值父结点持有的右子树指针就悬空了。5. 验证与调试我不信一棵没测过的平衡树5.1 双重检查中序有序 全局平衡写完代码之后光靠“看起来对”是远远不够的。AVL 树的一个重要性质是中序遍历结果必须严格递增这是 BST 性质的直接体现能过滤掉旋转过程中指针接错导致的顺序破坏。我建议写一个中序遍历函数把结果存入 vector然后检查是否单调递增。这个方法能查出 90% 的指针连接错误因为它验证的是整棵树的全局顺序而平衡因子验证的只是局部高度关系。第二个检查是递归验证每个结点的平衡因子绝对值不超过 1。这个检查要配合 getHeight 函数完成如果某个结点的 height 字段更新错误平衡因子会立刻暴露出来。两个检查一起跑一张大网把“结构错误”和“顺序错误”同时兜住。template typename T bool isAVLTree(AVLNodeT* node) { if (!node) { return true; } int balance getBalance(node); if (balance 1 || balance -1) { return false; } return isAVLTree(node-left) isAVLTree(node-right); }小心一个细节这个检查依赖 getHeight 的返回值而 getHeight 返回的是结点里存的 height 字段。如果 height 字段本身更新错了这个检查会误报。所以更稳妥的做法是写一个独立的“真实高度”计算函数递归取 max用真实高度来验证结点的 height 字段是否一致。我在初期调试时就是吃了这个亏树的平衡明明有问题isAVLTree 却返回 true因为结点里的 height 也被错误地沿用了。5.2 随机插入删除模糊测试我最推荐的自测方案是做一个模糊测试生成大量乱序 key 依次插入每插入一批就跑一遍双重检查然后随机删除一部分 key再跑检查最后再把剩下的 key 清空。这样做的好处是能覆盖到 LL、RR、LR、RL 的各种组合包括删除触发双旋的隐蔽场景。光靠手动插几个数字永远碰不到那些藏在边角里的 bug。建议测试规模从 1000 开始逐步到 10 万。规模太小旋转路径覆盖不全规模太大递归深度和内存占用对新手调试不友好。10 万量级是我实测下来比较舒服的规模既能在几秒内跑完又能把各种旋转路径逼出来。5.3 常见问题速查表现象可能原因排查方法插入顺序乱序后树还是 BST但性能极差旋转后新根未返回给上层检查 insert 的每个 return 是否都被上层正确接住中序遍历有序但 isAVLTree 返回 falseheight 更新顺序错误常见于旋转后先更新新根再更新子树检查旋转函数中 updateHeight 的调用顺序删除后树失衡但插入正常删除后没有继续在祖先链上检查平衡删除的递归回溯必须对每个结点做完整旋转判断双旋后子树结构异常第一次旋转的返回值没有赋给 node-left 或 node-right检查 LR、RL 分支中两次旋转的赋值语句内存泄漏删除时只 delete 了目标结点未处理孩子指针确保单孩删除分支中把孩子指针保存后再 delete6. 复杂度与适用场景AVL 树在真实项目中的位置6.1 复杂度对照为什么值得多读几十行的实现代价AVL 树的查找、插入、删除平均和最坏时间复杂度都是 O(log n)这一点是普通 BST 完全做不到的。普通 BST 在随机数据下平均也是 O(log n)但最坏情况是 O(n)正是这个不稳定的尾部风险让它在很多场景里不可用。结构查找平均查找最坏插入最坏删除最坏额外存储普通 BSTO(log n)O(n)O(n)O(n)少AVL 树O(log n)O(log n)O(log n)O(log n)每结点一个 int红黑树O(log n)O(log n)O(log n)O(log n)每结点一个颜色位AVL 树比红黑树严格但相应地插入删除时旋转次数更多常数更大。而查找性能上AVL 树因为树高更矮通常稍快于红黑树。所以业界常见的选型法则是如果你的操作高度偏向读、写操作相对少AVL 树的“矮树高”优势能发挥作用如果写操作极其频繁红黑树因为平衡条件更宽松只要最长路径不超过最短路径两倍调整次数更少整体吞吐更高。C 标准库里的 std::map 采用红黑树不代表 AVL 树没有用武之地它更代表一种在“写入成本”和“查询效率”之间做出的工程折中。6.2 什么时候我依然会选 AVL 树我个人的实战经验是三个场景优先考虑 AVL 树一是需要频繁进行有序遍历或范围查找的内存索引树越矮遍历时的指针跳转会稍微少一些二是数据分布不可预估、且对查询延迟非常敏感的系统AVL 树的严格平衡能给出一个非常稳定的性能上界三是学习场景这个理由最朴素——红黑树可以借助 std::map 用现成的但 AVL 树是理解所有平衡树的最佳起点谁先手写一遍 AVL谁再看红黑树都会觉得轻松很多。实现 AVL 树并不难难的是把它和普通 BST 的边界理清楚普通 BST 只负责“插入到正确位置”AVL 树负责“插入后让整棵树继续保持健康”。很多人写不好不是因为旋转记不住而是因为没有意识到“回溯修复”才是平衡树的灵魂。最后分享一个我自己的小习惯每次实现完 AVL 树我会故意用一段已排序的数据去插入它然后看它是不是还能保持 O(log n) 的查找速度。这是对一棵 AVL 树最简单也最直观的信任测试。数据结构和算法这东西纸上谈兵什么都简单跑一次真实数据、踩一次真实的坑才会真正变成你的东西。
