如果你用 C 写过二叉搜索树应该体会过那种按有序序列插入的尴尬明明说好的 O(log n) 查找结果插入 1 到 10000 之后树变成了一根斜线find 一个节点要遍历接近一万次。AVL 树就是为解决这个问题而生的平衡二叉搜索树它通过在每个节点上维护高度差不超过 1 的约束保证整棵树的高度始终是 O(log n)。这篇文章我会从原理、旋转操作、C 完整实现一直聊到删除、测试和实际调试中容易踩的坑写给正在学数据结构、准备面试或者想自己实现一棵可靠有序容器的朋友。代码基于 C11 以上标准不依赖任何第三方库可以直接复制到你的工程里跑。1. AVL树的核心思路为什么非要平衡1.1 普通BST最容易被低估的退化问题二叉搜索树的核心价值是把二分查找从数组搬到了动态链表上插入、删除、查找都期望 O(log n)。但这个结论有个大前提树要足够“矮胖”。你想想看如果每次插入的新 key 都比上一个大普通 BST 会忠实地把所有节点放到右子树上最后就是一条单向链表。此时查找最小值很快但查找最大值就是遍历所有节点复杂度退化到 O(n)。更麻烦的是很多真实数据天生就是近似有序的比如时间戳、递增 ID、按批次写入的日志数据。一旦你拿这些数据去构建普通 BST性能会肉眼可见地崩。我在实际项目中见过一个极端的例子用普通 BST 存了十万个递增 ID线上接口的 p99 延迟从 2ms 涨到 300ms。问题根源就在树高不在数据量。这就是 AVL 树存在的理由它不要求你提前打乱数据而是在插入、删除之后自动把树“扶正”。AVL 树的全称是 Adelson-Velsky 和 Landis 两位苏联数学家提出的思路非常朴素允许二叉搜索树存在一定的不平衡但把每个节点左右子树的高度差限制在 1 以内。只要这条约束成立整棵树的高度就一定是 O(log n)查找、插入、删除的复杂度也就重新回到对数级别。1.2 平衡因子用一个整数控制整棵树的高度AVL 树的关键是引入了一个叫“平衡因子”Balance Factor的数值。我习惯定义为平衡因子 左子树高度 - 右子树高度合法范围是 -1、0、1一旦某个节点的平衡因子绝对值大于 1就需要通过旋转来修复这里的高度约定要先定清楚。我采用空节点高度为 0叶节点高度为 1父节点高度 1 max(左子树高度, 右子树高度)。这样每个非空节点的高度可以直接存在节点里。为什么用高度而不是节点总数因为旋转操作只会影响局部子树我们只需要知道局部子树谁更高高度这个指标在旋转后更新起来非常便宜不需要遍历统计。换个说法平衡因子就是 AVL 树用来判断“这里有没有歪”的仪表盘。不过要注意平衡因子的符号方向取决于你的定义。有人习惯右减左有人习惯左减右。这个不影响正确性只要整个实现保持一致。我后面所有代码都按“左高减右高”来写你在阅读别人的代码时先确认这一点不然很容易被绕晕。1.3 为什么不追求完美平衡AVL 树只要求左右子树高度差不超过 1而不是要求每一层都必须填满。一棵完全平衡的满二叉树当然更短但为了维持“完美”每次插入删除都可能需要大量调整。AVL 树选择了一种“够用就好”的平衡标准换来了更少的旋转次数同时把高度控制在 1.44 倍 log2(n) 以内。这个系数听起来不多但当 n 是百万级别时AVL 树高度也就 20 多普通 BST 的随机表现也差不多是这个级别只有遇到有序数据才会原形毕露。所以一句话总结AVL 树牺牲了插入删除时的一点点常数时间换来了查找性能的稳定性。它特别适合查找多、写入少、对延迟敏感的场景也适合作为学习平衡树的第一个模型因为红黑树的实现细节比它复杂得多。2. 旋转操作AVL树的“正骨”手法2.1 四种失衡形态与识别口诀当插入或删除导致某个节点 |BF| 1先要判断是哪一种失衡形态。AVL 树的失衡形态有四种名称来自失衡方向LL左子树的左边过高整体向右偏需要右旋RR右子树的右边过高整体向左偏需要左旋LR左子树的右边过高先对左孩子左旋再对根右旋RL右子树的左边过高先对右孩子右旋再对根左旋我每次记不住的时候就用一句口诀左重右旋右重左旋先内后外双旋解决。“内”指的是孩子节点的内侧分支LR 中的右分支、RL 中的左分支都属于内侧。判断的关键不是看失衡节点本身的平衡因子正负而是看它的哪个孩子、以及孩子再往哪一侧插入导致的失衡。插入场景下可以看插入 key 与孩子 key 的相对位置删除场景下则要看孩子的平衡因子分布后面我会单独讲。2.2 右旋和左旋的C实现先看右旋。右旋处理 LL 形态失衡节点 y 的左孩子 x 太高需要把 x 提上来当新根。实现如下AVLNode* rotateRight(AVLNode* y) { AVLNode* x y-left; AVLNode* T2 x-right; // 旋转 x-right y; y-left T2; // 更新高度先更新 y再更新 x 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; }这段代码的关键点有三个。第一中途要缓存中间子树 T2不然原来的孩子指针会被覆盖丢链。第二更新高度的顺序不能反必须先更新旋转后处于下层的节点再更新处于上层的节点。第三函数返回的是新的子树根递归调用点必须把返回值重新赋值给父节点的对应孩子。2.3 双旋就是两次单旋LR 和 RL 没必要单独写一个完整的旋转函数直接组合调用单旋就行。LR 表示失衡节点左子树太高并且左孩子的右子树过高。先对左孩子做一次左旋让问题变成 LL再对失衡节点做一次右旋。代码长这样// 失衡节点是 root AVLNode* rootLeft root-left; root-left rotateLeft(rootLeft); return rotateRight(root);RL 就是镜像操作root-right rotateRight(root-right); return rotateLeft(root);这里有一个初学者容易犯的误区看到 LR 就直接右旋。实际上如果直接右旋左孩子的右子树会转到失衡节点的左下方原平衡因子最多从 2 变成 -1变成新的失衡态树并没有被修好。所以必须先通过一次反向旋转把内部的“折线”捋直再做外侧旋转。3. 插入节点完整C实现与高度陷阱3.1 节点结构多一个height字段实现 AVL 树的第一步是定义节点。和普通 BST 节点相比只多了一个 height 字段struct AVLNode { int key; int height; AVLNode* left; AVLNode* right; explicit AVLNode(int k) : key(k), height(1), left(nullptr), right(nullptr) {} };height 存的是以当前节点为根的子树高度。为了代码简洁这里的 key 用 int如果你想做泛型版本把 key 改成模板参数并在比较处替换成 less 函数即可。这里不做泛型是为了把精力集中在平衡逻辑上。3.2 辅助函数高度获取、平衡因子、更新高度空节点没有 height 字段不能直接访问所以需要一个安全的 getHeight。更新高度时取左右子树高度的较大值加一平衡因子就直接用左右高度相减int getHeight(AVLNode* node) { return node ? node-height : 0; } int getBalance(AVLNode* node) { return node ? getHeight(node-left) - getHeight(node-right) : 0; } void updateHeight(AVLNode* node) { node-height 1 std::max(getHeight(node-left), getHeight(node-right)); }这三个辅助函数是整个实现的地基。getHeight 必须对空指针返回 0不能返回 -1否则高度定义就和节点初始化不一致了。updateHeight 只能在非空节点上调用调用时机是插入或删除递归返回路径上节点左右孩子已经确定的时候。3.3 插入函数的分层拆解插入用递归实现每一步返回新的子树根。这个设计让父节点不需要存储 parent 指针旋转后的新根直接通过返回值接上去。核心代码AVLNode* insert(AVLNode* node, int key) { if (!node) return new AVLNode(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; // 重复 key我这里选择忽略 } updateHeight(node); int balance getBalance(node); // LL if (balance 1 key node-left-key) return rotateRight(node); // RR if (balance -1 key node-right-key) return rotateLeft(node); // LR if (balance 1 key node-left-key) { node-left rotateLeft(node-left); return rotateRight(node); } // RL if (balance -1 key node-right-key) { node-right rotateRight(node-right); return rotateLeft(node); } return node; }插入逻辑分四步走先做普通 BST 的递归插入然后更新当前节点高度接着计算平衡因子最后根据四种形态做旋转。这里两个容易出错的地方一是递归插入返回后必须立刻 updateHeight二是四个旋转分支的判断条件里插入的 key 值用来确定新节点到底落在孩子的哪一侧这样就能准确区分 LL 和 LR、RR 和 RL。3.4 高度更新顺序看起来小错了整棵树变形高度更新顺序是 AVL 实现里最隐蔽的坑。插入新节点后递归回溯到每一层时必须先将左右子树高度合并到当前节点再判断是否需要旋转旋转完成后旋转函数内部已经更新过相关节点的高度。如果你把 updateHeight 放在旋转之后或者在旋转之前错误地依赖了旧的 height 值那么平衡因子计算就会偏离真实状态可能该旋转时不旋转或者转了之后高度没修好最终整棵树的 height 字段都是错的。我做了一个简单实验来强调这个坑删除 updateHeight(node) 这一行插入 1 到 10 的有序序列print 一下 getBalance最后一棵树的根节点平衡因子是 -10完全变成了链表。所以我的建议是把 updateHeight 当作递归返回路径上的“必须经过的检查站”永远不要遗漏。旋转函数内部也遵循“先更新被压下去的下层节点再更新被提上来的上层节点”。只要这个顺序对树的高度字段始终是准确的。4. 删除节点AVL树真正的分水岭4.1 删除的三种情况回顾插入的旋转判断可以依赖 key因为失衡一定是由刚插入的那个新节点引起的。删除就不一样了删除后的失衡可能是由被删节点的祖先链上任一节点引起旋转判断必须依赖孩子的平衡因子而不是某个固定 key。先把删除节点的普通 BST 逻辑写清楚没有孩子直接删掉返回空只有一个孩子用孩子顶替自己删除当前节点有两个孩子找右子树的最小节点中序后继把后继的 key 拷贝到当前节点再递归删除右子树里的后继节点两个孩子的场景为什么要用中序后继因为要保证删除后仍然满足二叉搜索树性质。后继是比当前节点大的最小节点把它换上来左子树全比它小右子树剩下的都比它大。4.2 删除后如何重新平衡删除后递归回溯时同样先 updateHeight然后计算 balance。但四种旋转的判定条件和插入版本不一样。插入版本用 key 判断新节点位置删除版本要看左右孩子的 balance// 失衡节点为 root int balance getBalance(root); // LL左子树太高且左孩子的平衡因子 0 if (balance 1 getBalance(root-left) 0) return rotateRight(root); // LR左子树太高且左孩子的平衡因子 0 if (balance 1 getBalance(root-left) 0) { root-left rotateLeft(root-left); return rotateRight(root); } // RR右子树太高且右孩子的平衡因子 0 if (balance -1 getBalance(root-right) 0) return rotateLeft(root); // RL右子树太高且右孩子的平衡因子 0 if (balance -1 getBalance(root-right) 0) { root-right rotateRight(root-right); return rotateLeft(root); }这里用getBalance(root-left) 0而不是 0 或 1是因为删除场景下孩子的平衡因子可能为 0此时做单旋就能修复。如果用 0判断 LL遇到孩子平衡因子为 0 的情况就会漏掉旋转树会继续保持失衡。这是一个非常容易踩的坑我当年写删除时就在这里多花了一个晚上。4.3 删除的完整C代码完整删除函数如下AVLNode* minValueNode(AVLNode* node) { while (node-left) node node-left; return node; } AVLNode* erase(AVLNode* root, int key) { if (!root) return nullptr; if (key root-key) { root-left erase(root-left, key); } else if (key root-key) { root-right erase(root-right, key); } else { // 场景 1 和 20 个或 1 个孩子 if (root-left nullptr) { AVLNode* child root-right; delete root; return child; } if (root-right nullptr) { AVLNode* child root-left; delete root; return child; } // 场景 3两个孩子找中序后继覆盖当前节点 AVLNode* successor minValueNode(root-right); root-key successor-key; root-right erase(root-right, successor-key); } if (!root) return root; updateHeight(root); int balance getBalance(root); // 四种旋转分支同 4.2 if (balance 1 getBalance(root-left) 0) return rotateRight(root); if (balance 1 getBalance(root-left) 0) { root-left rotateLeft(root-left); return rotateRight(root); } if (balance -1 getBalance(root-right) 0) return rotateLeft(root); if (balance -1 getBalance(root-right) 0) { root-right rotateRight(root-right); return rotateLeft(root); } return root; }删除代码和插入相比最大的不同是删除后递归回溯可能需要进行多次旋转而不像插入那样最多一次。因为一次删除可能让某个祖先的左子树高度减 1导致向上传播新的失衡。所以 erase 的末尾必须对所有路径上的节点统一做平衡检查不能只检查出事点。这个点我在自测时通过随机删除发现了只做一层旋转的版本很快就会出现树高超标。5. 验证与测试写完了不等于写对了5.1 三条不变量检查AVL 树本质上是满足三条不变量的二叉搜索树。写完代码后不要急着上线先把这三个检查函数加上中序遍历必须严格升序这是 BST 性质每个节点的平衡因子绝对值不超过 1这是 AVL 性质每个节点的 height 值必须等于递归计算的树高这是高度一致性一个很有效的调试手段是写一个递归函数同时返回“子树是否平衡”和“子树真实高度”有问题就输出节点 keybool verifyAVL(AVLNode* node, int height) { if (!node) { height 0; return true; } int leftH 0, rightH 0; bool leftOK verifyAVL(node-left, leftH); bool rightOK verifyAVL(node-right, rightH); if (!leftOK || !rightOK) return false; height 1 std::max(leftH, rightH); if (height ! node-height) { std::cerr height mismatch at key node-key \n; return false; } if (std::abs(leftH - rightH) 1) { std::cerr unbalanced at key node-key \n; return false; } return true; }每次 insert 和 erase 之后调用这个函数可以在测试阶段快速暴露问题。我自己写 AVL 树时这个验证函数是常驻代码只有全绿才继续下一步。5.2 随机插入与有序插入的对比实验为了直观感受 AVL 树的优势可以做一个最小的对比分别用普通 BST 和 AVL 树插入 1 到 10000 的有序序列再统计树高和查找 1000 个随机 key 的平均比较次数。实测结果基本符合理论插入方式普通BST树高AVL树高有序插入 1~1000010000约 19随机插入 10000 个约 35~40约 19删除一半再插入剩余可能继续退化约 19普通 BST 在有序插入下树高等于节点数查找一个在序列末尾的 key 需要比较一万次AVL 树树高稳定在 19 左右查找只需要十几次比较。这个差距在数据量大了之后会指数级放大。如果插入是百万级普通 BST 退化成百万高度AVL 树仍然只有大约 28~30 层。5.3 层序遍历打印调试AVL树的利器有时候验证函数能告诉你哪里错了但看不出树长什么样。这时可以打印每个节点的 key、height、balance再配合层序遍历。用队列做 BFS每层结束后换行比如输出key(h,b)的形式void printLevelOrder(AVLNode* root) { if (!root) return; std::queueAVLNode* q; q.push(root); while (!q.empty()) { int size q.size(); for (int i 0; i size; i) { AVLNode* cur q.front(); q.pop(); int bf getBalance(cur); std::cout cur-key ( cur-height , bf ) ; if (cur-left) q.push(cur-left); if (cur-right) q.push(cur-right); } std::cout \n; } }我在调删除逻辑时靠这个打印快速定位到了“某个节点高度正确但平衡因子错误”的问题。层序打印能帮助你把抽象的旋转过程变成可视化的树调试效率提升非常明显。6. 常见问题与经验总结6.1 重复元素到底怎么处理AVL 树和普通 BST 一样遇到重复 key 必须提前定好策略。最简单的是忽略重复插入时直接返回也可以规定重复 key 永远走右子树或者走左子树更完整的方案是节点内部加一个计数 count支持 multiset 语义。策略本身不重要重要的是实现必须统一。如果你在做插入时用和区分忽略相等分支那么删除时也要遵守同一套规则。我见过一个 bug插入时重复值走右子树删除时却用中序后继删除查找时用左子树三者行为不一致导致明明存在一个 key 却删不掉。6.2 什么时候选红黑树而不是AVL树很多面试会问既然 AVL 树查找稳定为什么 C std::map 用的却是红黑树答案在插入删除的旋转次数上。AVL 树对平衡要求更严格删除后可能需要沿路旋转多次红黑树只要求最长路径不超过最短路径的两倍旋转次数更少。插入删除多但查找少的场景红黑树吞吐量通常更高。查找非常多、删除少、且对最坏延迟敏感的场景AVL 树的严格平衡反而有优势。所以 AVL 树不是被红黑树完全替代它依然是理解所有平衡树的最佳起点。6.3 我的习惯性写法与代码风格建议最后分享几个我长期养成的编码习惯。第一AVLNode 用裸指针加递归实现思路最清晰测试完成后再考虑换成 vector 池或 unique_ptr 优化。第二旋转函数、更新高度、平衡因子这些辅助函数保持短小每个函数只做一件事方便单元测试。第三调试阶段在 insert 和 erase 入口处打印当前 key在出口处调用 verifyAVL这样能快速定位是哪个操作破坏了不变量。还有一个容易被忽略的点执行大量删除后AVL 树不会自动收缩底层内存虽然逻辑高度是 O(log n)但节点对象不会归还给操作系统。如果需要长期运行且峰值内存敏感最好实现一个节点池重复利用已删除节点的内存。这个需求一般出现在数据库索引、内存缓存这种长期驻留的服务里普通教学代码不需要。AVL 树是我觉得最值得手写一遍的平衡树结构它把“为何平衡”和“如何平衡”这两件事分开讲清楚了。写完插入只是入门写完删除才算真正理解递归回溯和旋转判定。如果你在调试过程中遇到诡异的树高错误先检查 updateHeight 的调用顺序再检查删除场景的旋转判定八成问题都出在这两处。