AVL树这个名词学数据结构的同学应该都不陌生。但上课听懂了和手写能跑之间隔着很厚的一层窗户纸。我记得自己第一次试图独立写出完整的AVL树时插入第4个元素树就长歪了后来重新梳理了平衡因子、旋转和回溯更新的时机才真正把它打通。这篇文章就用最直白的方式把AVL树从概念到完整的C实现完整拆开讲覆盖插入、删除、旋转、校验逻辑并且提供整套可运行代码。适合刚学完二叉搜索树、准备手写AVL树或者正在为面试手撕代码做准备的开发者。我尽量把每个为什么都说清楚尤其是那些网上教程很少提到的边界细节——比如插入只要一次旋转删除却可能要一路回溯旋转再比如删除场景的四种旋转判定为什么不能照抄插入的思路。读完之后你不仅能跑通代码还能大概理解AVL树为什么被设计成这个样子。1. 从会偏科的二叉搜索树说起AVL树到底解决了什么1.1 一棵可能长歪的BST二叉搜索树BST的特性很简单左子树的所有节点都比根小右子树的所有节点都比根大插入和查找都沿着一条路径向下走。如果数据是随机的树会长得比较匀称查找复杂度接近O(log n)。可一旦插入的数据本身有序问题就来了。我举一个最经典的场景把1、2、3、4、5……一直到10000按顺序插入一棵空的BST。每个新节点都比当前所有节点大于是每次都走最右侧路径挂在最右叶子节点的右孩子上。最终这棵树变成一条只有右孩子的甘蔗也就是退化成链表。此时查找第10000个节点要沿着这串节点从头走到尾复杂度O(n)。如果你在这棵树上做高频查找性能在数据量上来后会肉眼可见地变慢。我在实际开发里遇到过类似的状况。某个模块用自建BST存递增的交易ID刚开始一切正常后来节点数到几十万查询越来越慢拉了一下树的形态才发现中间部分已经歪得不像样。BST的偏科问题不是理论上的杞人忧天而是真实会踩的坑。1.2 平衡的定义不是完全对称而是高度受控AVL树的核心思路是给每个节点加一条约束任意节点的左右子树高度差绝对值不超过1。这里的高度我统一用从节点到最远叶子经过的边数来定义空节点高度为0单个叶子节点高度为1。注意AVL树不要求左右子树完全对称也不要求节点数一样多只要求高度差在一个很小的范围内。这个约束看起来宽松但数学上足够把整棵树的高度限制在O(log n)。你可以这样直观理解一棵高度为h的AVL树里节点数再怎么少也不会少于左右子树分别为高度h-1和h-2的两棵AVL树加上根节点的数量。这个递推关系会逼着树高和节点数之间形成对数关系具体的公式推导这里不展开你只要记住结论节点数n的AVL树高度大约在1.44倍的log2(n)以内比完全二叉树略高一点但远好于退化成链表的O(n)。1.3 为什么是AVL而不是其他平衡树说到自平衡树很多人会问现代标准库里普遍用红黑树为什么还要单独学AVL这两者的选择其实是个很现实的工程问题。红黑树维护的是统计平衡允许左右子树高度差最多到两倍插入删除时需要的旋转次数更少适合写操作非常频繁的通用场景——C标准库的map、setJava的TreeMap底层都是红黑树。AVL树维护的是严格平衡查找路径更短、更稳定但插入删除时为了维持绝对平衡往往需要更多次旋转。所以我的选择逻辑很简单如果你的场景是读多写少、对单次查询延迟敏感AVL树是更好的选择如果数据规模较大且插入删除同样频繁标准库的红黑树容器更省心。从学习角度讲AVL树是所有自平衡树里最直观、最容易手写的一种把它吃透之后再看红黑树或者Treap会轻松很多。这篇文章用C实现AVL树也是希望你能在代码层面真正把旋转和回溯这两个核心动作练熟。2. 平衡因子与旋转AVL树最核心的纠偏机制2.1 平衡因子让每个节点自己报告偏了多少AVL树判断是否失衡靠的是平衡因子Balance Factor简称BF。常见的定义有两种一种是我下面代码里采用的左子树高度减去右子树高度另一种是反过来。两种都可以但代码里所有判断必须保持一致否则会出现左右旋全反的尴尬局面。平衡因子为0表示左右等高为1表示左子树高一层为-1表示右子树高一层。只要绝对值不超过1这棵树在这个节点上就是合格的。如果某个节点的BF变成2或者-2就说明从这里开始失衡了必须进行旋转。细心的读者会问为什么节点里不直接存平衡因子而要存height原因是旋转和回溯的每一步都需要知道左右子树的真实高度平衡因子只是一个差值光靠它无法还原子树高度。而且旋转之后新子树的高度也变了必须用更新后的height重新计算。所以在节点里存height用的时候临时算BF是AVL树实现中最稳妥的做法。高度更新公式也特别简单node-height 1 std::max(getHeight(node-left), getHeight(node-right));这里先更新子节点的高度再更新父节点的高度顺序不能反因为父节点高度依赖子节点高度。这个先子后父的顺序在后面旋转代码里同样是关键。2.2 四种失衡形态与对应的旋转操作失衡形态其实就是高的那一支在哪个方向对应四种情况LL型左子树的左子树偏高。此时把根节点往右拎起来一次即右旋。RR型右子树的右子树偏高。此时把根节点往左拎起来一次即左旋。LR型左子树的右子树偏高。只做一次右旋解决不了问题需要先对左子树做一次左旋再对根做一次右旋也就是双旋。RL型右子树的左子树偏高。先对右子树做一次右旋再对根做一次左旋。以右旋为例想象三个节点自上而下排成一条往左偏的斜线根是30左孩子是2020的左孩子是10。右旋做的就是把20拎到根的位置30让位成为20的右孩子20原来的右子树挂到30的左边。这样一轮操作三个节点的高度关系就理顺了。LR型为什么要先局部旋再整体旋因为中间那个拱出来的节点卡在左子树的右侧如果直接对根做右旋你会发现中间节点反而落到了更别扭的位置。只有先对左子树做一次左旋让三个关键节点重新排成一条往左倾斜的直线再对整棵子树做右旋才能真正把最高的那支压下去。这是个很直觉的过程画一遍图就懂了。2.3 旋转的本质维持中序遍历有序性很多人把旋转当成一种玄学操作其实它的本质非常朴素只改变树的形态不改变节点之间的相对顺序。不管你怎么转整棵子树的中序遍历序列始终保持不变。右旋和左旋本质上就是把某个节点和它相邻的孩子交换上下位置同时把孩子原来多余的那棵子树过继给下降的一方。理解这一点对调试特别有用。如果旋转之后你发现中序遍历顺序变了那一定是代码里指针挂错了而不是旋转本身改变顺序。我在写代码时只要怀疑旋转写错第一件事就是打印中序遍历先确认全局有序性没有被破坏再逐节点检查高度和平衡因子。这个排查顺序能让问题定位快很多。3. 插入节点后的回溯再平衡完整C实现3.1 节点结构设计与辅助函数AVL树的节点比普通BST节点多一个height字段。我用结构体来定义简洁直接#include iostream #include algorithm struct AVLNode { int key; AVLNode* left; AVLNode* right; int height; AVLNode(int k) : key(k), left(nullptr), right(nullptr), height(1) {} };然后是几个辅助函数。getHeight处理空指针的情况getBalanceFactor在空指针时返回0这样递归过程中不需要到处判空int getHeight(AVLNode* node) { return node nullptr ? 0 : node-height; } int getBalanceFactor(AVLNode* node) { return node nullptr ? 0 : getHeight(node-left) - getHeight(node-right); }提示高度定义统一为边数。空节点高度0叶子节点高度1。这个约定贯穿全文写代码时不要混用节点数和边数两种口径。3.2 插入的递归逻辑一层层往上汇报AVL树的插入分为三步普通BST的递归插入、回溯更新高度、检查并旋转。递归的好处是天然具备回溯能力——新节点插入到叶子之后函数一层层返回每一层都能顺便更新自己这个节点的高度并检查自己是否失衡。关键点在于递归返回后当前节点要先更新height再计算BF最后根据BF和插入key的走向决定转哪一种。插入时的四种旋转判定并不需要额外看当前节点的孩子高度只要知道新key插入到哪个方向就够了AVLNode* insertNode(AVLNode* node, int key) { if (node nullptr) { return new AVLNode(key); } if (key node-key) { node-left insertNode(node-left, key); } else if (key node-key) { node-right insertNode(node-right, key); } else { return node; // 重复key不插入 } node-height 1 std::max(getHeight(node-left), getHeight(node-right)); int balance getBalanceFactor(node); // LL型 if (balance 1 key node-left-key) { return rightRotate(node); } // RR型 if (balance -1 key node-right-key) { return leftRotate(node); } // LR型 if (balance 1 key node-left-key) { node-left leftRotate(node-left); return rightRotate(node); } // RL型 if (balance -1 key node-right-key) { node-right rightRotate(node-right); return leftRotate(node); } return node; }递归函数返回的是这一层子树的新根。因为旋转操作会换掉子树的根节点所以调用方必须用返回值更新自己的left或right指针。我见过不少新手在这里漏掉赋值比如直接写insertNode(node-left, key)而不接返回值结果树在第一次旋转后就把原来的子树根丢掉指针一片混乱。3.3 四种旋转的代码实现旋转代码是AVL树最容易写错指针的地方建议先把单个旋转的指针交换顺序背下来再考虑双旋组合。右旋的逻辑把y的左孩子x拎到根的位置y降为x的右孩子x原来的右子树T2过继给y当左子树。写代码时要先把x的right缓存到T2防止指针被覆盖AVLNode* rightRotate(AVLNode* y) { AVLNode* x y-left; AVLNode* T2 x-right; x-right y; y-left T2; y-height 1 std::max(getHeight(y-left), getHeight(y-right)); x-height 1 std::max(getHeight(x-left), getHeight(x-right)); return x; }左旋完全对称把y的右孩子x拎到根的位置y降为x的左孩子x原来的左子树T2过继给y当右子树AVLNode* leftRotate(AVLNode* x) { AVLNode* y x-right; AVLNode* T2 y-left; y-left x; x-right T2; x-height 1 std::max(getHeight(x-left), getHeight(x-right)); y-height 1 std::max(getHeight(y-left), getHeight(y-right)); return y; }双旋不需要单独写函数直接组合两个单旋就行。LR型就是先对左子树做左旋再对根做右旋RL型先对右子树做右旋再对根做左旋。在insertNode里我已经写好了。3.4 为什么插入只需要一次旋转就能恢复平衡这是一个很多人没细想的问题插入新节点后可能从叶子到根一路上有多个祖先的BF绝对值超过1为什么递归回溯只做一次旋转就够了答案是旋转会压缩子树高度。比如某个子树插入之前高度为h插入后变h1导致失衡做一次旋转后这棵子树的高度会恢复到h正好等于插入前的水平。既然子树高度恢复原样它对自己上层祖先的高度贡献自然也没有变化上层原本平衡的状态就不需要再调整了。所以在插入这个场景下递归从叶子向上回溯时第一个出现失衡的节点做完旋转上层就全部感知不到这次插入的发生过程到此结束。这也是AVL树插入高效的原因之一平均情况下插入后顶多做常数次旋转。需要注意的例外是双旋它内部包含两次单旋但整体仍然算一次再平衡操作。4. 删除节点比插入更麻烦的多级再平衡链路4.1 被删节点的三种情况删除操作的第一步和普通BST完全一样分三种情况被删节点是叶子直接删掉返回空指针给父节点。被删节点只有一个孩子用这个孩子顶替被删节点的位置。被删节点有两个孩子用右子树的最小节点中序后继或左子树的最大节点中序前驱替换被删节点的值然后递归删除那个用来替换的节点。我习惯选右子树的最小节点做替换。理由是删除一个只有一个右孩子且有左子树的节点时这个中序后继一定在被删节点的右子树最左侧递归删除时只需要沿着left一路下行回溯路径非常干净。换成前驱也行但左右逻辑要注意配套。4.2 删除后牵一发而动全身的失衡传播删除和插入一个非常重要的区别插入只让某条路径的高度增加旋转一次把高度压回原值就完事删除则是让某条路径的高度减少可能会导致多个祖先逐一失衡。因为每一层子树的高度一旦变化就会传递给更上层所以删除后的再平衡可能需要在多个节点上重复执行。还有一个更隐蔽的差别删除场景里你并不知道哪个方向刚被改动过所以不能像插入那样用key的走向来判断旋转类型。标准做法是看当前节点的平衡因子和它孩子节点的平衡因子来综合判断具体对应关系如下当前节点BF孩子节点BF失衡形态处理方式 1左孩子BF 0LL型对当前节点右旋 1左孩子BF 0LR型先对左孩子左旋再对当前节点右旋 -1右孩子BF 0RR型对当前节点左旋 -1右孩子BF 0RL型先对右孩子右旋再对当前节点左旋注意第二行的条件当前节点BF大于1时左孩子BF正好等于0的情况也要按LL型处理直接右旋。这在插入场景里几乎不会出现因为插入一定增加了左子树高度左孩子BF不可能还是0但在删除场景里很常见当前节点左高右低而左孩子的左右子树同高。如果不兼容这种BF0的情况删除后的再平衡会漏掉一个分支。4.3 删除再平衡的完整实现按上面的规则写出来的代码如下。删除递归返回后同样先判空、更新高度、算BF再做四种旋转判定AVLNode* getMinNode(AVLNode* node) { AVLNode* current node; while (current-left ! nullptr) { current current-left; } return current; } AVLNode* deleteNode(AVLNode* root, int key) { if (root nullptr) { return root; } 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 nullptr) { AVLNode* temp root-right; delete root; return temp; } if (root-right nullptr) { AVLNode* temp root-left; delete root; return temp; } AVLNode* temp getMinNode(root-right); root-key temp-key; root-right deleteNode(root-right, temp-key); } if (root nullptr) { return root; } root-height 1 std::max(getHeight(root-left), getHeight(root-right)); int balance getBalanceFactor(root); if (balance 1 getBalanceFactor(root-left) 0) { return rightRotate(root); } if (balance 1 getBalanceFactor(root-left) 0) { root-left leftRotate(root-left); return rightRotate(root); } if (balance -1 getBalanceFactor(root-right) 0) { return leftRotate(root); } if (balance -1 getBalanceFactor(root-right) 0) { root-right rightRotate(root-right); return leftRotate(root); } return root; }这段代码里的if (root nullptr)不能省。因为当某个节点只有一个孩子时删除可能直接返回空指针给上层上层在计算height前必须先判空否则就是对空指针解引用。我第一次写的时候漏了这个检查删除叶子节点后程序直接崩溃排查了半小时才发现。删除之所以可能沿途多次旋转是因为每旋转完一层当前子树的高度可能再次降低这个变化会继续向上传递。递归代码的好处是每一层的返回路径都自动执行一次再平衡检查所以你不需要手动遍历祖先链只要保证每个递归层级都做了完整的更新高度旋转判定即可。5. 用自测程序给AVL树体检中序遍历与平衡校验5.1 中序遍历验证有序性写完AVL树之后第一件事不是看平衡不平衡而是先验证最基础的BST性质没有被破坏。方法很简单中序遍历打印所有节点如果输出是严格递增的序列说明旋转操作至少没有把元素顺序搞乱void inorder(AVLNode* root) { if (root nullptr) { return; } inorder(root-left); std::cout root-key ; inorder(root-right); }如果一个节点有多个元素、或者你支持重复key这个判断要做相应调整但本文的实现不允许重复key所以严格递增就够了。5.2 递归检查平衡因子接下来验证AVL树的真正约束每个节点BF的绝对值都不超过1。写一个递归校验函数空树返回true当前节点BF合法且左右子树都合法时返回truebool isBalanced(AVLNode* node) { if (node nullptr) { return true; } int bf getBalanceFactor(node); if (bf -1 || bf 1) { return false; } return isBalanced(node-left) isBalanced(node-right); }这个函数配合getHeight能一票否决看起来树形挺好看但实际上某个节点偷偷偏了的情况。调试时我建议同时在节点数比较多的时候打印整棵树的高度和理论值对照。比如1000个节点的AVL树按边数计高度应该在十几层左右如果算出来是25层甚至更高说明某个环节的再平衡没有生效。5.3 压力测试场景与结果我常用的自测套路有三种都写在一个小的main里int main() { AVLNode* root nullptr; // 场景1顺序插入验证树没有退化成链表 for (int i 1; i 1000; i) { root insertNode(root, i); } std::cout height after asc insert: getHeight(root) std::endl; std::cout balanced: isBalanced(root) std::endl; inorder(root); std::cout std::endl; // 场景2随机删除部分节点验证删除后仍然平衡 for (int i 1; i 1000; i 2) { root deleteNode(root, i); } std::cout balanced after delete: isBalanced(root) std::endl; return 0; }实测下来顺序插入1000个节点AVL树的高度在14以内而普通BST会直接长成1000层的链表。删除500个奇数节点之后isBalanced依然返回true说明删除路径上的多次再平衡逻辑是可靠的。提示调试的时候不要光看isBalanced的结果我建议临时写一个遍历所有节点、打印key、height、BF三条信息的调试函数。一旦某次操作后isBalanced返回false靠这个输出能快速定位是哪个节点开始失衡以及它的旋转是否被正确触发。6. 我在写AVL树时踩过的坑以及什么时候别用它6.1 三个容易写错的地方第一忘记更新高度。插入和删除的递归返回后第一步就是重新计算当前节点的高度。如果漏掉这一步再往上的所有BF都会算错而且错误会一层层放大。我调试时见过一种很迷惑的现象insert之后isBalanced返回false但打印BF发现某个节点BF为2它是上一个节点高度更新失败的受害者。第二旋转时指针覆盖顺序不对。右旋里必须先用局部变量存T2再开始改y的left和x的right。如果直接写y-left x-right而x-right还没改这行代码会把x的right变成y的left丢失整棵T2子树。旋转函数里的指针操作建议拿着笔画一遍再写。第三删除的旋转判定不能照抄插入。我在4.2节专门讲过删除时必须用孩子节点的BF符号来判断LL、LR、RR、RL而不是用key的方向。照抄insert的key判断在某些删除场景下会漏旋转或错旋转导致树在一两次操作后悄悄失衡。这是我改了很多次才长记性的地方。6.2 与普通BST的性能实测对比为了让AVL值不值这件事有个直观印象我用随机生成的10万个数做过一轮简单测试。普通BST在随机数据下表现其实不错树高大约四十几层按顺序插入10万个数后普通BST退化成十万层的链表查找最后一个数要遍历十万次而AVL树的高度只有二十几层查找时间基本可以忽略不计。在包含随机插入和删除的混合操作里AVL树的插入、删除因为要维护height和旋转会比普通BST慢一些一般在个位数到十几个百分点的差距。这个代价换来的是查找路径的稳定和可控。所以评价AVL树不能只看单次操作耗时而要看你服务的业务到底偏读还是偏写。还有一个细节AVL树这些旋转都发生在递归回溯的过程中递归深度等于树高。对AVL树来说这没问题因为树高始终是对数级的但如果你在一棵未平衡的BST上递归写AVL的检查逻辑深度可能直接爆栈。这也是为什么所有自平衡操作都在递归返回路径里做而不是在向下查找的路径里做。6.3 什么时候不要用AVL树写项目不是做算法题选型要看实际场景。如果你的容器大量插入和删除、但查找频率很低AVL树严格维持平衡带来的收益不明显旋转开销却实实在在这时候红黑树甚至跳表都更合适。如果数据规模不大且本身可以一次性加载直接存数组然后排序配合二分查找代码简单得多cache友好度也更高。如果数据量大到要落盘、要范围查询那也不是AVL树的战场B树、B树才是为磁盘场景设计的。我在实际项目里很少自己手写平衡树因为标准库的map和set已经足够好用。手写AVL树这件事我更愿意把它当成一次精读数据结构原理的训练——它逼着你理解旋转、回溯、高度更新这些底层思维理解了这些后面再看红黑树、Treap、B树你会发现自己能一眼看穿它们的设计动机。如果你正在学这部分内容我建议你按本文的步骤把代码敲一遍再改几个边界条件比如把重复key的处理逻辑改掉、把中序后继换成前驱感受一下牵一发而动全身的调试体验这比背十遍原理都管用。