拓冰网站定制 
先说清楚一个事红黑树这东西不管你是刷题、面试、还是日常工作里排查线上问题迟早是要撞上的。很多同学一听到红黑树三个字就头大觉得它比AVL树复杂得多一堆变色、旋转的规则绕来绕去背了忘、忘了背最后干脆放弃。其实问题不在于红黑树本身难而在于大多数资料一上来就堆性质、贴代码压根没讲清楚它到底在解决什么问题、每一步操作背后在维护什么。我这篇文章不打算给你念教科书而是从为什么需要红黑树开始把它的原理拆开揉碎然后给出一个可以直接照着写的C实现最后把我自己实际写代码时踩过的坑、调试用的工具、以及笔试面试里常见的考察点全部整理出来。目标只有一个看完这篇文章你能自己手写出一棵红黑树并且知道每一行代码是在干嘛。这篇文章适合三类人一是正在学数据结构、准备校招笔试的学生二是需要用红黑树做底层组件开发比如实现定时器、内存管理、自定义容器的工程师三是面试前想快速搞清楚TreeMap、STL map底层逻辑的选手。至于纯刷题党我建议你也认真看因为红黑树的删除操作是我见过最能拉开面试差距的考点没有之一。1. 红黑树到底在平衡什么1.1 从二叉搜索树的偏科说起把一个有序序列插入普通的二叉搜索树BST最坏情况下会退化成链表。比如你按顺序插入1、2、3、4、5树就变成了一根斜线查找复杂度从O(log n)直接劣化到O(n)。这就是BST最大的缺陷查找效率完全取决于插入顺序。解决思路有两个方向。一个方向是AVL树它要求每个节点的左右子树高度差绝对值不超过1。听起来很严格确实也能保证树的平衡但问题在于为了维护这个严格平衡插入和删除时旋转操作极其频繁。另一个方向就是红黑树它放宽了平衡条件不要求严格的高度差而是用最长路径不超过最短路径的两倍这个松散的约束来保证整体复杂度仍然是对数级别。红黑树的高明之处就在这里它用一套染色规则间接约束树的形态换取了更少的旋转次数。在实际场景中插入和删除的频率往往高于查找所以这种牺牲一点查找的绝对平衡、换取整体操作效率的思路在工程上反而是更优的选择。这也解释了为什么C STL的map、Java的TreeMap底层都选红黑树而不是AVL树。1.2 五条性质的真正含义红黑树的五条性质几乎所有教材都会罗列但很少有人告诉你每条性质到底在管什么事节点是红色或黑色——这不是废话是后面一切规则的基础。根节点是黑色——保证树的入口稳定同时配合性质5。所有叶子节点NIL节点是黑色——这里说的是空节点也不是废话。红色节点的两个子节点必须是黑色不能出现连续的红色节点——这条性质本质上是在限制红色节点不能串联间接控制路径上的红节点数量。从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点黑高相等——这是最核心的一条它保证了没有一条路径会比其他路径长一倍以上。把性质4和性质5合起来看你会发现一个关键推论任何一条路径上红色节点数最多等于黑色节点数所以最长路径红黑交替最多是最短路径全黑的两倍。这就是红黑树近似平衡的数学基础。理解了这几条性质之间的关系你就知道为什么插入时默认把新节点染成红色了因为如果插入黑色节点必然会破坏性质5黑高不等而修复黑高不等比修复连续红色节点要麻烦得多。先破坏一条好修的性质4再用旋转和变色去修复这就是整个插入算法的核心逻辑。1.3 和AVL树、B树、跳表的横向对比我在面试里经常被问到红黑树和AVL树的区别这里给一个我常用的对比口径比较维度红黑树AVL树平衡标准最长路径不超过最短路径的2倍左右子树高度差≤1查找性能O(log n)常数稍大O(log n)常数更小插入删除旋转次数少性能更优旋转次数多性能较差适用场景写多读少如STL map、进程调度读多写少如数据库索引的某些场景实现复杂度相对复杂相对简单至于跳表它用概率代替了旋转代码实现比红黑树简单得多Redis的zset就用了跳表。但跳表需要额外的层指针内存占用并不低而且它的性能保证是概率性的不像红黑树是确定性的。在语言标准库里你很少看到用跳表实现的容器因为红黑树的渐进复杂度更稳。2. 插入操作变色和旋转怎么配合2.1 插入的三种基础情况红黑树插入分两步第一步是普通的BST插入把新节点挂到合适的位置第二步是根据父节点和叔叔节点的颜色分情况修复。修复的核心是新节点默认染红这个前提。假设我们插入的节点是z它的父节点是p祖父节点是g叔叔节点是u。只要p是黑色插入直接结束因为红色节点接在黑色节点下面不会违反任何性质。麻烦就麻烦在p也是红色此时出现了连续红色节点必须处理。根据u的颜色分成两大类如果u是红色处理方式是变色p和u都变成黑色g变成红色然后把当前节点上移为g继续循环。这就像把红色往根方向顶了一层原先在g这一层的红黑分布被局部修正了但g可能和它的父节点又形成连续红色所以需要向上递归处理。如果u是黑色处理方式是旋转仔细观察z、p、g的位置关系如果它们是左左或右右的折线关系直接对g做一次单旋转如果是左右或右左的对折关系先对p做一次旋转把它转成直线再对g做一次反方向的单旋转。旋转完成后把g染红、p染黑这个局部子树的黑高就恢复原样了。2.2 为什么插入这么设计一个直觉很多人背插入的流程时很痛苦是因为不理解为什么要分u是红还是黑。我的理解方法很简单叔叔红色说明祖父节点这棵子树还有能力吸收一个红色节点那就局部变色把红色上移叔叔黑色NIL也算黑色说明局部的红色容量已经满了只能用旋转改变树的结构形态让黑色节点下沉。你仔细想想变色操作其实是在不改变树形结构的前提下重新分配红黑颜色而旋转操作是在改变树形结构的前提下来维持黑高。所有的插入问题本质上就是这段红压红的冲突往哪放的问题。先把冲突用变色转移上去遇到不能转移的情况就旋转把形状捋直这个思路贯穿了插入的完全流程。2.3 一个完整的插入示例假设一棵初始只有根节点10的空红黑树我们依次插入5、15、20、12。用之前讲的规则走一遍插入10根节点染黑。插入5父节点10是黑色直接插入染红。插入15父节点10是黑色直接插入染红。插入20父节点15是红色祖父节点10是红色叔叔是5为红色。此时u是红色执行变色5和15变黑10变红然后把当前节点上移到10。10是根节点再把根染黑。一棵新的红黑树就调整好了。插入12父节点15是红色祖父节点10是红色叔叔节点5是黑色。u是黑色且12位于15的左子树而15位于10的右子树属于右左折线情况。先对15做一次右旋变成右右直线再对10做一次左旋。旋转完成后把15染黑、10染红。这个过程你手动在纸上画一遍比看十遍代码都有用。我强烈建议你写代码之前先手工推演两三个这样的例子把旋转方向、变色位置画清楚后面实现的时候才知道自己在写什么。3. 删除操作最难的部分没有之一3.1 删除的底层矛盾删除操作在所有树结构里都比插入难红黑树的删除更是难上加难。难在哪插入时你破坏的是性质4连续红色节点修复思路很直接但删除时你破坏的是性质5黑高相等因为你删掉的很可能是一个黑色节点导致某条路径少了一个黑色节点——这是全局性的问题不是局部变色能解决的。标准的处理方式是双黑double black的概念。当删除一个黑色节点后我们把它的位置标记为双黑也就是说这条路径上欠了一个黑色节点。接下来的修复过程就是通过一系列旋转和变色把这个双黑节点在树里移动最终把它消除。如果删除的是红色节点不需要任何修复因为它不影响黑高。如果删除的黑色节点有一个红色孩子那直接把孩子染黑顶上来就行。真正的困难在于删除的黑色节点两边都是NIL叶子或者两个子树都是空的情况——此时调整路线最长情况也最复杂。3.2 删除的四种修复场景假设被删除的黑色节点的兄弟节点为s父节点为p按s的颜色和s的子节点情况主要有四种修复场景场景一s是红色。此时把s变黑、p变红然后对p做一次旋转使得新的兄弟节点变成黑色。这一步不直接解决问题而是把问题转化成兄弟为黑的场景。场景二s是黑色且s的两个孩子都是黑色。此时把s染红把双黑上移到p。如果p是红色把p染黑就结束了如果p是黑色p变成新的双黑继续向上循环。场景三s是黑色s的左孩子是红色、右孩子是黑色需要针对方向做对称。此时对s做右旋把s和左孩子的颜色互换转换成场景四。场景四s是黑色s的右孩子是红色。此时对p做左旋然后把s的颜色变为p的旧颜色p染黑s的右孩子染黑。到此双黑消除结束。这四个场景我在面试里见过无数版本同学们普遍反应是背了又忘了。我的建议是不要死背而是抓住一个主线所有修复的目的都是让双黑节点能够向上移动直到它遇到一个红色节点把它吸收或者遇到根节点时直接把它变成普通黑色。兄弟节点是红色时我们用旋转把红色兄弟变成黑色孩子兄弟节点和孩子全黑时我们把红色上移兄弟孩子有红色时我们通过旋转重新分配黑色节点一次性结清。3.3 删除的直观理解与调试建议我自己实现删除操作花了整整一个周末。第一次写完代码后对着随机数据跑老是弹出断言失败。后来我用了三招终于把bug清干净第一招是写一个校验函数每次插入和删除操作后都跑一遍五条性质检查把不符合的性质编号打印出来。第二招是生成大量随机数据用STL的map做对照把红黑树实现的结果和标准库map的结果逐项对比。第三招是把树结构可视化打印出来我打印的是带颜色的括号表达式类似(10(B) 5(R) 15(B))这种格式一目了然。删除操作最容易出错的地方是删完节点后忘记维护父节点指针、旋转时忘记把父节点指针改对、NIL节点处理不一致。这些我到后面专门讲实现细节的小节里会一一说明。4. 从零实现完整的C代码与关键细节4.1 节点结构与数据结构定义先把节点的数据结构定义好。我习惯用枚举来区分红黑而不是直接用bool因为我看的时候RED和BLACK比true和false直观得多。节点除了常规的key、left、right非常重要的是要有parent指针而且所有空指针都用一个公共的NIL节点表示而不是直接用nullptr。这是红黑树实现里最重要的一个设计决策。NIL节点必须是黑色的这一点如果处理不好后面校验黑高时百分之百出错。我见过很多人偷懒直接用nullptr结果每个空指针都要特判颜色代码里到处是if (node)的嵌套逻辑混成一团。用哨兵NIL节点的好处是你不需要为空节点没有颜色这种问题做分支处理规则更统一。#include iostream #include vector enum Color { RED, BLACK }; struct Node { int key; Color color; Node* left; Node* right; Node* parent; explicit Node(int k) : key(k), color(RED), left(nullptr), right(nullptr), parent(nullptr) {} }; class RBTree { public: RBTree() : root_(nullptr) {} void insert(int key) { ... } void remove(int key) { ... } bool contains(int key) const { ... } private: Node* root_; // 辅助函数 };很多教材还会搞一个Nil节点统一挂在所有叶子上这个设计更优雅但初学时容易懵。我上面的实现里先用nullptr后面在讲NIL哨兵时再给进阶版本。用nullptr实现也有一个好处你能更直观地理解哪些地方需要判空哪些地方不会为空。4.2 左旋和右旋一切的基石旋转是红黑树所有调整操作的基础。写旋转最经典的坑是指针更新顺序不对导致局部树结构错乱。我先讲左旋右旋就是完全对称的镜像操作。左旋的过程形象地说就是把节点x往左下旋转让它的右孩子y顶替x的位置。具体分四步记录y x-right把y的左子树β挂到x的右子树上。更新β的父节点为x。用y接替x的位置如果x是根节点则把根设为y否则把x父节点的对应子指针指向y。把x挂到y的左子树上更新x的父节点为y。我写旋转时总结了一个铁律只要改了一个节点的指针指向就必须同步更新新子树的父指针。很多人只改了子指针忘了改父指针结果后面往上回溯时就挂了。你可以记住四行口诀先动孙子再动儿子再动爸爸最后动自己。void leftRotate(Node* x) { Node* y x-right; // 1. y的左子树变为x的右子树 x-right y-left; if (y-left ! nullptr) { y-left-parent x; } // 2. y接替x的位置 y-parent x-parent; if (x-parent nullptr) { root_ y; } else if (x x-parent-left) { x-parent-left y; } else { x-parent-right y; } // 3. x变为y的左孩子 y-left x; x-parent y; }右旋就是把右和左、左和右全部对调把上面代码里的left和right互换、把x-right换成x-left其它逻辑完全一样。我强烈建议你把左旋和右旋写在一起同时放在文件相邻位置然后分别用几个小例子测试比如只有两个节点的树左旋和三个节点的链式树左旋确认各种情况下的父指针都指向正确。4.3 插入的实现代码Insert分两步走第一步是普通BST插入第二步是插入后修复。普通插入这段代码不看就能写但有两个点要提醒一是插入完成后一定要设置新节点的左右子树为空、父节点为当前遍历到的位置。二是插入的新节点和已有的key冲突时我这里的实现选择直接返回如果你要支持重复key可以在节点里加一个count字段或者直接把重复的插入到右子树。修复函数里我按之前讲的逻辑来实现。用循环替代递归的好处是即使树的高度很大也不会发生栈溢出的问题而且很多面试手写代码时用循环更容易理清思路。void insert(int key) { Node* z new Node(key); Node* y nullptr; Node* x root_; while (x ! nullptr) { y x; if (z-key x-key) { x x-left; } else if (z-key x-key) { x x-right; } else { delete z; return; } } z-parent y; if (y nullptr) { root_ z; } else if (z-key y-key) { y-left z; } else { y-right z; } insertFixup(z); }关键在insertFixup里void insertFixup(Node* z) { while (z-parent ! nullptr z-parent-color RED) { if (z-parent z-parent-parent-left) { Node* y z-parent-parent-right; // 叔叔 if (y ! nullptr y-color RED) { // case 1: 叔叔是红色变色 z-parent-color BLACK; y-color BLACK; z-parent-parent-color RED; z z-parent-parent; } else { // case 2/3: 叔叔是黑色旋转 if (z z-parent-right) { z z-parent; leftRotate(z); } z-parent-color BLACK; z-parent-parent-color RED; rightRotate(z-parent-parent); } } else { // 对称逻辑镜像处理 Node* y z-parent-parent-left; if (y ! nullptr y-color RED) { z-parent-color BLACK; y-color BLACK; z-parent-parent-color RED; z z-parent-parent; } else { if (z z-parent-left) { z z-parent; rightRotate(z); } z-parent-color BLACK; z-parent-parent-color RED; leftRotate(z-parent-parent); } } } root_-color BLACK; }注意insertFixup函数的入口条件是while循环在z的父节点是红色时持续执行。因为如果父节点是黑色插入红色节点根本不会有问题。循环结束时把根节点染黑这一句不要漏掉因为case1的变色可能导致根节点变成红色。4.4 删除的完整代码transplant与删除主体删除操作要先实现子树替换函数transplant它的作用是把一棵子树替换成另一棵子树。这个函数实现起来不复杂但有一个细节总被人忽略transplant不处理被替换节点的左右子树内容只处理它和父节点的连接关系。也就是说它把v接到u的父节点上然后u就和原来的树断开了。void transplant(Node* u, Node* v) { if (u-parent nullptr) { root_ v; } else if (u u-parent-left) { u-parent-left v; } else { u-parent-right v; } if (v ! nullptr) { v-parent u-parent; } }删除主体函数里要保留几个临时变量需要修复的节点x以及x的父节点xParent。我见过很多简化版实现直接传x进入删除修复函数但修复过程中x的父节点会变所以必须单独保存。完整的删除函数大概是这个骨架void remove(int key) { Node* z search(key); if (z nullptr) return; Node* x; Node* xParent; Color yOriginalColor z-color; if (z-left nullptr) { x z-right; xParent z-parent; transplant(z, z-right); } else if (z-right nullptr) { x z-left; xParent z-parent; transplant(z, z-left); } else { Node* y minimum(z-right); yOriginalColor y-color; x y-right; if (y-parent z) { if (x ! nullptr) x-parent y; xParent y; } else { xParent y-parent; transplant(y, y-right); y-right z-right; y-right-parent y; } transplant(z, y); y-left z-left; y-left-parent y; y-color z-color; } delete z; if (yOriginalColor BLACK) { // 这里需要特别小心x可能为空 removeFixup(x, xParent); } }上面代码里我专门区分了xParent这个变量。原因很简单当z只有一边子树时transplant之后x的父节点就是z的父节点没问题但当z有两个子树且后继y不是z的直接右孩子时调整完x的父节点已经变化了所以绝不能只靠x-parent来定位。这个细节我在写第一版代码时裁过跟头查了整整半天。删除修复函数removeFixup的完整实现长得像这样它的参数需要x和xParent两个值因为x可能是nullptrvoid removeFixup(Node* x, Node* xParent) { while (x ! root_ (x nullptr || x-color BLACK)) { if (x xParent-left) { Node* w xParent-right; if (w-color RED) { w-color BLACK; xParent-color RED; leftRotate(xParent); w xParent-right; } if ((w-left nullptr || w-left-color BLACK) (w-right nullptr || w-right-color BLACK)) { w-color RED; x xParent; xParent x-parent; } else { if (w-right nullptr || w-right-color BLACK) { if (w-left ! nullptr) { w-left-color BLACK; } w-color RED; rightRotate(w); w xParent-right; } w-color xParent-color; xParent-color BLACK; if (w-right ! nullptr) { w-right-color BLACK; } leftRotate(xParent); x root_; } } else { // 对称逻辑 } } if (x ! nullptr) { x-color BLACK; } }删除修复里最烦人的一个问题是x是nullptr时还要不要处理颜色答案是要。因为x已经是空节点了它代表原删除位置的那条路径少了一个黑色节点这个双黑状态还在所以修复的一开始就需要知道x的父节点是xParent。如果x非空且颜色为红那直接把x染黑就结束了这也是while循环条件把x为nullptr或黑色作为继续循环依据的原因。这里有个小技巧循环结束后把x染黑但如果x是nullptr染不染不重要反正没有实际节点但如果你用了NIL哨兵节点则是把NIL染黑。4.5 坚持写校验函数你会省下一天时间写完插入和删除之后不要急着提交代码测试先写一个validate函数。这个函数做四件事检查根节点是黑色。检查每个红色节点的两个孩子都是黑色排除空节点。计算从根到每个叶子的黑色节点数确保相等。检查整棵树的父指针一致性保证没有悬空指针。我把这个函数写成返回bool并且把违反的性质编号作为输出参数带出来。测试时每执行一次插入或删除就调用一次validate一旦失败立刻打印关键信息并终止。bool validate() const { Node* blackHeight nullptr; return validateFrom(root_, blackHeight, 0); } bool validateFrom(Node* node, Node* blackHeight, int blackCount) const { if (node nullptr) { if (blackHeight nullptr) { blackHeight node; return true; } return blackCount blackHeight; } if (node-color RED) { if ((node-left node-left-color RED) || (node-right node-right-color RED)) { return false; } } int nextBlackCount blackCount (node-color BLACK ? 1 : 0); return validateFrom(node-left, blackHeight, nextBlackCount) validateFrom(node-right, blackHeight, nextBlackCount); }5. 实际应用场景与变种扩展5.1 STL map/set与Linux内核的定时器STL的std::map和std::set底层实现就是红黑树。你在C代码里天天用的map它的增删改查、迭代器自增自减全部依赖红黑树的节点结构和旋转操作。你注意到一个现象没有map的迭代器遍历是有序的这就是BST的左根右遍历特性而map的insert不会使已有迭代器失效这也是红黑树作为链式结构的一大优势。Linux内核里也有红黑树的身影最有名的就是CFS调度器和epoll。CFS用红黑树来管理就绪队列每个进程的虚拟运行时间作为key调度器每次取出最左边的节点就是下一个要运行的进程。epoll用红黑树来管理被监视的文件描述符增删O(log n)满足高并发场景的要求。你在Linux下写高性能网络编程多多少少都会间接接触到红黑树。5.2 TreeMap、TreeSet与并发容器Java的TreeMap和TreeSet也同样基于红黑树。Java里红黑树的实现比STL更原生化节点里没有parent指针的而是把节点包装成Entry用内部类持有左右孩子和父节点引用。Java 8以后HashMap在单个桶内元素超过8个时会把链表转成红黑树结构这也是红黑树在工程里的一个经典变体应用。如果你去读TreeMap的源码会发现它注释里写得很清楚插入删除的修复逻辑和CLRS教材完全一致只是多了对comparator的支持。阅读这些源码时我的建议是先读插入部分跳过删除等工作几年后有了更多实战经验再回头啃删除会轻松很多。5.3 红黑树的常见变种LLRB树和B树左倾红黑树LLRB树是Robert Sedgewick提出的一个变种它把3-node映射为红色左倾子节点实现起来代码量更少因为只需要处理左孩子是红色的情况旋转只有左旋。很多教学场景用LLRB树来简化红黑树的讲解但它和标准红黑树并不完全等价有些工程问题里标准红黑树更合适所以不要把LLRB当作标准。B树和红黑树的联系也很有意思。从某种意义上说红黑树和4阶B树2-3-4树是等价的。你可以把一个红色节点想象成它和父节点共同组成B树里的一个多键节点。理解了这层关系红黑树的很多旋转规则就会变得非常自然——本质上是在维持一个4阶B树的结构。对这方面感兴趣的话可以去看算法导论第三版的第18章和13章对照阅读。6. 面试里的高频考点与避开套路的技巧6.1 手写代码的高频考点和答题节奏面试里考察红黑树最常见的三种形式是让你完整手写插入和删除这种偏难面试官想看你慌不慌让你讲清楚插入修复的几种case这种偏多让你对比红黑树和AVL树并说明工程选型理由这种最简单。关于手写我有一个比较实用的答题顺序建议。第一先和面试官确认使用什么语言以及是否需要支持重复key。第二先实现搜索和插入把插入调通以后腾出时间实现删除。第三删除的时候先讲清楚思路比如删除黑色节点产生双黑我按兄弟的情况分类处理即便代码没写完思路清晰也是加分项。千万不要一上来就背代码。面试官最反感的是背题选手你背得再流畅他换个问法你就露馅。最好是边写边注释把每个case的触发条件写清楚展示你是真的理解了机制。6.2 常被追问的五个边界问题空树插入第一个元素时为什么根是黑色——因为性质2要求根节点必须是黑色。插入的新节点为什么默认红色——避免破坏性质5否则调整成本更高。NIL节点算不算叶子节点——性质3明确规定了NIL节点是黑色而在实际实现里空指针也算黑色。删除后x是nullptr还要修复吗——要因为你删除的是黑节点修复是针对路径少黑这件事而不是针对某个具体节点。红黑树能保证O(log n)的查找吗——能。因为最长路径不超过最短路径的2倍所以树的高度的最坏值是2*log2(n1)。这些问题我在面试别人的时候都会问也是我当年被问过的。你说不定会在哪个面试里碰到同款提前想好怎么答别临时组织语言。6.3 写在最后的调试技巧调试红黑树最重要的是可视化。我自己的做法是写一个printTree函数用类似(key,color)的嵌套括号输出整棵树。比如一棵包含10、5、15、12的红黑树输出会是(10,B) (5,R) () () (15,R) (12,B) () () ()每个节点后面跟着它的颜色空子树用()表示。这样每次操作完打印出来配合validate函数的校验结果就能快速定位问题出在旋转方向、父亲指针更新还是颜色赋值。实测下来这个可视化断言校验随机对照的三件套组合比任何调试器都好用因为红黑树的错误往往要经过多次旋转后才暴露断点很难盯住。最后一件事不管你是用STL的map做对照测试还是自己跑十万级随机数据一定要把校验函数开启。当年我写删除操作时经常一跑就崩后来开了validate才发现某几种场景下旋转完父指针没更新。把校验开着错误会在第一时间暴露而不是在几万次操作后神秘崩溃。相信我这个习惯会让你省下大把时间。 红黑树原理详解与C++实现：从变色旋转到STL工程应用
先说清楚一个事红黑树这东西不管你是刷题、面试、还是日常工作里排查线上问题迟早是要撞上的。很多同学一听到红黑树三个字就头大觉得它比AVL树复杂得多一堆变色、旋转的规则绕来绕去背了忘、忘了背最后干脆放弃。其实问题不在于红黑树本身难而在于大多数资料一上来就堆性质、贴代码压根没讲清楚它到底在解决什么问题、每一步操作背后在维护什么。我这篇文章不打算给你念教科书而是从为什么需要红黑树开始把它的原理拆开揉碎然后给出一个可以直接照着写的C实现最后把我自己实际写代码时踩过的坑、调试用的工具、以及笔试面试里常见的考察点全部整理出来。目标只有一个看完这篇文章你能自己手写出一棵红黑树并且知道每一行代码是在干嘛。这篇文章适合三类人一是正在学数据结构、准备校招笔试的学生二是需要用红黑树做底层组件开发比如实现定时器、内存管理、自定义容器的工程师三是面试前想快速搞清楚TreeMap、STL map底层逻辑的选手。至于纯刷题党我建议你也认真看因为红黑树的删除操作是我见过最能拉开面试差距的考点没有之一。1. 红黑树到底在平衡什么1.1 从二叉搜索树的偏科说起把一个有序序列插入普通的二叉搜索树BST最坏情况下会退化成链表。比如你按顺序插入1、2、3、4、5树就变成了一根斜线查找复杂度从O(log n)直接劣化到O(n)。这就是BST最大的缺陷查找效率完全取决于插入顺序。解决思路有两个方向。一个方向是AVL树它要求每个节点的左右子树高度差绝对值不超过1。听起来很严格确实也能保证树的平衡但问题在于为了维护这个严格平衡插入和删除时旋转操作极其频繁。另一个方向就是红黑树它放宽了平衡条件不要求严格的高度差而是用最长路径不超过最短路径的两倍这个松散的约束来保证整体复杂度仍然是对数级别。红黑树的高明之处就在这里它用一套染色规则间接约束树的形态换取了更少的旋转次数。在实际场景中插入和删除的频率往往高于查找所以这种牺牲一点查找的绝对平衡、换取整体操作效率的思路在工程上反而是更优的选择。这也解释了为什么C STL的map、Java的TreeMap底层都选红黑树而不是AVL树。1.2 五条性质的真正含义红黑树的五条性质几乎所有教材都会罗列但很少有人告诉你每条性质到底在管什么事节点是红色或黑色——这不是废话是后面一切规则的基础。根节点是黑色——保证树的入口稳定同时配合性质5。所有叶子节点NIL节点是黑色——这里说的是空节点也不是废话。红色节点的两个子节点必须是黑色不能出现连续的红色节点——这条性质本质上是在限制红色节点不能串联间接控制路径上的红节点数量。从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点黑高相等——这是最核心的一条它保证了没有一条路径会比其他路径长一倍以上。把性质4和性质5合起来看你会发现一个关键推论任何一条路径上红色节点数最多等于黑色节点数所以最长路径红黑交替最多是最短路径全黑的两倍。这就是红黑树近似平衡的数学基础。理解了这几条性质之间的关系你就知道为什么插入时默认把新节点染成红色了因为如果插入黑色节点必然会破坏性质5黑高不等而修复黑高不等比修复连续红色节点要麻烦得多。先破坏一条好修的性质4再用旋转和变色去修复这就是整个插入算法的核心逻辑。1.3 和AVL树、B树、跳表的横向对比我在面试里经常被问到红黑树和AVL树的区别这里给一个我常用的对比口径比较维度红黑树AVL树平衡标准最长路径不超过最短路径的2倍左右子树高度差≤1查找性能O(log n)常数稍大O(log n)常数更小插入删除旋转次数少性能更优旋转次数多性能较差适用场景写多读少如STL map、进程调度读多写少如数据库索引的某些场景实现复杂度相对复杂相对简单至于跳表它用概率代替了旋转代码实现比红黑树简单得多Redis的zset就用了跳表。但跳表需要额外的层指针内存占用并不低而且它的性能保证是概率性的不像红黑树是确定性的。在语言标准库里你很少看到用跳表实现的容器因为红黑树的渐进复杂度更稳。2. 插入操作变色和旋转怎么配合2.1 插入的三种基础情况红黑树插入分两步第一步是普通的BST插入把新节点挂到合适的位置第二步是根据父节点和叔叔节点的颜色分情况修复。修复的核心是新节点默认染红这个前提。假设我们插入的节点是z它的父节点是p祖父节点是g叔叔节点是u。只要p是黑色插入直接结束因为红色节点接在黑色节点下面不会违反任何性质。麻烦就麻烦在p也是红色此时出现了连续红色节点必须处理。根据u的颜色分成两大类如果u是红色处理方式是变色p和u都变成黑色g变成红色然后把当前节点上移为g继续循环。这就像把红色往根方向顶了一层原先在g这一层的红黑分布被局部修正了但g可能和它的父节点又形成连续红色所以需要向上递归处理。如果u是黑色处理方式是旋转仔细观察z、p、g的位置关系如果它们是左左或右右的折线关系直接对g做一次单旋转如果是左右或右左的对折关系先对p做一次旋转把它转成直线再对g做一次反方向的单旋转。旋转完成后把g染红、p染黑这个局部子树的黑高就恢复原样了。2.2 为什么插入这么设计一个直觉很多人背插入的流程时很痛苦是因为不理解为什么要分u是红还是黑。我的理解方法很简单叔叔红色说明祖父节点这棵子树还有能力吸收一个红色节点那就局部变色把红色上移叔叔黑色NIL也算黑色说明局部的红色容量已经满了只能用旋转改变树的结构形态让黑色节点下沉。你仔细想想变色操作其实是在不改变树形结构的前提下重新分配红黑颜色而旋转操作是在改变树形结构的前提下来维持黑高。所有的插入问题本质上就是这段红压红的冲突往哪放的问题。先把冲突用变色转移上去遇到不能转移的情况就旋转把形状捋直这个思路贯穿了插入的完全流程。2.3 一个完整的插入示例假设一棵初始只有根节点10的空红黑树我们依次插入5、15、20、12。用之前讲的规则走一遍插入10根节点染黑。插入5父节点10是黑色直接插入染红。插入15父节点10是黑色直接插入染红。插入20父节点15是红色祖父节点10是红色叔叔是5为红色。此时u是红色执行变色5和15变黑10变红然后把当前节点上移到10。10是根节点再把根染黑。一棵新的红黑树就调整好了。插入12父节点15是红色祖父节点10是红色叔叔节点5是黑色。u是黑色且12位于15的左子树而15位于10的右子树属于右左折线情况。先对15做一次右旋变成右右直线再对10做一次左旋。旋转完成后把15染黑、10染红。这个过程你手动在纸上画一遍比看十遍代码都有用。我强烈建议你写代码之前先手工推演两三个这样的例子把旋转方向、变色位置画清楚后面实现的时候才知道自己在写什么。3. 删除操作最难的部分没有之一3.1 删除的底层矛盾删除操作在所有树结构里都比插入难红黑树的删除更是难上加难。难在哪插入时你破坏的是性质4连续红色节点修复思路很直接但删除时你破坏的是性质5黑高相等因为你删掉的很可能是一个黑色节点导致某条路径少了一个黑色节点——这是全局性的问题不是局部变色能解决的。标准的处理方式是双黑double black的概念。当删除一个黑色节点后我们把它的位置标记为双黑也就是说这条路径上欠了一个黑色节点。接下来的修复过程就是通过一系列旋转和变色把这个双黑节点在树里移动最终把它消除。如果删除的是红色节点不需要任何修复因为它不影响黑高。如果删除的黑色节点有一个红色孩子那直接把孩子染黑顶上来就行。真正的困难在于删除的黑色节点两边都是NIL叶子或者两个子树都是空的情况——此时调整路线最长情况也最复杂。3.2 删除的四种修复场景假设被删除的黑色节点的兄弟节点为s父节点为p按s的颜色和s的子节点情况主要有四种修复场景场景一s是红色。此时把s变黑、p变红然后对p做一次旋转使得新的兄弟节点变成黑色。这一步不直接解决问题而是把问题转化成兄弟为黑的场景。场景二s是黑色且s的两个孩子都是黑色。此时把s染红把双黑上移到p。如果p是红色把p染黑就结束了如果p是黑色p变成新的双黑继续向上循环。场景三s是黑色s的左孩子是红色、右孩子是黑色需要针对方向做对称。此时对s做右旋把s和左孩子的颜色互换转换成场景四。场景四s是黑色s的右孩子是红色。此时对p做左旋然后把s的颜色变为p的旧颜色p染黑s的右孩子染黑。到此双黑消除结束。这四个场景我在面试里见过无数版本同学们普遍反应是背了又忘了。我的建议是不要死背而是抓住一个主线所有修复的目的都是让双黑节点能够向上移动直到它遇到一个红色节点把它吸收或者遇到根节点时直接把它变成普通黑色。兄弟节点是红色时我们用旋转把红色兄弟变成黑色孩子兄弟节点和孩子全黑时我们把红色上移兄弟孩子有红色时我们通过旋转重新分配黑色节点一次性结清。3.3 删除的直观理解与调试建议我自己实现删除操作花了整整一个周末。第一次写完代码后对着随机数据跑老是弹出断言失败。后来我用了三招终于把bug清干净第一招是写一个校验函数每次插入和删除操作后都跑一遍五条性质检查把不符合的性质编号打印出来。第二招是生成大量随机数据用STL的map做对照把红黑树实现的结果和标准库map的结果逐项对比。第三招是把树结构可视化打印出来我打印的是带颜色的括号表达式类似(10(B) 5(R) 15(B))这种格式一目了然。删除操作最容易出错的地方是删完节点后忘记维护父节点指针、旋转时忘记把父节点指针改对、NIL节点处理不一致。这些我到后面专门讲实现细节的小节里会一一说明。4. 从零实现完整的C代码与关键细节4.1 节点结构与数据结构定义先把节点的数据结构定义好。我习惯用枚举来区分红黑而不是直接用bool因为我看的时候RED和BLACK比true和false直观得多。节点除了常规的key、left、right非常重要的是要有parent指针而且所有空指针都用一个公共的NIL节点表示而不是直接用nullptr。这是红黑树实现里最重要的一个设计决策。NIL节点必须是黑色的这一点如果处理不好后面校验黑高时百分之百出错。我见过很多人偷懒直接用nullptr结果每个空指针都要特判颜色代码里到处是if (node)的嵌套逻辑混成一团。用哨兵NIL节点的好处是你不需要为空节点没有颜色这种问题做分支处理规则更统一。#include iostream #include vector enum Color { RED, BLACK }; struct Node { int key; Color color; Node* left; Node* right; Node* parent; explicit Node(int k) : key(k), color(RED), left(nullptr), right(nullptr), parent(nullptr) {} }; class RBTree { public: RBTree() : root_(nullptr) {} void insert(int key) { ... } void remove(int key) { ... } bool contains(int key) const { ... } private: Node* root_; // 辅助函数 };很多教材还会搞一个Nil节点统一挂在所有叶子上这个设计更优雅但初学时容易懵。我上面的实现里先用nullptr后面在讲NIL哨兵时再给进阶版本。用nullptr实现也有一个好处你能更直观地理解哪些地方需要判空哪些地方不会为空。4.2 左旋和右旋一切的基石旋转是红黑树所有调整操作的基础。写旋转最经典的坑是指针更新顺序不对导致局部树结构错乱。我先讲左旋右旋就是完全对称的镜像操作。左旋的过程形象地说就是把节点x往左下旋转让它的右孩子y顶替x的位置。具体分四步记录y x-right把y的左子树β挂到x的右子树上。更新β的父节点为x。用y接替x的位置如果x是根节点则把根设为y否则把x父节点的对应子指针指向y。把x挂到y的左子树上更新x的父节点为y。我写旋转时总结了一个铁律只要改了一个节点的指针指向就必须同步更新新子树的父指针。很多人只改了子指针忘了改父指针结果后面往上回溯时就挂了。你可以记住四行口诀先动孙子再动儿子再动爸爸最后动自己。void leftRotate(Node* x) { Node* y x-right; // 1. y的左子树变为x的右子树 x-right y-left; if (y-left ! nullptr) { y-left-parent x; } // 2. y接替x的位置 y-parent x-parent; if (x-parent nullptr) { root_ y; } else if (x x-parent-left) { x-parent-left y; } else { x-parent-right y; } // 3. x变为y的左孩子 y-left x; x-parent y; }右旋就是把右和左、左和右全部对调把上面代码里的left和right互换、把x-right换成x-left其它逻辑完全一样。我强烈建议你把左旋和右旋写在一起同时放在文件相邻位置然后分别用几个小例子测试比如只有两个节点的树左旋和三个节点的链式树左旋确认各种情况下的父指针都指向正确。4.3 插入的实现代码Insert分两步走第一步是普通BST插入第二步是插入后修复。普通插入这段代码不看就能写但有两个点要提醒一是插入完成后一定要设置新节点的左右子树为空、父节点为当前遍历到的位置。二是插入的新节点和已有的key冲突时我这里的实现选择直接返回如果你要支持重复key可以在节点里加一个count字段或者直接把重复的插入到右子树。修复函数里我按之前讲的逻辑来实现。用循环替代递归的好处是即使树的高度很大也不会发生栈溢出的问题而且很多面试手写代码时用循环更容易理清思路。void insert(int key) { Node* z new Node(key); Node* y nullptr; Node* x root_; while (x ! nullptr) { y x; if (z-key x-key) { x x-left; } else if (z-key x-key) { x x-right; } else { delete z; return; } } z-parent y; if (y nullptr) { root_ z; } else if (z-key y-key) { y-left z; } else { y-right z; } insertFixup(z); }关键在insertFixup里void insertFixup(Node* z) { while (z-parent ! nullptr z-parent-color RED) { if (z-parent z-parent-parent-left) { Node* y z-parent-parent-right; // 叔叔 if (y ! nullptr y-color RED) { // case 1: 叔叔是红色变色 z-parent-color BLACK; y-color BLACK; z-parent-parent-color RED; z z-parent-parent; } else { // case 2/3: 叔叔是黑色旋转 if (z z-parent-right) { z z-parent; leftRotate(z); } z-parent-color BLACK; z-parent-parent-color RED; rightRotate(z-parent-parent); } } else { // 对称逻辑镜像处理 Node* y z-parent-parent-left; if (y ! nullptr y-color RED) { z-parent-color BLACK; y-color BLACK; z-parent-parent-color RED; z z-parent-parent; } else { if (z z-parent-left) { z z-parent; rightRotate(z); } z-parent-color BLACK; z-parent-parent-color RED; leftRotate(z-parent-parent); } } } root_-color BLACK; }注意insertFixup函数的入口条件是while循环在z的父节点是红色时持续执行。因为如果父节点是黑色插入红色节点根本不会有问题。循环结束时把根节点染黑这一句不要漏掉因为case1的变色可能导致根节点变成红色。4.4 删除的完整代码transplant与删除主体删除操作要先实现子树替换函数transplant它的作用是把一棵子树替换成另一棵子树。这个函数实现起来不复杂但有一个细节总被人忽略transplant不处理被替换节点的左右子树内容只处理它和父节点的连接关系。也就是说它把v接到u的父节点上然后u就和原来的树断开了。void transplant(Node* u, Node* v) { if (u-parent nullptr) { root_ v; } else if (u u-parent-left) { u-parent-left v; } else { u-parent-right v; } if (v ! nullptr) { v-parent u-parent; } }删除主体函数里要保留几个临时变量需要修复的节点x以及x的父节点xParent。我见过很多简化版实现直接传x进入删除修复函数但修复过程中x的父节点会变所以必须单独保存。完整的删除函数大概是这个骨架void remove(int key) { Node* z search(key); if (z nullptr) return; Node* x; Node* xParent; Color yOriginalColor z-color; if (z-left nullptr) { x z-right; xParent z-parent; transplant(z, z-right); } else if (z-right nullptr) { x z-left; xParent z-parent; transplant(z, z-left); } else { Node* y minimum(z-right); yOriginalColor y-color; x y-right; if (y-parent z) { if (x ! nullptr) x-parent y; xParent y; } else { xParent y-parent; transplant(y, y-right); y-right z-right; y-right-parent y; } transplant(z, y); y-left z-left; y-left-parent y; y-color z-color; } delete z; if (yOriginalColor BLACK) { // 这里需要特别小心x可能为空 removeFixup(x, xParent); } }上面代码里我专门区分了xParent这个变量。原因很简单当z只有一边子树时transplant之后x的父节点就是z的父节点没问题但当z有两个子树且后继y不是z的直接右孩子时调整完x的父节点已经变化了所以绝不能只靠x-parent来定位。这个细节我在写第一版代码时裁过跟头查了整整半天。删除修复函数removeFixup的完整实现长得像这样它的参数需要x和xParent两个值因为x可能是nullptrvoid removeFixup(Node* x, Node* xParent) { while (x ! root_ (x nullptr || x-color BLACK)) { if (x xParent-left) { Node* w xParent-right; if (w-color RED) { w-color BLACK; xParent-color RED; leftRotate(xParent); w xParent-right; } if ((w-left nullptr || w-left-color BLACK) (w-right nullptr || w-right-color BLACK)) { w-color RED; x xParent; xParent x-parent; } else { if (w-right nullptr || w-right-color BLACK) { if (w-left ! nullptr) { w-left-color BLACK; } w-color RED; rightRotate(w); w xParent-right; } w-color xParent-color; xParent-color BLACK; if (w-right ! nullptr) { w-right-color BLACK; } leftRotate(xParent); x root_; } } else { // 对称逻辑 } } if (x ! nullptr) { x-color BLACK; } }删除修复里最烦人的一个问题是x是nullptr时还要不要处理颜色答案是要。因为x已经是空节点了它代表原删除位置的那条路径少了一个黑色节点这个双黑状态还在所以修复的一开始就需要知道x的父节点是xParent。如果x非空且颜色为红那直接把x染黑就结束了这也是while循环条件把x为nullptr或黑色作为继续循环依据的原因。这里有个小技巧循环结束后把x染黑但如果x是nullptr染不染不重要反正没有实际节点但如果你用了NIL哨兵节点则是把NIL染黑。4.5 坚持写校验函数你会省下一天时间写完插入和删除之后不要急着提交代码测试先写一个validate函数。这个函数做四件事检查根节点是黑色。检查每个红色节点的两个孩子都是黑色排除空节点。计算从根到每个叶子的黑色节点数确保相等。检查整棵树的父指针一致性保证没有悬空指针。我把这个函数写成返回bool并且把违反的性质编号作为输出参数带出来。测试时每执行一次插入或删除就调用一次validate一旦失败立刻打印关键信息并终止。bool validate() const { Node* blackHeight nullptr; return validateFrom(root_, blackHeight, 0); } bool validateFrom(Node* node, Node* blackHeight, int blackCount) const { if (node nullptr) { if (blackHeight nullptr) { blackHeight node; return true; } return blackCount blackHeight; } if (node-color RED) { if ((node-left node-left-color RED) || (node-right node-right-color RED)) { return false; } } int nextBlackCount blackCount (node-color BLACK ? 1 : 0); return validateFrom(node-left, blackHeight, nextBlackCount) validateFrom(node-right, blackHeight, nextBlackCount); }5. 实际应用场景与变种扩展5.1 STL map/set与Linux内核的定时器STL的std::map和std::set底层实现就是红黑树。你在C代码里天天用的map它的增删改查、迭代器自增自减全部依赖红黑树的节点结构和旋转操作。你注意到一个现象没有map的迭代器遍历是有序的这就是BST的左根右遍历特性而map的insert不会使已有迭代器失效这也是红黑树作为链式结构的一大优势。Linux内核里也有红黑树的身影最有名的就是CFS调度器和epoll。CFS用红黑树来管理就绪队列每个进程的虚拟运行时间作为key调度器每次取出最左边的节点就是下一个要运行的进程。epoll用红黑树来管理被监视的文件描述符增删O(log n)满足高并发场景的要求。你在Linux下写高性能网络编程多多少少都会间接接触到红黑树。5.2 TreeMap、TreeSet与并发容器Java的TreeMap和TreeSet也同样基于红黑树。Java里红黑树的实现比STL更原生化节点里没有parent指针的而是把节点包装成Entry用内部类持有左右孩子和父节点引用。Java 8以后HashMap在单个桶内元素超过8个时会把链表转成红黑树结构这也是红黑树在工程里的一个经典变体应用。如果你去读TreeMap的源码会发现它注释里写得很清楚插入删除的修复逻辑和CLRS教材完全一致只是多了对comparator的支持。阅读这些源码时我的建议是先读插入部分跳过删除等工作几年后有了更多实战经验再回头啃删除会轻松很多。5.3 红黑树的常见变种LLRB树和B树左倾红黑树LLRB树是Robert Sedgewick提出的一个变种它把3-node映射为红色左倾子节点实现起来代码量更少因为只需要处理左孩子是红色的情况旋转只有左旋。很多教学场景用LLRB树来简化红黑树的讲解但它和标准红黑树并不完全等价有些工程问题里标准红黑树更合适所以不要把LLRB当作标准。B树和红黑树的联系也很有意思。从某种意义上说红黑树和4阶B树2-3-4树是等价的。你可以把一个红色节点想象成它和父节点共同组成B树里的一个多键节点。理解了这层关系红黑树的很多旋转规则就会变得非常自然——本质上是在维持一个4阶B树的结构。对这方面感兴趣的话可以去看算法导论第三版的第18章和13章对照阅读。6. 面试里的高频考点与避开套路的技巧6.1 手写代码的高频考点和答题节奏面试里考察红黑树最常见的三种形式是让你完整手写插入和删除这种偏难面试官想看你慌不慌让你讲清楚插入修复的几种case这种偏多让你对比红黑树和AVL树并说明工程选型理由这种最简单。关于手写我有一个比较实用的答题顺序建议。第一先和面试官确认使用什么语言以及是否需要支持重复key。第二先实现搜索和插入把插入调通以后腾出时间实现删除。第三删除的时候先讲清楚思路比如删除黑色节点产生双黑我按兄弟的情况分类处理即便代码没写完思路清晰也是加分项。千万不要一上来就背代码。面试官最反感的是背题选手你背得再流畅他换个问法你就露馅。最好是边写边注释把每个case的触发条件写清楚展示你是真的理解了机制。6.2 常被追问的五个边界问题空树插入第一个元素时为什么根是黑色——因为性质2要求根节点必须是黑色。插入的新节点为什么默认红色——避免破坏性质5否则调整成本更高。NIL节点算不算叶子节点——性质3明确规定了NIL节点是黑色而在实际实现里空指针也算黑色。删除后x是nullptr还要修复吗——要因为你删除的是黑节点修复是针对路径少黑这件事而不是针对某个具体节点。红黑树能保证O(log n)的查找吗——能。因为最长路径不超过最短路径的2倍所以树的高度的最坏值是2*log2(n1)。这些问题我在面试别人的时候都会问也是我当年被问过的。你说不定会在哪个面试里碰到同款提前想好怎么答别临时组织语言。6.3 写在最后的调试技巧调试红黑树最重要的是可视化。我自己的做法是写一个printTree函数用类似(key,color)的嵌套括号输出整棵树。比如一棵包含10、5、15、12的红黑树输出会是(10,B) (5,R) () () (15,R) (12,B) () () ()每个节点后面跟着它的颜色空子树用()表示。这样每次操作完打印出来配合validate函数的校验结果就能快速定位问题出在旋转方向、父亲指针更新还是颜色赋值。实测下来这个可视化断言校验随机对照的三件套组合比任何调试器都好用因为红黑树的错误往往要经过多次旋转后才暴露断点很难盯住。最后一件事不管你是用STL的map做对照测试还是自己跑十万级随机数据一定要把校验函数开启。当年我写删除操作时经常一跑就崩后来开了validate才发现某几种场景下旋转完父指针没更新。把校验开着错误会在第一时间暴露而不是在几万次操作后神秘崩溃。相信我这个习惯会让你省下大把时间。