C++红黑树从原理到实现：平衡二叉树为何默认是它？-开发者社区

在C++里提到平衡二叉树，十有八九指的并不是AVL树，而是红黑树。不管你是用std::map、std::set还是std::multiset，底层容器都是同一棵红黑树。我最早真正读红黑树源码，是翻开源STL的rb_tree，第一感觉就是：这堆旋转和染色到底有什么规律？后来把插入、删除的全部分支画出来逐个验证，才明白为什么面试和技术讨论里总把红黑树当作平衡二叉树的“默认代表”。

这篇文章我会完全站在动手实现的角度，先把红黑树的性质讲透，然后给出一个用C++实现的简化版红黑树，重点拆解插入修复和删除修复这两块核心逻辑，最后分享我实际踩过的坑以及自检方法。如果你准备手写一棵红黑树、准备面试，或者只是想知道STL里的map/set为什么这么快，这篇内容都适合你。

1. 先聊清楚：为什么平衡二叉树在C++里几乎等于红黑树

1.1 二叉查找树为什么需要“平衡”

普通的二叉查找树实现起来很简单，插入、搜索、删除平均复杂度都是O(log n)。但“平均”这两个字非常狡猾，当数据有序插入时，树会自动退化成一个单链表，比如依次插入1、2、3、4、5，树就变成一条右斜线。这时候搜索一个节点要从头一路找到底，复杂度变成O(n)，和线性表没有区别。

平衡二叉树要解决的问题，就是让树高始终保持在O(log n)量级。实现“平衡”的思路大体有两种：一种是限制左右子树高度差，比如AVL树；另一种是给节点染上红黑两色，通过颜色约束保证最长路径不会超过最短路径的两倍，比如红黑树。红黑树并不是绝对平衡，它允许左右子树高度差超过1，但这种“宽松约束”换来了更少的调整次数。

1.2 STL选择红黑树而不是AVL树的现实原因

很多人会产生疑惑：AVL树平衡程度比红黑树高，查找效率理论上更好，为什么C++标准库关联容器选择了红黑树？答案在于插入删除的代价。AVL树在插入后可能要一直回溯调整到根，删除后也一样，旋转次数通常比红黑树多。红黑树插入发生旋转的概率低，删除的修复虽然复杂，但整体也控制在常数次旋转加O(log n)的变色。

我们开发的场景里，map和set不光是查询，更频繁的是插入和删除。红黑树在频繁动态修改的场景下表现更稳，所以STL实现几乎清一色采用红黑树。你去看libstdc++的_Rb_tree，或者libc++的__tree，本质都是红黑树。记住一个结论：C++关联容器默认的平衡二叉树就是红黑树，这不是偶然，是工程权衡后的结果。

1.3 红黑树与B+树的分工，千万别搞混

顺便提一个高频问题：B+树是红黑树吗？不是。B+树是多路搜索树，通常用在数据库索引和文件系统里，它把多个键存在一个节点中，高度更低，适合磁盘块读取。红黑树是二叉树，节点之间靠指针串联，适合内存中的关联容器。

如果你面试时被问到“为什么数据库不用红黑树”，核心回答是：数据库索引要尽量减少磁盘IO次数，B+树一个节点可以存很多键值，树高明显更小；红黑树一个节点只存一个键值，内存中高效，但磁盘场景下一次IO能读到的有效数据太少。它们是不同层级的平衡数据结构，各管各的场景。

2. 红黑树的五个性质，以及它们是怎么把树高压到O(log n)的

2.1 五个性质的完整解读

红黑树必须满足以下五条性质：

每个节点不是红色就是黑色。
根节点一定是黑色。
所有叶子节点（NIL节点）都是黑色。
如果一个节点是红色，那么它的两个子节点必须都是黑色。
从任意节点出发，到它所有后代叶子节点的路径上，黑色节点数量相同。

第4条保证了红色节点不能连续出现。第5条在工程上被称为“黑高相等”，它确保任意节点到其叶子节点的所有路径包含相同数目的黑色节点。这两个性质加起来，就是红黑树“弱平衡”的数学基础。

很多初学者会把“叶子节点”理解成带键值的实际节点，这是大坑。红黑树里的叶子节点统一指的是空节点，也就是NIL哨兵。真实数据节点内部的两个孩子指针都指向NIL，而NIL节点是黑色、没有键值。这样设计是为了让每条路径的终点整齐统一，方便判断颜色和黑高。

2.2 从黑高推导树高上界

设一棵红黑树有n个内部节点（带键值的节点），其黑高为bh。因为性质5，所有路径黑色数相同；又因为性质4，红色节点不能连续出现，所以从根到叶子的最长路径不会超过最短路径的两倍。最短路径全由黑色组成，长度正好等于bh；最长路径则是黑红交替，最多2*bh步。

这个结论直接推出树高h <= 2bh。进一步可以证明，若一棵树黑高为bh，内部节点数n最少时是满二叉树形态，即n >= 2^bh - 1。反推bh <= log2(n+1)，于是树高h <= 2log2(n+1)。这就是红黑树能保证增删查复杂度稳定为O(log n)的来历。

理解推导比死记性质更有用。你面试时如果能把“为什么红黑树高度上界是2log2(n+1)”讲清楚，已经超过大多数只会背性质的候选人了。实际操作中不需要每次插入删除都严格验证黑高，但自测代码里一定要写这个检查函数，后面我会给出来。

2.3 插入删除为什么都要围绕性质4和5做文章

插入新节点时，我习惯把它先染成红色。原因很直接：染红色不会破坏黑高相等（性质5），只可能破坏性质4（红节点不能连续），修复范围被大大缩小。如果新节点染黑色，虽然不会出现连续红节点，但所有经过新节点的路径黑色数都会多1，修复起来反而更麻烦。

删除节点时，如果被删除节点颜色是红色，不会影响黑高，也基本不用修复；如果被删除节点颜色是黑色，那么经过该节点的路径少了一个黑色，性质5被破坏，必须通过复杂的“双黑修复”过程来弥补。所以你可以把红黑树的插入删除修复，本质上看作“破坏性质4就染色+旋转，破坏性质5就走双黑修复循环”。

3. 手写前的准备工作：节点结构、NIL哨兵与旋转函数

3.1 节点结构定义

我习惯这样定义红黑树节点：

enum Color { RED, BLACK }; template <typename T> struct RBNode { T key; RBNode *left, *right, *parent; Color color; explicit RBNode(const T& k) : key(k), left(nullptr), right(nullptr), parent(nullptr), color(RED) {} };

给节点加parent指针是为了方便回溯，但代价是旋转和删除时指针更新多，容易出错。如果你不想用parent指针，插入修复只能靠递归回溯，写起来更别扭；删除修复没有parent基本没法高效实现。所以手写教学版建议带parent指针。

3.2 NIL哨兵的作用

如果没有NIL哨兵，空节点直接用nullptr表示，那“空节点颜色为黑色”这条性质就很难统一处理。插入修复时还可以勉强判断，删除修复遇到被删节点是叶子、替代节点为空的情况就会格外难受，因为无法从一个空指针取得父节点信息。

所以标准做法是给每棵红黑树维护一个nil节点。新节点的左右孩子都指向nil，nil的左右孩子也指向nil，颜色为黑色。在树的类里初始化时这样写：

RBNode<T>* nil; nil = new RBNode<T>(T{}); nil->color = BLACK; nil->left = nil->right = nil;

注意不要对NIL发起删除操作，它只作为空叶子存在。整棵树析构时，后序遍历释放真实节点，最后单独释放nil。

3.3 左旋右旋的C++实现及细节

红黑树的旋转和AVL树旋转原理一致，但多了parent指针维护，细节更碎。先看左旋，假设节点x的右孩子是y，左旋就是把x变成y的左孩子：

void leftRotate(RBNode<T>* x) { RBNode<T>* 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; }

右旋完全对称，把right和left互换即可。我这里没有使用传引用的方式，而是假设树类内部维护root成员。手写时最常犯的错误是：改完y->left指向x后忘记更新x->parent，或者改父节点孩子指针时用错了判断条件。我的习惯是每次旋转后立刻检查三个关系：x->parent是否指向y，y->parent是否指向原来的祖父，x的右孩子是否被正确转移。

4. 插入后的修复流程：分情况处理，记住套路就行

4.1 插入真正要处理的情况

插入新节点后，如果新节点是根节点，直接染黑。如果它父亲是黑色，没有冲突。只有当父亲是红色时才需要修复，此时祖父必然存在且为黑色，因为性质4要求红节点不能连续。

把待处理节点记为z，可以分为三大类：

Case 1：叔叔节点是红色。
Case 2：叔叔节点是黑色，且z是父亲的右孩子。
Case 3：叔叔节点是黑色，且z是父亲的左孩子。

Case 2可以直接左旋变成Case 3，然后通过一次右旋结束。这个套路建议画图记忆。我一开始对着三张图反复看，后来总结了一句口诀：父左叔黑，左旋再右旋；父右叔黑，右旋再左旋。

4.2 插入修复完整C++代码

下面是插入修复函数，叔叔节点用y表示：

void insertFixup(RBNode<T>* z) { while (z->parent->color == RED) { if (z->parent == z->parent->parent->left) { RBNode<T>* 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(z); } z->parent->color = BLACK; z->parent->parent->color = RED; rightRotate(z->parent->parent); } } else { RBNode<T>* y = z->parent->parent->left; 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->left) { z = z->parent; rightRotate(z); } z->parent->color = BLACK; z->parent->parent->color = RED; leftRotate(z->parent->parent); } } } root->color = BLACK; }

因为NIL节点是黑色，所以叔叔节点一定存在且颜色可判断。插入修复结束时强制把根染黑，这个操作很重要，因为Case 1可能把红色一路向上传导到根。

4.3 插入修复的直观理解与模拟

不管哪种Case，修复目标都是让红色节点不连续，同时不破坏黑高相等。Case 1不旋转，只染色，让祖父变成红色，然后把z上移两层继续检查。这是因为父和叔都是红色，把它们染黑会破坏黑高，只能让祖父变红保持局部黑高不变。

Case 2是Case 3的前置形态，先旋转一层，把“折线”变成“直线”，再统一处理。Case 3直接旋转祖父，把红色父亲提上去，祖父放下来，再染色，恢复性质。整个过程很机械，如果你把代码跑一遍打印树结构，会发现每一棵子树都保持了黑高一致，只是局部颜色变了。

5. 删除后的修复流程：红黑树里唯一的硬骨头

5.1 删除的基本逻辑：谁的颜色决定要不要修复

删除节点的代码可以用BST标准替换逻辑，核心点在于记录“真正被删除的节点”y的原始颜色。如果y原本是红色，删除它不会减少任何路径的黑色节点数，因此不需要修复。如果y原本是黑色，它的位置被替代节点x占据后，这条路径就少了一个黑色节点，需要调用deleteFixup(x)。

工程实现上，我会把“找一个孩子”的简单删除和“找后继替换”的复杂删除分开写。只有两个孩子时，找后继y，用y替换z，之后真正删除y。y的颜色决定是否进入修复。

5.2 删除修复的四种情况

删除修复的循环条件是：x不是根节点，并且x颜色是黑色。这里的x是占据被删除位置的节点，可能是真实节点，也可能是NIL。循环内根据x是父节点的左孩子还是右孩子，分成对称的两套处理。以x是左孩子为例，设它的兄弟节点为w：

Case 1：w是红色。把w染黑、父染红，左旋父节点，w更新为原兄弟的左孩子，继续处理。
Case 2：w是黑色，且w的两个孩子都是黑色。直接把w染红，x移动到父节点，把“双黑”问题上移一层。
Case 3：w是黑色，w的右孩子是黑色，左孩子是红色。把w染红、w左孩子染黑，右旋w，w更新，转为Case 4。
Case 4：w是黑色，w的右孩子是红色。通过染色和左旋父节点解决，然后令x=root结束循环。

这四类情况的顺序不能乱。Case 1解决的是兄弟是红的特殊情况，它会把问题转成兄弟是黑的一种Case；Case 2把问题向上传播；Case 3为Case 4做铺垫；Case 4是最终“收尾”操作。

5.3 删除修复完整C++代码

我用标准CLRS风格写了一个可用版本，前提是nil哨兵已经初始化，并且节点颜色都能正确访问：

void deleteFixup(RBNode<T>* x) { while (x != root && x->color == BLACK) { if (x == x->parent->left) { RBNode<T>* w = x->parent->right; if (w->color == RED) { w->color = BLACK; x->parent->color = RED; leftRotate(x->parent); w = x->parent->right; } if (w->left->color == BLACK && w->right->color == BLACK) { w->color = RED; x = x->parent; } else { if (w->right->color == BLACK) { w->left->color = BLACK; w->color = RED; rightRotate(w); w = x->parent->right; } w->color = x->parent->color; x->parent->color = BLACK; w->right->color = BLACK; leftRotate(x->parent); x = root; } } else { RBNode<T>* w = x->parent->left; if (w->color == RED) { w->color = BLACK; x->parent->color = RED; rightRotate(x->parent); w = x->parent->left; } if (w->left->color == BLACK && w->right->color == BLACK) { w->color = RED; x = x->parent; } else { if (w->left->color == BLACK) { w->right->color = BLACK; w->color = RED; leftRotate(w); w = x->parent->left; } w->color = x->parent->color; x->parent->color = BLACK; w->left->color = BLACK; rightRotate(x->parent); x = root; } } } x->color = BLACK; }

这段代码的核心是：NIL节点不会导致空指针访问，因为w->left和w->right永远有值，至少是nil。这也是我强烈建议用nil哨兵的原因。

5.4 为什么删除修复比插入修复难这么多

插入修复最多向上进行O(log n)层，但每层的操作都很规整；删除修复则要处理兄弟节点的颜色、侄子节点的颜色，并且Case 2会让“双黑”问题向上继续传导。双黑是删除修复独有的概念：被删节点是黑色，替代节点也是黑色，但路径上又少了一个黑，需要想象成这个位置带着“额外的黑色债”。

我在第一次手写删除修复时，犯过把Case 3和Case 4合并处理的错误，结果随机测试跑到第几千次就崩了。后来老老实实按CLRS的分支写，每处理一个Case都打印当前x和w的颜色，才把这块啃下来。所以如果你觉得自己懂了但代码总错，建议先写一个随机数据测试工具，问题会很快暴露。

6. 正确性验证与常见坑

6.1 用随机插入删除验证性质

红黑树代码写完必须做随机验证。我的做法是生成一批随机整数，依次插入；校验函数检查根是否为黑、红节点是否有红孩子、每条路径黑高是否相等。然后继续随机删除，每删一个都重新校验。

校验黑高可以用递归：从某节点出发，空节点黑高为1，实际节点等于左右子树黑高较大者，但如果左右黑高不相等就直接判错。递归时要把真实节点和nil区分开：

int blackHeight(RBNode<T>* node) { if (node == nil) return 1; int l = blackHeight(node->left); int r = blackHeight(node->right); if (l != r) return -1; if (node->color == BLACK) return l + 1; return l; }

检查连续红节点时要判断左右孩子是否红色，同时小心nil节点，nil必须视为黑色，不能读取它的color后当成红色。

6.2 常见问题排查

我最常遇到的几个坑，按出现频率排序：

旋转后parent指针没有正确更新，插入删除中途就形成了环。
删除函数里没有正确处理nil的parent指针，导致deleteFixup里x->parent访问到野指针。
插入新节点时左右孩子没有指向nil，后面判断w->left颜色时崩溃。
根节点颜色没有强制设为黑色，验证函数立刻报警。
内存泄漏：忘了删除真实节点，或者误删nil。

排查时我会在关键函数里加一段断言，比如旋转后检查y->left == x和x->parent == y，一旦不满足立刻输出指针关系。这个调试方法非常管用，比人肉推演快十倍。

6.3 工程上建议直接用std::map/set

手写红黑树确实能让你对平衡二叉树的理解上升一个台阶，但如果在正式项目里需要红黑树结构，请直接使用std::map、std::set、std::multimap、std::multiset。它们的质量经过多年生产级验证，对分配器、异常安全、迭代器失效语义都有完整处理。

手写版本的用途是学习、面试和特殊场景定制。如果只是为了排序索引，别重复造轮子。这个建议不是劝退，而是说先会读、会写、会验证，再去考虑“我要不要自己实现一个”。

7. 最后聊点实用经验

我自己实现的简化版红黑树前前后后写了三遍，第一遍用递归写，第二遍用nullptr代替nil，第三遍才用带哨兵的标准实现。三遍下来最大的感受是：不要在有空指针判空的地方来回打补丁，直接按经典算法用nil哨兵，代码反而更干净。插入、删除修复的每一种Case都值得画一遍图，特别是删除Case 3转Case 4那一步，很多教程一句带过，但面试官最爱问。

如果你也准备手写红黑树，我建议按这个顺序练：先实现插入并跑通随机校验，再实现删除并跑通随机校验，最后再去看STL源码优化自己的代码。这样你的收获绝对不只是记住套路，而是真正理解“为什么平衡”以及“为什么工程选择红黑树”。