尧图网站建设 
红黑树这名字在C圈子里基本等同于“劝退”二字。它是std::map和std::set的底层实现也是面试中挂了无数次的高频考点。网上讲原理的文章很多但真正能用 C 把插入、删除完整跑通还能经得起 delete 和 rotate 连环考验的代码反而很少。我最早是在做一个内存索引模块时被逼着从零手写红黑树的当时对着算法导论抄了三天抄完发现九个空指针debug 到凌晨三点。后来把节点设计、旋转、双黑修复这些环节一个个理清之后才明白红黑树难的不是代码本身而是缺少一个按“为什么这样做”来组织的完整脉络。这篇文章就用实际动手写代码的视角把红黑树从节点设计、插入、删除到性质验证完整拆开讲一遍所有代码都是可直接编译运行的 C 模板实现。适合正在准备 C 面试、想彻底搞懂 STL map 底层机制、或者需要在工程里自己维护有序结构的同学。我会把我踩过的坑、容易写错的地方、验证树是否合法的方法一并放进来你看完之后不仅能照抄代码还能在面试时把原理讲清楚。1. 红黑树为什么能成为“工业级平衡树”的主流选择1.1 从AVL的“强迫症”到红黑树的“松而不垮”很多人学第一棵平衡树就是从 AVL 开始的。AVL 的定义非常严格每个节点的左右子树高度差不能超过 1。这个约束保证了树的高度严格趋近 log₂n查询性能极其稳定。但代价是每次插入或删除后只要某个节点的高度差超过 1就得沿着路径回溯调整最坏情况下可能要旋转很多次。红黑树换了一条路它不要求每一棵子树的高度都差不多而是通过“节点颜色”这一层抽象把平衡约束放宽到“从根到任一叶子的路径上最长路径不超过最短路径的两倍”。这看起来比 AVL 宽松很多但换来的是插入操作最多只需要两次旋转删除操作最多三次旋转剩下的调整都可以通过变色完成。对频繁增删的场景来说这个特性非常宝贵。你可以把 AVL 想成一名强迫症患者书架上的每一本书都要求对齐到毫米红黑树则像一个粗中有细的管理员只要求书架整体高度差不超过一半整理起来轻松很多查书的时候也不会慢到哪去。1.2 五条性质里真正决定平衡的是“黑高”红黑树的五条性质网上到处都有但大多数文章只是列出来没有解释哪条才是核心。我按自己的理解重新排一下每个节点要么红要么黑。根节点是黑的。每个叶子节点NIL 哨兵是黑的。如果一个节点是红的那么它的两个子节点都是黑的即红节点不能连续。从任意节点出发到其每个后代叶子节点的所有路径上黑色节点的数量相同这个数量叫“黑高”。其中第 4 条和第 5 条才是关键。第 4 条保证了任何一条路径上红色节点不能连续出现所以哪怕路径再长红色节点最多和黑色节点交替排列。第 5 条保证了每条路径的黑色节点数相同。比如一棵黑高为 h 的树最短路径就是一条全黑路径长度为 h最长路径就是红黑交替长度为 2h。因此整棵树的高度被限制在 2log₂(n1) 以内查询、插入、删除的时间复杂度都是 O(log n)。这里有个小细节值得注意说到黑高NIL 哨兵是算作黑色节点的。所以从根到叶子的路径长度里叶子本身也算一个黑高度。初学红黑树的人经常在这个地方数错。1.3 红黑树 vs AVL vs B树选型表搞清楚红黑树的定位之后再看它和另外两种常见树的区别会更清楚。下面的表是我在实际工程选择时常用的参考特性红黑树AVL树B树/B树平衡方式弱平衡最长路径≤2倍最短路径强平衡左右高度差≤1多路平衡每个节点多个key查询性能O(log n)常数略高O(log n)常数更小O(log n)但适合磁盘顺序访问插入旋转次数最多2次最多2次节点分裂/合并删除旋转次数最多3次可能O(log n)次节点借用/合并使用场景内存中的有序容器查询为主、少增删数据库、文件系统所以红黑树的定位非常明确它是内存里“增删查都很快”的通用型有序数据结构。如果你要用 C 实现一个按键有序的容器又不希望在某些极端输入下性能断崖式下跌红黑树几乎是默认答案。2. 先把C实现的基础骨架搭对节点设计、哨兵与旋转2.1 为什么新插入节点默认是红色动手写代码之前先解决一个最基本的问题新插入的节点为什么要染成红色而不是黑色答案是如果插入一个黑色节点那么从根到该节点的这条路径上就多了一个黑节点直接违反性质 5所有路径的黑高都得重新调整而插入红色节点只可能违反性质 4红节点不能连续而且只有当父节点恰好也是红色时才需要修复。也就是说默认插红能把“需要修复”的概率降到最低修复起来也只处理局部冲突。这个选择贯穿整个实现插入后的修复循环条件就是父节点为红。如果父节点本来就是黑色那么插入操作到此结束什么都不用做。2.2 节点结构与哨兵NIL别忘了模板的坑节点结构本身并不复杂每个节点保存 key、value、颜色、左右孩子指针和父指针。但有一个设计决策非常重要空指针用nullptr还是用一个专门的哨兵节点。我一开始用的是nullptr结果在插入修复和删除修复里到处都要写“if (left ! nullptr left-color Red)”这样的判空不仅啰嗦还容易漏判。后来改成全局哨兵节点nil这个节点永远是黑色它的 left、right、parent 都指向自己。这样所有对空节点的颜色访问都变成合法的代码里再也不用区分“空指针”和“真实节点”。哨兵还有一个好处红黑树的叶子节点就是 NIL所有叶子都是黑色。而用nullptr表示叶子时你还需要在逻辑上默认空节点为黑色容易在修复的时候忘记这一点。下面是节点的模板定义#include iostream #include functional enum class Color { Red, Black }; template typename K, typename V, typename Compare std::lessK class RBTree { private: struct Node { K key; V value; Color color; Node* left; Node* right; Node* parent; Node(const K k, const V v) : key(k), value(v), color(Color::Red), left(nullptr), right(nullptr), parent(nullptr) {} }; Node* root; Node* nil; // 哨兵节点始终为黑色 Compare comp; size_t count_; void initNil() { nil new Node(K(), V()); nil-color Color::Black; nil-left nil-right nil-parent nil; } // ... 后续函数 public: RBTree() : root(nullptr), count_(0) { initNil(); root nil; } // ... };这里initNil里用了K()和V()的默认构造函数。对常见的 int、string 这些类型完全够用。如果你的 key 类型不支持默认构造可以把哨兵提成静态成员或者在节点里单独加一个bool isNil标志。工程上我更推荐后一种做法但演示代码里为了可读性用默认构造没问题。2.3 左旋和右旋让树形改变但中序遍历不变旋转是红黑树里最基本的结构调整操作。左旋就是把某个节点的右孩子“提上来”自己变成右孩子的左子树右旋则正好相反。旋转过程中所有节点的 key 大小关系都不会被破坏因为中序遍历序列在旋转前后完全一样。我自己的理解方式是旋转其实是把一条“斜线”掰直。比如一棵树向右倾斜最深的路径在右子树里右旋可以把右侧的负担往左匀一匀。红黑树本身并不需要保证左右子树高度完全一致但旋转配合变色可以优雅地把“红色冲突”转移走。下面给出左旋和右旋的实现。需要注意的细节是旋转不仅要改两个孩子指针还要改父指针以及树的根节点可能发生变化void rotateLeft(Node* x) { Node* y x-right; // y 是要提上来的节点 x-right y-left; // y 的左子树过继给 x 当右子树 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; } void rotateRight(Node* x) { Node* y x-left; // y 是要提上来的节点 x-left y-right; if (y-right ! nil) { y-right-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-right x; x-parent y; }2.4 旋转代码里的空指针陷阱旋转这段代码看起来简单但最容易犯的错误是忘记更新两个节点的父指针。我最早写的时候只改了左右孩子指针结果 rotate 之后树上直接出现两个 parent 指向同一个节点的荒唐局面。更隐蔽的是当x是根节点的孩子时旋转后根节点指针要更新否则整棵树的入口就丢了。还有一个细节在设置x-right y-left之后如果y-left是哨兵nil不能对nil-parent写值。我在实现里加了if (y-left ! nil)的判断这很关键。如果nil节点的 parent 被意外设置成x后续修复循环里判断z-parent-parent时就会出现不可预测的遍历路径很难排查。所以当你看到leftRotate和rightRotate的代码时要重点检查三件事孩子指针是否双向挂接、父指针是否更新、根节点是否换人。这三条都对了旋转才算写对。3. 插入后如何用“父-叔-祖父”三层判断收敛冲突3.1 先按普通BST规则插入插入的第一步和普通二叉搜索树完全一样从根开始key 小于当前节点走左子树大于走右子树直到碰到 NIL把新节点挂上去。这一步必须把新节点的 left、right 都指向nilparent 指向找到的父节点颜色设为 Red。我这里的实现没有处理重复 key直接往右走。工程上更严谨的做法是插入前先 find 一次如果已经存在就覆盖 value 或忽略。演示代码为了保持简洁用了后者的简化逻辑void insert(const K key, const V value) { Node* z new Node(key, value); Node* y nil; Node* x root; while (x ! nil) { y x; if (comp(z-key, x-key)) x x-left; else x x-right; } z-parent y; if (y nil) { root z; } else if (comp(z-key, y-key)) { y-left z; } else { y-right z; } z-left z-right nil; z-color Color::Red; insertFixup(z); count_; }这里用Compare comp而不是直接operator目的是让树支持任意排序规则。std::map也是这么做的。你可以在构造红黑树时传入自定义函数对象从而支持倒序、按结构体某个字段排序等需求。3.2 叔叔为红色颜色翻转指针上移插入后的修复函数基本流程是这样先看父节点是不是红色如果不是红色整棵树已经合法如果是红色就找到祖父节点再看叔叔节点祖父的另一个孩子是什么颜色。叔叔是红色的时候修复最简单把父节点和叔叔节点都涂黑把祖父节点涂红然后把关注点z上移到祖父节点。这一步做完之后以祖父为根的子树内部黑高不变因为原来父和叔两个红节点变成黑祖父从黑变红整体黑高没变。但是祖父变成红色之后它和它的父节点可能又产生新的红色冲突所以要继续循环处理。用代码表示就是这样if (z-parent-color Color::Red) { // z-parent 是 z-grandparent 的左孩子 if (z-parent z-parent-parent-left) { Node* uncle z-parent-parent-right; if (uncle-color Color::Red) { z-parent-color Color::Black; uncle-color Color::Black; z-parent-parent-color Color::Red; z z-parent-parent; } // ... } }此时要注意uncle可能是 NIL 哨兵。但哨兵的颜色是黑色所以不会误判成红色这就体现了哨兵的价值不需要额外判空。3.3 叔叔为黑色旋转加变色收尾叔叔是黑色或 NIL时情况稍微复杂但思路其实很固定。先看z是它父节点的左孩子还是右孩子。如果z是右孩子先把父节点左旋一次让z变成左孩子。这样做的目的是把问题统一成“LL 型”或者“RR 型”。然后对祖父做一次右旋同时把父节点涂黑、祖父涂红。这个旋转加变色结束后之前的“红父-红子”冲突就消失了而且整棵树的黑高保持不变修复可以终止。完整的 insertFixup 我放在一起左父和右父的情况是对称的void insertFixup(Node* z) { while (z-parent-color Color::Red) { if (z-parent z-parent-parent-left) { Node* uncle z-parent-parent-right; if (uncle-color Color::Red) { z-parent-color Color::Black; uncle-color Color::Black; z-parent-parent-color Color::Red; z z-parent-parent; } else { if (z z-parent-right) { z z-parent; rotateLeft(z); } z-parent-color Color::Black; z-parent-parent-color Color::Red; rotateRight(z-parent-parent); } } else { Node* uncle z-parent-parent-left; if (uncle-color Color::Red) { z-parent-color Color::Black; uncle-color Color::Black; z-parent-parent-color Color::Red; z z-parent-parent; } else { if (z z-parent-left) { z z-parent; rotateRight(z); } z-parent-color Color::Black; z-parent-parent-color Color::Red; rotateLeft(z-parent-parent); } } } root-color Color::Black; }注意循环结束之后根节点可能已经被染红尤其是插入第一个节点或翻转之后祖父成了根。所以最后无条件把根染黑这是红黑树性质 2 的兜底。3.4 修复循环里的边界细节写 insertFixup 时有几个边界问题我反复栽过。第一z上移之后可能变成根节点的子节点此时z-parent-parent可能等于 NIL。但nil的 parent 是nil所以不会段错误只是需要保证循环条件只检查z-parent-color就能安全退出。这正是哨兵带来的好处。第二旋转之后z的指向不要弄丢。在叔叔为黑分支里如果先执行了左旋z已经变成了原来父节点的左子树紧接着的变色和右旋必须基于z-parent-parent去做不能基于旧的z-parent。我把这段逻辑里的z先赋值为父节点再旋转就能保证后续操作一致。第三root-color Color::Black这行必须放在循环外面。有的初学者把这一句放在 while 里面导致每次循环都强制把根染黑如果根不是当前修复路径上的节点就会破坏黑高。4. 删除修复坑比插入多得多核心是“双黑”4.1 先找到真正被删的节点删除的入口是找到 key 对应的节点。如果目标节点有两个孩子直接删除它会留下两个子树的拼接问题所以通常的做法是找到它的中序后继用后继的 key、value 覆盖目标节点然后删除后继节点。这样实际被物理删除的节点最多只有一个孩子问题大幅简化。这里有一个容易忽略的点当后继节点就是目标节点的右孩子时指针处理略有不同。CLRS 里的标准做法是先判断y是否等于z-right如果不等才先 transplant 后继的右子树。逻辑上要保证替换过程中不会丢失子树指针。删除时还要记录被删除节点的原始颜色因为只有删除黑色节点才会导致黑高失衡。如果被删除节点是红色那么各路径的黑高都没变不需要修复。4.2 双黑一次黑高失衡的“债”先看双黑问题。假设被删除的黑色节点是 z顶替它位置的节点是 x。如果 z 是黑色那么原本经过 z 的路径上就少了一个黑色节点。为了描述这个“债务”我们把 x 标记为“双黑”——它原本的颜色之上还背负着一层额外的黑。修复的目标就是把这层额外的黑传递出去直到遇到红色节点把它染黑或者一路推到根节点债务清零。所以双黑不是真的存在一种叫“双黑”的颜色开关它只是帮助我们理解修复逻辑的抽象概念。真正的代码里我们用while (x ! root x-color Color::Black)来判断“x 还在背负债务”。如果 x 本身是红色循环会退出最后把它染黑债务就还清了。4.3 五种修复场景的判断顺序删除修复的代码分支很多但核心原则是固定的从被删除节点的位置 x 出发看它的兄弟节点 w 的颜色再根据 w 的孩子颜色分支。常见的四种情况以 x 是左孩子为例兄弟 w 是红色把 w 染黑、父节点染红左旋父节点。这一步把问题转化为兄弟是黑色的情况因为红兄弟经过旋转之后变成了 x 的新兄弟而且新兄弟是黑的。兄弟 w 是黑色且 w 的两个孩子都是黑色把 w 染红把债务上移给父节点令 x parent。这是因为 x 和 w 两条路径都少一个黑把 w 也变成“欠债”节点后父节点变成双黑问题向上传递。兄弟 w 是黑色w 的左孩子是红色、右孩子是黑色把 w 染红w 的左孩子染黑右旋 w。这一步把问题转化为第 4 种情况。兄弟 w 是黑色w 的右孩子是红色把 w 染成父节点颜色父节点染黑w 的右孩子染黑左旋父节点令 x root 结束循环。x 是右孩子时完全镜像对称。下面是完整的删除修复代码void eraseFixup(Node* x) { while (x ! root x-color Color::Black) { if (x x-parent-left) { Node* w x-parent-right; if (w-color Color::Red) { w-color Color::Black; x-parent-color Color::Red; rotateLeft(x-parent); w x-parent-right; } if (w-left-color Color::Black w-right-color Color::Black) { w-color Color::Red; x x-parent; } else { if (w-right-color Color::Black) { w-left-color Color::Black; w-color Color::Red; rotateRight(w); w x-parent-right; } w-color x-parent-color; x-parent-color Color::Black; w-right-color Color::Black; rotateLeft(x-parent); x root; } } else { // x 是右孩子镜像处理 Node* w x-parent-left; if (w-color Color::Red) { w-color Color::Black; x-parent-color Color::Red; rotateRight(x-parent); w x-parent-left; } if (w-right-color Color::Black w-left-color Color::Black) { w-color Color::Red; x x-parent; } else { if (w-left-color Color::Black) { w-right-color Color::Black; w-color Color::Red; rotateLeft(w); w x-parent-left; } w-color x-parent-color; x-parent-color Color::Black; w-left-color Color::Black; rotateRight(x-parent); x root; } } } x-color Color::Black; }这里有个细节要特别注意删除修复里对 w 的左孩子和右孩子访问时w 可能是 NIL 吗不会。因为如果 x 是左孩子兄弟 w 如果不存在NIL那么父节点左路径黑高和右路径黑高不同这棵红黑树本身就是非法的。所以只要树合法w 必然是真实节点或者至少拥有颜色判断能力。但 w 的孩子完全可能是 NIL代码里访问w-left-color是安全的因为 NIL 就是黑色。eraseFixup 结束后还要把 x 染黑。这是因为循环退出时 x 可能已经被赋值为 root而 root 必须是黑色或者 x 本身是红色染黑后债务正好清零。4.4 删除时最容易写错的地方删除操作远比插入复杂主要错在三处。第一没有区分“后继是右孩子本身”和“后继在右子树的深处”这两种情况。在后继不是 z 的右孩子时要把后继的右子树先 transplant 上去再把 z 的右子树接给后继。这一步被很多人直接省略导致删除后子树丢失。第二transplant 函数里最后一行v-parent u-parent是无条件执行的。但如果 v 是 NIL很多初学者怕给 NIL 赋 parent 导致问题就跳过这行结果 NIL 的 parent 还是旧值删除修复里判断x x-parent-left时会出错。正确的做法是v 的 parent 必须无条件更新因为 NIL 也是树的一部分。第三删除一个红色节点时根本不需要调用 eraseFixup但很多人会统一调用导致 x 是一个普通黑节点却进入修复循环白白做很多无效操作。记住只有被删除节点颜色为黑时才需要修复。5. 完整实现与测试验证拿数据说话5.1 合并头文件与核心注释到这里前面的所有片段可以合并成一棵完整的红黑树了。为了让你能直接跑起来我把关键部分拼成一个可用的类包含 insert、erase、find、中序遍历和合法性验证。完整的模板代码较长这里给一个精简版函数体里做了必要的注释#include iostream #include functional #include vector enum class Color { Red, Black }; template typename K, typename V, typename Compare std::lessK class RBTree { private: struct Node { K key; V value; Color color; Node* left; Node* right; Node* parent; Node(const K k, const V v) : key(k), value(v), color(Color::Red), left(nullptr), right(nullptr), parent(nullptr) {} }; Node* root; Node* nil; Compare comp; size_t count_; void initNil() { nil new Node(K(), V()); nil-color Color::Black; nil-left nil-right nil-parent nil; } void clear(Node* x) { if (x nil) return; clear(x-left); clear(x-right); delete x; } Node* minimum(Node* x) const { while (x-left ! nil) x x-left; return x; } void rotateLeft(Node* x) { Node* 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; } void rotateRight(Node* x) { Node* y x-left; x-left y-right; if (y-right ! nil) y-right-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-right x; x-parent y; } void insertFixup(Node* z) { while (z-parent-color Color::Red) { if (z-parent z-parent-parent-left) { Node* uncle z-parent-parent-right; if (uncle-color Color::Red) { z-parent-color Color::Black; uncle-color Color::Black; z-parent-parent-color Color::Red; z z-parent-parent; } else { if (z z-parent-right) { z z-parent; rotateLeft(z); } z-parent-color Color::Black; z-parent-parent-color Color::Red; rotateRight(z-parent-parent); } } else { Node* uncle z-parent-parent-left; if (uncle-color Color::Red) { z-parent-color Color::Black; uncle-color Color::Black; z-parent-parent-color Color::Red; z z-parent-parent; } else { if (z z-parent-left) { z z-parent; rotateRight(z); } z-parent-color Color::Black; z-parent-parent-color Color::Red; rotateLeft(z-parent-parent); } } } root-color Color::Black; } void transplant(Node* u, Node* v) { if (u-parent nil) root v; else if (u u-parent-left) u-parent-left v; else u-parent-right v; v-parent u-parent; } void eraseFixup(Node* x) { while (x ! root x-color Color::Black) { if (x x-parent-left) { Node* w x-parent-right; if (w-color Color::Red) { w-color Color::Black; x-parent-color Color::Red; rotateLeft(x-parent); w x-parent-right; } if (w-left-color Color::Black w-right-color Color::Black) { w-color Color::Red; x x-parent; } else { if (w-right-color Color::Black) { w-left-color Color::Black; w-color Color::Red; rotateRight(w); w x-parent-right; } w-color x-parent-color; x-parent-color Color::Black; w-right-color Color::Black; rotateLeft(x-parent); x root; } } else { Node* w x-parent-left; if (w-color Color::Red) { w-color Color::Black; x-parent-color Color::Red; rotateRight(x-parent); w x-parent-left; } if (w-right-color Color::Black w-left-color Color::Black) { w-color Color::Red; x x-parent; } else { if (w-left-color Color::Black) { w-right-color Color::Black; w-color Color::Red; rotateLeft(w); w x-parent-left; } w-color x-parent-color; x-parent-color Color::Black; w-left-color Color::Black; rotateRight(x-parent); x root; } } } x-color Color::Black; } public: RBTree() : root(nullptr), count_(0) { initNil(); root nil; } ~RBTree() { clear(root); delete nil; } size_t size() const { return count_; } bool empty() const { return count_ 0; } void insert(const K key, const V value) { Node* z new Node(key, value); Node* y nil; Node* x root; while (x ! nil) { y x; if (comp(z-key, x-key)) x x-left; else x x-right; } z-parent y; if (y nil) root z; else if (comp(z-key, y-key)) y-left z; else y-right z; z-left z-right nil; z-color Color::Red; insertFixup(z); count_; } bool find(const K key) const { Node* cur root; while (cur ! nil) { if (comp(key, cur-key)) cur cur-left; else if (comp(cur-key, key)) cur cur-right; else return true; } return false; } bool erase(const K key) { Node* z root; while (z ! nil) { if (comp(key, z-key)) z z-left; else if (comp(z-key, key)) z z-right; else break; } if (z nil) return false; Node* y z; Node* x; Color y_original_color y-color; if (z-left nil) { x z-right; transplant(z, z-right); } else if (z-right nil) { x z-left; transplant(z, z-left); } else { y minimum(z-right); y_original_color y-color; x y-right; if (y-parent z) { x-parent y; } else { 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; } if (y_original_color Color::Black) { eraseFixup(x); } delete z; --count_; return true; } C++红黑树完整实现：插入、删除与旋转修复实战
红黑树这名字在C圈子里基本等同于“劝退”二字。它是std::map和std::set的底层实现也是面试中挂了无数次的高频考点。网上讲原理的文章很多但真正能用 C 把插入、删除完整跑通还能经得起 delete 和 rotate 连环考验的代码反而很少。我最早是在做一个内存索引模块时被逼着从零手写红黑树的当时对着算法导论抄了三天抄完发现九个空指针debug 到凌晨三点。后来把节点设计、旋转、双黑修复这些环节一个个理清之后才明白红黑树难的不是代码本身而是缺少一个按“为什么这样做”来组织的完整脉络。这篇文章就用实际动手写代码的视角把红黑树从节点设计、插入、删除到性质验证完整拆开讲一遍所有代码都是可直接编译运行的 C 模板实现。适合正在准备 C 面试、想彻底搞懂 STL map 底层机制、或者需要在工程里自己维护有序结构的同学。我会把我踩过的坑、容易写错的地方、验证树是否合法的方法一并放进来你看完之后不仅能照抄代码还能在面试时把原理讲清楚。1. 红黑树为什么能成为“工业级平衡树”的主流选择1.1 从AVL的“强迫症”到红黑树的“松而不垮”很多人学第一棵平衡树就是从 AVL 开始的。AVL 的定义非常严格每个节点的左右子树高度差不能超过 1。这个约束保证了树的高度严格趋近 log₂n查询性能极其稳定。但代价是每次插入或删除后只要某个节点的高度差超过 1就得沿着路径回溯调整最坏情况下可能要旋转很多次。红黑树换了一条路它不要求每一棵子树的高度都差不多而是通过“节点颜色”这一层抽象把平衡约束放宽到“从根到任一叶子的路径上最长路径不超过最短路径的两倍”。这看起来比 AVL 宽松很多但换来的是插入操作最多只需要两次旋转删除操作最多三次旋转剩下的调整都可以通过变色完成。对频繁增删的场景来说这个特性非常宝贵。你可以把 AVL 想成一名强迫症患者书架上的每一本书都要求对齐到毫米红黑树则像一个粗中有细的管理员只要求书架整体高度差不超过一半整理起来轻松很多查书的时候也不会慢到哪去。1.2 五条性质里真正决定平衡的是“黑高”红黑树的五条性质网上到处都有但大多数文章只是列出来没有解释哪条才是核心。我按自己的理解重新排一下每个节点要么红要么黑。根节点是黑的。每个叶子节点NIL 哨兵是黑的。如果一个节点是红的那么它的两个子节点都是黑的即红节点不能连续。从任意节点出发到其每个后代叶子节点的所有路径上黑色节点的数量相同这个数量叫“黑高”。其中第 4 条和第 5 条才是关键。第 4 条保证了任何一条路径上红色节点不能连续出现所以哪怕路径再长红色节点最多和黑色节点交替排列。第 5 条保证了每条路径的黑色节点数相同。比如一棵黑高为 h 的树最短路径就是一条全黑路径长度为 h最长路径就是红黑交替长度为 2h。因此整棵树的高度被限制在 2log₂(n1) 以内查询、插入、删除的时间复杂度都是 O(log n)。这里有个小细节值得注意说到黑高NIL 哨兵是算作黑色节点的。所以从根到叶子的路径长度里叶子本身也算一个黑高度。初学红黑树的人经常在这个地方数错。1.3 红黑树 vs AVL vs B树选型表搞清楚红黑树的定位之后再看它和另外两种常见树的区别会更清楚。下面的表是我在实际工程选择时常用的参考特性红黑树AVL树B树/B树平衡方式弱平衡最长路径≤2倍最短路径强平衡左右高度差≤1多路平衡每个节点多个key查询性能O(log n)常数略高O(log n)常数更小O(log n)但适合磁盘顺序访问插入旋转次数最多2次最多2次节点分裂/合并删除旋转次数最多3次可能O(log n)次节点借用/合并使用场景内存中的有序容器查询为主、少增删数据库、文件系统所以红黑树的定位非常明确它是内存里“增删查都很快”的通用型有序数据结构。如果你要用 C 实现一个按键有序的容器又不希望在某些极端输入下性能断崖式下跌红黑树几乎是默认答案。2. 先把C实现的基础骨架搭对节点设计、哨兵与旋转2.1 为什么新插入节点默认是红色动手写代码之前先解决一个最基本的问题新插入的节点为什么要染成红色而不是黑色答案是如果插入一个黑色节点那么从根到该节点的这条路径上就多了一个黑节点直接违反性质 5所有路径的黑高都得重新调整而插入红色节点只可能违反性质 4红节点不能连续而且只有当父节点恰好也是红色时才需要修复。也就是说默认插红能把“需要修复”的概率降到最低修复起来也只处理局部冲突。这个选择贯穿整个实现插入后的修复循环条件就是父节点为红。如果父节点本来就是黑色那么插入操作到此结束什么都不用做。2.2 节点结构与哨兵NIL别忘了模板的坑节点结构本身并不复杂每个节点保存 key、value、颜色、左右孩子指针和父指针。但有一个设计决策非常重要空指针用nullptr还是用一个专门的哨兵节点。我一开始用的是nullptr结果在插入修复和删除修复里到处都要写“if (left ! nullptr left-color Red)”这样的判空不仅啰嗦还容易漏判。后来改成全局哨兵节点nil这个节点永远是黑色它的 left、right、parent 都指向自己。这样所有对空节点的颜色访问都变成合法的代码里再也不用区分“空指针”和“真实节点”。哨兵还有一个好处红黑树的叶子节点就是 NIL所有叶子都是黑色。而用nullptr表示叶子时你还需要在逻辑上默认空节点为黑色容易在修复的时候忘记这一点。下面是节点的模板定义#include iostream #include functional enum class Color { Red, Black }; template typename K, typename V, typename Compare std::lessK class RBTree { private: struct Node { K key; V value; Color color; Node* left; Node* right; Node* parent; Node(const K k, const V v) : key(k), value(v), color(Color::Red), left(nullptr), right(nullptr), parent(nullptr) {} }; Node* root; Node* nil; // 哨兵节点始终为黑色 Compare comp; size_t count_; void initNil() { nil new Node(K(), V()); nil-color Color::Black; nil-left nil-right nil-parent nil; } // ... 后续函数 public: RBTree() : root(nullptr), count_(0) { initNil(); root nil; } // ... };这里initNil里用了K()和V()的默认构造函数。对常见的 int、string 这些类型完全够用。如果你的 key 类型不支持默认构造可以把哨兵提成静态成员或者在节点里单独加一个bool isNil标志。工程上我更推荐后一种做法但演示代码里为了可读性用默认构造没问题。2.3 左旋和右旋让树形改变但中序遍历不变旋转是红黑树里最基本的结构调整操作。左旋就是把某个节点的右孩子“提上来”自己变成右孩子的左子树右旋则正好相反。旋转过程中所有节点的 key 大小关系都不会被破坏因为中序遍历序列在旋转前后完全一样。我自己的理解方式是旋转其实是把一条“斜线”掰直。比如一棵树向右倾斜最深的路径在右子树里右旋可以把右侧的负担往左匀一匀。红黑树本身并不需要保证左右子树高度完全一致但旋转配合变色可以优雅地把“红色冲突”转移走。下面给出左旋和右旋的实现。需要注意的细节是旋转不仅要改两个孩子指针还要改父指针以及树的根节点可能发生变化void rotateLeft(Node* x) { Node* y x-right; // y 是要提上来的节点 x-right y-left; // y 的左子树过继给 x 当右子树 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; } void rotateRight(Node* x) { Node* y x-left; // y 是要提上来的节点 x-left y-right; if (y-right ! nil) { y-right-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-right x; x-parent y; }2.4 旋转代码里的空指针陷阱旋转这段代码看起来简单但最容易犯的错误是忘记更新两个节点的父指针。我最早写的时候只改了左右孩子指针结果 rotate 之后树上直接出现两个 parent 指向同一个节点的荒唐局面。更隐蔽的是当x是根节点的孩子时旋转后根节点指针要更新否则整棵树的入口就丢了。还有一个细节在设置x-right y-left之后如果y-left是哨兵nil不能对nil-parent写值。我在实现里加了if (y-left ! nil)的判断这很关键。如果nil节点的 parent 被意外设置成x后续修复循环里判断z-parent-parent时就会出现不可预测的遍历路径很难排查。所以当你看到leftRotate和rightRotate的代码时要重点检查三件事孩子指针是否双向挂接、父指针是否更新、根节点是否换人。这三条都对了旋转才算写对。3. 插入后如何用“父-叔-祖父”三层判断收敛冲突3.1 先按普通BST规则插入插入的第一步和普通二叉搜索树完全一样从根开始key 小于当前节点走左子树大于走右子树直到碰到 NIL把新节点挂上去。这一步必须把新节点的 left、right 都指向nilparent 指向找到的父节点颜色设为 Red。我这里的实现没有处理重复 key直接往右走。工程上更严谨的做法是插入前先 find 一次如果已经存在就覆盖 value 或忽略。演示代码为了保持简洁用了后者的简化逻辑void insert(const K key, const V value) { Node* z new Node(key, value); Node* y nil; Node* x root; while (x ! nil) { y x; if (comp(z-key, x-key)) x x-left; else x x-right; } z-parent y; if (y nil) { root z; } else if (comp(z-key, y-key)) { y-left z; } else { y-right z; } z-left z-right nil; z-color Color::Red; insertFixup(z); count_; }这里用Compare comp而不是直接operator目的是让树支持任意排序规则。std::map也是这么做的。你可以在构造红黑树时传入自定义函数对象从而支持倒序、按结构体某个字段排序等需求。3.2 叔叔为红色颜色翻转指针上移插入后的修复函数基本流程是这样先看父节点是不是红色如果不是红色整棵树已经合法如果是红色就找到祖父节点再看叔叔节点祖父的另一个孩子是什么颜色。叔叔是红色的时候修复最简单把父节点和叔叔节点都涂黑把祖父节点涂红然后把关注点z上移到祖父节点。这一步做完之后以祖父为根的子树内部黑高不变因为原来父和叔两个红节点变成黑祖父从黑变红整体黑高没变。但是祖父变成红色之后它和它的父节点可能又产生新的红色冲突所以要继续循环处理。用代码表示就是这样if (z-parent-color Color::Red) { // z-parent 是 z-grandparent 的左孩子 if (z-parent z-parent-parent-left) { Node* uncle z-parent-parent-right; if (uncle-color Color::Red) { z-parent-color Color::Black; uncle-color Color::Black; z-parent-parent-color Color::Red; z z-parent-parent; } // ... } }此时要注意uncle可能是 NIL 哨兵。但哨兵的颜色是黑色所以不会误判成红色这就体现了哨兵的价值不需要额外判空。3.3 叔叔为黑色旋转加变色收尾叔叔是黑色或 NIL时情况稍微复杂但思路其实很固定。先看z是它父节点的左孩子还是右孩子。如果z是右孩子先把父节点左旋一次让z变成左孩子。这样做的目的是把问题统一成“LL 型”或者“RR 型”。然后对祖父做一次右旋同时把父节点涂黑、祖父涂红。这个旋转加变色结束后之前的“红父-红子”冲突就消失了而且整棵树的黑高保持不变修复可以终止。完整的 insertFixup 我放在一起左父和右父的情况是对称的void insertFixup(Node* z) { while (z-parent-color Color::Red) { if (z-parent z-parent-parent-left) { Node* uncle z-parent-parent-right; if (uncle-color Color::Red) { z-parent-color Color::Black; uncle-color Color::Black; z-parent-parent-color Color::Red; z z-parent-parent; } else { if (z z-parent-right) { z z-parent; rotateLeft(z); } z-parent-color Color::Black; z-parent-parent-color Color::Red; rotateRight(z-parent-parent); } } else { Node* uncle z-parent-parent-left; if (uncle-color Color::Red) { z-parent-color Color::Black; uncle-color Color::Black; z-parent-parent-color Color::Red; z z-parent-parent; } else { if (z z-parent-left) { z z-parent; rotateRight(z); } z-parent-color Color::Black; z-parent-parent-color Color::Red; rotateLeft(z-parent-parent); } } } root-color Color::Black; }注意循环结束之后根节点可能已经被染红尤其是插入第一个节点或翻转之后祖父成了根。所以最后无条件把根染黑这是红黑树性质 2 的兜底。3.4 修复循环里的边界细节写 insertFixup 时有几个边界问题我反复栽过。第一z上移之后可能变成根节点的子节点此时z-parent-parent可能等于 NIL。但nil的 parent 是nil所以不会段错误只是需要保证循环条件只检查z-parent-color就能安全退出。这正是哨兵带来的好处。第二旋转之后z的指向不要弄丢。在叔叔为黑分支里如果先执行了左旋z已经变成了原来父节点的左子树紧接着的变色和右旋必须基于z-parent-parent去做不能基于旧的z-parent。我把这段逻辑里的z先赋值为父节点再旋转就能保证后续操作一致。第三root-color Color::Black这行必须放在循环外面。有的初学者把这一句放在 while 里面导致每次循环都强制把根染黑如果根不是当前修复路径上的节点就会破坏黑高。4. 删除修复坑比插入多得多核心是“双黑”4.1 先找到真正被删的节点删除的入口是找到 key 对应的节点。如果目标节点有两个孩子直接删除它会留下两个子树的拼接问题所以通常的做法是找到它的中序后继用后继的 key、value 覆盖目标节点然后删除后继节点。这样实际被物理删除的节点最多只有一个孩子问题大幅简化。这里有一个容易忽略的点当后继节点就是目标节点的右孩子时指针处理略有不同。CLRS 里的标准做法是先判断y是否等于z-right如果不等才先 transplant 后继的右子树。逻辑上要保证替换过程中不会丢失子树指针。删除时还要记录被删除节点的原始颜色因为只有删除黑色节点才会导致黑高失衡。如果被删除节点是红色那么各路径的黑高都没变不需要修复。4.2 双黑一次黑高失衡的“债”先看双黑问题。假设被删除的黑色节点是 z顶替它位置的节点是 x。如果 z 是黑色那么原本经过 z 的路径上就少了一个黑色节点。为了描述这个“债务”我们把 x 标记为“双黑”——它原本的颜色之上还背负着一层额外的黑。修复的目标就是把这层额外的黑传递出去直到遇到红色节点把它染黑或者一路推到根节点债务清零。所以双黑不是真的存在一种叫“双黑”的颜色开关它只是帮助我们理解修复逻辑的抽象概念。真正的代码里我们用while (x ! root x-color Color::Black)来判断“x 还在背负债务”。如果 x 本身是红色循环会退出最后把它染黑债务就还清了。4.3 五种修复场景的判断顺序删除修复的代码分支很多但核心原则是固定的从被删除节点的位置 x 出发看它的兄弟节点 w 的颜色再根据 w 的孩子颜色分支。常见的四种情况以 x 是左孩子为例兄弟 w 是红色把 w 染黑、父节点染红左旋父节点。这一步把问题转化为兄弟是黑色的情况因为红兄弟经过旋转之后变成了 x 的新兄弟而且新兄弟是黑的。兄弟 w 是黑色且 w 的两个孩子都是黑色把 w 染红把债务上移给父节点令 x parent。这是因为 x 和 w 两条路径都少一个黑把 w 也变成“欠债”节点后父节点变成双黑问题向上传递。兄弟 w 是黑色w 的左孩子是红色、右孩子是黑色把 w 染红w 的左孩子染黑右旋 w。这一步把问题转化为第 4 种情况。兄弟 w 是黑色w 的右孩子是红色把 w 染成父节点颜色父节点染黑w 的右孩子染黑左旋父节点令 x root 结束循环。x 是右孩子时完全镜像对称。下面是完整的删除修复代码void eraseFixup(Node* x) { while (x ! root x-color Color::Black) { if (x x-parent-left) { Node* w x-parent-right; if (w-color Color::Red) { w-color Color::Black; x-parent-color Color::Red; rotateLeft(x-parent); w x-parent-right; } if (w-left-color Color::Black w-right-color Color::Black) { w-color Color::Red; x x-parent; } else { if (w-right-color Color::Black) { w-left-color Color::Black; w-color Color::Red; rotateRight(w); w x-parent-right; } w-color x-parent-color; x-parent-color Color::Black; w-right-color Color::Black; rotateLeft(x-parent); x root; } } else { // x 是右孩子镜像处理 Node* w x-parent-left; if (w-color Color::Red) { w-color Color::Black; x-parent-color Color::Red; rotateRight(x-parent); w x-parent-left; } if (w-right-color Color::Black w-left-color Color::Black) { w-color Color::Red; x x-parent; } else { if (w-left-color Color::Black) { w-right-color Color::Black; w-color Color::Red; rotateLeft(w); w x-parent-left; } w-color x-parent-color; x-parent-color Color::Black; w-left-color Color::Black; rotateRight(x-parent); x root; } } } x-color Color::Black; }这里有个细节要特别注意删除修复里对 w 的左孩子和右孩子访问时w 可能是 NIL 吗不会。因为如果 x 是左孩子兄弟 w 如果不存在NIL那么父节点左路径黑高和右路径黑高不同这棵红黑树本身就是非法的。所以只要树合法w 必然是真实节点或者至少拥有颜色判断能力。但 w 的孩子完全可能是 NIL代码里访问w-left-color是安全的因为 NIL 就是黑色。eraseFixup 结束后还要把 x 染黑。这是因为循环退出时 x 可能已经被赋值为 root而 root 必须是黑色或者 x 本身是红色染黑后债务正好清零。4.4 删除时最容易写错的地方删除操作远比插入复杂主要错在三处。第一没有区分“后继是右孩子本身”和“后继在右子树的深处”这两种情况。在后继不是 z 的右孩子时要把后继的右子树先 transplant 上去再把 z 的右子树接给后继。这一步被很多人直接省略导致删除后子树丢失。第二transplant 函数里最后一行v-parent u-parent是无条件执行的。但如果 v 是 NIL很多初学者怕给 NIL 赋 parent 导致问题就跳过这行结果 NIL 的 parent 还是旧值删除修复里判断x x-parent-left时会出错。正确的做法是v 的 parent 必须无条件更新因为 NIL 也是树的一部分。第三删除一个红色节点时根本不需要调用 eraseFixup但很多人会统一调用导致 x 是一个普通黑节点却进入修复循环白白做很多无效操作。记住只有被删除节点颜色为黑时才需要修复。5. 完整实现与测试验证拿数据说话5.1 合并头文件与核心注释到这里前面的所有片段可以合并成一棵完整的红黑树了。为了让你能直接跑起来我把关键部分拼成一个可用的类包含 insert、erase、find、中序遍历和合法性验证。完整的模板代码较长这里给一个精简版函数体里做了必要的注释#include iostream #include functional #include vector enum class Color { Red, Black }; template typename K, typename V, typename Compare std::lessK class RBTree { private: struct Node { K key; V value; Color color; Node* left; Node* right; Node* parent; Node(const K k, const V v) : key(k), value(v), color(Color::Red), left(nullptr), right(nullptr), parent(nullptr) {} }; Node* root; Node* nil; Compare comp; size_t count_; void initNil() { nil new Node(K(), V()); nil-color Color::Black; nil-left nil-right nil-parent nil; } void clear(Node* x) { if (x nil) return; clear(x-left); clear(x-right); delete x; } Node* minimum(Node* x) const { while (x-left ! nil) x x-left; return x; } void rotateLeft(Node* x) { Node* 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; } void rotateRight(Node* x) { Node* y x-left; x-left y-right; if (y-right ! nil) y-right-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-right x; x-parent y; } void insertFixup(Node* z) { while (z-parent-color Color::Red) { if (z-parent z-parent-parent-left) { Node* uncle z-parent-parent-right; if (uncle-color Color::Red) { z-parent-color Color::Black; uncle-color Color::Black; z-parent-parent-color Color::Red; z z-parent-parent; } else { if (z z-parent-right) { z z-parent; rotateLeft(z); } z-parent-color Color::Black; z-parent-parent-color Color::Red; rotateRight(z-parent-parent); } } else { Node* uncle z-parent-parent-left; if (uncle-color Color::Red) { z-parent-color Color::Black; uncle-color Color::Black; z-parent-parent-color Color::Red; z z-parent-parent; } else { if (z z-parent-left) { z z-parent; rotateRight(z); } z-parent-color Color::Black; z-parent-parent-color Color::Red; rotateLeft(z-parent-parent); } } } root-color Color::Black; } void transplant(Node* u, Node* v) { if (u-parent nil) root v; else if (u u-parent-left) u-parent-left v; else u-parent-right v; v-parent u-parent; } void eraseFixup(Node* x) { while (x ! root x-color Color::Black) { if (x x-parent-left) { Node* w x-parent-right; if (w-color Color::Red) { w-color Color::Black; x-parent-color Color::Red; rotateLeft(x-parent); w x-parent-right; } if (w-left-color Color::Black w-right-color Color::Black) { w-color Color::Red; x x-parent; } else { if (w-right-color Color::Black) { w-left-color Color::Black; w-color Color::Red; rotateRight(w); w x-parent-right; } w-color x-parent-color; x-parent-color Color::Black; w-right-color Color::Black; rotateLeft(x-parent); x root; } } else { Node* w x-parent-left; if (w-color Color::Red) { w-color Color::Black; x-parent-color Color::Red; rotateRight(x-parent); w x-parent-left; } if (w-right-color Color::Black w-left-color Color::Black) { w-color Color::Red; x x-parent; } else { if (w-left-color Color::Black) { w-right-color Color::Black; w-color Color::Red; rotateLeft(w); w x-parent-left; } w-color x-parent-color; x-parent-color Color::Black; w-left-color Color::Black; rotateRight(x-parent); x root; } } } x-color Color::Black; } public: RBTree() : root(nullptr), count_(0) { initNil(); root nil; } ~RBTree() { clear(root); delete nil; } size_t size() const { return count_; } bool empty() const { return count_ 0; } void insert(const K key, const V value) { Node* z new Node(key, value); Node* y nil; Node* x root; while (x ! nil) { y x; if (comp(z-key, x-key)) x x-left; else x x-right; } z-parent y; if (y nil) root z; else if (comp(z-key, y-key)) y-left z; else y-right z; z-left z-right nil; z-color Color::Red; insertFixup(z); count_; } bool find(const K key) const { Node* cur root; while (cur ! nil) { if (comp(key, cur-key)) cur cur-left; else if (comp(cur-key, key)) cur cur-right; else return true; } return false; } bool erase(const K key) { Node* z root; while (z ! nil) { if (comp(key, z-key)) z z-left; else if (comp(z-key, key)) z z-right; else break; } if (z nil) return false; Node* y z; Node* x; Color y_original_color y-color; if (z-left nil) { x z-right; transplant(z, z-right); } else if (z-right nil) { x z-left; transplant(z, z-left); } else { y minimum(z-right); y_original_color y-color; x y-right; if (y-parent z) { x-parent y; } else { 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; } if (y_original_color Color::Black) { eraseFixup(x); } delete z; --count_; return true; }