最近在帮一个学弟调他的二叉搜索树代码他一脸认真地把所有测试数据都拉满了结果程序跑起来之后肉眼可见地变卡。我把他的插入序列打印出来一看好家伙数据基本是升序排列的他的二叉搜索树直接退化成了链表查找效率从 O(log n) 掉到了 O(n)。这种场景我太熟悉了几乎每个学到树结构的人都会踩一遍。今天就把这个问题的解法——AVL 树一次性讲清楚从算法思路到 C 实现一步不落。1. 先搞清楚问题你的二叉搜索树为什么慢1.1 二叉搜索树的性能与树高的死磕关系二叉搜索树BST之所以“快”靠的是一个核心承诺对任意节点的左子树所有值都比它小右子树所有值都比它大。有了这个性质查找、插入、删除都能通过不断折半来定位目标理论上每次比较都把搜索范围缩小一半时间复杂度和二分查找一样都是 O(log n)。注意我说的是“理论上”。这个理论成立的前提是树的形态足够“满”、足够“矮”也就是从根节点到任意叶子节点的路径都要短。树的高度 h 和节点数 n 的关系只有在一棵完全平衡的树里才是 h ≈ log₂(n1) - 1。比如 100 万个节点的完全二叉树高度大约只有 20也就是说最坏情况下你只要比较 20 次就能找到任意节点。这个速度是炸裂级别的。但二叉搜索树从不保证自己长成“完全平衡”的样子。树长什么样完全取决于插入顺序。这是二叉搜索树最任性、也最致命的一点。1.2 数据顺序如何让二叉搜索树“报废”假设你依次往一棵空 BST 里插入 1、2、3、4、5、6、7。我请你闭上眼睛想一想会发生什么根节点是 1。插入 2因为 2 1变成 1 的右孩子。插入 3因为 3 1往右走又因为 3 2变成 2 的右孩子。依次类推……最终这棵“树”完全退化成一条向右延伸的单链表。写代码的时候你根本感受不到异常因为 BST 的插入逻辑对每个节点都是普适的它不会判断“你这么插会把树弄成一条直线我拒绝”。它只会老实按规则放。这时候再查一个 7 的值你需要沿着 1 → 2 → 3 → 4 → 5 → 6 → 7 一路比下去整整 7 次比较。如果数据量是 10 万个升序节点你查最后一个节点真的要比较 10 万次。这不叫二分查找这叫顺序遍历。更扎心的是实际业务里“有序插入”不仅不罕见反而相当常见。比如按时间戳写入日志索引、按自增 ID 建用户表、按日期追加日程数据这些都是天然的升序流。你拿普通 BST 去接这种数据性能直接垮掉。1.3 用数量级思维看退化O(log n) 与 O(n) 之间隔着一个宇宙我给自己脑子里装了一个常驻的换算表遇到数据规模先估一下退化前后的差距n 1,000平衡树约 10 层退化后最多 1,000 层差 100 倍。n 1,000,000平衡树约 20 层退化后最多 1,000,000 层差 50,000 倍。n 100,000,000平衡树约 27 层退化后最多 100,000,000 层差 370 万倍。你看这个差距根本不是“稍微慢一点”而是“数据结构直接失去意义”。至少在查找、插入、删除特别频繁的场景里一颗失衡的 BST 还不如老老实实排好序用数组加二分来查至少后者性能可预测。所以问题的根源清晰了二叉搜索树性能不稳定的元凶就是树高失控。我们要做的不是换掉二叉搜索树这个方向而是给它加一个强制约束——任何时刻任何节点的左右子树高度差不能太大。这个思路催生了 AVL 树也是这篇博文的主角。2. 解锁平衡的力量AVL 树的核心思想2.1 平衡因子高度差的量化监控AVL 树是两位苏联数学家 Adelson-Velsky 和 Landis 在 1962 年提出的也是计算机科学中第一个自平衡二叉搜索树。它的规则极其简单粗暴任意节点的左右子树高度差绝对值不超过 1。为了量化这个约束我们引入平衡因子Balance Factor平衡因子BF 左子树高度 - 右子树高度在 AVL 树里每个节点的 BF 只允许取 -1、0、1 三个值BF 1左子树比右子树高 1 层合法微微左倾。BF -1右子树比左子树高 1 层合法微微右倾。BF 0左右子树等高完全标准。BF 2 或 -2失衡必须立刻通过旋转修正。这里的“高度”指的是从当前节点到最远叶子节点的最长路径上的节点数。空节点的高度记为 0叶子节点高度为 1。有了这个量化标准我们就能在每次插入、删除之后精确判断“谁失衡了、失到什么程度”。这里说一个没经验的人容易忽略的点插入一个节点只可能影响从插入点到根节点路径上那些祖先的平衡因子和插入点不在同一条路径上的那些节点高度根本不会变。所以修复工作只需要沿着回溯路径做不需要全树扫描这也是 AVL 树插入能保持在 O(log n) 的前提。2.2 为什么 AVL 选择“严格平衡”而非“近似平衡”市面上的自平衡搜索树不止 AVL 一种红黑树同样是经典方案。很多初学者会问既然红黑树也能自平衡而且 C 的 std::map、std::set 底层用的就是红黑树为什么还要学 AVL我的回答是应用场景不同取舍不同。红黑树允许“最长路径不超过最短路径的 2 倍”那么最坏树高约为 2log₂(n1)它是个近似平衡。这个放宽约束的代价是红黑树在插入时最多只需两次旋转就能恢复平衡删除也只需三次旋转旋转开销小、重平衡频率低。AVL 树极端追求严格平衡树高更矮更稳定查找性能最强。但代价是插入可能需要一次或两次旋转删除则最坏情况下需要一路回溯到根、执行 O(log n) 次旋转。结论很清楚如果你的场景是大量查找、插入删除少——比如数据库索引、字典读多写少的系统——AVL 树更好如果是写多读也多的通用场景红黑树更省心。但作为学习AVL 树把“平衡”这两个字贯彻到了极致它把旋转、递归回溯、平衡因子维护这些基本功全部打磨到位你先能吃透 AVL红黑树后面就是顺水推舟的事。2.3 用叠积木的思路理解旋转我先用一句话概括旋转的本质在“中序遍历顺序不变”的前提下把树的结构重新扯回平衡。中序遍历顺序不变意味着旋转前后这棵树作为一个搜索树的“语义”完全一致——所有节点的相对大小关系一个字都没改只是形状变了。怎么理解这句话想象你在叠积木。把一根长条积木倾斜着架在两个短块上你觉得它随时会塌于是你把长条拿下来搁到另一侧又把某个短块垫到下面。积木还是那些积木但整体重心稳了。旋转干的就是这件事。3. 四种失衡形态与旋转修复方案3.1 一眼识别从失衡节点入手看形态当我们发现某个节点的平衡因子绝对值超过 1第一件事是判断它属于四种失衡形态中的哪一种。判定方法不是看平衡因子的绝对值大小而是看“失衡节点”和“它的较高孩子”各自偏向哪一边失衡形态失衡节点的 BF较高孩子的 BF修复方式LL 型2左重0 或 1左孩子的左子树高右旋失衡节点RR 型-2右重0 或 -1右孩子的右子树高左旋失衡节点LR 型2左重-1左孩子的右子树高先左旋左孩子再右旋失衡节点RL 型-2右重1右孩子的左子树高先右旋右孩子再左旋失衡节点看到这个表你可能会疑惑LL 型里较高孩子的 BF 是 0 也算 LL算的。这是一种边界情况比如插入一个节点导致某祖先失衡但其子节点的左右子树高度差为 0也就是它的两个子树一样高这时也按 LL 或 RR 处理直接单旋修好。我后面讲代码实现的时候会把这个判断写清楚。3.2 LL 型与 RR 型单旋操作全图解LL 型的意思是“左边太重而且重在最左边的链上”。失衡节点记为 AA 的左孩子记为 BB 的左子树更高。修复办法是绕 A 做一次右旋正旋B 升为这棵子树的根。A 变成 B 的右孩子。B 原本的右子树记作 T2转挂给 A 的左孩子位置。为什么 T2 要挂到 A 的左孩子位置因为这棵子树里所有值都大于 B 且小于 A——它既应该在 B 的右边又必须在 A 的左边所以挂在 A 的左侧正好满足 BST 顺序。旋转完成后 A 被“降级”B 被“提拔”中序遍历序列一个元素都没乱。RR 型是镜像对称版失衡节点 A 的右孩子 C 的右子树更高绕 A 做左旋反旋C 升为根。A 变成 C 的左孩子。C 原本的左子树T2转挂给 A 的右孩子位置。原因和 LL 完全相同T2 里所有值大于 A 且小于 C它必须在 A 的右边、C 的左边挂 A 右侧既顺 BST 规则又不需要移动任何其他节点。单旋的 C 代码以右旋为例Node* rotateRight(Node* A) { Node* B A-left; Node* T2 B-right; // 旋转B 升根A 成为 B 的右孩子 B-right A; A-left T2; updateHeight(A); updateHeight(B); return B; // 新子树的根 }这段代码的精髓在于“指针重新接了三处”B 的右孩子换成 AA 的左孩子换成原 B 的右子树最后返回 B 作为局部根。调用方拿到这个新根之后把它接回原来 A 的位置即可。3.3 LR 型与 RL 型双旋分解成两步LR 型最坑的地方在于它不能用一次单旋解决。失衡节点 A 的左子树偏高但偏高的位置在“左孩子的右子树”里。如果直接对 A 做右旋你会发现旋转完依然失衡只是从一边歪变成了另一边歪问题原地打转。正确做法是先治局部再治整体第一步对 A 的左孩子 B 做一次左旋。做完之后 B 的左子树变高形态退化成 LL 型。第二步对失衡节点 A 做一次右旋。换句话说LR 型 先左旋孩子 再右旋自己。RL 型完全镜像RL 型 先右旋孩子 再左旋自己。以 LR 型为例走一遍完整过程。假设 A 的平衡因子是 2A 的左孩子 B 的平衡因子是 -1B 的右孩子 C 的较高侧是左子树。第一轮左旋 B 后C 顶替 B 成为 A 的左孩子第二轮右旋 AC 顶替 A 成为局部根。两步做完中序遍历序列保持不变且整棵子树恢复平衡。双旋代码用组合的方式写最干净Node* rotateLR(Node* A) { A-left rotateLeft(A-left); // 第一步左旋转左孩子 return rotateRight(A); // 第二步右旋失衡节点 } Node* rotateRL(Node* A) { A-right rotateRight(A-right); // 第一步右旋转右孩子 return rotateLeft(A); // 第二步左旋失衡节点 }注意第一步旋转完之后要把返回的新子树根重新赋值给 A-left 或 A-right否则你那一转等于白发功力指针指不到新节点上。这个细节写代码时错的人最多。3.4 旋转之后的高度更新顺序别搞反旋转操作里最容易被忽略、又最容易出 bug 的环节是高度更新的顺序。以右旋为例旋转前B 的右子树 T2 挂在 B 右侧A 的左指针指向 B。旋转后B 的右孩子变成 AA 的左孩子变成 T2。这意味着 A 的高度依赖于 T2而 B 的高度依赖于旋转后 A 的高度。所以必须先更新 A 的高度再更新 B 的高度。如果你先更新 B 的高度B 会拿旧的子树高度来算——错了。我建议养成一个铁律凡是旋转涉及的两个节点永远先更新降级的那个原来在上面的再更新升级的那个原来在下面的。每次写旋转代码都默念一遍能帮你省掉大量调试时间。4. 从零实现一棵 AVL 树C4.1 节点结构和辅助函数老规矩先定数据结构。AVL 节点在普通二叉树节点基础上多了两个字段子树高度 height以及为了调试方便的平衡因子可以现算不存。我一般不存平衡因子而是每次用height(left) - height(right)现算避免多维护一个变量的同步问题。#include iostream #include algorithm #include queue using namespace std; struct Node { int key; Node* left; Node* right; int height; Node(int k) : key(k), left(nullptr), right(nullptr), height(1) {} };辅助函数三个取高度、更新高度、算平衡因子。空指针的高度按 0 处理这是一个每次都要用不能嫌烦的地方int getHeight(Node* node) { return node ? node-height : 0; } void updateHeight(Node* node) { if (node) { node-height max(getHeight(node-left), getHeight(node-right)) 1; } } int getBalanceFactor(Node* node) { return node ? getHeight(node-left) - getHeight(node-right) : 0; }看到getHeight(nullptr)返回 0 了吗这就是空子树高度的约定——没有节点高度为 0叶子节点的高度是 1。一定要坚持这一套约定后面所有平衡判断都建立在这个 0/1 约定上。4.2 插入操作递归回溯中逐层修正插入逻辑分四步顺序绝对不能乱按 BST 规则递归找到插入位置创建新节点。沿递归路径逐层回溯更新每个祖先的 height。在每一个祖先处检查平衡因子。若失衡按形态执行旋转替换局部根。为什么递归天然适合 AVL 插入因为递归返回的时候天然就是“从最深的叶子往根回溯”的顺序正好匹配我们“自底向上更新高度、检查平衡”的需求。你不需要额外维护一个回溯用的栈函数调用栈本身就帮你把这个工作干了。Node* insert(Node* root, int key) { if (root nullptr) { return new Node(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; // 重复值不插入 } // 回溯更新高度 updateHeight(root); // 回溯检查平衡因子 int bf getBalanceFactor(root); // LL 型 if (bf 1 key root-left-key) { return rotateRight(root); } // RR 型 if (bf -1 key root-right-key) { return rotateLeft(root); } // LR 型 if (bf 1 key root-left-key) { root-left rotateLeft(root-left); return rotateRight(root); } // RL 型 if (bf -1 key root-right-key) { root-right rotateRight(root-right); return rotateLeft(root); } return root; }判断失衡形态我用的是“比较 key 和孩子 key 的大小”来判定新节点插在哪个方向。这个做法的前提是树里没有重复值如果支持重复值你得换个方式来比较方向比如先用递归的入参做方向标。每次旋转之后需要返回新的局部根所以整个插入函数的返回值设计成 Node* 是必须的——每一层递归都通过“把左/右孩子替换为递归返回的新根”来保持树结构正确。这个手法在普通 BST 的插入里也一样AVL 额外多做了平衡修正。4.3 删除操作比插入麻烦在哪删除是 AVL 树里最容易翻车的地方。麻烦主要在三处目标节点可能有两个孩子这时需要用右子树最小节点或左子树最大节点来接替接替完还要删掉那个替身节点涉及二次递归删除。删除节点后沿着回溯路径上可能有多个节点失衡需要一路修到根。插入时最多一次旋转就能修完删除则需要一直循环到根为止。替换节点的子树上至少一个子树高度减一它的高度变化会连带影响所有祖先所以要保证每层都重新 update 再检查。我实现一个递归删除完整贴出来供参考Node* minValueNode(Node* node) { Node* cur node; while (cur-left) { cur cur-left; } return cur; } Node* remove(Node* root, int key) { if (root nullptr) { return nullptr; } if (key root-key) { root-left remove(root-left, key); } else if (key root-key) { root-right remove(root-right, key); } else { // 找到了要删的节点 if (root-left nullptr || root-right nullptr) { Node* child root-left ? root-left : root-right; if (child nullptr) { delete root; return nullptr; } else { Node* temp child; *root *child; // 用值覆盖保留 root 的地址 delete child; } } else { Node* successor minValueNode(root-right); root-key successor-key; root-right remove(root-right, successor-key); } } // 如果树变成空树直接返回 if (root nullptr) { return nullptr; } updateHeight(root); int bf getBalanceFactor(root); // 四种形态修复 if (bf 1 getBalanceFactor(root-left) 0) { return rotateRight(root); } if (bf 1 getBalanceFactor(root-left) 0) { root-left rotateLeft(root-left); return rotateRight(root); } if (bf -1 getBalanceFactor(root-right) 0) { return rotateLeft(root); } if (bf -1 getBalanceFactor(root-right) 0) { root-right rotateRight(root-right); return rotateLeft(root); } return root; }注意和插入的判断差异插入时可以用 key 和 root-left-key 的关系来确定新节点方向但删除时我们不知道目标值相对于“孩子”的位置——因为要删的可能本来就是孩子节点自己。所以这里改用getBalanceFactor(root-left)来判断更高孩子内部的偏向更可靠。这是我实际调过 bug 之后总结出的改进版写法强烈推荐按这个风格写。*root *child这种做法是“只改值、不改地址”好处是整个树内部指针都不用改坏处是在树节点承载更大的数据时开销较大。如果 key 只是 int这个写法的简单优势就非常明显。如果你不希望值拷贝可以改成标准的“把节点摘掉”写法但慎防内存泄漏。4.4 验证工具用中序遍历和高度检查双重校验写 AVL 树的 debug 阶段不能只靠肉眼看结果。我习惯写两个验证函数每次插入或删除完都跑一遍inorder必须严格升序确认 BST 性质没被破坏。isBalanced递归检查每个节点的平衡因子绝对值不超过 1同时顺便递归校对每个节点的 height 是否等于max(左高, 右高) 1。void inorder(Node* root) { if (!root) return; inorder(root-left); cout root-key ; inorder(root-right); } bool isBalanced(Node* root) { if (!root) return true; int bf getBalanceFactor(root); if (abs(bf) 1) return false; return isBalanced(root-left) isBalanced(root-right); } void debugInfo(Node* root) { cout inorder: ; inorder(root); cout \nisBalanced: (isBalanced(root) ? true : false) endl; }写测试时最经典的序列就是按 1 到 100 的升序插入。普通 BST 会退化成链表AVL 树却能靠自动旋转把树高维持在个位数级别——你每次 debug 都能清楚看到平衡机制在起作用。5. 常见问题、避坑技巧与性能实测5.1 为什么我的 AVL 树插入没问题删除后却乱了这个问题的常见根源前面提到过插入和删除的失衡形态判定逻辑不能完全照搬。插入场景里你手上有“新插入的 key”这个明确信息可以拿它和孩子 key 比较来区分 LL/LR/RR/RL但删除场景里你没有这个参照点了必须改用getBalanceFactor(子树根)来判断孩子偏向。我自己第一次实现删除时把插入的四个 if 直接复制过去结果删了几个节点之后树就乱套了。原因就是判断条件不够稳健。另外删除后可能不止一个祖先失衡。别以为处理完一个就一定安全必须一路回溯到根。递归写法天然能做到这点因为每层递归返回前都会重新 update 和检查如果你用迭代写法至少要确保 while 循环一路走到根。5.2 高度更新漏掉一个全盘皆输AVL 树里最容易出 bug 的单项操作就是updateHeight的调用时机。漏更新一个节点的高度本层平衡因子可能恰好误判成正确值但上一层再用这个错误高度算平衡因子时就会爆雷。而且这种 bug 很隐蔽往往不是立刻崩而是插入若干节点后才悄悄出现一次小失衡肉眼很难抓住。我的防御策略是写一个assert(isBalanced(root))塞到每次插入、删除后的测试代码里。开发阶段随时验证后面改代码心里才有底。断言本身也是文档——后来人一看就知道这个函数的不变量是什么。5.3 随机数据压力测试验证你的树真的“稳”单元测试通过不等于实战没问题。我建议做一个“暴力验证”随机插 100,000 个不重复整数边插边查再随机删一批删的过程中继续查剩余所有节点能否正常找到最后再检验isBalanced。这个测试能同时验证搜索正确性、平衡性和内存安全性借助 valgrind 或 AddressSanitizer。另外可以统计插入完成后树的高度。理论上 100,000 个节点的 AVL 树高度约为 log₂(100,001) ≈ 17实际在 17~20 算正常。如果你测出来 30说明你的平衡机制有明显漏洞回去查旋转逻辑。这里有一组我实际测的对照数据供参考插入顺序均为升序n100,000随机查找 100,000 次实现树高查找耗时插入耗时普通 BST~100,000数十毫秒~数百毫秒极快但就是构建出链表AVL 树~18极稳定且极快旋转有轻微开销但可忽略每次看到 18 对 10 万我都替普通 BST 捏把汗。一个查找操作差出几个数量级在数据量大一些的实际项目里就是“能跑”和“不能跑”的区别。5.4 面试与应试中 AVL 树的常见考点如果是冲着面试刷题AVL 树常考的点通常集中在这几处手写插入并说明四种失衡形态与对应旋转。问为什么插入最多两次旋转而删除可能一路旋转到根——考察对“局部失衡 vs 全局失衡”的理解。给你一层插入前的树和一个新节点值让你画出插入后旋转的每一步。对比 AVL 树和红黑树的场景取舍不要只背结论要说出“查找多选 AVL、修改多选红黑树”的根本原因一个是严格平衡但旋转多一个是近似平衡但旋转少。会手写 AVL 树插入的人写红黑树就有了一半基本功这一层递进关系面试官也都懂。写在最后从 AVL 树里悟到的数据结构的“契约精神”我练 AVL 树练了不下四五遍每一次重写都有新体会。第一遍能跑通但代码很啰嗦第二遍开始懂旋转的本质是“保序换形”第三遍才真正理解了高度更新顺序的重要性。数据结构这东西你听别人讲永远觉得“就这么回事”轮到自己动手各种边界问题全部原形毕露。AVL 树是极少数把“自查自纠”做到极致的结构——它每次插入删除后都强制复核自身是否合规不放过任何一个失衡的节点。这种“过程中的自律”就是它区别于普通 BST 的灵魂。最后再分享一个小技巧写 AVL 树或任何自平衡树时把getHeight、updateHeight、getBalanceFactor这类两三行的辅助函数写得越干净越好。它们被调用的频率极高任何一点“偷懒”都会在后续调试时加倍还回来。先把地基打稳再谈上层旋转的优雅。如果你刚学完 AVL我的建议是顺手再把红黑树、B 树、跳表拿出来横向对比一下。你会发现所谓“高效数据结构”拼的不是某一次的聪明操作而是把不变量贯彻到底的执行力。
