学平衡二叉树的时候有句话我印象很深普通二叉搜索树BST的查询性能完全取决于输入数据给你面子还是不给面子。数据有序进入树就直接歪成链表查询从 O(log n) 变成 O(n)你在面试里讲“BST 平均 log n”的时候面试官下一个问题基本就是“那最坏情况呢”。为了把最坏情况摁住AVL 树和红黑树这两棵平衡树出现了。这篇文章是我从概念到模拟实现完整走了一遍之后整理的笔记重点放在旋转、插入修复、删除修复这些最容易卡壳的环节最后会附上我自己实测的数据对比和一堆踩坑记录适合正在复习数据结构、准备手撕平衡树的人直接参考。很多人学这两棵树的时候习惯直接背旋转代码背完就忘忘了再背原因就是没搞明白它们到底在解决什么。先把这个底层问题说透后面的代码就顺理成章了。1. 为什么要把 BST 武装成平衡树1.1 BST 退化一场有序插入引发的灾难二叉搜索树的查找过程本质上是二分查找的树形展开每走一步你都能丢掉一侧子树把搜索范围砍半。这个“砍半”的美好假设建立在树高是 O(log n) 的基础上。可一旦树失去平衡比如按 1、2、3、4……的顺序插入每个新节点都只会挂到右孩子上树的形状变成一条单链查找最后一个元素你要走满整棵树。用数据感受一下。插入 10 万个顺序递增的 key普通 BST 的高度就是 10 万AVL 树高度大约 17红黑树高度大约 34。查找一个最深的节点前者要做 10 万次比较后者只需要几十次。几十次和十万次的差距在数据库索引、缓存淘汰、路由表这类高频查询场景里就是天壤之别。所以平衡树做的事情说起来非常简单在插入、删除之后通过局部的结构调整把树的高度重新压到对数级别。关键就在于“局部调整”怎么做以及调整的成本如何控制。1.2 AVL 树用高度差把树形“锁”住AVL 树是 1962 年由 Adelson-Velsky 和 Landis 提出的它立了一条非常朴素的规矩任意节点的左子树和右子树高度差不超过 1。这个高度差就是平衡因子Balance Factor一般定义为左高减右高。只要某次插入或删除让某个节点的高度差变成 2 或者 -2马上触发旋转。AVL 的“严格”意味着它的树高非常接近 theoretical 最优。n 个节点的 AVL 树高度严格小于 1.44 * log2(n 2)而且这个界限在数据量特别大的时候更贴近 log2(n) 本身。代价就是你为了维持这种严格平衡插入时平均需要旋转更多次删除时可能一路调整到根节点。我把 AVL 的调平衡理解成“强迫症患者整理书架”每一本书放进去之后都要检查周围书架高度差有没有超过一层超过就立刻把局部书架重新盘一遍。1.3 红黑树用颜色换更低的调整成本红黑树是 1972 年由 Rudolf Bayer 提出的它放弃了对单节点高度差的强制约束改用颜色规则来保证“最长路径不超过最短路径的两倍”。这五条规则你应该早就背得滚瓜烂熟每个节点非红即黑根节点是黑色叶子节点NIL是黑色红色节点的两个子节点必须是黑色不能出现连续红节点从任一节点到其每个叶子节点的所有路径包含相同数量的黑色节点第 5 条规则是红黑树的灵魂。它保证了“黑高”一致再加上第 4 条限制连续红节点理论上最长路径就是“黑 红 黑 红……”交替最多是纯黑路径的两倍。这个“不超过两倍”虽然不如 AVL 的“高度差不超过 1”精确但已经足够把树高限制在 O(log n)换来的是更少的旋转。AVL 追求绝对均衡红黑树追求“尚算均衡”。所以红黑树在插入、删除频繁的场景下整体成本更低STL 的 map、setLinux 内核的调度器、虚拟内存管理用的都是红黑树。2. AVL 树模拟实现旋转是最值得写十遍的代码2.1 节点设计和高度维护AVL 节点的数据结构比普通 BST 多一个height字段。不需要像红黑树那样存父指针因为插入修复时我们用递归自底向上回退父节点天然就在递归栈里。#include algorithm using namespace std; struct AVLNode { int key; int height; AVLNode* left; AVLNode* right; AVLNode(int k) : key(k), height(1), left(nullptr), right(nullptr) {} }; 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 max(getHeight(node-left), getHeight(node-right)) 1; }这里有个新手最容易犯的错getHeight(nullptr)返回 0 才能让高度计算正确千万不能因为偷懒在空指针判断里返回 -1那会导致父节点高度全部算错。叶子节点高度为 1 而不是 0这是我习惯的约定你把nullptr高度当 0、空叶子当 0、单节点高当 1这套保持全局一致就没有问题。2.2 四种失衡与旋转选择AVL 插入之后只需要处理四种失衡情况。如果用 LL、LR、RL、RR 来命名记忆方式非常简单LL 和 RR 是单旋LR 和 RL 是双旋。LL 就是“左边太重往右掰”RR 就是“右边太重往左掰”。LR 是“左孩子的右子树过长”必须先左旋左孩子变成 LL再右旋根节点RL 同理。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; }为什么双旋不能直接用两次单旋代替可以双旋本来就是两次单旋的复合。关键在于顺序和轴的选取。LR 的情况如果直接对根节点右旋你会把“左孩子的右子树”提上来但那个子树依然偏在右边问题没有解决。必须先让左孩子左旋把 LL 形态构造出来再对整体右旋。这个“先处理孩子再处理自己”的思路在红黑树里还会出现一次。判断用哪种旋转我用 balance 因子加插入位置来区分平衡因子插入位置情况处理 1左孩子的左子树LL右旋当前节点 1左孩子的右子树LR左旋左孩子右旋当前节点 -1右孩子的右子树RR左旋当前节点 -1右孩子的左子树RL右旋右孩子左旋当前节点2.3 插入过程的完整代码AVL 插入的递归写法和普通 BST 几乎一样只是每次递归返回后要重新计算高度并检查平衡因子。插入的 key 和当前节点相等时我直接返回不处理这对应集合语义如果要做映射表就在相等分支里覆盖 value。AVLNode* insertAVL(AVLNode* node, int key, int rotateCount) { if (!node) return new AVLNode(key); if (key node-key) node-left insertAVL(node-left, key, rotateCount); else if (key node-key) node-right insertAVL(node-right, key, rotateCount); else return node; updateHeight(node); int balance getBalance(node); // LL if (balance 1 key node-left-key) { rotateCount; return rotateRight(node); } // RR if (balance -1 key node-right-key) { rotateCount; return rotateLeft(node); } // LR if (balance 1 key node-left-key) { node-left rotateLeft(node-left); rotateCount; return rotateRight(node); } // RL if (balance -1 key node-right-key) { node-right rotateRight(node-right); rotateCount; return rotateLeft(node); } return node; }写这段代码的时候有个隐藏的细节判断 LL 时用的是key node-left-key而不是盲目比较balance 1就右旋。因为 balance 1 只能说明左子树比右子树高但具体是左孩子的哪一侧变高要靠 key 的数值去判断。如果插入的是重复 key函数在前面就直接 return 了不会走到这里。把 key 判断换成“比较两个子树高度”也能判断但用 key 更直观而且不需要额外查询。LR 分支里那句node-left rotateLeft(node-left)很容易被漏写。漏掉之后直接把根右旋旋转后的树依然是失衡的树高并没有真正恢复。我自己第一次手撕 AVL 就犯过这个错表现出来就是插入了固定数据之后验证函数检查平衡因子没过。3. 红黑树模拟实现插入修复的三种情形3.1 红黑规则与节点默认颜色红黑树的节点结构比 AVL 多一个 parent 指针和颜色标记。有人问 non-recursive 实现是不是必须存 parent我的回答是如果只做插入递归加引用也能绕过去但删除修复的循环逻辑里有大量“找叔父、找祖父、找兄弟”的操作没有 parent 指针写起来的复杂度会指数级上升。STL 的实现也是带 parent 的。enum Color { RED, BLACK }; struct RBNode { int key; Color color; RBNode* left; RBNode* right; RBNode* parent; RBNode(int k) : key(k), color(RED), left(nullptr), right(nullptr), parent(nullptr) {} };新插入的节点为什么默认红色想一下规则 5如果插入黑色节点从祖父到叶子的某一条路径就会多一个黑色节点后面对黑高的破坏需要大范围调整。红色节点则不同它唯一可能违反的是规则 4连续红节点而连续红节点只会影响局部路径修复范围小得多。所以“先默认红再向上修复”是成本最低的策略。3.2 三种修复情形的判别与处理插入修复的逻辑可以收敛成一张很清晰的决策表。假设插入的节点是 z它的父节点是红色如果是黑色就直接结束了看叔叔节点 y 的颜色情况一叔叔是红色把父节点和叔叔都变黑祖父变红然后 z 上移到祖父继续循环。这是一种“扩散式”修复红黑颜色向上浮把冲突从局部推向更高层。纯变色完成后子树的黑高不变所以不需要旋转。情况二叔叔是黑色且 z 是内侧节点也就是 z 是父节点的右孩子而父节点是祖父的左孩子或者镜像。先用父节点做一次旋转让内侧变外侧此时树形从 LR/RL 变成 LL/RR但颜色冲突还在走到情况三。情况三叔叔是黑色且 z 是外侧节点父节点变黑祖父变红然后对祖父旋转。旋转完成后原来的父节点代替祖父成为子树根整棵子树的黑高和旋转前保持一致而且不会再出现连续红节点。下面是一个可以直接跑通的插入修复代码我把左、右两侧分开写成两个函数避免在一大段 if-else 里迷路void rotateLeft(RBNode* root, RBNode* x) { RBNode* y x-right; x-right y-left; if (y-left) y-left-parent x; y-parent x-parent; if (!x-parent) root y; else if (x x-parent-left) x-parent-left y; else x-parent-right y; y-left x; x-parent y; } void rotateRight(RBNode* root, RBNode* x) { RBNode* y x-left; x-left y-right; if (y-right) y-right-parent x; y-parent x-parent; if (!x-parent) root y; else if (x x-parent-right) x-parent-right y; else x-parent-left y; y-right x; x-parent y; } void fixupInsert(RBNode* root, RBNode* z) { while (z-parent z-parent-color RED) { RBNode* grand z-parent-parent; if (z-parent grand-left) { RBNode* uncle grand-right; if (uncle uncle-color RED) { z-parent-color BLACK; uncle-color BLACK; grand-color RED; z grand; } else { if (z z-parent-right) { z z-parent; rotateLeft(root, z); } z-parent-color BLACK; grand-color RED; rotateRight(root, grand); } } else { RBNode* uncle grand-left; if (uncle uncle-color RED) { z-parent-color BLACK; uncle-color BLACK; grand-color RED; z grand; } else { if (z z-parent-left) { z z-parent; rotateRight(root, z); } z-parent-color BLACK; grand-color RED; rotateLeft(root, grand); } } } root-color BLACK; }这里最容易被忽略的一点是while循环的进入条件。第一次循环判断的是“父节点是不是红色”如果父节点是黑色就可以退出了如果父节点为空说明 z 已经升到根循环退出后强制把根染黑。很多实现会额外在uncle判断里先判空实际上空叔叔等价于黑色叔叔直接走 else 分支即可不需要单独处理。旋转的时候还有个小坑rotateLeft/rotateRight里必须同步更新 parent 指针。有些人只改了 left、right 没改 parent结果修复循环里走两步就拿到了 nullptr程序直接崩溃。3.3 删除修复的“双黑”难题删除比插入难这是红黑树的共识。插入修复只需要处理“父红子红”的冲突删除修复要解决的问题是“某个路径少了一个黑色节点”也就是黑高失衡。为了解决这个问题我们把这个缺失黑节点的路径标记成“双黑”double black修复的目标就是消除双黑。删除分两步先用 BST 的方式找到替代节点右子树最小或左子树最大把目标节点值拷过来然后物理删除替代节点。如果被删除的节点是红色没有任何问题直接结束如果被删除的节点是黑色它的位置就变成了双黑节点需要把它的兄弟节点分情况讨论兄弟是红色父节点变红兄弟变黑然后旋转父节点转换之后问题变成兄弟是黑色的情形。兄弟是黑色兄弟的两个孩子都是黑色兄弟变红双黑节点向上移动到父节点。如果父节点是红色父节点变黑就结束如果父节点是黑色父节点继续作为双黑节点递归处理。兄弟是黑色兄弟的左孩子是红色右孩子是黑色对兄弟做右旋把红色孩子翻到外侧转换成情况 4。兄弟是黑色兄弟的右孩子是红色外侧红父节点的颜色平移给兄弟父节点变黑兄弟的右孩子变黑旋转父节点双黑消除。这四种情况是等镜像的两侧各一套。写删除修复的时候我强烈建议先把对称的两半各自用一个函数封装比如fixupDeleteLeft和fixupDeleteRight否则很容易在镜像转换的时候把 left/right 写反。我在第一次写删除修复时就是因为左右镜像没对应上测了一晚上全是断言失败最后把两半拆开才找到问题。物理删除节点时还有一个边界条件如果要删的节点是根节点直接置空返回如果只有一个孩子直接用孩子顶上来并保持颜色如果两个孩子的替代节点是叶子或只有一个右孩子需要先把替代节点从树上摘下来。4. 实测对比高度、旋转次数与场景选择4.1 实测高度、旋转次数与调用成本学习平衡树不能只看理论。我写了一段压测程序分别对普通 BST、AVL 树、红黑树插入十万个随机整数统计三者的高度和旋转次数结果如下指标普通 BSTAVL 树红黑树10万随机数据高度约 37约 17约 2710万有序数据高度100000约 17约 27单次插入平均旋转次数0约 0.46约 0.42随机数据下 AVL 和红黑树的表现差距不大红黑树更高是因为它的平衡条件更宽松。有序数据下普通 BST 直接退化AVL 和红黑树依然稳定。旋转次数上插入阶段 AVL 与红黑树实际差距并不明显真正的差距会在删除操作上进一步拉开红黑树删除修复的触发频率比 AVL 低不少。这就是为什么 STL map、set 选红黑树而不选 AVLmap 是高频读写的容器删除操作频繁红黑树的整体调整成本更低。而像数据库的只读索引、比赛评测中大量查询的场景AVL 的严格平衡更能压榨出性能。4.2 AVL 与红黑树的选择建议选型从来不是“谁更高级”的问题而是“你的场景里什么操作最频繁”的问题。我做了一个表格方便直接对照维度AVL 树红黑树平衡严格度高度差不超过 1最长路径不超过最短路径 2 倍树高上界约 1.44 * log2(n)约 2 * log2(n)查询性能更好略逊但仍在 log n 量级插入旋转成本略高更低删除修复成本更高可能一路回溯到根最多 3 次旋转定性解决适用场景查询多、内存敏感插入删除多、通用容器实际工程里红黑树因为删除操作的“3 次旋转定胜负”特性很容易实现可预测的延迟AVL 的删除则可能一直旋转到根最坏情况下旋转次数是 O(log n)。如果你做的是硬实时系统红黑树的删出成本更容易被保证。但也不要盲目迷信红黑树。纯粹的“读多写少”场景AVL 的查询路径更短加上缓存友好的节点布局实测查询能比红黑树快 10% 到 20%。很多内存数据库的跳表与 AVL 并存也是因为读请求占比太高时AVL 更划算。4.3 用断言验证树的性质模拟实现写完最怕的是“以为自己写对了”。调试平衡树最有效的手段不是断点跟代码而是写一个验证函数断言的性质不满足就立刻失败。AVL 的验证函数是这样bool verifyAVL(AVLNode* node) { if (!node) return true; int bf getBalance(node); if (abs(bf) 1) return false; if (getHeight(node) ! max(getHeight(node-left), getHeight(node-right)) 1) return false; if (node-left node-left-key node-key) return false; if (node-right node-right-key node-key) return false; return verifyAVL(node-left) verifyAVL(node-right); }红黑树的验证要更麻烦一些需要检查五条性质。下面这个函数返回路径上的黑色节点数如果某个性质被破坏就返回 -1int verifyRB(RBNode* node) { if (!node) return 1; // NIL 是黑色黑高至少为 1 if (node-color RED) { if (node-left node-left-color RED) return -1; if (node-right node-right-color RED) return -1; } int leftBH verifyRB(node-left); int rightBH verifyRB(node-right); if (leftBH -1 || rightBH -1) return -1; if (leftBH ! rightBH) return -1; return leftBH (node-color BLACK ? 1 : 0); } bool isRBTree(RBNode* root) { if (!root) return true; if (root-color ! BLACK) return false; return verifyRB(root) ! -1; }注意verifyRB对空节点返回的是 1不是 0因为在我的约定里 NIL 节点视为黑色且黑高为 1。如果你采用另一种约定空节点黑高为 0那叶子节点的黑高计数会整体少 1但只要全局一致就没问题。不要混用两套约定不然写断言时永远会对不上。我把这一套验证函数放在每次插入、删除之后调用所有随机测试数据都跑了一遍它可以立刻暴露旋转时漏更新高度、颜色没变、或者是镜像写反的问题。5. 模拟实现中的常见翻车现场5.1 我在写旋转时踩过的三个坑第一个坑AVL 里更新高度的顺序。旋转函数中先更新两棵子树的高度然后再更新新的根节点高度。顺序写反的话旋转后根节点的高度会算成旧的子树高度导致下一次平衡判断直接出错。最好写成先更新子节点、再更新父节点并且把更新高度的逻辑独立成updateHeight而不是内联。第二个坑红黑树旋转后忘了维护根指针。当旋转的节点没有父节点时它就是根旋转结束后 root 必须指向新的节点。这个分支我一开始没写结果旋转后整棵树从局部看是对的但根部丢失程序一跑就直接段错误。标准实现里那个if (!x-parent) root y;一行都不能省。第三个坑递归里使用局部引用变量保存 node 地址。AVL 插入用递归返回新根是安全的因为每个调用点都会接收返回值。但如果有人试图用node的引用在整个函数里来回传一旦发生旋转局部引用指向的地址变了后面的代码操作的就是废弃节点。我在学习期间曾经为了“优化”把返回值改成引用结果很快意识到这个思路在旋转发生时会自毁。5.2 什么时候要用哨兵节点红黑树实现里NIL 叶子节点是个很微妙的设计。有的人用nullptr直接当叶子有的人建一个静态的黑色节点当哨兵。STL 用的就是哨兵节点好处是删除修复中的“兄弟节点”永远不为空你能少写一半的空指针判断。用nullptr的好处是内存分配简单代码阅读直观坏处是写删除修复时要时刻判断sibling nullptr的情况一旦漏判就会出现空指针访问。我的建议是学习阶段先用nullptr把旋转和插入修复跑通写删除修复时再考虑引入哨兵。不要一开始就用哨兵否则你分不清“逻辑上该判断空指针”和“语法上哨兵避免了判断”到底是怎么回事。5.3 调试平衡树的三个实用技巧第一个技巧小数据量暴力验证。先用 1 到 100 的所有排列顺序去插入或者随机生成 1000 个数每次都调用验证函数检查性质。数据量小才能让你在断言失败时快速手推那几条路径。第二个技巧把树的结构打印出来。不要只打印 key要把平衡因子或颜色一起印出来。我在调试红黑树时专门写了一个带缩进的树形打印函数红黑树还会标上R/B后缀一眼就能看出连续红节点位置。这是追踪修复过程最直接的手段。第三个技巧每次旋转都留日志。旋转是树形结构的关键转折点在旋转函数里打一条日志记录旋转节点、旋转方向和前后状态。删除修复出问题时配合日志能快速定位到第几步的镜像写错了。两个树完整模拟实现之后我觉得最大的收获不是背会了旋转代码而是理解了“平衡”的本质不是某一瞬间的巧合而是一套在任何操作之后都能自我修复的机制。AVL 用高度差驱动旋转红黑树用颜色驱动变色和旋转它们都是在 BST 的骨架上加了“后悔药”每次操作结束之后都能把自己拉回安全状态。我自己在写完两棵树之后又顺手用红黑树的五条性质去验证了一遍标准库 map 的实现发现它比教科书版本多了很多针对缓存命中和内存池的优化但核心逻辑和这篇笔记里的插入修复基本一致。