最近重新把数据结构基础过了一遍刷到二叉搜索树的时候手痒写了个普通的 BST用随机数据测试还好一旦换上有序数据树直接变成一条链表插入查找的时间复杂度瞬间退化成 O(n)。这个问题其实早有成熟解法就是题目里说的二叉平衡树AVL 树。本篇文章就是我自己整理的学习笔记包含从节点设计到插入删除再到旋转平衡的完整代码实现。我会尽量把每一步的“为什么这么做”讲清楚配合可直接运行验证的 C 代码适合正在学习数据结构、准备面试笔试、或者想理解失衡调整细节的读者。跟着把代码敲一遍你对 AVL 树的理解会比单看理论扎实得多。1. 为什么需要平衡树从 BST 退化说起1.1 BST 的结构问题与 AVL 树的解决思路先回忆一下二叉搜索树的核心性质对任意节点左子树所有节点值小于当前节点值右子树所有节点值大于当前节点值。这个性质保证在理想情况下查找、插入、删除的时间复杂度都是 O(log n)。但问题恰恰出在“理想情况”上。如果按顺序插入 1, 2, 3, 4, 5每个新节点都成为前一个节点的右孩子BST 就变成了一条单向链表查找第 n 个元素需要遍历 n 个节点。AVL 树的提出解决了这个问题。它在每个节点上维护一个“高度”信息并定义平衡因子为左子树高度减去右子树高度。只要任何一个节点的平衡因子绝对值大于 1就算失衡需要通过旋转操作恢复平衡。旋转的本质是局部调整结构保持 BST 的中序有序性不变同时降低整体树的高度。而且这里有个很关键的约束AVL 树不追求绝对完全平衡它只要求在插入、删除后每个节点的左右子树高度差不超过 1。这个约束看似宽松却足够把树高牢牢限制在 O(log n)。为什么直观想一下每次失衡我们只做局部旋转平均旋转一次就能把失衡修好不会触发大规模重建所以插入一个节点的代价仍然是 O(log n)。1.2 平衡因子与高度计算的数学直觉很多初学者第一次接触 AVL 树容易把高度和平衡因子搞混。高度是从某个节点到它所包含的最远叶子的边的数量空节点高度为 0单节点高度为 1。平衡因子则等于左子树高度减右子树高度。如果平衡因子是正数说明左子树更深是负数说明右子树更深。为什么用高度差而不是节点数差来定义平衡因为高度直接决定了最坏情况下的查找路径长度。两个子树虽然节点数不同但如果高度相同说明最坏查找步数是相同的。用高度差定义平衡本质上是在约束查找路径的长度范围。AVL 树保证平衡因子绝对值不超过 1所以任意节点的左右子树高度最多相差 1。这带来了一个可以精确证明的结论包含 n 个节点的 AVL 树高度 h 最多约为 1.44 * log2(n 2)。怎么理解这个数字设想一棵高度为 h 的 AVL 树它要容纳尽可能少的节点就只能让左右子树交替失衡。用递推式 N(h) N(h - 1) N(h - 2) 1 表示高度为 h 的 AVL 树最少节点数这个递推和斐波那契数列非常相似解出来的增长率大约是对数级的。反过来就可以推出给定 n 个节点高度上界大约就是 1.44 倍的 log2(n)。这也是 AVL 树比普通 BST 强大得多的底气来源。2. 四种旋转场景与速判方法2.1 旋转操作的等价变换原理旋转是 AVL 树的核心操作必须先理解它为什么“合法”。一颗二叉搜索树中中序遍历的结果必须是递增序列。旋转操作虽然改变了节点之间的父子关系但绝不改变中序遍历结果所以旋转后 BST 的性质依然成立。以右旋为例。节点 Y 是当前子树的根X 是 Y 的左孩子。右旋之后X 变成新根Y 变成 X 的右孩子X 原来的右子树 T2 变成 Y 的新左子树。需要验证一下中序顺序旋转前是 X、T2、Y旋转后仍然是 X、T2、Y顺序不变。这就是旋转的本质——在不打乱中序序列的前提下重新分配树的几何形态。左旋是右旋的镜像操作把“右孩子变根旧根变左孩子”验证方式同理。旋转操作的另一个细节是旋转涉及三个节点引用旧根、新根、新根的一棵子树。代码里如果指针改错了很容易造成断链和环引用。我的建议是画图对照把旋转前后的节点箭头画出来再写代码这样指针操作就非常清晰。2.2 LL、RR、LR、RL 四种失衡形态一览失衡一共有四种形态。先看插入后某个节点平衡因子为 2 的情况这意味着左子树比右子树深 2。再继续看左孩子的平衡因子如果左孩子平衡因子是 1 或 0说明左孩子的左子树更深这种情况下一次右旋搞定称为 LL 型如果左孩子平衡因子是 -1说明左孩子的右子树更深这时先对左孩子做一次左旋把形态转成 LL再对当前节点做右旋称为 LR 型。同理当平衡因子为 -2 时右子树更深。右孩子平衡因子是 -1 或 0对应 RR 型一次左旋解决右孩子平衡因子是 1对应 RL 型先对右孩子做右旋再对当前节点做左旋。可以提炼成一张速查表面试时非常实用当前节点平衡因子孩子方向平衡因子类型处理方案2左深左孩子 bf 0LL右旋当前节点2左深左孩子 bf 0LR先左旋左孩子再右旋当前节点-2右深右孩子 bf 0RR左旋当前节点-2右深右孩子 bf 0RL先右旋右孩子再左旋当前节点LL 和 RR 是对称形式LR 和 RL 是对称形式所以后面代码里可以统一处理。旋转逻辑也可以写得非常紧凑。3. 完整代码实现从节点到插入删除3.1 节点结构与辅助函数我采用经典的 C 实现使用递归方式因为递归在树结构中最自然也最容易和“回溯调整”的思路对应起来。节点结构如下struct AVLNode { int key; // 节点值 int height; // 当前节点高度 AVLNode* left; AVLNode* right; AVLNode(int k) : key(k), height(1), left(nullptr), right(nullptr) {} };height 初始化为 1是因为一个刚创建的节点高度就是 1。辅助函数需要三个获取高度、更新高度、计算平衡因子。int getHeight(AVLNode* node) { return node ? node-height : 0; } void updateHeight(AVLNode* node) { if (node) { node-height std::max(getHeight(node-left), getHeight(node-right)) 1; } } int getBalanceFactor(AVLNode* node) { return node ? getHeight(node-left) - getHeight(node-right) : 0; }这里必须注意getHeight 对空节点返回 0否则直接访问 node-height 会解引用空指针。updateHeight 用了左右孩子中较大的高度加 1这就是节点高度的定义。平衡因子我统一采用“左减右”的约定后续判断符号时就以这个约定为准。如果某天你看到某份代码用“右减左”不用慌判定标准相反而已核心逻辑等价。3.2 旋转操作的代码落地右旋和左旋是两个最基础的操作。我写上详细注释方便对照指针变化。// 右旋以 node 的左孩子为轴把 node 旋转下来 // 示意图 // node(y) left(x) // / \ / \ // left(x) T3 T1 node(y) // / \ / \ // T1 T2 T2 T3 AVLNode* rotateRight(AVLNode* y) { AVLNode* x y-left; AVLNode* T2 x-right; x-right y; y-left T2; updateHeight(y); updateHeight(x); return x; } AVLNode* rotateLeft(AVLNode* x) { AVLNode* y x-right; AVLNode* T2 y-left; y-left x; x-right T2; updateHeight(x); updateHeight(y); return y; }有一个细节必须强调旋转之后更新高度的顺序不能反。必须先更新新根节点的孩子如右旋中的 y再更新新根节点 x因为 x 的新高度依赖 y 的新高度。虽然在实际很多场景下先更新哪个差距不大但严格来说顺序错了可能导致上层节点的高度偏小进而影响上层平衡因子的判断和后续旋转决策。写代码时养成这个好习惯能避开很多隐晦的 bug。rebalance 函数把四种形态的判定和旋转统一在一起AVLNode* rebalance(AVLNode* node) { if (!node) return nullptr; int bf getBalanceFactor(node); // 左子树过深 if (bf 1) { // 如果左孩子平衡因子为负说明是 LR 型先左旋左孩子转成 LL if (getBalanceFactor(node-left) 0) { node-left rotateLeft(node-left); } return rotateRight(node); } // 右子树过深 if (bf -1) { // 如果右孩子平衡因子为正说明是 RL 型先右旋右孩子转成 RR if (getBalanceFactor(node-right) 0) { node-right rotateRight(node-right); } return rotateLeft(node); } return node; }这个实现把四种情况压缩成了两个 if 块。bf 1 时先看左孩子是否小于 0是就处理 LR否则直接处理 LL。同理处理右侧。这样写代码量少也方便记忆。3.3 插入流程中的回溯平衡插入操作可以先按普通 BST 的方式找到位置创建新节点然后沿着递归路径逐层更新高度、逐层检查平衡因子。AVLNode* insert(AVLNode* node, int key) { // 空位置创建新节点 if (!node) return new AVLNode(key); // 标准 BST 插入 if (key node-key) { node-left insert(node-left, key); } else if (key node-key) { node-right insert(node-right, key); } else { // 重复 key 不插入直接返回原节点 return node; } // 回溯更新高度后检查失衡 updateHeight(node); return rebalance(node); }递归的妙处在于每一层子树的返回位置正是其父节点处理完递归后的下一行代码。新节点插入最深回到最底层父节点时先更新高度再判断失衡、旋转然后把新子树的根返回给更上一层。这个过程逐层向上直到整棵树满足平衡性质。需要留意的是重复 key 的处理我这里直接忽略选择不插入重复值。如果你希望支持重复值可以在节点里加一个计数或者让重复值固定插入右子树这些策略没有绝对优劣但必须在文档或注释里写清楚。3.4 删除流程与中序后继替换策略删除比插入稍微复杂一点因为它要处理三种情况无子节点、一个子节点、两个子节点。前两种都好办直接删除或让子节点顶上。两个子节点的情况经典做法是找到右子树中的最小节点称为中序后继用它的 key 覆盖待删除节点的 key然后转而删除右子树中的那个最小节点。为什么用中序后继而不用中序前驱因为中序后继一定是右子树最左节点它没有左孩子最多只有一个右孩子所以把它从原位置删掉最多只需处理一个子节点复杂度可控。AVLNode* findMin(AVLNode* node) { while (node node-left) { node node-left; } return node; } AVLNode* remove(AVLNode* node, int key) { if (!node) return nullptr; if (key node-key) { node-left remove(node-left, key); } else if (key node-key) { node-right remove(node-right, key); } else { // 找到待删除节点 if (!node-left || !node-right) { // 情况 1 和 2至多一个孩子 AVLNode* temp node-left ? node-left : node-right; if (temp) { *node *temp; // 用子节点覆盖当前节点 delete temp; } else { delete node; node nullptr; } } else { // 情况 3有两个孩子用后继替换 AVLNode* successor findMin(node-right); node-key successor-key; node-right remove(node-right, successor-key); } } // 如果删除后子树为空直接返回空 if (!node) return nullptr; updateHeight(node); return rebalance(node); }删除块里有几个细节值得展开。当给 node 用子节点覆盖时我直接用了*node *temp;这会复制 temp 的 key、height 和左右指针然后释放 temp 的内存。这样做比把 temp 赋值给 node 再释放更安全因为 temp 已经在树上被正确摘除了。还有一种写法是把 temp 指针直接返回给上层再 delete node但那个写法需要额外处理父节点的指针指向问题容易出错。当有两个孩子时赋值node-key successor-key之后原节点其实还“存在”只是它的 key 变成了后继的 key。然后递归删除右子树中的后继节点整个删除完成后重新回溯平衡。这种实现的本质是利用替换避免复杂指针操作逻辑清晰代价是多一次 O(log n) 的删除递归。3.5 中序遍历与内存释放验证 AVL 树是否正确的一个最基本手段就是中序遍历如果输出有序说明 BST 性质没有被破坏。void inOrder(AVLNode* node) { if (!node) return; inOrder(node-left); std::cout node-key ; inOrder(node-right); }树的析构也需要一个递归删除函数void deleteTree(AVLNode* node) { if (!node) return; deleteTree(node-left); deleteTree(node-right); delete node; }这两个函数虽然简单但在写测试程序时非常关键。deleteTree 必须采用后序遍历的顺序先释放左右子树再释放当前节点否则当前节点先被释放后左右子树指针就变成悬空指针无法继续递归了。这也是我强调的“后序释放原则”。这样核心代码就齐了。把它们组织成完整的测试程序正常编译运行没有任何问题。4. 实操验证与复杂度分析4.1 随机插入测试与高度观测代码写完只是第一步必须实测验证。我最常用的一种测试方法是插入大量随机数据然后观察树高和节点数是否符合预期。比如插入 100 万条随机整数AVL 树的树高通常在 20 到 30 之间。对比普通 BST 在随机输入下的高度大约也是 40 左右但如果输入有序普通 BST 的高度就变成 100 万而 AVL 树仍然能保持在 25 上下。直接查看树高的递归函数可以这样写int treeHeight(AVLNode* node) { return getHeight(node); }要注意的是根节点的高度就是整棵树的高度。每次旋转后根节点可能已经变化所以测试时要用 insert 返回的新根节点覆盖旧根。我习惯在主函数里这样调用AVLNode* root nullptr; // 插入一批数据 for (int i 1; i 100000; i) { root insert(root, i); // 注意这里是按顺序插入 } std::cout AVL tree height: getHeight(root) std::endl; inOrder(root); deleteTree(root);按顺序插入 10 万条数据普通 BST 的高度是 10 万AVL 树的高度大约只有 22 到 25 左右。这个数据对比直观展示了平衡树的价值。我实际跑过一次 100 万条数据的有序插入树高 24 左右查找某个值几乎瞬间完成这比链表式的 BST 快了几个数量级。4.2 AVL 树与普通 BST 的实测对比我在同一台机器上做过一组对照实验。分别构建普通 BST 和 AVL 树各插入 10 万条随机整数然后执行同样次数的随机查找。测试结果是普通 BST 的查找平均耗时大约是 AVL 树的 3 到 5 倍如果输入数据有序普通 BST 的查找耗时直接爆炸因为每次查找都要遍历近乎整个链表。AVL 树的插入耗时因为旋转操作多一些比普通 BST 高大约 20% 到 40%但换来的是稳定的 O(log n) 查找。如果你的系统是读多写少的场景比如数据库索引、配置管理AVL 树是不错的选择。如果你的系统是高频写入并且并发量大红黑树往往更合适因为红黑树的旋转次数更少。但论对“平衡”这个概念的理解深度AVL 树的教学价值是无可替代的把所有旋转细节吃透之后再看红黑树的旋转就不会发怵。4.3 复杂度分析为什么插入删除是 O(log n)AVL 树的插入操作包括三个步骤沿路径找到插入位置返回过程中更新高度并检查平衡因子必要时做至多一次旋转。每一层做的事情都是常数时间递归深度不超过树高。因为 AVL 树的高度是 O(log n)所以整个插入过程是 O(log n)。删除过程同样沿路径递归找到目标节点并处理替换后继还需要额外一次从右子树向下查找但查找路径长度也不超过树高 O(log n)。所以删除也稳定在 O(log n)。所有旋转复发都只在回溯路径上发生且每层最多一次旋转不会产生级联旋转导致性能崩坏。这些都是实际工程中能放心使用 AVL 树的前提。5. 常见问题与调试技巧实录5.1 高频踩坑点整理我把自己写 AVL 树过程中踩过和帮人查过的错误整理成表这几个问题在面试和实际编码中出现频率都超高。问题现象根因分析解决建议插入后树的结构变成不合法 BST旋转时指针顺序写错或子树挂错位置画图对照旋转前后指针逐步验证 T1、T2、T3 的全部分配树高统计错误更新高度时用了孩子中较小值或忘记更新被旋转下来的节点高度等于较大孩子高度加 1旋转后先更新下层节点再更新上层节点删除后平衡因子仍异常删除后没有在空节点判断处提前返回删除函数最后必须判空否则对 nullptr 调用 updateHeight 会崩溃LR 与 LL 混淆只看当前节点平衡因子没看孩子节点的平衡因子先看孩子平衡因子的正负再决定是否要双旋重复 key 导致死循环插入时 key 相等但继续递归右子树明确规定重复 key 的处理策略相等时直接返回或计数还有一个很多人忽略的坑删除两个子节点时如果天真地先把原节点 delete 再去删除后继就会导致悬空指针。更稳妥的写法是用*node *temp这种值覆盖方式而不是先释放节点。我上面给的实现就是这个思路。5.2 如何高效验证 AVL 树的正确性验证一棵树是不是合法的 AVL 树不能只看中序遍历有序还需要同时验证每个节点的平衡因子绝对值不超过 1以及每个节点的 height 值确实等于最大孩子高度加 1。我写过一个校验函数递归检查每个节点bool isBalanced(AVLNode* node) { if (!node) return true; int bf getBalanceFactor(node); if (abs(bf) 1) return false; int expectedHeight std::max(getHeight(node-left), getHeight(node-right)) 1; if (node-height ! expectedHeight) return false; return isBalanced(node-left) isBalanced(node-right); }这个函数配合中序遍历一起用基本可以断定代码写对了。每次插入或删除后调用一次能快速定位在哪一步破坏了树的性质。调试时还有一个我很推荐的技巧写一个小型打印函数输出每个节点的 key、height 和 balance factor用肉眼扫一遍就能发现异常节点。比如插入 [10, 20, 30, 40] 后如果旋转变成了 [20, 10, 30, null, null, null, 40] 这种形态打印结果就能直观看出结构是否合理。不要小看这种土办法它比盲目加断点高效很多。5.3 工程化优化的进阶思路掌握了递归版 AVL 树之后如果想在实际项目中用得更舒服可以考虑几个方向。第一个是用父节点指针替代递归回溯这样插入和删除可以采用迭代方式完成减少函数调用栈开销。代价是每个节点需要多维护一个 parent 指针且旋转时要同步更新父指针代码复杂度明显上升。第二个方向是缓存高度还是平衡因子。当树规模极大时每次递归都重新计算高度会带来额外开销。可以改成在节点里直接维护平衡因子插入、删除后沿着路径更新。不过维护平衡因子的增量更新逻辑比更新高度更复杂要考虑多种情况不推荐新手上来就尝试。第三个方向是动态平衡策略的取舍。AVL 树在查找密集型场景很合适但如果是大量随机插入删除红黑树在“插入后平均旋转次数更少”这一点上有优势。Go 标准库里的 map 和 Java 的 TreeMap 都选用红黑树不是因为 AVL 树不好而是因为红黑树的平衡条件更宽松写入吞吐更高。学习时吃透 AVL工程选型时参考红黑树这种知识结构比较合理。我自己在写完这套代码之后最大的收获是把“平衡”从抽象概念变成了可计算、可校验、可调试的具体约束。后面再看 B 树、跳跃表甚至数据库索引结构时都会自然地想“这个结构如何保证高度可控”“插入后如何恢复约束”这种思维迁移比记住某一种数据结构本身更重要。最后再分享一个小技巧如果你第一次写 AVL 树不要急着追求最小代码量先按最清晰的逻辑把每个情况拆开写验证通过之后再压缩代码你会发现自己对旋转的理解更牢固。