如果你读过 STL 里 map 的实现或者翻过 Linux 内核的定时器管理、Nginx 的 epoll 超时集合会发现这些硬骨头底层都用同一个数据结构红黑树。它不像 AVL 树那样追求绝对平衡也不像普通二叉搜索树那样随时可能退化成链表而是用一种巧妙的染色约束把树高稳定在 log2(n) 级别。这篇文章我会先用图把红黑树的核心思想拆开讲透再给出一份可以直接编译运行的 C 语言实现核心部分 200 行左右适合已经会写二叉树、想彻底搞懂平衡数据结构原理的读者。红黑树的原理本身不难难的是网上大部分资料要么只讲概念不给代码要么甩出一大段代码却不解释背后的为什么。这次我换一个讲法先说清楚红黑树到底在解决什么问题再讲五条性质怎么理解然后一步一步推导插入和删除的修复过程最后给出完整 C 语言实现和验证方法。看完之后你会发现红黑树就是旋转和变色两种动作的组合剩下的事情全是分类讨论。1. 为什么放弃完美平衡红黑树却成了工程标配1.1 二叉搜索树最大的坑有序插入直接退化成链表普通二叉搜索树BST有一个很直观的性质左子树所有节点小于根右子树所有节点大于根插入和查找时通过比较不断缩小范围理想情况下每次丢掉一半节点复杂度 O(log n)。但理想情况是有前提的——插入序列必须足够随机。一旦数据有序进场比如依次插入 1、2、3、4、5树就会歪成一条只有右子树的直线1(B) \ 2 \ 3 \ 4 \ 5这种形态下查找 5 要从根一路走 5 次复杂度退化成 O(n)。数据量一大性能直接崩盘。更麻烦的是你没法保证业务数据永远足够随机所以工程上必须用某种机制让树保持平衡。1.2 严格平衡的 AVL 树为什么不够用AVL 树的做法是严格要求任意节点的左右子树高度差不超过 1也就是绝对平衡。这种约束能让查询稳定在 O(log n)但它有个代价插入和删除时为了恢复平衡可能需要频繁旋转而且旋转是自底向上反复执行的。你想想在高频插入、删除的场景下维护绝对平衡的成本是很高的。数据库索引、内存分配器这类场景往往读多写少AVL 还能扛但像内核定时器、epoll 事件管理这种动不动就插入、删除、更新的场景AVL 换来的那一点查询优势远不够抵消频繁旋转的开销。红黑树聪明就聪明在它放弃了绝对平衡转而用一套更宽松的约束把树高控制在一个可接受的范围内——最长路径不超过最短路径的两倍。查询依然接近 O(log n)但插入和删除需要调整的次数大幅减少。1.3 三种平衡方案的性价比对比数据结构树高上限查询插入删除实现复杂度典型场景BSTO(n)O(n)O(n)O(n)低教学示例、规模受控的场景AVL1.44·log2(n)O(log n)O(log n) 但旋转频繁O(log n) 但旋转频繁中读多写少的字典查询红黑树2·log2(n)O(log n)O(log n) 旋转少O(log n) 旋转少中高Linux内核、STL map、Nginx、Java TreeMap所以你会看到越是追求通用的基础组件越倾向选红黑树。它不是某一项指标最极致而是把查询、插入、删除、实现成本这几项加权之后综合得分最高。这也是我推荐每个写 C 的开发者都手写一遍红黑树的原因——写完你就理解了为什么全世界的基础软件都在用它。2. 五条性质的记忆锚点每一条都在堵漏洞2.1 先背五个约束再理解约束的意义红黑树本质上还是一棵二叉搜索树它只是额外多了 5 条染色规则每个节点非红即黑。根节点是黑色。每个叶子节点NIL是黑色。注意这里的叶子是哨兵节点不是普通节点。红色节点的两个子节点必须是黑色换句话说不能出现连续两个红色节点。从任意节点到其每个叶子节点的路径上经过的黑色节点数量相同。很多人背完这五条就结束了然后开始怀疑人生这跟我有什么关系其实这五条不是随机拼凑的它们环环相扣。性质 2 保证根稳定性质 3 让所有空指针都统一表示性质 4 限制红节点不能连坐性质 5 保证黑节点的分布均匀。把这四个堵住了整个树的高度就不会失控。2.2 为什么最长路径不超过最短路径两倍这是理解红黑树平衡性最关键的一步。由性质 5任意路径上的黑色节点数相同设为 h。再看性质 4红色节点不能相邻这意味着同一条路径上红色节点最多只能和黑色节点交替出现红节点的数量不可能超过黑色节点数量。所以极端情况下一条最短路径全是黑色长度就是 h一条最长路径是黑红黑红交替节点数是 2h。于是任何路径的长度都不可能超过最短路径的两倍。这就是红黑树平衡性的由来——它不是强行把树压成满二叉树而是通过颜色分布把树高限制在 O(log n) 级别。你可以用一个小类比黑色节点是公司的正式员工红色节点是外包临时工。制度规定临时工头上必须有个正式工盯着红节点父必须是黑每个部门从头到脚正式员工的数量必须一样多。这样一来就算临时工招得再多任何一条汇报链的长度也顶多是正式工链的两倍。整个组织的层级不会失控。所谓松约束带来低成本就是这么回事。3. 左旋右旋红黑树唯二的物理动作3.1 旋转到底旋的是什么红黑树的插入和删除修复本质上就是两类操作变色、旋转。变色好理解把节点的颜色从红变黑或从黑变红。旋转则是调整节点位置用来搬动局部结构。左旋的意思是以某个节点 x 为轴心把它的右子 y 提升上来x 变成 y 的左子树y 原来的左子树转交给 x 当新的右子树。右旋完全对称以 x 为轴心把它的左子 y 提升上来x 变成 y 的右子树y 原来的右子树转交给 x 当新的左子树。我用文本树示意一下左旋前和左旋后左旋前 左旋后 x(B) y(B) / \ / \ A y(R) x(R) C / \ / \ B C A B看到没旋转只改变了三个节点之间的父子关系没有改变中序遍历的顺序A、x、B、y、C 这个顺序在旋转前后完全一致。这一点极其重要——它保证了旋转不会破坏二叉搜索树的基本排序性质。3.2 旋转代码到底在改哪几组指针很多人写旋转容易头晕是因为指针太多。其实只需要盯住三组关系x 的右指针指向 y 的左子树左旋场景。被旋转上来的 y 的父亲指针指向 x 原来的父亲并让 x 的父亲节点正确指向 y。y 的左指针指向 xx 的父亲指针指向 y。下面这段是左旋的 C 代码配合注释看void leftRotate(RBTree *t, RBNode *x) { // 第1步y是x的右孩子y的左子树beta要过继给x RBNode *y x-right; x-right y-left; if (y-left ! t-nil) y-left-parent x; // 第2步y顶替x的位置成为x父节点的孩子 y-parent x-parent; if (x-parent t-nil) t-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; }右旋就是完全对称的镜像操作。旋转本身是 O(1) 的因为它只动了常数量级的指针。真正消耗 O(log n) 的是修复过程中可能需要沿着从插入点/删除点到根的路径一路旋转但每次操作都是 O(1)路径长度是树高所以整体复杂度还是对数级别。3.3 为什么插入修复最多只需要两次旋转这是一个非常反直觉的结论插入操作虽然可能触发多次变色但真正发生旋转的次数最多两次。因为插入修复一共有三种情况第一种叔叔是红色只变色不上旋把矛盾向上抛第二种叔叔黑色当前节点是右孩子旋转一次后变成第三种第三种叔叔黑色当前节点是左孩子旋转一次结束。一旦执行了第二种或第三种循环就会退出后面全是给根染黑的收尾动作。明白这层关系你写代码的时候节奏感会强很多。4. 插入修复的三个 Case给新红点一个合法身份4.1 新节点为什么必须是红色插入一个新节点时把它染成红色有两个好处不会破坏性质 5黑色节点数相同。如果一开始就染黑那这条路径凭空多了一个黑节点后面所有路径都可能要调整代价太大。最多只会破坏性质 4红节点不能有红子节点。因为新节点的父亲可能恰好也是红色。所以插入后的修复目标就一个消除连续红节点。如果新节点 z 的父亲是黑色那万事大吉什么都不用改就怕父亲也是红的。下面按z 的父亲是祖父的左孩子这一半来拆解另一半完全对称。4.2 Case 1叔叔是红色只变色不上旋先看场景z 是红色z 的父亲是红色z 的叔叔也是红色。此时祖父必然是黑色否则早就违反性质 4 了。我们把父亲和叔叔都染黑把祖父染红然后把 z 指向祖父继续向上检查。祖父(B) 祖父(R) / \ 变色后 / \ 父(R) 叔(R) ------ 父(B) 叔(B) / z(R) z(R)为什么要把祖父染红因为祖父这条路径的黑色节点数不能变。父亲和叔叔各从红变黑等于这两条分支各多了一个黑那祖父就得从黑变红把多出来的黑吐回去这样从祖父到下面各叶子路径的黑高才保持不变。但祖父变成红又可能导致更上层的连续红节点所以要把 z 上移两层继续检查。这就是所谓矛盾上抛。4.3 Case 2 和 Case 3叔叔是黑色必须旋转当叔叔是黑色时只靠变色解决不了问题因为父亲变黑会使得父亲分支的黑高度增加 1而叔叔分支没变性质 5 被破坏。这时必须先做旋转。如果 z 是父亲的右孩子那形态是之字形祖父、父亲、新节点不在一条直线上。我们先把 z 和父亲做一次左旋把 z 转成父亲的左孩子逻辑上 z 和父亲互换位置然后走 Case 3。Case 3 的形态是一字形z 是父亲的左孩子。操作分两步父亲染黑祖父染红。对祖父做一次右旋。旋转之后的效果是把红祖父放到了右边路径上同时通过换色把原先的父亲现在的新祖父变成黑色整棵子树重新满足所有性质并且树高也恢复了。祖父(B) 父(B) / \ 右旋后 / \ 父(R) t(T) ------ z(R) 祖父(R) / \ z(R) t(T)这里 t(T) 只是表示一个子树占位。由于旋转不会改变中序顺序所以整体等于把红父亲红 z这组连续红节点拆开让黑色父亲坐镇顶部。4.4 插入修复的完整 C 代码void insertFixup(RBTree *t, RBNode *z) { while (z-parent-color RED) { if (z-parent z-parent-parent-left) { RBNode *y z-parent-parent-right; // 叔叔 if (y-color RED) { // Case 1叔叔红色变色后矛盾上移 z-parent-color BLACK; y-color BLACK; z-parent-parent-color RED; z z-parent-parent; } else { // Case 2叔叔黑色z 在右侧先左旋变成 Case 3 if (z z-parent-right) { z z-parent; leftRotate(t, z); } // Case 3父亲染黑祖父染红右旋祖父 z-parent-color BLACK; z-parent-parent-color RED; rightRotate(t, z-parent-parent); } } else { // 对称逻辑父节点是祖父的右孩子 RBNode *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(t, z); } z-parent-color BLACK; z-parent-parent-color RED; leftRotate(t, z-parent-parent); } } } t-root-color BLACK; // 根永远保持黑色 }注意循环结束后根节点强制染黑。即使某轮修复把根染红了最后这一步也能保证性质 2。5. 删除修复所有麻烦都源于少了一个黑5.1 用替身思想化繁为简删除的难点不在于找到要删的节点而在于删完之后如何保持红黑性质。这里有一个非常经典的化简思路先找替身。如果被删除节点 z 最多只有一个非空子节点那直接让它的唯一子节点或 NIL顶替它的位置。如果 z 有两个非空子节点就不能直接删而是找 z 的后继 y右子树中最小的节点把 y 的值拷贝给 z然后删除 y。因为 y 是右子树最小节点所以 y 不可能有左孩子最多只有一个右孩子。于是问题又转化成了删一个最多只有一个孩子的节点。这样统一之后真正要处理的删除永远是一个最多只有一个非空子节点的节点。这个简化极其重要它把复杂的删除场景全部收敛到一个统一流程里。5.2 双重黑删除修复的核心思想如果我们删掉一个黑色节点那么这条路径上就少了一个黑色节点性质 5 被破坏。为了在思维上方便可以理解为顶替上来的节点 x 获得了双重黑即它多背了一份黑债需要把欠下的黑色补回来。这里必须说清楚普通节点要么红要么黑不存在物理上的双重黑这只是修复过程中的概念。修复的目标就是还债——通过变色和旋转让 x 把多的一份黑债转移出去直到它变成普通黑色或者一路转移到根节点。如果 x 是红色直接染黑就能还清如果 x 是黑色就得具体分四种情况。5.3 四种情况的递进从兄弟身上借黑删除修复的四个 Case描述的是节点 x 是双重黑时如何处理。为了叙述方便假设 x 是父亲 p 的左孩子w 是 x 的兄弟。只需要看半边另半边镜像对称。Case 1兄弟 w 是红色。把兄弟染黑、父亲染红对父亲左旋。旋完之后 x 的新兄弟变成了原先 w 的左孩子黑色问题转化为后面几种兄弟黑的情况。p(B) w(B) / \ 左旋 p / \ x(2B) w(R) ------ p(R) C / \ / \ A B x(2B) A为什么这样转化有意义红色兄弟的存在会挡住后面操作的路径我们先把红色兄弟洗成黑色家族后续才好统一处理。这一步只是变换形态目的是让问题落入可收尾的场景。Case 2兄弟 w 是黑色且 w 的两个孩子都是黑色。这时把 w 染红让 x 上移到父节点。逻辑是w 是黑的它两个孩子也是黑的那就把 w 直接变红等于从这条路径减去一个黑色刚好和 x 多出的黑债抵消一部分。但这样 x 的父节点这一层又少了黑所以把 x 指向父节点让父节点成为新的欠债人继续循环。如果父节点原来是红色循环退出后把它染黑债就还清了。Case 3兄弟 w 是黑色w 的左孩子是红色、右孩子是黑色。这是为了进入 Case 4 前的过渡形态。做法是把 w 的红色左孩子染黑w 染红对 w 右旋。旋转后x 的新兄弟变成了原先的左红孩子并且它的右孩子是红色原来 w 由于刚才染红变成红色了。目的是把一个红色侄子挪到 x 兄弟的右子树位置方便下一步统一向它借黑。Case 4兄弟 w 是黑色w 的右孩子是红色另一侧可以是任意颜色。这是修复的终态w 染成父节点 p 的颜色因为 w 要顶替 p 的位置。p 染黑。w 的右孩子染黑。对 p 左旋。这几步做完从根到 x 路径上多出的黑色债被还清整棵子树恢复红黑性质循环直接结束x 跳到根退出。要理解为什么这是终态你可以把旋转画出来看p 变黑后x 路径上补回一个黑色而右子树通过以 w 顶替 p 的颜色并右孩子变黑保持了黑色节点数量不减少。5.4 删除修复的完整 C 代码void deleteFixup(RBTree *t, RBNode *x) { while (x ! t-root x-color BLACK) { if (x x-parent-left) { RBNode *w x-parent-right; // 兄弟 if (w-color RED) { // Case 1兄弟红转为兄弟黑 w-color BLACK; x-parent-color RED; leftRotate(t, x-parent); w x-parent-right; } if (w-left-color BLACK w-right-color BLACK) { // Case 2侄子全黑兄弟染红矛盾上移 w-color RED; x x-parent; } else { if (w-right-color BLACK) { // Case 3左侄红右侄黑右旋兄弟 w-left-color BLACK; w-color RED; rightRotate(t, w); w x-parent-right; } // Case 4右侄红兄弟换色并左旋父节点收工 w-color x-parent-color; x-parent-color BLACK; w-right-color BLACK; leftRotate(t, x-parent); x t-root; } } else { // 镜像对称逻辑 RBNode *w x-parent-left; if (w-color RED) { w-color BLACK; x-parent-color RED; rightRotate(t, x-parent); w x-parent-left; } if (w-right-color BLACK w-left-color BLACK) { w-color RED; x x-parent; } else { if (w-left-color BLACK) { w-right-color BLACK; w-color RED; leftRotate(t, w); w x-parent-left; } w-color x-parent-color; x-parent-color BLACK; w-left-color BLACK; rightRotate(t, x-parent); x t-root; } } } x-color BLACK; }删除修复最多执行 3 次旋转整体还是 O(log n)。为什么比插入多因为 Case 2 的矛盾上抛可能一直向上传递直到根而每次旋转都意味着可以收尾所以旋转次数并不会像变色次数那样一路上涨。6. 手写一份能跑的 C 语言实现200 行核心逻辑6.1 设计选择用哨兵 NIL 消灭空指针判断写红黑树最常见的一个痛点是大量代码在处理 NULL 指针。为了简化这个实现里我引入了一个哨兵节点nil它永远存在、永远黑色所有原本为 NULL 的指针都指向它。这样做的好处非常直接空节点有 parent、color、left、right 四个字段代码里不需要做if (node NULL) return;这类判断。性质 3叶子都是黑色自动成立。旋转和修复函数里统一用t-nil代表空子树逻辑干净很多。代价是每个节点多占一点内存而且必须小心nil-parent会被反复赋值。但这些对学习者来说是值得的代码可读性大幅提升。6.2 完整代码下面这份代码包含插入、删除、查找、中序遍历、红黑性质校验以及随机插删的测试 main。代码风格偏紧凑去掉空行和校验辅助函数核心增删逻辑在 200 行左右。#include stdio.h #include stdlib.h #include time.h #define RED 0 #define BLACK 1 typedef struct RBNode { int key, color; struct RBNode *left, *right, *parent; } RBNode; typedef struct { RBNode *root; RBNode *nil; } RBTree; /* 创建哨兵与空树 */ RBTree *createTree() { RBTree *t (RBTree *)malloc(sizeof(RBTree)); t-nil (RBNode *)malloc(sizeof(RBNode)); t-nil-color BLACK; t-nil-left t-nil-right t-nil-parent NULL; t-root t-nil; return t; } RBNode *newNode(RBTree *t, int key) { RBNode *n (RBNode *)malloc(sizeof(RBNode)); n-key key; n-color RED; n-left n-right n-parent t-nil; return n; } /* 左旋 */ void leftRotate(RBTree *t, RBNode *x) { RBNode *y x-right; x-right y-left; if (y-left ! t-nil) y-left-parent x; y-parent x-parent; if (x-parent t-nil) t-root y; else if (x x-parent-left) x-parent-left y; else x-parent-right y; y-left x; x-parent y; } /* 右旋 */ void rightRotate(RBTree *t, RBNode *x) { RBNode *y x-left; x-left y-right; if (y-right ! t-nil) y-right-parent x; y-parent x-parent; if (x-parent t-nil) t-root y; else if (x x-parent-right) x-parent-right y; else x-parent-left y; y-right x; x-parent y; } /* 插入修复 */ void insertFixup(RBTree *t, 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(t, z); } z-parent-color BLACK; z-parent-parent-color RED; rightRotate(t, z-parent-parent); } } else { RBNode *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(t, z); } z-parent-color BLACK; z-parent-parent-color RED; leftRotate(t, z-parent-parent); } } } t-root-color BLACK; } /* 插入 */ void insert(RBTree *t, int key) { RBNode *z newNode(t, key); RBNode *y t-nil; RBNode *x t-root; while (x ! t-nil) { y x; if (z-key x-key) x x-left; else if (z-key x-key) x x-right; else { free(z); return; } } z-parent y; if (y t-nil) t-root z; else if (z-key y-key) y-left z; else y-right z; insertFixup(t, z); } RBNode *minimum(RBTree *t, RBNode *x) { while (x-left ! t-nil) x x-left; return x; } /* 用 v 子树替换 u 子树 */ void transplant(RBTree *t, RBNode *u, RBNode *v) { if (u-parent t-nil) t-root v; else if (u u-parent-left) u-parent-left v; else u-parent-right v; v-parent u-parent; } /* 删除修复 */ void deleteFixup(RBTree *t, RBNode *x) { while (x ! t-root x-color BLACK) { if (x x-parent-left) { RBNode *w x-parent-right; if (w-color RED) { w-color BLACK; x-parent-color RED; leftRotate(t, 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(t, w); w x-parent-right; } w-color x-parent-color; x-parent-color BLACK; w-right-color BLACK; leftRotate(t, x-parent); x t-root; } } else { RBNode *w x-parent-left; if (w-color RED) { w-color BLACK; x-parent-color RED; rightRotate(t, x-parent); w x-parent-left; } if (w-right-color BLACK w-left-color BLACK) { w-color RED; x x-parent; } else { if (w-left-color BLACK) { w-right-color BLACK; w-color RED; leftRotate(t, w); w x-parent-left; } w-color x-parent-color; x-parent-color BLACK; w-left-color BLACK; rightRotate(t, x-parent); x t-root; } } } x-color BLACK; } /* 删除 */ void deleteNode(RBTree *t, int key) { RBNode *z t-root; while (z ! t-nil) { if (z-key key) break; if (key z-key) z z-left; else z z-right; } if (z t-nil) return; RBNode *y z; RBNode *x; int y_original_color y-color; if (z-left t-nil) { x z-right; transplant(t, z, z-right); } else if (z-right t-nil) { x z-left; transplant(t, z, z-left); } else { y minimum(t, z-right); y_original_color y-color; x y-right; if (y-parent z) { x-parent y; } else { transplant(t, y, y-right); y-right z-right; y-right-parent y; } transplant(t, z, y); y-left z-left; y-left-parent y; y-color z-color; } free(z); if (y_original_color BLACK) deleteFixup(t, x); } /* 查找 */ RBNode *search(RBTree *t, int key) { RBNode *x t-root; while (x ! t-nil) { if (key x-key) return x; if (key x-key) x x-left; else x x-right; } return t-nil; } /* 中序遍历 */ void inorder(RBTree *t, RBNode *n) { if (n t-nil) return; inorder(t, n-left); printf(%d(%s) , n-key, n-color RED ? R : B); inorder(t, n-right); } /* 校验红黑性质返回黑高ok 置 0 表示违反 */ int validate(RBTree *t, RBNode *n, int *ok) { if (n t-nil) return 1; int l validate(t, n-left, ok); int r validate(t, n-right, ok); if (l ! r) *ok 0; if (n-color RED) { if (n-left-color RED || n-right-color RED) *ok 0; } return l (n-color BLACK); } int main() { srand((unsigned)time(NULL)); RBTree *t createTree(); int i, key, op; /* 随机插入并验证 */ for (i 0; i 1000; i) { key rand() % 5000; insert(t, key); int ok 1; validate(t, t-root, ok); if (!ok) { printf(insert validate failed at %d\n, i); return 1; } } /* 随机混合插入、删除并验证 */ for (i 0; i 5000; i) { key rand() % 5000; op rand() % 2; if (op) insert(t, key); else deleteNode(t, key); int ok 1; validate(t, t-root, ok); if (!ok) { printf(mixed validate failed at %d\n, i); return 1; } } insert(t, 42); insert(t, 17); insert(t, 88); inorder(t, t-root); printf(\n); RBNode *r search(t, 42); if (r ! t-nil) printf(found 42\n); int ok 1; validate(t, t-root, ok); printf(validate: %s\n, ok ? pass : fail); return 0; }6.3 自己动手验证黑高一致是关键指标这份代码里最核心的校验函数是validate。它递归统计每棵子树的黑色高度然后判断左右是否相等同时检查红色节点是否有红色子节点。如果你自己加需求比如要支持重复 key那插入的分支判断要小心处理如果你要删除指定 key 的节点注意先search或直接在deleteNode里从根往下找。我在实际测试中发现一个很容易被忽略的地方删除两个子节点的分支里如果y恰好是z的直接右孩子x-parent y必须显式赋值。因为这时候x是y的右子树如果不设置x-parent后面deleteFixup从x往上找父节点时可能拿到错误指针。这行看着多余实际上缺了会出大问题。6.4 一个常见误区变黑就能恢复性质变红不一定用这份代码反复调试之后我最大的体会是很多人以为出现红红冲突把子节点变黑就完事了但这样会立刻破坏性质 5。红黑树修复的精髓是一举两得既要消除红红冲突又不能改变任意路径上的黑色节点数。所以你会发现插入修复里凡是把父变黑的操作都会伴随祖父变红或者旋转补偿让黑高在局部达到平衡。想明白这层关系红黑树就真的拿下了。最后再分享一个调试技巧不要只测插入不测删除。插入修复只有三种 Case删除修复有四种 Case 和大量镜像分支每一个分支都可能因指针细节出错。建议用一个循环不断随机插入删除每次操作后调用validate校验整棵树是否满足红黑性质。只要有一次校验失败说明某个分支的修复逻辑有问题。我就是靠这个办法把一支看起来没问题的错误实现从几千次随机操作中揪出来的。