红黑树这个词写过几年C的人多少都听过但真敢说自己彻底搞懂它的人不多。我最早接触它是在啃STL源码的时候当时发现std::map和std::set底层居然不是哈希表而是一棵红黑树心里挺意外——明明哈希查找是O(1)为什么标准库偏要选一棵树后来自己动手实现了一棵红黑树又踩了不少迭代器、比较器相关的坑才算把这件事真正想明白。这篇就把我理解的红黑树以及它在Cmap与set里的具体角色一次讲清楚。适合正在学C、准备面试、或者想深入STL实现原理的读者不需要你数学多好但最好有基本的二叉树概念。1. 红黑树到底解决什么问题1.1 从二叉搜索树的退化说起二叉搜索树BST有个很诱人的特性插入、删除、查找的平均复杂度都是O(log n)而且中序遍历就能得到有序序列。问题在于“平均”这两个字。如果插入的数据本身就有序比如依次插入1, 2, 3, 4, 5BST会退化成一条链表高度变成n查找复杂度直接掉到O(n)。我早期写过一段时间BST上线后遇到一个按时间戳分批导入的场景每次导入都有序结果查询性能肉眼可见地崩了。复盘时才发现树的形状已经歪得不成样子。解决办法是让树在插入删除后自我调整保持左右子树高度大致相当。于是有了平衡树这个家族。平衡树的核心思路很简单不追求绝对平衡而是通过一些局部调整让树的高度始终维持在O(log n)量级。调整的代价不能太大否则插入删除就算省了查找时间也被调整成本吞掉了。红黑树和AVL树都是这个思路下的产物只不过它们对“平衡”的定义不同。1.2 五条性质与“近似平衡”的含义红黑树的平衡不是靠高度差而是靠颜色规则。它有五条经典性质每个节点要么是红色要么是黑色。根节点是黑色。每个叶子节点NIL空节点是黑色。红色节点的两个子节点必须是黑色也就是说不能出现连续的两个红色节点。从任一节点到它的每个叶子节点经过的黑色节点数量相同这个数量叫黑高。第4条和第5条是灵魂。第5条保证了所有路径的黑色节点数一致第4条则限制了红色节点不能连续出现所以一条路径上红色节点最多是黑色节点数量减一。综合下来任意一条路径的长度最多是另一条路径的两倍。这就是“近似平衡”——它不保证左右子树高度差不超过1但保证树的高度不会超过2 log n。对计算机来说2倍和1倍的差距在复杂度上都是O(log n)完全可以接受。我把这五条性质当成红黑树的“物理定律”所有调整动作最终都是为了重新满足这些定律。理解了这一点后面看插入删除修复过程就不会晕。1.3 为什么C标准库选红黑树而不选AVL树AVL树比红黑树更严格它要求任意节点的左右子树高度差不超过1因此AVL树的查找确实会更快一点。但严格是要付出代价的插入和删除时触发旋转的频率远高于红黑树。红黑树因为容忍了“最长路径是最短路径两倍”这种松平衡插入时最多做两次旋转删除时最多做三次旋转变色可以上溯但整体复杂度还是O(log n)。STL里的map和set是给通用场景设计的插入、删除、查找都是重头戏谁也不比谁更常被调用。红黑树是这三者之间的折中查找只比AVL略慢但插入删除的调整成本低得多。C标准本身没有规定必须用什么数据结构实现map只要求插入、删除、查找等操作是对数复杂度且迭代器在插入删除后保持稳定。红黑树刚好满足这些条件。有意思的是主流C标准库实现——libstdc、libc、MSVC STL——最终都选了红黑树这事说明工程选择往往不是选“最优”而是选“综合最不差”。2. 旋转、插入、删除把红黑树的三个核心动作拆开2.1 左旋和右旋只调结构不动顺序旋转是所有平衡树的基本动作。左旋和右旋做的事情本质上是交换局部父子关系同时保证二叉搜索树的顺序性质不被破坏。可以这么理解旋转让你把一棵子树里的某个节点“提上来”另一个节点“降下去”但节点之间的中序顺序完全不变。左旋的具体过程是以某个节点x为轴把它的右孩子y提上来。y的左子树过继给x当右子树x变成y的左孩子。右旋完全对称。很多初学者觉得旋转难其实按三步走就不会乱先处理中间那个“过继”的子树再处理y和x的父子关系最后处理y和x原来父节点的连接。这中间最容易漏的是更新parent指针后面我讲自己实现时会再强调。旋转为什么能把树调平衡因为旋转发生时被提上来的那个节点它的左子树或右子树在结构上被“拆”走了一部分另一侧被补上了。通过把高的一侧往低的一侧转树局部的高度差就缩小了。2.2 插入节点先染红再修复插入新节点时第一步永远是按普通BST的方式找到位置然后把新节点染成红色。为什么是红色因为如果染成黑色会直接破坏第5条性质——某个路径的黑高会多1修复非常麻烦。而新节点是红色只会破坏第4条性质也就是可能出现连续的红色节点修复起来情况少得多。插入修复是沿着新节点向上做的每次看新节点z的父节点和叔叔节点的颜色分成三种情况叔叔是红色把父节点和叔叔节点都染黑把祖父节点染红然后把z上移到祖父节点继续循环。叔叔是黑色且z是右孩子先对父节点左旋把情况转成下一种。叔叔是黑色且z是左孩子父节点染黑祖父节点染红然后对祖父节点右旋。我在纸上画过很多遍这三步发现一个记忆窍门叔叔是红色就只变色、往上走叔叔是黑色就必须旋转。旋转时如果z是“内侧”孩子就先转一次把它变成“外侧”再转一次解决。理解了这个规律代码就好写了。2.3 删除节点最考验耐心的部分删除是红黑树里最劝退的部分。真正删掉的节点在BST里其实是“最多只有一个孩子”的那个节点如果目标节点有两个孩子标准做法是找它的后继节点右子树的最小值来覆盖它的值然后删掉后继节点。所以红黑树删除的核心其实是删除一个“只有一个非NIL孩子或没有孩子”的节点。如果被删除的节点是红色直接删掉就行因为红节点不影响黑高。如果被删除的节点是黑色麻烦就来了——这条路径上少了一个黑节点第5条性质被破坏。修复时我们假设当前节点x“额外带有一层黑色”它可能是黑色也可能变成红色然后通过旋转和变色把这层额外的黑往上推直到遇到一个红节点、或推到根节点。删除修复的分支比插入多一倍核心看兄弟节点的颜色和兄弟节点的子节点颜色大致也是三种情况兄弟是红色对父节点旋转把兄弟变成黑色。兄弟是黑色且兄弟的两个子节点都是黑色兄弟染红把额外黑色上移到父节点。兄弟是黑色且兄弟有红色子节点通过旋转和变色让红色子节点顶上来承担黑色。删除修复最多三次旋转变色可能一路上溯到根但整体还是O(log n)。建议初学者先不要背每一种情况的代码而是把第5条性质放在脑子里每次调整前问自己哪条路径的黑高多了一哪少了调整以后会不会产生连续的红色节点想明白这两句分支再多也乱不了。2.4 为什么插入最多两次旋转、删除最多三次旋转很多人面试被问到这个但说不出本质。插入修复里的旋转只有在叔叔是黑色的时候才会触发这种触发会把局部问题直接解决掉不需要继续上溯。所以整个插入过程中旋转只会发生一到两次剩下的情况都是纯变色加向上走循环次数可能多但旋转次数是常数。删除也类似真正需要旋转的分支都会在旋转后终结循环如果走纯变色分支则问题被上移不会触发额外旋转。这个性质保证了红黑树在插入删除时的常数开销远小于AVL树也是它适合STL这种通用容器的重要原因。3. map与set是如何长在红黑树上的3.1 节点长什么样set存Keymap存pair有的朋友学了红黑树实现再看std::map的接口时会有点懵因为map的每个元素是pairconst Key, T不是单独的Key。实际上红黑树节点里存的东西对set来说是Key本身对map来说是pairconst Key, T。std::set可以理解成一个“只有键没有值”的mapstd::map则是在红黑树节点里多塞了一个T。libstdc里甚至直接把set用_Rb_treeKey, Key, _IdentityKey实现把map用_Rb_treeKey, pairconst Key, T, _Select1stpairconst Key, T实现同一个红黑树模板套了两层皮。这里有个容易被忽略的点map的Key是const的。这意味着你不能通过迭代器修改key只能修改value。这个设计不是随便加的而是红黑树的有序性要求key一旦插入就绝不能变如果key变了树的结构就全乱了。做法上STL直接让key带上const从类型系统层面杜绝了这种错误。3.2 有序遍历和lower_bound红黑树的独特优势哈希表能O(1)查找但给不了你“从小到大遍历”的能力也给不了“找第一个大于等于某个值的元素”这种范围查询。红黑树作为BST中序遍历天然有序。std::map的迭代器本质就是找当前节点的后继如果有右子树就一路向左到最左如果没有右子树就向上找直到某节点是它父节点的左孩子。lower_bound、upper_bound、equal_range这三个接口就是红黑树的BST性质直接提供的。我写业务代码时常需要查“时间戳落在某区间内的所有记录”这时候map.lower_bound(start)和upper_bound(end)配合遍历能非常优雅地把区间拎出来。哈希表完全做不到这一点你得把元素全部排序或者扫一遍。这也是为什么即便有了unordered_map我仍然会在很多场景里坚持用std::map。3.3 insert的返回值与operator[]的秘密std::map::insert返回pairiterator, booliterator指向插入位置或已存在的元素bool表示是否真的插入了。这个设计很实用比如你要维护一个去重队列直接靠返回值判断有没有插入成功不用再查一遍。operator[]则更巧妙。map[k]做的事情是如果k存在返回对应value的引用如果不存在就插入一个用默认构造函数生成的value再返回引用。所以map[hello] 1能成立背后其实是两步如果“hello”不存在先插入pairconst string, int(hello, int{})再赋值为1。这就要求value类型必须能默认构造。如果你的value没有默认构造函数operator[]就编译不过此时该用insert或try_emplace。const map没人用operator[]因为它在key不存在时会插入这对const容器是矛盾的编译阶段就会报错。3.4 迭代器稳定性map和set的隐藏卖点红黑树插入和删除时只修改了局部节点的parent、left、right指针其余节点的内存地址完全不变。这意味着只要你不删除某个迭代器指向的那个元素其他所有迭代器和引用都依然有效。这在写带缓存、带观察者模式的代码时特别有用。比如我维护一个对象注册表外部持有指向元素的迭代器或指针插入新元素完全不影响老元素。换成std::vector插入可能触发扩容所有迭代器全部失效换成std::unordered_maprehash时迭代器也会失效。红黑树这个“稳”的特性是STL选它而不是其他数据结构的又一关键原因。3.5 实际性能对比与选型建议我做过一个简单的评测插入10万个随机整数然后随机查找10万次再按序遍历全部元素。结果大致是容器类型随机插入随机查找有序遍历std::map中等偏慢中等偏慢自然有序std::unordered_map快最快无序需额外排序std::vector sort很快二分查找也快但插入慢需手动排序如果你的操作是纯查找、纯读写而且不需要有序unordered_map是更好的选择。但一旦你需要范围查询、有序遍历、前缀查找这类操作std::map的价值就体现出来了。它比哈希表慢但慢得有限——红黑树的高度大约是2 log n查找一次也就二十多次比较这对绝大多数应用完全够用。很多人的性能焦虑都来自“O(1)优越论”实际工程里数据量没到百万千万级哈希表的cache不友好和rehash抖动反而更难受。4. 从零实现一棵红黑树代码与避坑实录4.1 设计取舍哨兵NIL节点为什么关键自己实现红黑树第一个决定是用nullptr还是用一个哨兵节点表示空叶子。我强烈建议用哨兵NIL。原因有两个第一红黑树第3条性质明确要求所有叶子NIL是黑色如果你用nullptr代码里到处都是判空第二插入删除修复逻辑里大量访问“父节点的父节点”“叔叔节点”如果节点为空访问parent直接崩用NIL可以统一处理空节点。哨兵通常是一个静态的、颜色为黑色的节点left、right、parent都不需要特别初始化因为它本身就是一个终点。所有新节点的left、right、parent都先指向NIL。这样旋转和修复时你不需要每步都判断“这个节点是不是空的”。4.2 核心代码左旋右旋与插入修复节点的定义大概是这样的enum Color { RED, BLACK }; template typename Key, typename Value struct RBNode { Key key; Value value; Color color; RBNode* left; RBNode* right; RBNode* parent; RBNode(const Key k, const Value v) : key(k), value(v), color(RED), left(nullptr), right(nullptr), parent(nullptr) {} };左旋的代码我写过很多遍以后的最终版本void leftRotate(RBNode* root, RBNode* NIL, RBNode* x) { RBNode* y x-right; x-right y-left; if (y-left ! NIL) { y-left-parent x; } y-parent x-parent; if (x-parent NIL) { root y; } else if (x x-parent-left) { x-parent-left y; } else { x-parent-right y; } y-left x; x-parent y; }右旋对称不列了。注意每改一个指针马上更新对应的parent这是避免树断裂的唯一办法。插入修复的关键代码void insertFixup(RBNode* root, RBNode* NIL, RBNode* z) { while (z-parent-color RED) { if (z-parent z-parent-parent-left) { RBNode* y z-parent-parent-right; // 叔叔 if (y-color RED) { z-parent-color BLACK; y-color BLACK; z-parent-parent-color RED; z z-parent-parent; } else { if (z z-parent-right) { z z-parent; leftRotate(root, NIL, z); } z-parent-color BLACK; z-parent-parent-color RED; rightRotate(root, NIL, z-parent-parent); } } else { // 对称分支不再重复 } } root-color BLACK; }这里的while条件用的是z-parent-color RED因为NIL是黑色所以循环一定会在到根时终止。最后把根染黑那一步保证了第2条性质永远成立千万别漏。4.3 删除修复的难点与我的调试方法删除修复比插入更容易踩坑。我碰到过最折磨人的一个bug是在删除后修复循环里把兄弟节点的左孩子和右孩子判断反了导致在某些随机序列下树的结构完全正确但性质检查偶发失败。后来我写了一个校验函数递归检查全部五条性质插入和删除后都跑一遍才在随机测试中抓到它。校验函数的骨架大概是int check(RBNode* n, RBNode* NIL, bool ok) { if (n NIL) return 1; // 空节点黑高为1 if (n-color RED) { if (n-left-color ! BLACK || n-right-color ! BLACK) ok false; } int lh check(n-left, NIL, ok); int rh check(n-right, NIL, ok); if (lh ! rh) ok false; return lh (n-color BLACK ? 1 : 0); }在每次插入删除后调用assert(ok)配合随机数据反复跑是我最推荐的调试策略。这比看断点有效得多因为红黑树的问题往往不是某一处执行错而是某次旋转后一处性质被破坏后续所有操作都跟着错。删除修复里还有一个常见的疏漏被删除节点如果有唯一子节点需要用子节点顶替它但顶替节点的颜色要继承被删节点的颜色否则黑高会变。这个细节忘了树会立刻出问题。4.4 验证红黑树正确性的实用测试我给自己写红黑树定了一条规矩不通过随机压力测试就不算写完。具体做法是先往树里插入10万个随机数每插1000个就快速校验一遍性质然后再随机删除5万个每删1000个再校验一次。同时把插入的元素存入一个std::map作为参照删除时也从参照里删最后把红黑树的中序遍历结果和std::map的遍历结果逐项对比。如果两边完全一致说明我的树在功能上是兼容标准库的。随机测试里要特别加一类数据高度有序的序列比如1到10万正序插入再倒序插入。这类数据是BST退化的重灾区红黑树应该稳定保持高度为O(log n)。如果你的实现能让这组数据的高度不超过40基本可以放心。4.5 不会写在教科书里的几个细节第一个细节是parent指针。很多教材画图只画left和right代码也只显示这两个指针但一旦实现删除和旋转parent指针错误是最隐蔽的因为它不会立刻让程序崩溃只会在后续访问时拿到错误节点。每次旋转后我建议马上检查被旋转的子树的所有节点的parent是否指回正确父节点。第二个细节是颜色默认值。新节点必须默认红色但如果你的节点构造函数忘了初始化颜色在Debug下可能随机得到黑色节点把整棵树搞出“双黑”问题。C的类成员默认不会初始化内建类型这一点特别坑。第三个细节是析构。红黑树节点是用new一个个创建的析构时要后序遍历删除千万不能用递归中序否则先删了父节点子节点就找不到了。我在实现时是先用迭代版后序遍历把节点地址收集到一个vector里再统一delete最简单直接。5. 常见问题与实战排查5.1 自定义比较器写错会导致什么std::map和std::set都要求提供比较器默认是std::lessKey也就是用比较。这个比较器必须满足严格弱序strict weak ordering意思是不能同时a b和b a还要满足传递性。如果比较器写得不满足这个条件红黑树的结构就不可预期可能find永远找不到已经插入的元素或者插入时出现逻辑错误。我踩过的一个实际例子是给一个结构体写比较器时用了多个字段但优先级写反了导致两个不同的key被判定为相等。插入时以为是重复key实际不是查找时明明是存在的数据却返回end。排查起来特别隐蔽因为它不报错只是行为怪异。建议所有自定义比较器都写单元测试至少验证三条自反性comp(a, a)为false、反对称性、传递性。这个功夫不能省。5.2 迭代器失效FAQ很多人会把vector的迭代器失效规则套到map上这是不准确的。map和set的插入不会使任何现有迭代器失效删除时只有指向被删除元素的迭代器失效其他全部有效。这意味着你可以在遍历map时安全地删除非当前元素但不能删除当前元素后继续使用当前迭代器。C11之后erase会返回下一个元素的迭代器所以可以用it m.erase(it)来安全遍历删除。这里还有个经验如果你在一个循环里用迭代器删除元素删除之前最好先把迭代器自增一次或者用erase的返回值不要在删除后还拿旧迭代器做运算。我用这个规则清理过大批过期缓存从来没出过错。5.3 map/set面试题速答面试问红黑树高频问题来来去去就这几个红黑树和AVL树的区别核心是平衡严格度不同红黑树近似平衡旋转少适合插入删除频繁的场景。红黑树的高度上限2 log(n1)这是由黑高和“红色节点不连续”共同推出的。新插入节点为什么是红色为了不破坏黑高把问题限制在“连续红色节点”这个局部矛盾上。插入最多多少次旋转两次。删除最多多少次旋转三次。为什么STL的map不直接用哈希表因为map要求有序、要求迭代器稳定这两个需求哈希表都给不了。回答时不用背定义把“调整目的”说清楚面试官一般就满意了。一定要提性质5黑高相等这是红黑树所有调整的根本指向。5.4 什么时候需要自己写红黑树绝大多数情况下直接用标准库就够了。自己写红黑树的学习价值大于工程价值但有两个工程场景会逼你动手。第一个场景是需要红黑树之外的附加信息比如每个子树的大小。这可以用来实现“按排名查元素”或“第k小”的查询也就是Order Statistic Tree。C标准库没有这个容器但扩展一棵红黑树只需在节点里加一个size字段旋转时顺手更新一下就行。第二个场景是内存受限、想定制节点布局和内存池时。STL的std::map每次插入都会单独分配一个节点如果你的场景需要频繁插入删除分配器开销很大。自己实现时可以预分配节点池把分配器开销压到最低。我在一个实时数据流处理组件里就干过这事用固定大小的节点池替代每次new性能提升非常明显。我个人的体会是红黑树是一棵只要真正手写过一遍就很难再忘掉的树。它不像AVL那样直观但它的每一条设计都在为同一个目标服务在保持有序性的同时把调整成本控制在常数旋转移位范围内。你在C里用得越多map和set就越能体会这棵树的克制与老练。如果这篇能帮你把红黑树从“背五条性质”升级成“理解设计取舍”那我的功夫就没白费。