1. 为什么学了STL还得回头啃AVL树先说个场面话STL里真有AVL树吗没有。std::map、std::set底层是红黑树std::unordered_map底层是哈希表AVL树压根没进标准库。那这门《C进阶之STL》课里为什么要专门讲AVL树因为AVL树是所有自平衡二叉搜索树里最容易讲清楚、最容易从零实现、也最能帮你建立平衡直觉的那一个。理解了AVL树你再看红黑树、跳表、B树会发现它们都在回答同一个问题如何让二叉搜索树在动态插入删除下保持高效。二叉搜索树的查找、插入、删除理论上都是O(log n)这是建立在树高和节点数呈对数关系的基础上。但如果你按顺序插入1、2、3、4、5树会退化成一条链表查找一个节点要从头遍历到尾复杂度变成O(n)。真实业务里的数据往往不是均匀随机的用户ID自增、日志时间递增、排行榜分数趋向集中这些场景都会导致搜索树倾斜。AVL树解决的就是这件事它保证任意节点的左右子树高度差绝对值不超过1让树高始终被压在O(log n)以内。我当年第一次实现AVL树的时候踩过两个大坑。第一个坑是把旋转当成背代码来学四个旋转函数抄来抄去抄完就忘根本不知道什么时候触发左旋、什么时候触发右旋。第二个坑是对失衡是自下而上传播的没有概念只处理了插入节点附近的一个失衡节点导致树在上层仍然是歪的。所以这篇文章不打算按四种旋转直接扔给你的套路来我想先讲清楚平衡是什么、失衡怎么检测、旋转的本质是什么然后给出完整可编译的C实现最后聊聊和STL容器放在一起看时的一些启发。你如果正处在STL容器会用但说不出所以然的阶段或者准备面试C岗位被问过红黑树但支支吾吾这篇文章都合适。AVL树代码量不大核心逻辑大概两百行但吃透它你对树形结构为什么需要平衡哪种平衡策略适合什么场景会有质的理解回头再看STL关联容器会多一层通透感。2. 平衡因子与节点设计一切从高度差开始2.1 为什么是高度差不超过1而不是完全等高AVL树定义很简单每个节点的左右子树高度差的绝对值不能超过1这个高度差就是平衡因子balance factor。为什么要求不超过1而不是要求左右子树完全一样高因为完全等高只对节点数为 (2^k - 1) 的完美二叉树才成立插入一个节点就可能破坏完美形态然后你为了恢复完美形态付出的调整代价会非常大。允许高度差为1树高最多比完美情况多一层复杂度依然是对数级别但调整起来就从容多了。你可以这样感受一个节点数为n的AVL树树高上限大约是 (1.44 \log_2(n1))和完美二叉树的 (\log_2(n1)) 只差一个常数因子。这个1.44倍的差距换来的是每次插入删除最多O(log n)次旋转的代价这笔账非常划算。作为对比如果要求完全等高每次插入几乎都要全局重排那才是得不偿失。平衡因子具体怎么算我习惯用右子树高度减左子树高度。约定balanceFactor height(right) - height(left)那么平衡状态就是平衡因子等于-1、0、1三个值之一。注意这里高度定义也有讲究有人用从根到最远叶子的路径边数有人用路径上的节点数。我用的是前者空树高度记为-1叶子节点高度为0这样一套代码统一不容易混。2.2 节点结构要不要单独存平衡因子一个AVL树节点至少要包含键、值、左右孩子指针、高度这四个字段。键和值单独看键用于排序和查找值用于承载业务数据左右孩子指针是二叉树的骨架高度字段是为了在旋转时能快速算平衡因子。这里有一个设计选择是直接存平衡因子还是存子树高度STL的红黑树节点里存的是节点颜色因为红黑树的平衡条件是用颜色来描述的旋转后只要局部改颜色就行。AVL树如果直接存平衡因子每次旋转后都得重新计算并写回平衡因子写回时还得区分是新根还是旧根很容易出错。我在实现中发现存子树高度反而更稳旋转函数里先算新高度再算平衡因子逻辑是顺序的不会漏更新。节点代码长这样template typename K, typename V struct AVLNode { K key; V value; AVLNode* left; AVLNode* right; int height; AVLNode(const K k, const V v) : key(k), value(v), left(nullptr), right(nullptr), height(0) {} };高度为0表示叶子节点。空指针的高度定义为-1这样才能让只有一个根节点的树高度为0和空树高度为-1统一起来。后面实现getHeight函数时空节点返回-1而不是返回0这个细节特别容易被忽视一旦写成返回0所有高度差计算会整体偏移1旋转条件全部乱套。int getHeight(AVLNodeK, V* node) { return node nullptr ? -1 : node-height; } int getBalance(AVLNodeK, V* node) { return node nullptr ? 0 : getHeight(node-right) - getHeight(node-left); }getBalance返回的就是平衡因子右高为正、左高为负。后面旋转逻辑全靠这个正负号和大小判断方向。3. 四种旋转的底层逻辑别背代码看失衡怎么折返3.1 左左失衡与右旋最基础的修正先看最简单的一种情况。新节点插入到某个节点的左孩子的左子树里导致这个节点的平衡因子变成-2这就是LL型失衡。这种失衡是一条路往左拐到底修正方式是把中间那个节点抬起来整体右旋。右旋的代码AVLNodeK, V* rotateRight(AVLNodeK, V* y) { AVLNodeK, V* x y-left; AVLNodeK, V* t2 x-right; // 旋转 x-right y; y-left t2; // 先更新下层节点y的高度再更新上层节点x的高度 y-height max(getHeight(y-left), getHeight(y-right)) 1; x-height max(getHeight(x-left), getHeight(x-right)) 1; return x; // 新的子树根节点 }为什么先更新y再更新x因为旋转后y成了x的右孩子x的高度依赖y的高度顺序反了会拿到旧值。这是AVL树实现里最常见的低级错误很多初学版本在这里栽跟头表现就是旋转后树越来越歪最后干脆崩掉。如果你觉得代码抽抽象想象一个晾衣架y是顶部的挂钩x是中间挂的衣架t2是衣架右侧挂的一件衣服。右旋就是把衣架整个提到挂钩的位置原来的挂钩变成衣架的右挂点顺便把右挂点挂着的那件衣服挪到挂钩原来的左侧位置。图示在纸上画一遍比看文字快得多我强烈建议你拿笔画一个只有三个节点的最小LL型失衡图把t2的位置标出来。3.2 右右失衡与左旋完全镜像RR型失衡就是LL的镜像节点插入到右孩子的右子树平衡因子变成2需要左旋。代码就是rotateRight把所有left和right互换。左旋代码AVLNodeK, V* rotateLeft(AVLNodeK, V* x) { AVLNodeK, V* y x-right; AVLNodeK, V* t2 y-left; y-left x; x-right t2; x-height max(getHeight(x-left), getHeight(x-right)) 1; y-height max(getHeight(y-left), getHeight(y-right)) 1; return y; }我最早学的时候总觉得左右旋容易记混后来找到一个可靠的判断方法看失衡节点的平衡因子。负值说明左重需要右旋正值说明右重需要左旋。也就是说balance 0往右转balance 0往左转方向相反这样至少在决策层不会搞反。至于代码里孩子的左右指针怎么换那是机械操作多写两遍就熟练了。3.3 LR型与RL型为什么旋转两次而不是一次现在问题来了。如果插入发生在左孩子的右子树里此时失衡节点平衡因子是-2但它的左孩子平衡因子是1你会发现单纯右旋并不能恢复平衡——右旋之后左孩子被翻到上面但它自己的右子树还是偏高新根的平衡因子依然超过1。这就是LR型失衡。LR型的处理分两步先对失衡节点的左孩子做一次左旋把这个先右后左的路径捋直变成LL型。再对失衡节点做一次右旋。RL型就是镜像先对右孩子做右旋捋直再对失衡节点做左旋。为什么不能一步到位因为AVL树单次旋转只能处理一直往同一方向拐的链式结构。LL是一条直线一旋就直LR是先向下往左、再向下往右像个闪电形单旋只能把闪电旋成更奇怪的形状。必须先用一次旋转把这个折返掰成直线再用第二旋转回到平衡。以后再看到LR、RL别慌就是先掰直再平衡。3.4 用插入返回值判断旋转类型的技巧纸上谈兵说完了实操里判断该用哪种旋转写起来其实非常机械。我把这段逻辑封装成一个rebalance函数输入失衡节点输出经过旋转后的新子树根AVLNodeK, V* rebalance(AVLNodeK, V* node) { int balance getBalance(node); // 左左 if (balance -1 getBalance(node-left) 0) { return rotateRight(node); } // 左右 if (balance -1 getBalance(node-left) 0) { node-left rotateLeft(node-left); return rotateRight(node); } // 右右 if (balance 1 getBalance(node-right) 0) { return rotateLeft(node); } // 右左 if (balance 1 getBalance(node-right) 0) { node-right rotateRight(node-right); return rotateLeft(node); } return node; }判断条件里有一个细节LL型要求左孩子的平衡因子小于等于0LR型要求大于0。为什么LL型允许等于0因为有一种特殊情况——插入节点后左子树整体高度没变但平衡因子为-2的情况依然可能出现这时左孩子的平衡因子是0。如果这里写成getBalance(node-left) 0那种-2但左孩子平衡因子为0的场景就会漏判。这个细节在LeetCode那种裸裸的AVL题里可能遇不到但你自己实现完整树容器时一定会撞上漏一次就会出现整棵树看着没问题跑随机插入10000个元素后树高比预期多一层的诡异现象。4. 插入操作用递归写平衡因子的更新顺序是关键插入逻辑分三步按二叉搜索树规则找到位置并插入叶子从插入点回溯更新高度沿途发现失衡就rebalance。前两步如果用递归写代码会很自然地合在一起——每次递归返回时重新计算当前节点高度然后判断是否需要旋转。我自己写完插入才发现这个递归返回即回溯更新的写法天然规避了手动维护平衡因子的麻烦。插入函数完整代码AVLNodeK, V* insert(AVLNodeK, V* node, const K key, const V value) { if (node nullptr) { return new AVLNodeK, V(key, value); } if (key node-key) { node-left insert(node-left, key, value); } else if (key node-key) { node-right insert(node-right, key, value); } else { node-value value; // 键已存在则更新值 return node; } // 递归返回时才更新高度 node-height max(getHeight(node-left), getHeight(node-right)) 1; // 检查并修复失衡 return rebalance(node); }这段代码的关键是最后两行先height更新再rebalance。顺序不能反因为rebalance内部要用getBalance判断是否需要旋转而getBalance依赖height。如果先旋转再更新高度旋转函数里拿到的还是旧高度算出来的平衡因子就是错上加错。旋转函数内部虽然没有显式调用rebalance但它更新了局部节点的高度所以从整体来看树在递归返回链上是一层一层被修正的。为什么不写成迭代版本AVL树插入的迭代版本需要手动维护一个路径栈把从根到插入点的所有节点压栈然后再逐层弹栈更新高度和旋转。递归版本在函数调用栈上天然完成了这个回溯代码短得多也不容易漏节点。C的递归深度在普通情况下完全够用AVL树的树高被限制在O(log n)所以递归深度最多也就是几十层不用担心爆栈。我在实测里插入一千万个随机键递归版本没有出现任何栈溢出问题。插入完成后AVL树仍然是一棵二叉搜索树也就意味着中序遍历的结果一定是递增序列。这个性质用来做自检特别方便我后面专门有一节讲测试就是基于这个性质写验证函数的。5. 删除比插入复杂在哪里不止一处可能失衡5.1 删除的基本框架AVL树的删除首先还是二叉搜索树的删除规则分三种情况被删除节点是叶子直接删父节点指向nullptr。被删除节点只有一个孩子让孩子顶替被删除节点的位置。被删除节点有两个孩子找到右子树的最小节点或者左子树的最大节点替代当前节点然后递归删除那个替代节点。第三种情况为什么选右子树最小值因为右子树最小值一定大于当前节点的所有左子树节点且小于右子树所有其他节点用它顶上来二叉搜索树的中序顺序不会被破坏。这个节点从右子树里被拿走后递归删除它本身删除逻辑又回到前两种情况。删除之后AVL树可能不止一处失衡。插入只会让一条路径上的高度变化删除则可能让某棵子树高度降低了一整层那个子树的父节点失衡了处理完父节点祖父节点可能又失衡了。所以删除必须沿着递归回溯路径一路检查到根。这一点比插入复杂插入的旋转往往只影响局部删除的旋转则可能连环触发。5.2 删除的实现与一个容易忽略的细节删除函数我用递归写返回删除后的子树根这样每层递归自然拿到新的子树根方便往上接。核心代码如下AVLNodeK, V* remove(AVLNodeK, V* node, const K key) { if (node nullptr) { 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 nullptr) { AVLNodeK, V* tmp node-right; delete node; return tmp; } if (node-right nullptr) { AVLNodeK, V* tmp node-left; delete node; return tmp; } // 两个孩子的场景找右子树最小节点 AVLNodeK, V* minNode findMin(node-right); node-key minNode-key; node-value minNode-value; node-right remove(node-right, minNode-key); } // 空节点不需要更新高度 if (node nullptr) { return nullptr; } node-height max(getHeight(node-left), getHeight(node-right)) 1; return rebalance(node); }这里最容易忽略的细节是在更新高度之前要判断node是否为空。因为函数走到node-left nullptr分支时直接返回了右子树父节点递归接收到的可能是nullptr。如果父节点在rebalance之前贸然取node-height空指针访问就崩了。我在代码里专门加了空判断这个判断不是为懒写的是真实崩溃换来的。另一个细节替代节点用的是findMin(node-right)它返回的是右子树最左边的节点。删除它的时候递归传的是node-right和minNode-key路径上每层都会重新更新高度和旋转所以不会出现右子树最小值删了但子树高度没修正的情况。查找最小值的辅助函数 AVLNodeK, V* findMin(AVLNodeK, V* node) { while (node-left ! nullptr) { node node-left; } return node; }删除后的rebalance逻辑和插入完全复用同一个函数这是把rebalance抽出来的好处插入和删除共用一套失衡修复逻辑代码量少了正确性也更容易验证。6. 从AVL树到STL容器为什么红黑树成为STL默认6.1 查找、插入、删除的复杂度对比STL的std::map和std::set底层选择红黑树而不是AVL树这背后不是AVL树不好而是AVL树的查找略快但调整代价偏高。红黑树的平衡条件比AVL树宽松红黑树不要求左右子树高度差不超过1只要求最长路径长度不超过最短路径长度的两倍。也就是说红黑树允许的树高上限是 (2\log_2(n1))比AVL树的 (1.44\log_2(n1)) 略大但插入删除时需要旋转的次数更少。用数据说话这里指理论最坏情况和工程经验特性AVL树红黑树查找性能略快树更矮略慢一点点插入删除旋转次数最多约 (O(\log n))平均更容易触发最多3次旋转调整效率更高实现复杂度较低逻辑直观较高颜色变化和旋转配合更繁琐更适合场景读多写少需要稳定查找性能写多读少或读写均衡STL容器面向通用场景插入删除和查找的比例是未可知的于是选择了牺牲一点查找性能、换取写入效率更稳定的红黑树。很多C面试官爱问map为什么不用AVL树这个问题的标准答案就是红黑树插入删除旋转次数更少是更均衡的工程选择。但你要真能补充一句AVL树树高更矮、查找更快只读场景里AVL树依然有优势面试观感会完全不同。6.2 看透平衡策略AVL树教给你的是红黑树的一半AVL树的核心是高度差约束红黑树的核心是路径长度约束但两者本质相同在动态数据流中维持搜索树的结构质量。我学AVL树最大的收获不是四个旋转函数而是旋转这个动作本身就是常数级别的局部操作——无论树多大失衡修复只需要动几个指针。这个特点让平衡树成为工程上可用的数据结构不然光重排整棵树就会卡死业务。红黑树的旋转只有左旋和右旋没有AVL的LR、RL这种双旋概念吗不是的红黑树同样会用到双旋只是你看《算法导论》给的伪码里往往把双旋拆成了两次单旋。所以你在AVL树里练熟的旋转直觉在红黑树的删除修复里同样能用。AVL树代码量小非常适合用来建立从失衡检测到旋转修复的完整心智模型。当你日后看红黑树那套while循环变色加旋转的时候你会发现底层动作还是那两下把链掰直再平衡。6.3 实际工程里AVL树还有用吗说句实在话现代工程里几乎不会手写AVL树需要平衡树就上STL的map/set或者用第三方库里的b-tree、skiplist。AVL树更大的价值是在教学和面试准备层面。但有一个场景我确实用过写一个小型内存索引模块读请求极多、写入只发生在启动阶段且键分布是连续递增的ID。这种场景下一旦构建完成就不再有写操作AVL树的高度优势能实打实地减少查找时的比较次数。当时我测过连续递增键插入到未平衡的BST里树高好几百层同样的键插入AVL树树高只有两位数。如果是亿级数据量还涉及磁盘IO对比这个差距就是秒级和分钟级的区别了。所以AVL树不是淘汰的技术它是理解所有平衡树的门把手。把门把手旋紧后面的门才推得开。7. 测试与调参如何验证一棵AVL树真的写对了7.1 三个必须过的自检函数写完AVL树不经测试就上线是不现实的。我自己最少要写三个自检函数任何一个不过都说明树有问题。第一个是中序遍历有序性检查。AVL树首先是二叉搜索树中序遍历结果必须严格递增。这个检查能抓出旋转时左右孩子接错的问题。实现就一个递归遍历然后依次比对相邻两个key。第二个是平衡因子合法性检查。递归计算每棵子树的实际高度然后验证abs(getBalance(node))不超过1。注意这个检查不能直接用节点里存的height字段因为节点里的height可能本身就被写错了必须重新递归求真实高度再比较。这也是为什么我建议把height和getHeight分开写——测试时用真实高度运行时用缓存高度。第三个是高度上限检查。构造n个节点后树高应当小于 (1.44 \log_2(n1)) 的近似上限。这个检查最严格因为前两个检查有可能碰巧通过但树斜了树高上限直接反映结构质量。检查代码bool isBalanced(AVLNodeK, V* node) { if (node nullptr) return true; int leftH getRealHeight(node-left); int rightH getRealHeight(node-right); if (abs(rightH - leftH) 1) return false; return isBalanced(node-left) isBalanced(node-right); }其中 getRealHeight 是递归重新计算的函数不能和节点里缓存的height混用不然测了个寂寞。7.2 随机插入删除压测唯一能逼出隐藏bug的方式自检函数有了测试数据怎么造先做随机插入测试。生成1万个随机键依次插入每插入1000个跑一次全部三个自检。这个能测出插入路径上有没有漏掉rebalance。再做随机删除测试插入全部键然后随机删除一半每次删除后跑自检。删除漏更新高度的问题往往在删除几十个节点后就会暴露因为树高会逐渐膨胀最后平衡因子检查会失败。然后是连续递增键压力测试这是二叉搜索树最容易暴露倾斜性的场景。AVL树必须在这种输入下依然保持平衡不然你去存自增ID就会莫名退化。我实测过连续插入10万个递增键AVL树的树高大约只有20层左右而普通二叉搜索树的树高是10万层。这个对比相当直观也是每次我给同事演示AVL树价值时最爱用的一个测试。7.3 一个小技巧打印树结构前先画纸如果你在调试过程中发现自检失败别急着改逻辑先把树结构打印出来。怎么打印写一个中序遍历带上缩进或括号的辅助函数缩进表示层级或者用括号表示法例如根节点的输出形式类似root(left_subtree, right_subtree)。画出来之后找到第一个失衡节点看它的平衡因子和孩子平衡因子就能确定是LL、RR还是LR、RL。纸上推演一遍旋转过程再对着代码检查指针挂接问题基本就定位了。我调试AVL树从没靠过断点单步都是靠这种输出树结构 纸上推演的组合原因是树形数据结构在断点窗口里根本看不出整体结构打印反而最直观。AVL树这门功课我建议每个学C的人都亲手实现一遍哪怕STL不用它哪怕工作中永远不手写平衡树。因为只有敲过旋转、踩过空指针、改过错乱的平衡因子你才算真正理解数据结构是为了性能上限而生的这句话。树是程序里最常见的非线性结构而AVL树就是那把打开平衡之门的小钥匙。
