尧图网页设计 
1. 先从“为什么”说起红黑树到底解决什么问题很多人在C学习路上都会遇到红黑树尤其是看到STL里map、set的底层实现时。我最早接触红黑树是在啃《STL源码剖析》那本书的时候说实话第一遍几乎没看明白各种旋转、变色、双红修正看得人头皮发麻。后来自己在工程项目里用C手搓了好几遍红黑树才慢慢把它的来龙去脉摸清楚。先说结论红黑树本质上还是一棵二叉搜索树BST它只是在BST的基础上加了一条“平衡”约束。普通的BST在最坏情况下会退化成链表——比如你按1、2、3、4、5的顺序插入节点树就变成一条直线查找复杂度直接从O(log n)退化到O(n)。红黑树通过对节点染上红色或黑色并维护五条性质保证树的高度始终维持在O(log n)的量级从而让插入、删除、查找的时间复杂度都稳定在O(log n)。那为什么STL选红黑树而不是AVL树这是个很经典的问题。AVL树的平衡要求更严格左右子树高度差不能超过1查找性能确实更好但每次插入删除后需要更多旋转来维持这种强平衡代价太大。红黑树允许一定程度的不平衡最长路径不超过最短路径的2倍换来的是更少的旋转次数。实际场景中插入删除越频繁红黑树的优势就越明显。STL的map和set都是高频插入删除的热门容器选红黑树是很务实的折中方案。这篇博文面向两类读者一是正在学习数据结构、想在C里亲手实现红黑树的同学二是面试前想系统梳理红黑树原理、准备手写代码的求职者。我会从设计思路讲起逐步拆解插入和删除两大核心流程附上完整可运行的C实现思路最后分享一些我在调试红黑树时踩过的坑和排查技巧希望能帮你把这棵“网红树”彻底拿捏。2. 设计与架构动手写代码前先把底子打好2.1 红黑树的五条性质先把地基夯实在谈实现之前必须把红黑树的五条性质刻在脑子里因为后面所有插入删除的修正逻辑本质上都是在维护这五条性质性质1每个节点不是红色就是黑色性质2根节点是黑色性质3每个叶子节点NIL节点也叫空节点是黑色性质4如果一个节点是红色的那么它的两个子节点必须是黑色的换句话说不能出现连续的红色节点性质5从任意节点到其每个叶子节点的所有路径都包含相同数目的黑色节点。这五条性质维护起来最直观的结果就是从根到叶子的最长路径不会超过最短路径的2倍。为什么因为性质5保证了所有路径的黑节点数相等性质4又限制了红色节点不能连续出现那么最长路径就是“红黑交替”最短路径就是“全黑”两条路径的长度差顶多就是一倍黑节点数。所以树的高度最多是2 * O(log n)依然是O(log n)。你只记住一条核心就行红黑树平衡的本质靠的是“约束黑色节点的数量和位置”而红色节点是工具人用来帮助调整。理解了这条逻辑后面再看插入删除的修正过程就不是背代码了而是推演。2.2 节点的数据结构我为什么选择三叉链实现红黑树的第一步是定义节点。红黑树的节点至少需要四样东西键值对或单独的key、左右孩子指针、颜色标记。我在工程落地的时候还额外加了一个parent指针用的是三叉链结构。enum Color { RED, BLACK }; template typename K, typename V struct RBNode { K key; V value; RBNode* left; RBNode* right; RBNode* parent; Color color; RBNode(const K k, const V v) : key(k), value(v), left(nullptr), right(nullptr), parent(nullptr), color(RED) {} };这里有个细节新节点默认染成红色。为什么因为插入一个红色节点最多只会破坏性质4也就是可能出现连续的红色节点修复它的成本很低。如果插入黑色节点性质5直接被破坏意味着从根到某个叶子的路径上多了一个黑节点整棵树所有路径的黑色数量都要重新对齐代价大得离谱。所以所有新节点一律涂红这是红黑树实现里的一个共识。不过这里有一个小坑new出来的节点其left、right、parent默认都是nullptr而这个nullptr在红黑树里是不能直接当作普通节点参与性质判断的。严谨的红黑树实现应该用“哨兵节点”NIL来代替nullptr让所有叶子节点都指向同一个黑色NIL节点。我在下面的代码中用nullptr做了简化处理但在判断需要区分空节点和叶子节点时特别注意别把空指针的“颜色”搞混了。后面讲删除的时候你会发现这个“空指针算黑色”的约定至关重要。2.3 模板设计从KV到KeyOfValue如果只是写一个红黑树最简单的方式就是定义模板参数为K和V。但如果你想让自己写的红黑树能像STL那样复用比如map的每个节点是pairconst K, Vset的节点就是K更优雅的设计是让模板参数接受一个仿函数来提取key。template typename Key, typename Value, typename KeyOfValue class RBTree { // KeyOfValue用于从Value中提取Key };比如map的节点存的是pairconst K, VKeyOfValue仿函数就写上取出pair.first的逻辑set的节点存的是KKeyOfValue直接返回K本身。这样一个红黑树可以同时服务map和set不用写两份。我当时就是这么干的因为STL也是这么设计的。不过要注意仿函数在比较key时必须使用const引用避免不必要的拷贝尤其是当Value是一个大对象时这个优化能省不少性能。2.4 左旋与右旋红黑树调整的“基本动作”红黑树的各种修正最终都会落到旋转操作上。旋转的本质是在不破坏BST中序遍历顺序的前提下改变子树的结构关系。左旋和右旋是一对镜像操作。左旋的语义是把某个节点x的右子树提上来让x变成右孩子的左子树。void leftRotate(RBNode* x) { RBNode* y x-right; // y是x的右孩子旋转后y成为子树的新根 x-right y-left; // y的左子树过继给x当右孩子 if (y-left) y-left-parent x; y-parent x-parent; // y接管x原先的父节点关系 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; }右旋的逻辑完全镜像可以当作练习自己写一遍。写旋转代码的时候最容易出错的地方是parent指针的维护尤其是改动子树的根节点后原有父节点的左、右指针指向必须同步更新。我建议在写完旋转操作后写一个小测试用例反复插入数据打印中序遍历确认BST性质没有被破坏。旋转不改变中序序列这是检验旋转代码正确性的黄金标准。核心实现一插入从“无脑插叶子”到“双红修复”3.1 插入的整体流程先BST后修正红黑树的插入过程可以拆成两步第一步是普通BST插入找到合适的空位挂上新节点第二步检查是否违反红黑树性质如果违反就通过变色和旋转修复。BST插入的部分很直接从根开始比key小往左走比key大往右走走到空位就挂上。这里有个决策点如果key已经存在怎么办我选择只在key严格大于当前节点时才往右走这样遇到相等key时直接返回false表示插入失败。这个细节在实现set的insert语义时会非常有用。插入完成后最核心的工作就来了调用insertFixUp修复颜色。3.2 双红冲突叔叔节点的颜色决定一切假设新插入节点是z如果z的父节点是黑色的万事大吉树仍然是合法的。但麻烦在于z的父节点也可能是红色那就违反了性质4——连续出现红色节点。这里的修复策略完全取决于z的叔叔节点即父节点的兄弟节点是什么颜色。情况一叔叔是红色。这时候不需要旋转只需要变色。把父节点和叔叔节点都涂成黑色把祖父节点涂成红色。为什么因为性质5要求每条路径的黑色节点数相等我们把祖父从黑变红把父和叔叔从红变黑相当于把黑色从祖父下沉到两个子节点路径上的黑节点总数没变但双红问题被消解了。处理完之后把z指向祖父节点继续往上检查因为祖父变红了它可能跟更上面的节点又形成双红。情况二叔叔是黑色或者是空节点空节点算黑色。这时候光变色不够必须旋转。但旋转之前还要看z、父、祖父三者是否位于同一侧。如果z是父的左孩子且父是祖父的左孩子属于LL型直接对祖父右旋然后父变黑、祖父变红。如果z是父的右孩子但父是祖父的左孩子属于LR型需要先对父左旋变成LL型再做LL处理。我第一次看这些字母组合时也有点晕后来我用一个生活化的类比就豁然开朗了变色解决“局部冲突”但无力改变“结构失衡”旋转改变“结构关系”但不动颜色。两者必须配合使用而触发旋转的判据就是叔叔是否为红色——叔叔红说明兄弟分支“有富余的黑色可以帮忙”叔叔黑说明兄弟分支“没有余力”必须自己调整结构。3.3 插入修复的代码与关键参数下面是我在C里实现insertFixUp的核心逻辑结合注释看会清晰很多void insertFixUp(RBNode* z) { while (z-parent z-parent-color RED) { if (z-parent z-parent-parent-left) { // 父节点是祖父的左孩子 RBNode* uncle z-parent-parent-right; if (uncle uncle-color RED) { // 情况一叔叔为红色变色处理 z-parent-color BLACK; uncle-color BLACK; z-parent-parent-color RED; z z-parent-parent; // 继续向上检查 } else { // 情况二叔叔为黑色或不存在 if (z z-parent-right) { // LR型先左旋父节点转成LL型 z z-parent; leftRotate(z); } // LL型右旋祖父然后变色 z-parent-color BLACK; z-parent-parent-color RED; rightRotate(z-parent-parent); } } else { // 父节点是祖父的右孩子镜像对称处理 RBNode* uncle z-parent-parent-left; if (uncle uncle-color RED) { z-parent-color BLACK; uncle-color BLACK; z-parent-parent-color RED; z z-parent-parent; } else { if (z z-parent-left) { // RL型先右旋父节点转成RR型 z z-parent; rightRotate(z); } // RR型左旋祖父 z-parent-color BLACK; z-parent-parent-color RED; leftRotate(z-parent-parent); } } } root-color BLACK; }有一个关键参数的细节值得展开循环的终止条件和根节点强制变黑。while循环里判断z-parent存在且为红色但只要循环结束我们最后还要无条件把根染黑这是因为情况一的变色处理可能把红色一路传递到根节点而性质2要求根必须是黑色。这个“最后根必黑”的兜底逻辑一定要写否则你会遇到根节点为红色的野Bug。另外判断叔叔是否存在时如果uncle是nullptr直接按黑色处理所以上面代码里uncle uncle-color RED的判断顺序不能调换。这在删除修复里更是性命攸关。3.4 插入后的个人验证心得我写完插入逻辑后第一件事不是看起来对不对而是写了一个随机测试随机生成1万个整数依次插入每次插入后遍历全树验证五条性质是否满足。特别是性质5我写了一个递归函数计算所有从根到叶子的路径的黑节点数如果任意两条路径数量不一致直接断言失败。这里有个小技巧不需要每次插入都从头验证性质5那样太慢。可以只在测试模式下开启严格校验比如每插入100次校验一次在Release版本下关闭。我当时就因为全量校验导致测试跑得极慢后来改成抽样校验效率提升明显。4. 核心实现二删除红黑树最难啃的硬骨头4.1 删除的第一步找替身转移问题我敢打赌绝大多数觉得红黑树“可怕”的人都是被删除操作劝退的。其实删除的难点完全不在删除这个动作本身而在于删完之后怎么恢复性质。先说一个关键技巧红黑树的删除并不是直接把目标节点从树上摘掉而是找“替死鬼”。如果目标节点z有两个非空孩子我们不能直接删它因为删掉后它有两个孩子要重新挂接非常麻烦。正确做法是找到z的中序后继节点即右子树中最小的那个节点把它“复制”或“移动”到z的位置然后实际删除的是那个后继节点。这样实际被删除的节点最多只有一个非空孩子。为什么这个方法好用因为中序后继一定没有左孩子它要么只有右孩子要么没有孩子这样一来删除就退化成“摘掉一个至多有一个孩子的节点”处理起来简单得多。STL的实现也是这个套路。4.2 真正棘手的地方删除黑色节点后的修复假如被实际删除的节点x是红色的那一切都好说红节点被摘掉树的深度和其他路径都没受影响五条性质纹丝不动直接完事。但如果x是黑色的性质5就炸了——从根到经过x的叶子路径少了一个黑节点相当于这条路径比其他路径“矮了一截”。我们需要引入“双黑”的概念来理解修复过程可以想象x的位置继承了一个“额外黑色负载”目标是把这个负载向上移动直到找到一个红色节点把它染成黑色来抵消负载或者把负载移动到树的根部直接不管。删除修复的完整情况分类比插入要多但核心判断还是看兄弟节点的颜色兄弟节点是红色还是黑色直接决定下一步是旋转还是变色。这里罗列主要的四种情况情况1兄弟节点是红色。把兄弟染黑、父染红然后对父做一次旋转根据兄弟在左还是右决定左旋还是右旋这样就把问题转化成兄弟为黑色的情况。这一步的本质是“通过旋转把红色兄弟踢到一边让黑色侄子顶上来当新的兄弟”。情况2兄弟是黑色且兄弟的两个孩子都是黑色或空。此时可以把兄弟染红然后把“额外黑色负载”上移到父节点继续循环处理父节点。情况3兄弟是黑色兄弟的左孩子是红色右孩子是黑色或者相反取决于兄弟在哪一侧。通过旋转把兄弟的红色孩子转到外侧并重新染色转化为情况4。这是为情况4做铺垫的“方向调整”。情况4兄弟是黑色且兄弟外侧的孩子是红色。这时候进行一次旋转交换父和兄弟的颜色把外侧红孩子染黑直接消除“额外黑色负载”循环结束。这套分情况讨论的逻辑我第一次看的时候完全懵了后来我自己做了一个折纸模型用不同颜色的小卡片代表节点在桌面上模拟每一次旋转和变色。这个方法意外地有效强烈推荐空间想象力不够的同学试试。纯看代码很难建立直觉动手模拟十几轮之后你对每种情况的触发条件下意识就能反应过来。4.3 删除修复代码与“空节点算黑色”的陷阱下面给出我实现的eraseFixUp核心骨架。这个函数接受两个参数被删除节点的替代者x以及x的父节点parent因为x可能已经是nullptr无法从x拿到parent指针。void eraseFixUp(RBNode* x, RBNode* parent) { while (x ! root (!x || x-color BLACK)) { if (x parent-left) { RBNode* brother parent-right; // 情况1兄弟为红色 if (brother brother-color RED) { brother-color BLACK; parent-color RED; leftRotate(parent); brother parent-right; // 更新兄弟指针 } // 情况2兄弟的孩子都是黑色或不存在 if ((!brother-left || brother-left-color BLACK) (!brother-right || brother-right-color BLACK)) { if (brother) brother-color RED; x parent; parent x-parent; } else { // 情况3兄弟的左孩子为红色右孩子为黑色 if (!brother-right || brother-right-color BLACK) { if (brother-left) brother-left-color BLACK; brother-color RED; rightRotate(brother); brother parent-right; } // 情况4兄弟的右孩子为红色 brother-color parent-color; parent-color BLACK; if (brother-right) brother-right-color BLACK; leftRotate(parent); x root; } } else { // 镜像逻辑 // ... 与上面结构完全对称把left和right互换即可 } } if (x) x-color BLACK; }这代码必须要强调兄弟可能是空节点而空节点在红黑树里算黑色节点。所以每次访问brother-left之前必须先判空。我在第一版实现里因为忘了判空在eraseFixUp里解引用空指针导致删除特定序列的数据时程序直接崩溃排查了一个多小时才发现问题。还有一个很容易写错的点删除操作在替换节点时不仅仅要改指针还要保留原始节点的颜色信息因为我们要判断被删节点的颜色来决定是否需要repair。另外如果被删节点有孩子节点替换后要把孩子的parent指针指向被删节点的父节点这个三叉链的维护很琐碎但漏了任何一条都会导致树崩溃。容器封装与迭代器从裸树到可用的STL风格容器5.1 为什么实现迭代器是“最后一公里”很多资料讲红黑树讲完插入删除就收工了。但如果你真的想在项目里用它光有一棵能插入能删除的树是远远不够的你必须能遍历它。在C里遍历容器最自然的姿势就是迭代器。实现一个红黑树迭代器也是从“数据结构作业”走向“工程可用”的关键一步。STL的红黑树迭代器本质上就是对节点指针的轻量封装但难点在operator和operator--。要知道红黑树不是线性结构内存里不存在“下一个节点”的概念你只能利用中序遍历的性质来推导。5.2 operator的逻辑没有右孩子就往上找到第一个“左拐点”我直接说结论中序遍历中一个节点的后继节点求法分两种情况如果当前节点有右子树后继就是右子树中最左边的节点如果当前节点没有右子树就需要沿着parent指针向上找直到找到一个节点p满足当前节点在p的左子树中也就是p的左孩子是当前节点或者当前节点在p的左子树上。这个p就是后继。RBNode* increment(RBNode* node) const { if (node-right) { // 右子树存在找右子树的最左节点 RBNode* cur node-right; while (cur-left) cur cur-left; return cur; } // 右子树不存在向上回溯 RBNode* cur node; RBNode* parent cur-parent; while (parent cur parent-right) { cur parent; parent cur-parent; } return parent; }这个“向上找第一个左拐点”的逻辑很有意思你仔细想想就明白中序遍历的顺序是“左-根-右”如果当前节点的右子树为空说明以它为根的子树已经遍历完了接下来要回到它的祖先节点而这个祖先必须是“左拐”过来的那个节点——也就是当前节点位于该祖先的左子树中。记住这句话面试问到迭代器实现时能背出来比自己现推强多了。注意如果红黑树使用了哨兵NIL节点迭代器到末尾时会指向哨兵节点这时候end()就代表遍历完毕。如果用nullptr实现需要额外判断返回nullptr的情况。我在代码里给迭代器增加了一个bool标识或者直接以nullptr作为end()的底层指针实测可用但严谨性稍差面试时可以主动提到这个取舍。5.3 begin()和end()的细节begin()应该返回中序遍历的第一个节点也就是整棵树的最左节点。end()在STL里的语义是“最后一个元素的下一个位置”对于红黑树来说通常就是nullptr或哨兵节点。这个对称设计很容易理解但有一个细节很少有人提当你插入或删除节点后迭代器的失效范围是多少红黑树的插入操作不会导致已有迭代器失效除了指向被删节点的迭代器这是基于BST的结构特性——插入新节点不会改变已有节点的相对位置关系。这个特性在写代码时非常有用。6. 测试与调试如何证明你的红黑树是对的6.1 用断言函数做“体检”红黑树写完了怎么证明它对写单元测试时不能只测插入和删除能否跑通关键在于验证五条性质每次操作后仍然成立。我当时写了一个validate函数递归检查整棵树int validateNode(RBNode* node) { if (!node) { return 1; // 空节点算一个黑节点 } // 性质4不出现连续红 if (node-color RED) { assert(!node-left || node-left-color BLACK); assert(!node-right || node-right-color BLACK); } // 递归校验左右子树的黑节点数 int leftBlack validateNode(node-left); int rightBlack validateNode(node-right); assert(leftBlack rightBlack); // 性质5左右路径黑节点数相等 return leftBlack (node-color BLACK ? 1 : 0); }这个递归函数本身就是一个极好的面试题目。它自底向上统计每条路径的黑色节点数并在任意节点的左右子树之间做一致性检查。关键是只要有一个节点的左右两侧黑节点数不相等整棵树必然不合法。这个断言在每次插入、删除后调用能抓出绝大多数实现错误。我在测试时用的是随机序列加边界序列的组合。边界序列包括顺序插入、逆序插入、全部相等的key、先插后删、先删后插、反复插入删除等。红黑树实现中常见的隐藏Bug比如删除后根节点被错误涂红、迭代器越界、旋转后parent指针错乱在这些组合下基本都能暴露出来。6.2 调试定位的土办法如果断言失败了怎么定位是哪一步操作导致的我个人的经验是不用急着上调试器先在每次插入、删除之后打印整棵树的结构用括号或缩进表示树的层次和颜色一目了然。void printTree(RBNode* node, int depth) { if (!node) return; printTree(node-left, depth 1); for (int i 0; i depth; i) std::cout ; std::cout node-key (node-color RED ? R : B) std::endl; printTree(node-right, depth 1); }别小看这个简单工具。有一次我删除后根节点的颜色变成了红色打印结果里一眼就看出变色逻辑写错了——我把eraseFixUp里最后根节点强制染黑的那一行漏掉了。如果没有可视化打印我可能会在调试器里断点走半天才能发现。7. 常见问题速查我自己踩过的坑和解决思路现象可能原因排查思路插入后根节点变红忘了在insertFixUp末尾强制root涂黑在insertFixUp最后加 root-color BLACK删除后程序崩溃eraseFixUp里访问brother-left时brother为nullptr所有对兄弟节点的孩子访问前先判空中序遍历结果不对旋转操作没有正确维护parent指针做一组旋转前后中序遍历对比插入重复key时被容忍BST插入时只用小于或大于判断没有等于返回逻辑严格小于左走严格大于右走等于直接返回插入失败eraseFixUp无限循环兄弟节点更新后没有把x或parent正确上移对照四种情况逐步打印当前节点判断循环是否推进我在工程实践中还有一个体会红黑树的代码一定要分模块写旋转、插入修复、删除修复各成一个函数不要为了省几次函数调用把逻辑揉在一起。否则一旦出错排查的难度会成倍增加。就算你担心性能也可以在类定义里把这些函数声明为inline让编译器帮你优化。另外提一个面试常问的细节为什么红黑树插入删除的时间复杂度是O(log n)很多人只会背结论。简单来说插入/删除本身是BST查找消耗O(log n)修复过程中无论是变色还是旋转每次最多沿路径向上走一层旋转次数是常数级插入最多2次旋转删除最多3次所以总复杂度还是O(log n)。这个“修复操作次数有常数上界”的特点正是红黑树工程可用的关键所在。8. 从“能跑”到“好用”一点经验补充红黑树写完之后如果你还想再往前一步可以考虑给它加上内存管理的支持。我最初手写的版本new出来的节点没有统一析构测试时只插不删没什么感觉后来做了十万级节点的压力测试才发现内存泄漏。最简单的做法是在析构函数里递归释放左右子树但树深较大时递归调用栈可能溢出更稳妥的做法是层序遍历配合队列来销毁节点。另外我建议你有机会就去读一下STL源码里红黑树的实际实现重点看它是怎么用哨兵节点统一处理空指针的。我自己的工程代码里用的是nullptr版本虽然测试都过了但每次访问颜色前都要判空代码里到处都是分支判断读起来很不优雅。哨兵节点一个固定的黑色NIL节点可以把所有判空逻辑都优化掉它能访问自己的left和right颜色永远是黑色这样红黑树的代码可以从“防崩溃版”升级为“流畅版”逻辑也更加清爽。最后分享一个小技巧如果要在面试中展示手写红黑树不要从节点定义开始写先跟面试官说清楚你的整体结构——节点三叉链、旋转、插入修复、删除修复、迭代器让他知道你在宏观层面是清晰的。然后在写代码时按顺序来别上来就写insertFixUp。清晰的思路比流畅的代码更让面试官认可。 红黑树核心原理与C++实现：从插入修复到STL容器封装
1. 先从“为什么”说起红黑树到底解决什么问题很多人在C学习路上都会遇到红黑树尤其是看到STL里map、set的底层实现时。我最早接触红黑树是在啃《STL源码剖析》那本书的时候说实话第一遍几乎没看明白各种旋转、变色、双红修正看得人头皮发麻。后来自己在工程项目里用C手搓了好几遍红黑树才慢慢把它的来龙去脉摸清楚。先说结论红黑树本质上还是一棵二叉搜索树BST它只是在BST的基础上加了一条“平衡”约束。普通的BST在最坏情况下会退化成链表——比如你按1、2、3、4、5的顺序插入节点树就变成一条直线查找复杂度直接从O(log n)退化到O(n)。红黑树通过对节点染上红色或黑色并维护五条性质保证树的高度始终维持在O(log n)的量级从而让插入、删除、查找的时间复杂度都稳定在O(log n)。那为什么STL选红黑树而不是AVL树这是个很经典的问题。AVL树的平衡要求更严格左右子树高度差不能超过1查找性能确实更好但每次插入删除后需要更多旋转来维持这种强平衡代价太大。红黑树允许一定程度的不平衡最长路径不超过最短路径的2倍换来的是更少的旋转次数。实际场景中插入删除越频繁红黑树的优势就越明显。STL的map和set都是高频插入删除的热门容器选红黑树是很务实的折中方案。这篇博文面向两类读者一是正在学习数据结构、想在C里亲手实现红黑树的同学二是面试前想系统梳理红黑树原理、准备手写代码的求职者。我会从设计思路讲起逐步拆解插入和删除两大核心流程附上完整可运行的C实现思路最后分享一些我在调试红黑树时踩过的坑和排查技巧希望能帮你把这棵“网红树”彻底拿捏。2. 设计与架构动手写代码前先把底子打好2.1 红黑树的五条性质先把地基夯实在谈实现之前必须把红黑树的五条性质刻在脑子里因为后面所有插入删除的修正逻辑本质上都是在维护这五条性质性质1每个节点不是红色就是黑色性质2根节点是黑色性质3每个叶子节点NIL节点也叫空节点是黑色性质4如果一个节点是红色的那么它的两个子节点必须是黑色的换句话说不能出现连续的红色节点性质5从任意节点到其每个叶子节点的所有路径都包含相同数目的黑色节点。这五条性质维护起来最直观的结果就是从根到叶子的最长路径不会超过最短路径的2倍。为什么因为性质5保证了所有路径的黑节点数相等性质4又限制了红色节点不能连续出现那么最长路径就是“红黑交替”最短路径就是“全黑”两条路径的长度差顶多就是一倍黑节点数。所以树的高度最多是2 * O(log n)依然是O(log n)。你只记住一条核心就行红黑树平衡的本质靠的是“约束黑色节点的数量和位置”而红色节点是工具人用来帮助调整。理解了这条逻辑后面再看插入删除的修正过程就不是背代码了而是推演。2.2 节点的数据结构我为什么选择三叉链实现红黑树的第一步是定义节点。红黑树的节点至少需要四样东西键值对或单独的key、左右孩子指针、颜色标记。我在工程落地的时候还额外加了一个parent指针用的是三叉链结构。enum Color { RED, BLACK }; template typename K, typename V struct RBNode { K key; V value; RBNode* left; RBNode* right; RBNode* parent; Color color; RBNode(const K k, const V v) : key(k), value(v), left(nullptr), right(nullptr), parent(nullptr), color(RED) {} };这里有个细节新节点默认染成红色。为什么因为插入一个红色节点最多只会破坏性质4也就是可能出现连续的红色节点修复它的成本很低。如果插入黑色节点性质5直接被破坏意味着从根到某个叶子的路径上多了一个黑节点整棵树所有路径的黑色数量都要重新对齐代价大得离谱。所以所有新节点一律涂红这是红黑树实现里的一个共识。不过这里有一个小坑new出来的节点其left、right、parent默认都是nullptr而这个nullptr在红黑树里是不能直接当作普通节点参与性质判断的。严谨的红黑树实现应该用“哨兵节点”NIL来代替nullptr让所有叶子节点都指向同一个黑色NIL节点。我在下面的代码中用nullptr做了简化处理但在判断需要区分空节点和叶子节点时特别注意别把空指针的“颜色”搞混了。后面讲删除的时候你会发现这个“空指针算黑色”的约定至关重要。2.3 模板设计从KV到KeyOfValue如果只是写一个红黑树最简单的方式就是定义模板参数为K和V。但如果你想让自己写的红黑树能像STL那样复用比如map的每个节点是pairconst K, Vset的节点就是K更优雅的设计是让模板参数接受一个仿函数来提取key。template typename Key, typename Value, typename KeyOfValue class RBTree { // KeyOfValue用于从Value中提取Key };比如map的节点存的是pairconst K, VKeyOfValue仿函数就写上取出pair.first的逻辑set的节点存的是KKeyOfValue直接返回K本身。这样一个红黑树可以同时服务map和set不用写两份。我当时就是这么干的因为STL也是这么设计的。不过要注意仿函数在比较key时必须使用const引用避免不必要的拷贝尤其是当Value是一个大对象时这个优化能省不少性能。2.4 左旋与右旋红黑树调整的“基本动作”红黑树的各种修正最终都会落到旋转操作上。旋转的本质是在不破坏BST中序遍历顺序的前提下改变子树的结构关系。左旋和右旋是一对镜像操作。左旋的语义是把某个节点x的右子树提上来让x变成右孩子的左子树。void leftRotate(RBNode* x) { RBNode* y x-right; // y是x的右孩子旋转后y成为子树的新根 x-right y-left; // y的左子树过继给x当右孩子 if (y-left) y-left-parent x; y-parent x-parent; // y接管x原先的父节点关系 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; }右旋的逻辑完全镜像可以当作练习自己写一遍。写旋转代码的时候最容易出错的地方是parent指针的维护尤其是改动子树的根节点后原有父节点的左、右指针指向必须同步更新。我建议在写完旋转操作后写一个小测试用例反复插入数据打印中序遍历确认BST性质没有被破坏。旋转不改变中序序列这是检验旋转代码正确性的黄金标准。核心实现一插入从“无脑插叶子”到“双红修复”3.1 插入的整体流程先BST后修正红黑树的插入过程可以拆成两步第一步是普通BST插入找到合适的空位挂上新节点第二步检查是否违反红黑树性质如果违反就通过变色和旋转修复。BST插入的部分很直接从根开始比key小往左走比key大往右走走到空位就挂上。这里有个决策点如果key已经存在怎么办我选择只在key严格大于当前节点时才往右走这样遇到相等key时直接返回false表示插入失败。这个细节在实现set的insert语义时会非常有用。插入完成后最核心的工作就来了调用insertFixUp修复颜色。3.2 双红冲突叔叔节点的颜色决定一切假设新插入节点是z如果z的父节点是黑色的万事大吉树仍然是合法的。但麻烦在于z的父节点也可能是红色那就违反了性质4——连续出现红色节点。这里的修复策略完全取决于z的叔叔节点即父节点的兄弟节点是什么颜色。情况一叔叔是红色。这时候不需要旋转只需要变色。把父节点和叔叔节点都涂成黑色把祖父节点涂成红色。为什么因为性质5要求每条路径的黑色节点数相等我们把祖父从黑变红把父和叔叔从红变黑相当于把黑色从祖父下沉到两个子节点路径上的黑节点总数没变但双红问题被消解了。处理完之后把z指向祖父节点继续往上检查因为祖父变红了它可能跟更上面的节点又形成双红。情况二叔叔是黑色或者是空节点空节点算黑色。这时候光变色不够必须旋转。但旋转之前还要看z、父、祖父三者是否位于同一侧。如果z是父的左孩子且父是祖父的左孩子属于LL型直接对祖父右旋然后父变黑、祖父变红。如果z是父的右孩子但父是祖父的左孩子属于LR型需要先对父左旋变成LL型再做LL处理。我第一次看这些字母组合时也有点晕后来我用一个生活化的类比就豁然开朗了变色解决“局部冲突”但无力改变“结构失衡”旋转改变“结构关系”但不动颜色。两者必须配合使用而触发旋转的判据就是叔叔是否为红色——叔叔红说明兄弟分支“有富余的黑色可以帮忙”叔叔黑说明兄弟分支“没有余力”必须自己调整结构。3.3 插入修复的代码与关键参数下面是我在C里实现insertFixUp的核心逻辑结合注释看会清晰很多void insertFixUp(RBNode* z) { while (z-parent z-parent-color RED) { if (z-parent z-parent-parent-left) { // 父节点是祖父的左孩子 RBNode* uncle z-parent-parent-right; if (uncle uncle-color RED) { // 情况一叔叔为红色变色处理 z-parent-color BLACK; uncle-color BLACK; z-parent-parent-color RED; z z-parent-parent; // 继续向上检查 } else { // 情况二叔叔为黑色或不存在 if (z z-parent-right) { // LR型先左旋父节点转成LL型 z z-parent; leftRotate(z); } // LL型右旋祖父然后变色 z-parent-color BLACK; z-parent-parent-color RED; rightRotate(z-parent-parent); } } else { // 父节点是祖父的右孩子镜像对称处理 RBNode* uncle z-parent-parent-left; if (uncle uncle-color RED) { z-parent-color BLACK; uncle-color BLACK; z-parent-parent-color RED; z z-parent-parent; } else { if (z z-parent-left) { // RL型先右旋父节点转成RR型 z z-parent; rightRotate(z); } // RR型左旋祖父 z-parent-color BLACK; z-parent-parent-color RED; leftRotate(z-parent-parent); } } } root-color BLACK; }有一个关键参数的细节值得展开循环的终止条件和根节点强制变黑。while循环里判断z-parent存在且为红色但只要循环结束我们最后还要无条件把根染黑这是因为情况一的变色处理可能把红色一路传递到根节点而性质2要求根必须是黑色。这个“最后根必黑”的兜底逻辑一定要写否则你会遇到根节点为红色的野Bug。另外判断叔叔是否存在时如果uncle是nullptr直接按黑色处理所以上面代码里uncle uncle-color RED的判断顺序不能调换。这在删除修复里更是性命攸关。3.4 插入后的个人验证心得我写完插入逻辑后第一件事不是看起来对不对而是写了一个随机测试随机生成1万个整数依次插入每次插入后遍历全树验证五条性质是否满足。特别是性质5我写了一个递归函数计算所有从根到叶子的路径的黑节点数如果任意两条路径数量不一致直接断言失败。这里有个小技巧不需要每次插入都从头验证性质5那样太慢。可以只在测试模式下开启严格校验比如每插入100次校验一次在Release版本下关闭。我当时就因为全量校验导致测试跑得极慢后来改成抽样校验效率提升明显。4. 核心实现二删除红黑树最难啃的硬骨头4.1 删除的第一步找替身转移问题我敢打赌绝大多数觉得红黑树“可怕”的人都是被删除操作劝退的。其实删除的难点完全不在删除这个动作本身而在于删完之后怎么恢复性质。先说一个关键技巧红黑树的删除并不是直接把目标节点从树上摘掉而是找“替死鬼”。如果目标节点z有两个非空孩子我们不能直接删它因为删掉后它有两个孩子要重新挂接非常麻烦。正确做法是找到z的中序后继节点即右子树中最小的那个节点把它“复制”或“移动”到z的位置然后实际删除的是那个后继节点。这样实际被删除的节点最多只有一个非空孩子。为什么这个方法好用因为中序后继一定没有左孩子它要么只有右孩子要么没有孩子这样一来删除就退化成“摘掉一个至多有一个孩子的节点”处理起来简单得多。STL的实现也是这个套路。4.2 真正棘手的地方删除黑色节点后的修复假如被实际删除的节点x是红色的那一切都好说红节点被摘掉树的深度和其他路径都没受影响五条性质纹丝不动直接完事。但如果x是黑色的性质5就炸了——从根到经过x的叶子路径少了一个黑节点相当于这条路径比其他路径“矮了一截”。我们需要引入“双黑”的概念来理解修复过程可以想象x的位置继承了一个“额外黑色负载”目标是把这个负载向上移动直到找到一个红色节点把它染成黑色来抵消负载或者把负载移动到树的根部直接不管。删除修复的完整情况分类比插入要多但核心判断还是看兄弟节点的颜色兄弟节点是红色还是黑色直接决定下一步是旋转还是变色。这里罗列主要的四种情况情况1兄弟节点是红色。把兄弟染黑、父染红然后对父做一次旋转根据兄弟在左还是右决定左旋还是右旋这样就把问题转化成兄弟为黑色的情况。这一步的本质是“通过旋转把红色兄弟踢到一边让黑色侄子顶上来当新的兄弟”。情况2兄弟是黑色且兄弟的两个孩子都是黑色或空。此时可以把兄弟染红然后把“额外黑色负载”上移到父节点继续循环处理父节点。情况3兄弟是黑色兄弟的左孩子是红色右孩子是黑色或者相反取决于兄弟在哪一侧。通过旋转把兄弟的红色孩子转到外侧并重新染色转化为情况4。这是为情况4做铺垫的“方向调整”。情况4兄弟是黑色且兄弟外侧的孩子是红色。这时候进行一次旋转交换父和兄弟的颜色把外侧红孩子染黑直接消除“额外黑色负载”循环结束。这套分情况讨论的逻辑我第一次看的时候完全懵了后来我自己做了一个折纸模型用不同颜色的小卡片代表节点在桌面上模拟每一次旋转和变色。这个方法意外地有效强烈推荐空间想象力不够的同学试试。纯看代码很难建立直觉动手模拟十几轮之后你对每种情况的触发条件下意识就能反应过来。4.3 删除修复代码与“空节点算黑色”的陷阱下面给出我实现的eraseFixUp核心骨架。这个函数接受两个参数被删除节点的替代者x以及x的父节点parent因为x可能已经是nullptr无法从x拿到parent指针。void eraseFixUp(RBNode* x, RBNode* parent) { while (x ! root (!x || x-color BLACK)) { if (x parent-left) { RBNode* brother parent-right; // 情况1兄弟为红色 if (brother brother-color RED) { brother-color BLACK; parent-color RED; leftRotate(parent); brother parent-right; // 更新兄弟指针 } // 情况2兄弟的孩子都是黑色或不存在 if ((!brother-left || brother-left-color BLACK) (!brother-right || brother-right-color BLACK)) { if (brother) brother-color RED; x parent; parent x-parent; } else { // 情况3兄弟的左孩子为红色右孩子为黑色 if (!brother-right || brother-right-color BLACK) { if (brother-left) brother-left-color BLACK; brother-color RED; rightRotate(brother); brother parent-right; } // 情况4兄弟的右孩子为红色 brother-color parent-color; parent-color BLACK; if (brother-right) brother-right-color BLACK; leftRotate(parent); x root; } } else { // 镜像逻辑 // ... 与上面结构完全对称把left和right互换即可 } } if (x) x-color BLACK; }这代码必须要强调兄弟可能是空节点而空节点在红黑树里算黑色节点。所以每次访问brother-left之前必须先判空。我在第一版实现里因为忘了判空在eraseFixUp里解引用空指针导致删除特定序列的数据时程序直接崩溃排查了一个多小时才发现问题。还有一个很容易写错的点删除操作在替换节点时不仅仅要改指针还要保留原始节点的颜色信息因为我们要判断被删节点的颜色来决定是否需要repair。另外如果被删节点有孩子节点替换后要把孩子的parent指针指向被删节点的父节点这个三叉链的维护很琐碎但漏了任何一条都会导致树崩溃。容器封装与迭代器从裸树到可用的STL风格容器5.1 为什么实现迭代器是“最后一公里”很多资料讲红黑树讲完插入删除就收工了。但如果你真的想在项目里用它光有一棵能插入能删除的树是远远不够的你必须能遍历它。在C里遍历容器最自然的姿势就是迭代器。实现一个红黑树迭代器也是从“数据结构作业”走向“工程可用”的关键一步。STL的红黑树迭代器本质上就是对节点指针的轻量封装但难点在operator和operator--。要知道红黑树不是线性结构内存里不存在“下一个节点”的概念你只能利用中序遍历的性质来推导。5.2 operator的逻辑没有右孩子就往上找到第一个“左拐点”我直接说结论中序遍历中一个节点的后继节点求法分两种情况如果当前节点有右子树后继就是右子树中最左边的节点如果当前节点没有右子树就需要沿着parent指针向上找直到找到一个节点p满足当前节点在p的左子树中也就是p的左孩子是当前节点或者当前节点在p的左子树上。这个p就是后继。RBNode* increment(RBNode* node) const { if (node-right) { // 右子树存在找右子树的最左节点 RBNode* cur node-right; while (cur-left) cur cur-left; return cur; } // 右子树不存在向上回溯 RBNode* cur node; RBNode* parent cur-parent; while (parent cur parent-right) { cur parent; parent cur-parent; } return parent; }这个“向上找第一个左拐点”的逻辑很有意思你仔细想想就明白中序遍历的顺序是“左-根-右”如果当前节点的右子树为空说明以它为根的子树已经遍历完了接下来要回到它的祖先节点而这个祖先必须是“左拐”过来的那个节点——也就是当前节点位于该祖先的左子树中。记住这句话面试问到迭代器实现时能背出来比自己现推强多了。注意如果红黑树使用了哨兵NIL节点迭代器到末尾时会指向哨兵节点这时候end()就代表遍历完毕。如果用nullptr实现需要额外判断返回nullptr的情况。我在代码里给迭代器增加了一个bool标识或者直接以nullptr作为end()的底层指针实测可用但严谨性稍差面试时可以主动提到这个取舍。5.3 begin()和end()的细节begin()应该返回中序遍历的第一个节点也就是整棵树的最左节点。end()在STL里的语义是“最后一个元素的下一个位置”对于红黑树来说通常就是nullptr或哨兵节点。这个对称设计很容易理解但有一个细节很少有人提当你插入或删除节点后迭代器的失效范围是多少红黑树的插入操作不会导致已有迭代器失效除了指向被删节点的迭代器这是基于BST的结构特性——插入新节点不会改变已有节点的相对位置关系。这个特性在写代码时非常有用。6. 测试与调试如何证明你的红黑树是对的6.1 用断言函数做“体检”红黑树写完了怎么证明它对写单元测试时不能只测插入和删除能否跑通关键在于验证五条性质每次操作后仍然成立。我当时写了一个validate函数递归检查整棵树int validateNode(RBNode* node) { if (!node) { return 1; // 空节点算一个黑节点 } // 性质4不出现连续红 if (node-color RED) { assert(!node-left || node-left-color BLACK); assert(!node-right || node-right-color BLACK); } // 递归校验左右子树的黑节点数 int leftBlack validateNode(node-left); int rightBlack validateNode(node-right); assert(leftBlack rightBlack); // 性质5左右路径黑节点数相等 return leftBlack (node-color BLACK ? 1 : 0); }这个递归函数本身就是一个极好的面试题目。它自底向上统计每条路径的黑色节点数并在任意节点的左右子树之间做一致性检查。关键是只要有一个节点的左右两侧黑节点数不相等整棵树必然不合法。这个断言在每次插入、删除后调用能抓出绝大多数实现错误。我在测试时用的是随机序列加边界序列的组合。边界序列包括顺序插入、逆序插入、全部相等的key、先插后删、先删后插、反复插入删除等。红黑树实现中常见的隐藏Bug比如删除后根节点被错误涂红、迭代器越界、旋转后parent指针错乱在这些组合下基本都能暴露出来。6.2 调试定位的土办法如果断言失败了怎么定位是哪一步操作导致的我个人的经验是不用急着上调试器先在每次插入、删除之后打印整棵树的结构用括号或缩进表示树的层次和颜色一目了然。void printTree(RBNode* node, int depth) { if (!node) return; printTree(node-left, depth 1); for (int i 0; i depth; i) std::cout ; std::cout node-key (node-color RED ? R : B) std::endl; printTree(node-right, depth 1); }别小看这个简单工具。有一次我删除后根节点的颜色变成了红色打印结果里一眼就看出变色逻辑写错了——我把eraseFixUp里最后根节点强制染黑的那一行漏掉了。如果没有可视化打印我可能会在调试器里断点走半天才能发现。7. 常见问题速查我自己踩过的坑和解决思路现象可能原因排查思路插入后根节点变红忘了在insertFixUp末尾强制root涂黑在insertFixUp最后加 root-color BLACK删除后程序崩溃eraseFixUp里访问brother-left时brother为nullptr所有对兄弟节点的孩子访问前先判空中序遍历结果不对旋转操作没有正确维护parent指针做一组旋转前后中序遍历对比插入重复key时被容忍BST插入时只用小于或大于判断没有等于返回逻辑严格小于左走严格大于右走等于直接返回插入失败eraseFixUp无限循环兄弟节点更新后没有把x或parent正确上移对照四种情况逐步打印当前节点判断循环是否推进我在工程实践中还有一个体会红黑树的代码一定要分模块写旋转、插入修复、删除修复各成一个函数不要为了省几次函数调用把逻辑揉在一起。否则一旦出错排查的难度会成倍增加。就算你担心性能也可以在类定义里把这些函数声明为inline让编译器帮你优化。另外提一个面试常问的细节为什么红黑树插入删除的时间复杂度是O(log n)很多人只会背结论。简单来说插入/删除本身是BST查找消耗O(log n)修复过程中无论是变色还是旋转每次最多沿路径向上走一层旋转次数是常数级插入最多2次旋转删除最多3次所以总复杂度还是O(log n)。这个“修复操作次数有常数上界”的特点正是红黑树工程可用的关键所在。8. 从“能跑”到“好用”一点经验补充红黑树写完之后如果你还想再往前一步可以考虑给它加上内存管理的支持。我最初手写的版本new出来的节点没有统一析构测试时只插不删没什么感觉后来做了十万级节点的压力测试才发现内存泄漏。最简单的做法是在析构函数里递归释放左右子树但树深较大时递归调用栈可能溢出更稳妥的做法是层序遍历配合队列来销毁节点。另外我建议你有机会就去读一下STL源码里红黑树的实际实现重点看它是怎么用哨兵节点统一处理空指针的。我自己的工程代码里用的是nullptr版本虽然测试都过了但每次访问颜色前都要判空代码里到处都是分支判断读起来很不优雅。哨兵节点一个固定的黑色NIL节点可以把所有判空逻辑都优化掉它能访问自己的left和right颜色永远是黑色这样红黑树的代码可以从“防崩溃版”升级为“流畅版”逻辑也更加清爽。最后分享一个小技巧如果要在面试中展示手写红黑树不要从节点定义开始写先跟面试官说清楚你的整体结构——节点三叉链、旋转、插入修复、删除修复、迭代器让他知道你在宏观层面是清晰的。然后在写代码时按顺序来别上来就写insertFixUp。清晰的思路比流畅的代码更让面试官认可。