C学到现在最常挂在嘴边的数据结构除了链表、栈、队列估计就要轮到二叉树了。而二叉搜索树一旦遇到有序插入直接退化成一个长链表查找性能从 O(logN) 掉到 O(N)让人血压上去。AVL 树就是为解决这个尴尬产生的——它在每次插入或删除后都通过最多几次旋转让整棵树保持高度平衡。我最近用 C 完整实现了一遍 AVL 树的插入、删除、旋转和自测踩了不少坑。很多坑藏得很深但一旦理解了旋转的对称性代码实际上可以短得让人惊讶。这篇文章适合那些已经会写普通二叉搜索树想进一步搞懂自平衡机制的 C 学习者。如果你还没写过二叉树建议先去复习一下前驱、后继、递归遍历AVL 树只是在这个基础上多加了一步平衡修复。正文里每一段代码我都跑过旋转、删除、验证函数都能直接复制下来用。你会看到对平衡因子的掌握比背八股有用得多也会明白为什么某一次删除需要一路旋转到根而插入只需要一次局部处理。文章不会只贴代码还会把每一步的“为什么”讲清楚。尤其是删除那一块是网上教程最容易含糊的地方我会把我自己 debug 的完整链路写出来。1. 为什么AVL树不是“平衡二叉树”那么简单1.1 从二叉搜索树的退化说起先想一个问题普通二叉搜索树什么时候最难受插入顺序是1, 2, 3, 4, 5, 6, 7的时候。每次新节点都挂在右孩子上树变成一条右斜链查找数字7需要走 7 层。数据规模一上来这个代价肉眼可见地失控。二叉搜索树的平均复杂度 O(logN) 默认建立在“随机插入”这个前提上。只要插入序列有规律比如几乎有序树就会偏向一边复杂度退化成 O(N)。AVL 树的核心方案是给每个节点加一个约束任意节点的左子树和右子树高度差绝对值不超过 1。满足这个条件的二叉搜索树就叫 AVL 树。这里容易产生一个误解有人把 AVL 树当成“完全二叉树”或者“完美平衡”要求每个节点的左右子树节点数一样。这个要求太苛刻也没必要。AVL 树关心的只是“高度差”不是“节点数差”。高度差不超过 1就能保证整棵树的高度接近 log 级别查找性能稳定。1.2 平衡因子与最小不平衡子树实现 AVL 树之前必须先明确两个概念。第一个是平衡因子Balance Factor。它表示某个节点的左子树高度减去右子树高度。我用的是int balanceFactor getHeight(root-left) - getHeight(root-right);你也可以用右减左但整棵树必须保持一致。我习惯左减右因为直觉上偏左就是正数偏右就是负数。第二个是最小不平衡子树。插入或删除一个节点后理论上从叶子到根这条路径上所有祖先的高度都可能变化但真正可能失衡的是离叶子最近的那个祖先不是路径上第一个出现 |平衡因子| 1 的节点。把以它为根的子树调整平衡之后这棵子树的高度会恢复成和插入/删除之前一样所以它上面的所有节点都不再受影响。这一棵需要调整的子树就是最小不平衡子树。我之前一直没想明白为什么插入只需要调整一次而删除可能要调整多次原因就在这里。插入新节点后某个子树高度从 h 变成 h1旋转后该子树高度变回 h上层不再失衡。删除节点后子树高度从 h 变成 h-1旋转后子树高度虽然变回 h但这是在原高度 h 的基础上减了个 1不对旋转后子树高度只能恢复到删除之前的高度 h但是删除导致整体少了一层上层节点感受到的高度变化还是存在所以失衡可能继续向上传播。这个区别非常重要。等后面写删除逻辑的时候你会看到我为什么在每一层递归返回处都调用rebalance而不是只在某一次旋转之后结束。2. 旋转操作的底层逻辑四种旋转的推导与记忆方法2.1 左旋与右旋的代码原型AVL 树的所有操作归根结底是两种基础旋转左旋、右旋。其余只是这两者的组合。右旋的场景某个节点的左孩子偏高需要把这个左孩子提上来当新根原节点变成新根的右孩子。看代码最直观AVLNode* rotateRight(AVLNode* node) { AVLNode* leftChild node-left; node-left leftChild-right; // 把左孩子的右子树挂到原节点的左子树 leftChild-right node; // 原节点降级为左孩子的右子树 updateHeight(node); updateHeight(leftChild); return leftChild; }左旋完全对称AVLNode* rotateLeft(AVLNode* node) { AVLNode* rightChild node-right; node-right rightChild-left; rightChild-left node; updateHeight(node); updateHeight(rightChild); return rightChild; }注意这两段代码有一个关键细节先更新原节点的高度再更新新根的高度。因为新根的高度依赖于原节点的高度顺序反了树的高度数据就会错乱。我最初写漏了这一步导致平衡因子算出来全是乱码花了半天才定位到。2.2 LL、RR、LR、RL四种情况的判定与旋转组合avl树的四种失衡形态名字都对应“偏高的方向”LL节点的左孩子偏高且左孩子的左子树偏高。处理对节点做一次右旋。RR节点的右孩子偏高且右孩子的右子树偏高。处理对节点做一次左旋。LR节点的左孩子偏高但左孩子的右子树偏高。处理先对左孩子做一次左旋再对节点做一次右旋。RL节点的右孩子偏高但右孩子的左子树偏高。处理先对右孩子做一次右旋再对节点做一次左旋。代码里怎么判断是哪一种靠平衡因子的符号。假设balance(root) getHeight(root-left) - getHeight(root-right)如果balance(root) 1说明 root 的左子树偏高。此时看balance(root-left) 0LL直接右旋。 0LR先左旋root-left再右旋root。如果balance(root) -1说明 root 的右子树偏高。此时看balance(root-right) 0RR直接左旋。 0RL先右旋root-right再左旋root。为什么用 0而不是 0判断 LL因为当左孩子平衡因子恰好为 0 时虽然左右子树一样高但结合父节点的失衡旋转后依然能恢复平衡。写成 0更稳妥能覆盖所有情况。我把这个逻辑封装成一个统一函数后面插入删除都调它AVLNode* rebalance(AVLNode* root) { if (!root) return nullptr; updateHeight(root); int balance balanceFactor(root); if (balance 1) { // 左偏高 if (balanceFactor(root-left) 0) { return rotateRight(root); } else { root-left rotateLeft(root-left); return rotateRight(root); } } if (balance -1) { // 右偏高 if (balanceFactor(root-right) 0) { return rotateLeft(root); } else { root-right rotateRight(root-right); return rotateLeft(root); } } return root; }2.3 旋转后高度为什么不会错再看一次旋转代码里那两行updateHeight。右旋rotateRight(node)中node的左右子树在旋转后都变了它的左子树变成了原来leftChild的右子树它的右子树保持不变。leftChild变成新根leftChild的右子树变成了node左子树保持不变。此时只有node和leftChild的高度可能变化其他节点高度都没动。高度更新顺序必须是先更新下层原节点再更新上层新根。因为leftChild的右子树是nodenode的高度本身就是计算leftChild高度的输入。不过你如果写成先更新leftChild再更新node后者的高度会用到更新过但还不应该包含本轮旋转结果的leftChild实际上先更新 node 不会有任何问题。养成这个习惯后双旋转时也要注意先旋转左/右孩子再旋转当前节点每次旋转内部都保持正确顺序。3. 手写AVL树插入从找位置到修复平衡3.1 节点结构设计与高度存储我的节点结构很简单没有 parent 指针。为什么不用 parent因为递归版本里每一层递归通过返回值把新的子树根传回去父节点自然能接住省掉了维护 parent 的烦恼。代码读起来也更清爽。struct AVLNode { int key; AVLNode* left; AVLNode* right; int height; explicit AVLNode(int k 0) : key(k), left(nullptr), right(nullptr), height(1) {} };高度存储用height叶子节点高度为 1空节点高度为 0。这样父节点的高度就是max(左子树高度, 右子树高度) 1。为什么叶子高度不是 0因为叶子节点的左空和右空高度都是 0它的高度应当是max(0,0)11。否则高度和平衡因子的计算会全乱。我见过不少教程用 0 作为叶子高度然后 getHeight 返回root ? root-height : 0问题不大但你要自己保证所有公式的一致性。我选择最经典的约定叶子为 1。3.2 插入后的回溯路径与失衡检查插入采用递归每次递归返回时调用rebalance。代码非常短AVLNode* insertNode(AVLNode* root, int key) { if (!root) return new AVLNode(key); if (key root-key) { root-left insertNode(root-left, key); } else if (key root-key) { root-right insertNode(root-right, key); } else { return root; // 已经存在不处理重复值 } return rebalance(root); }这个递归的神奇之处在于你不需要显式找“从哪个祖先开始修复”。因为递归调用的路径就是插入路径每一层返回时都调用rebalance它会检查当前节点是否失衡。路径上所有需要旋转的节点都会被处理。底层完成旋转后上层节点的高度可能因此还原所以上层计算出来的平衡因子也自动正确。为什么插入时最多只需要一次旋转因为插入让子树高度最多 1旋转能让子树高度恢复原值。恢复后上层不可能再失衡。这一点和删除形成对比。3.3 插入完整测试代码我把辅助函数都补上组成一个可直接运行的版本#include iostream #include algorithm struct AVLNode { int key; AVLNode* left; AVLNode* right; int height; explicit AVLNode(int k 0) : key(k), left(nullptr), right(nullptr), height(1) {} }; int getHeight(AVLNode* root) { return root ? root-height : 0; } void updateHeight(AVLNode* root) { if (root) { root-height std::max(getHeight(root-left), getHeight(root-right)) 1; } } int balanceFactor(AVLNode* root) { return root ? (getHeight(root-left) - getHeight(root-right)) : 0; } AVLNode* rotateRight(AVLNode* node) { AVLNode* leftChild node-left; node-left leftChild-right; leftChild-right node; updateHeight(node); updateHeight(leftChild); return leftChild; } AVLNode* rotateLeft(AVLNode* node) { AVLNode* rightChild node-right; node-right rightChild-left; rightChild-left node; updateHeight(node); updateHeight(rightChild); return rightChild; } AVLNode* rebalance(AVLNode* root) { if (!root) return nullptr; updateHeight(root); int bf balanceFactor(root); if (bf 1) { if (balanceFactor(root-left) 0) { return rotateRight(root); } else { root-left rotateLeft(root-left); return rotateRight(root); } } if (bf -1) { if (balanceFactor(root-right) 0) { return rotateLeft(root); } else { root-right rotateRight(root-right); return rotateLeft(root); } } return root; } AVLNode* insertNode(AVLNode* root, int key) { if (!root) return new AVLNode(key); if (key root-key) { root-left insertNode(root-left, key); } else if (key root-key) { root-right insertNode(root-right, key); } else { return root; } return rebalance(root); } void inorder(AVLNode* root) { if (!root) return; inorder(root-left); std::cout root-key ; inorder(root-right); } int main() { AVLNode* root nullptr; for (int i 1; i 7; i) { root insertNode(root, i); } inorder(root); std::cout \nHeight: root-height \n; return 0; }跑一下中序遍历输出1 2 3 4 5 6 7说明二叉搜索树性质没破坏。打根的高度实测是 3。因为 7 个节点的 AVL 树高度是 3比普通二叉树的有序插入高度 7 少了一半还多。这个例子也回答了“接近有序的数据会不会让 AVL 退化”的疑问不会退化成链表但会触发旋转插入 2、3、4 时都会有不同的旋转发生。4. AVL树的删除真正的重灾区4.1 删除节点后的失衡传播删除的难点不在“删”本身而在于删除之后平衡的连锁反应。前面说过删除一个节点后树高整体可能减少 1这意味着所有祖先节点的平衡因子都可能变化而且旋转修复后上层可能依然失衡。举个例子一棵树右子树偏高你从右子树里删了几个点右子树变矮了反而可能导致某个祖先左偏高。这时虽然你刚刚对某个局部做了右旋但上层节点的平衡因子依然可能是 -2 或者 2需要继续处理。所以删除的正确实现是每一层递归返回时都调用rebalance让修复一直传播到根。4.2 删除逻辑里的四个易错点我在写删除时踩过四个坑逐一说明。第一个坑删除有两个孩子的节点时不能只是用后继节点替换掉 key然后把后继删了就完事。你需要递归地调用deleteNode(root-right, successorKey)这样才能让被删除的后继所在路径上的节点完成平衡更新。如果你在原树里手动切断后继节点与父节点的连接很容易漏掉高度更新。第二个坑只有一个孩子或没有孩子的节点直接返回另一个孩子。但如果返回的是非空孩子这个孩子的高度可能没更新。别担心因为父节点递归返回后会调用rebalance它会重新计算高度。不过你必须在deleteNode的典型实现里小心删除一个叶子节点后rebalance(root)会处理断裂后的高度。如果直接把非空子树返回给上一层上层 rebalance 也能处理。第三个坑找后继用的是右子树的最小节点。最小节点一定没有左孩子所以删除它时会走入“只有一个孩子或没有孩子”的分支整个过程很干净。相反用前驱左子树最大节点也是对称的但前驱可能没有右孩子同样可行。我习惯用右子树最小。第四个坑删除全部节点后根变成 nullptr。任何对空节点的getHeight和balanceFactor都要返回 0否则越界崩溃。4.3 删除完整实现源码以下删除函数可以直接和插入部分拼在一起AVLNode* findMin(AVLNode* root) { while (root root-left) root root-left; return root; } AVLNode* deleteNode(AVLNode* root, int key) { if (!root) return nullptr; if (key root-key) { root-left deleteNode(root-left, key); } else if (key root-key) { root-right deleteNode(root-right, key); } else { // 找到了要删除的节点 if (!root-left) { AVLNode* temp root-right; delete root; return temp; } else if (!root-right) { AVLNode* temp root-left; delete root; return temp; } else { // 有两个孩子找右子树最小值 AVLNode* successor findMin(root-right); root-key successor-key; root-right deleteNode(root-right, successor-key); } } return rebalance(root); }这里我特别说明一下为什么deleteNode的递归调用返回后不需要手动判断是否需要继续旋转因为rebalance内部已经做了所有事情。它先updateHeight再检查平衡因子然后根据情况旋转。如果旋转后树的高度发生了变化上层递归返回时又会调用rebalance如此一层层向上修正。所以这个递归结构天然就能处理“删除需要多次旋转”的场景。为了验证删除后修复的正确性我做了一个测试依次插入 1 到 50然后从 1 到 25 顺序删除。输出中序遍历和根的高度。实测中序遍历始终有序树高始终在合理范围。我没有在代码里额外打印每一次的高度但每一步都用下面第 5 小节的自检函数验证过。5. 查找、遍历与正确性验证让代码“自证”平衡5.1 查找与中序遍历删除和插入都搞定后查找反而最简单。递归或者循环都行bool search(AVLNode* root, int key) { if (!root) return false; if (key root-key) return true; return key root-key ? search(root-left, key) : search(root-right, key); }中序遍历上面写过了顺序输出就是从小到大可以快速核对搜索树性质是否被破坏。5.2 自检函数isAVLTree写 AVL 树最容易出现的问题是某个旋转写错但自己看不出来。所以我强烈建议写一个自动校验函数递归检查两个条件是否满足二叉搜索树性质左子树所有 key 小于当前 key右子树所有 key 大于当前 key。是否满足 AVL 平衡条件每个节点的平衡因子绝对值不超过 1。判断 BST 时不能只比较当前节点和左右孩子的大小因为可能出现跨层的不符合。稳妥做法是传上下界bool isBST(AVLNode* root, long long minKey, long long maxKey) { if (!root) return true; if (root-key minKey || root-key maxKey) return false; return isBST(root-left, minKey, root-key) isBST(root-right, root-key, maxKey); }这里直接用long long初始上下界传LLONG_MIN和LLONG_MAX避免 key 等于极端整型时的边界问题。平衡检查bool isBalanced(AVLNode* root) { if (!root) return true; int bf balanceFactor(root); if (bf 1 || bf -1) return false; return isBalanced(root-left) isBalanced(root-right); }这两个函数组合起来就是isAVLTreebool isAVLTree(AVLNode* root) { return isBST(root, LLONG_MIN, LLONG_MAX) isBalanced(root); }我每次插入或删除后都调用它。一旦返回 false就说明某层出现了错误配合断点可以快速定位。我的实际经验是绝大部分错误发生在双旋转时 left/right 指针接错或者旋转后高度没有及时更新。由于自检盯着平衡因子这类错误基本上一跑就现形。5.3 随机数据压测与测试结果手写测试用例永远不可能覆盖所有情况我建议做随机测试。下面的代码生成随机序列插一组、删一组每次操作后检查isAVLTree#include random #include vector #include climits #include unordered_set int main() { AVLNode* root nullptr; std::mt19937 rng(2025); std::uniform_int_distributionint dist(0, 100000); std::unordered_setint nums; while (nums.size() 10000) { nums.insert(dist(rng)); } std::vectorint insertData(nums.begin(), nums.end()); std::vectorint deleteData(insertData.begin(), insertData.begin() 5000); for (int x : insertData) { root insertNode(root, x); if (!isAVLTree(root)) { std::cerr Insert failed at x \n; return 1; } } std::cout After insert: height getHeight(root) \n; for (int x : deleteData) { root deleteNode(root, x); if (!isAVLTree(root)) { std::cerr Delete failed at x \n; return 1; } } std::cout After delete: remaining (int)(nums.size() - deleteData.size()) height getHeight(root) \n; return 0; }我在本地跑过 1 万次插入、5 千次删除每一步自检都通过。1 万节点的 AVL 树高度实测是 14 左右和理论值ceil(log2(N1))非常接近。对比普通二叉搜索树如果按随机顺序插入高度大约在 24 上下如果按有序序列插入普通搜索树高度会直接变成 10000。AVL 的高度稳定优势在这里体现得清清楚楚。6. 工程实践中的几个细节与常见坑6.1 递归带来的栈深度其实不是大问题有人担心递归插入删除会爆栈。AVL 树保证高度 O(logN)以 10 亿节点的树来说高度也不到 30递归调用深度也就 30 层左右。正常情况下完全不用担心。普通二叉搜索树才需要担心递归深度的问——如果数据有序插入深度可能等于节点数几万次递归就可能把栈压爆。如果你想写一个不依赖递归的 AVL 树就得维护 parent 指针或者在迭代过程中用栈记录路径。工程上如果真的需要极致性能通常会考虑更复杂的自平衡结构。但学习阶段我认为递归是理解 AVL 树最好的方式它让每个节点都只关心自己这一层的平衡修复。6.2 指针引用与父节点维护网上有些版本的 AVL 树会用AVLNode* root或者双重指针传入根节点。这样做可以避免返回值但会让插入和删除代码更难读。我坚持用返回值更新父节点的指针原因很简单每个节点在递归返回后能明确拿到以自己为根的子树的新根然后挂在父节点对应位置逻辑无歧义。如果你非要在写完递归版本之后改成循环版本有一个很现实的坑rotateLeft和rotateRight返回新子树根后父节点必须立刻接住这个返回值否则新根就会丢失。递归版本天然接住了迭代版本里要手动操作很容易漏。我曾经在实现红黑树的时候漏过一次整个树直接乱掉从此更坚定地用递归来接。6.3 删除后根为空、释放与复用删除所有节点后deleteNode返回nullptr如果你的调用端没有把根变量置空后续再insertNode(root, key)时会直接把节点挂到已经悬空的指针上不会因为你的root变量在调用端仍然是旧指针但旧节点已经被delete这是典型的悬垂指针。正确的调用方式是root deleteNode(root, key);用root接收返回值而不是只调不接收。这一点很多人知道但真正写的时候容易因为deleteNode的参数和返回值同名而迷惑。我在设计函数时内部用root作为递归参数外部同样用root接收新根因为二者是不同作用域C 允许但新手看起来容易跟丢。你要么换名要么注释清楚。我测试随机删除时中途遇到过一次Access Violation就是因为删掉最后一个节点后没有把root更新为nullptr后续又取了一次root-height。6.4 平衡因子方向造成的旋转陷阱如果你的balanceFactor用的是“右子树高度减左子树高度”那么所有判断符号都得反过来。很多人写的时候只改了一个地方结果出现“有时候旋转正确有时候不对”的诡异 bug。我的建议是把平衡因子函数定义写在固定位置所有 rebalance 判断都从它出发。如果你以后想改成右减左全局搜索替换别手改单点。另一个细节是rebalance里对balanceFactor(root-left)的判断一定要在调用旋转前重新计算不能复用外部已经算过的bf因为先旋转左孩子后root-left已经变了。我在 2.2 的代码里就是这么写的先root-left rotateLeft(root-left)接着立刻return rotateRight(root)这个调用链顺理成章。6.5 什么时候该用AVL什么时候该用红黑树聊到这里顺口提一句工程选型。AVL 树查找时最坏比较次数就是树高比红黑树略小因为它对平衡的要求更高。但每次插入删除AVL 树可能要旋转多次红黑树最多旋转三次且对高度限制较松。如果你的场景是读多写少、需要频繁查询AVL 树在理论上更优。如果插入删除非常频繁红黑树更合适。C 标准库里的std::map和std::set一般用红黑树实现但这不是说 AVL 树没有价值——它结构直观自平衡原理清晰是理解更复杂平衡树的最佳跳板。实现 AVL 树的过程中我最深的体会是写代码前先把四种旋转画清楚比对着代码硬背有用得多。旋转的本质是“保序地换根”左孩子升上来原根往右挪中间的子树交接给原根。你只要记住这一点LL、RR、LR、RL 都可以现场推导出来。画完图再写旋转函数错误率会低非常多。插入和删除的核心都是递归回溯每一层rebalance都在做同一件事。你的代码只需要保证三件事高度准确、平衡因子可靠、旋转方向正确。这三件事都验证好一棵 AVL 树就立起来了。最后再说一个小技巧写完后先跑有序插入再跑随机插入再跑随机删除。有序插入能检验旋转对连续数据的反应随机测试能覆盖边界条件。如果这两种测试都能连续通过 10000 次操作不出错这棵树基本就可以放心用了。
