红黑树这个数据结构在 C 后端和基础架构岗位的面试里几乎成了标配考点。C 标准库里的map、multimap、set、multiset底层就是红黑树Linux 内核的调度器、内存管理里也有它的身影。你只要翻几家公司的后端 JD十有八九会把红黑树写进加分项面试现场手写红黑树的概率比你想象中高得多。这篇博文我打算用图解的方式把它彻底讲透从 5 条性质讲起把左旋右旋、插入修复、删除修复全部吃透再给出一份可以直接跑的 C 实现最后把这些年我面试别人时最常追问的问题和答题要点一并整理出来。先把丑话说在前面红黑树不是一道“背熟性质就能写出来”的题。我见过太多候选人能把五条性质背得滚瓜烂熟一让他们在白板上写删除修复整个人就卡住了。所以这篇文章不打算只给结论每一处旋转、变色都会解释为什么这么干并且会把容易踩的坑标出来。读完之后你不仅能手写出来还能说清楚每一步背后的取舍这才是面试官真正想看到的。1. 面试官为什么总爱考红黑树1.1 红黑树到底解决什么问题普通二叉搜索树BST的问题在于它的复杂度完全依赖输入顺序。拿同一组数据举例如果按7, 3, 18, 10这样的顺序插入树还比较像样但如果按1, 2, 3, 4, 5, 6递增插入BST 会直接退化成一条链表。此时查找一个元素的最坏情况要遍历所有结点时间复杂度从理想的O(log n)恶化到O(n)。红黑树本质上还是一棵二叉搜索树但它额外给每个结点增加了红黑颜色并通过一组规则约束整棵树的形态保证从根到任意叶子结点的路径不会比最短路径长一倍以上。这个约束让树的高度始终保持在O(log n)查找、插入、删除都可以在最多对数时间内完成。简单理解BST 是“可能歪”的树红黑树是“保证不会歪太狠”的树。打个比方。普通二叉搜索树就像一条没有任何秩序管理的排队队伍谁都可以插到自己喜欢的位置最后队伍可能扭成一团。红黑树等于是给每个人发了一张红色或黑色的牌子并且定了几条纪律红色牌子不能连续出现每条分支出口上的黑色牌子数量必须一样。有了这几条队伍再怎么插人整体形状都不会失控。1.2 五条规则和“黑高”的直觉红黑树的全部规则就下面五条每个结点要么是红色要么是黑色。根结点必须是黑色。所有叶子结点都是黑色。这里的叶子指 NIL 哨兵结点不是普通意义上的左右孩子为空的空指针。红色结点的两个子结点都必须是黑色。换句话说不能出现连续两个红色结点。从任一结点到它每个叶子结点的所有路径包含相同数目的黑色结点。第 5 条引出了“黑高”的概念。黑高就是从某个结点出发可以不包含该结点也可以包含取决于教材定义只要整篇文章自洽就行到达叶子结点路径上的黑色结点数量。性质 5 要求同一个结点的所有叶子路径黑高一致。有了性质 4 和性质 5可以得到一个很关键的结果一条路径上红色结点数量最多不超过黑色结点数量否则就会出现连续红色。那么最长的路径无非是“黑红黑红”交替长度最多是纯黑路径的 2 倍。这个“最长不超过最短 2 倍”的约束让红黑树不需要像 AVL 那样严格追求绝对平衡也能把高度限制在O(log n)并且付出的调整代价更小。这是红黑树工程上更好用的最核心原因。2. 从零手写红黑树结点、哨兵、左旋与右旋2.1 结点定义与哨兵结点设计先定义结点。我用一个最简单的int key来表示键值实际工程中你可以换成任意可比较类型enum Color { RED, BLACK }; struct Node { int key; Color color; Node *left, *right, *parent; explicit Node(int k) : key(k), color(RED), left(nullptr), right(nullptr), parent(nullptr) {} };注意构造函数里颜色默认是RED。后面会解释为什么新结点默认红色。红黑树的代码实现里最大的坑之一在于空指针处理。如果直接用nullptr表示空子树那么删除修复时会出现大量“判空”、“取兄弟”、“看侄子颜色”的分支代码又臭又容易漏。我的做法是引入一个 NIL 哨兵结点所有原本是空指针的位置都指向它。它永远为黑色所有叶子都挂在它下面。class RBTree { private: Node* nil_; Node* root_; public: RBTree() { nil_ new Node(0); nil_-color BLACK; nil_-left nil_-right nil_; nil_-parent nullptr; root_ nil_; } ~RBTree() { clear(root_); delete nil_; } };这里有个非常容易踩的坑初始化 NIL 结点时left和right必须指向它自己而不是nullptr。为什么因为后续修复代码里经常要访问某个结点的左孩子颜色、右孩子颜色比如w-left-color。如果 NIL 的孩子是nullptr访问就崩了如果 NIL 的孩子指向自己那nil_-left-color就是黑色代码天然安全。parent则不需要指向自己因为在各种插入删除过程中NIL 的parent会被动态设置成它的实际父结点等用到时再读取。2.2 左旋与右旋旋转为什么不会破坏顺序红黑树调整的核心操作就是旋转。旋转不改变中序遍历结果只改变局部父子关系本质上是把某个结点和它的左孩子或右孩子交换上下位置同时保持二叉搜索树的有序性。左旋的示意图x y / \ / \ A y x C / \ / \ B C A B左旋时x 的右孩子 y 升上来到 x 的位置x 变成 y 的左孩子而 y 原来的左孩子 B 过继给 x 当右孩子。为什么这样不破坏有序性因为左旋前 B 在 y 的左子树满足y B x左旋后 B 成为 x 的右子树仍然满足x B y中序顺序完全没变。右旋是左旋的镜像x y / \ / \ y C A x / \ / \ A B B C代码实现void leftRotate(Node* x) { Node* y x-right; // y 是 x 的右孩子 x-right y-left; // y 的左孩子过继给 x if (y-left ! nil_) y-left-parent x; y-parent x-parent; // y 接管 x 的位置 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 变成 y 的左孩子 x-parent y; }右旋实现基本对称void rightRotate(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-right) { x-parent-right y; } else { x-parent-left y; } y-right x; x-parent y; }写旋转代码最容易漏的点是根结点更新。如果 x 本身就是根x-parent是 NIL必须把root_更新成 y否则旋转后整棵树就没根了。另一个容易漏的点是旋转前一定要确认 y 不是 NIL否则解引用会崩实际调用旋转时x 的孩子必然是真实结点所以这几段代码里不额外校验。2.3 查找、最小值与后继后面删除要用这些基础操作看起来简单但删除时要依赖它们所以先过一遍。Node* searchNode(int key) const { Node* cur root_; while (cur ! nil_ cur-key ! key) { if (key cur-key) { cur cur-left; } else { cur cur-right; } } return cur nil_ ? nullptr : cur; } Node* minimum(Node* x) const { while (x-left ! nil_) x x-left; return x; } Node* successor(Node* x) const { if (x-right ! nil_) { return minimum(x-right); } Node* y x-parent; while (y ! nil_ x y-right) { x y; y y-parent; } return y; }后继的逻辑理解透如果一个结点有右子树那么下一个比它大的结点一定是右子树里最小的那个如果没有右子树就要向上找“自己是左孩子”的祖先第一个满足这个条件的祖先就是后继。这个操作在删除“有两个孩子”的结点时很关键。3. 插入操作先按普通 BST 插再变色旋转修复3.1 为什么新结点必须是红色插入的总体思路分两步先按普通二叉搜索树的方式把新结点挂到叶子位置然后通过变色和旋转修复红黑树性质。那么新结点应该设成什么颜色如果设成黑色那么它所在路径的黑高立刻比别的路径多 1直接破坏性质 5。修复性质 5 的成本很高意味着很可能需要一路向上调整。反过来如果设成红色那么它不会影响黑高唯一可能破坏的是性质 4——红色结点的子结点不能为红也就是新结点和它的父结点碰巧都是红色时才会出问题。父红这种失衡可以通过局部变色和旋转解决成本更低。所以新结点默认红色这是经过权衡的设计不是随意定的。void insert(int key) { Node* z new Node(key); Node* y nil_; Node* x root_; while (x ! nil_) { y x; if (z-key x-key) { x x-left; } else { x x-right; } } z-parent y; if (y nil_) { root_ z; } else if (z-key y-key) { y-left z; } else { y-right z; } z-left nil_; z-right nil_; z-color RED; insertFixUp(z); }插入后新结点是红色左右孩子都指向 NIL。接下来进入修复流程insertFixUp。3.2 叔结点为红变色上推插入修复的核心对象是当前红色结点z。如果z的父结点是黑色一切正常什么都不用做。只有当父结点也是红色时才需要处理。因为红黑树不允许父红子红所以祖父结点一定是黑色。这时看叔结点的颜色。先看叔结点是红色的情况。设父为p叔为u祖父为g并且 g 是黑色g黑 / \ p红 u红 / z红此时脏的不是一处而是“p 和 z 连续红”。修复办法是把黑色从祖父 g 拉下来让 p 和 u 都变黑g 变红。这样从 g 到下面每条路径的黑色数量没有变黑高保持平衡但 g 变成了红色g 又要和它自己的父结点重新检查是否连续红所以把z上移到 g继续循环。g红 / \ p黑 u黑 / z红这也是插入修复里唯一需要向上传播的情况条件是叔结点为红。如果叔结点是黑色的处理方式完全不同。3.3 叔结点为黑先转“外侧”再旋转变色当叔结点是黑色或者不存在NIL 算黑色时不可能再靠变色把问题一次性解决需要用旋转。这里又分两种子情况以父是祖父的左孩子为例右对称同理。情况一z是父结点的内侧孩子。比如父是祖父的左孩子z 是父的右孩子。这时先把z和父做一个左旋变成外侧形态但此时 z 变成了父的父结点原来的父变成了 z 的左孩子于是需要把当前待处理的z指针换成原来的父再用下面的外侧处理。情况二z是父结点的外侧孩子。比如父是祖父的左孩子z 也是父的左孩子。操作是父变黑祖父变红然后对祖父做一次右旋。旋转后原父成为子树的新根黑色祖父变红后成为原父的右孩子整棵子树的黑高保持不变且不再存在连续红。调整前: g黑 / \ p红 T黑 / z红 调整后: p黑 / \ z红 g红 \ T黑插入修复最多产生两次旋转内侧情况先旋转一次变成外侧外侧情况再旋转一次完成修复叔红的上推循环本身不旋转。因此红黑树插入操作的旋转次数上界是 2这是一个经常被面试官追问的点。3.4 插入修复的 C 实现void insertFixUp(Node* z) { while (z-parent-color RED) { if (z-parent z-parent-parent-left) { Node* y z-parent-parent-right; // 叔结点 if (y-color RED) { // 情况1叔红变色上推 z-parent-color BLACK; y-color BLACK; z-parent-parent-color RED; z z-parent-parent; } else { // 情况2z 是内侧孩子先转成外侧 if (z z-parent-right) { z z-parent; leftRotate(z); } // 情况3外侧孩子变色 右旋祖父 z-parent-color BLACK; z-parent-parent-color RED; rightRotate(z-parent-parent); } } else { // 镜像父是祖父的右孩子 Node* 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; }循环结束后特别把根染黑。这一步很有必要可能有一路变色把根变成了红色而性质 2 要求根必须是黑色最后强制兜底。由于整棵树的每条路径黑色数量不减把根从红变黑也不会破坏性质 5所以直接染黑永远安全。4. 删除操作传说中的硬骨头4.1 删除一个结点的 BST 操作删除比插入复杂因为它不仅要删还要在删完之后处理可能被破坏的性质 5。先回顾普通 BST 的删除逻辑如果待删结点没有左孩子直接用右孩子顶替它。如果待删结点没有右孩子直接用左孩子顶替它。如果两个孩子都在找右子树的最小结点作为后继用后继值覆盖待删结点然后转去删除后继。因为右子树最小结点一定有左子树为空所以这种情况会退化到前面某一种。红黑树删除也是这个骨架但要多记录两个重要变量实际被移动位置的结点y、实际被移动位置之前的颜色。如果y原本是黑色删除或者移动后那条路径少了一个黑色必须执行修复。void remove(int key) { Node* z searchNode(key); if (z nullptr) return; Node* y z; Node* x; Color yOriginalColor 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); yOriginalColor 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 (yOriginalColor BLACK) { removeFixUp(x); } delete z; }transplant负责把一棵子树顶到另一棵子树的位置上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; }删除代码里y是真正被删除或者被移动的结点z是键值对要被移除的结点两者千万别搞混。一个常见的错误是最后delete y结果把原来树上还在的结点删了树结构直接乱掉。4.2 “双黑”到底是什么意思如果一个黑色结点被删掉相当于这条路径少了一个黑色。为了直观理解修复过程可以把顶替上来的结点x看成“双黑”它原本有自己的颜色同时还要替被删的黑色结点多背一个黑色。修复的目标就是通过旋转和变色把这个额外的黑色从某个红色结点转移到树上某个位置后消掉或者把额外黑色上推到根。这个说法虽然不严谨但非常好用。面试时你说“现在 x 是双黑需要通过几种情况消掉双黑”面试官通常都会点头因为他们知道你已经理解了删除修复的本质。4.3 兄弟结点的四种情况与修复删除修复循环的条件是x不是根并且x是黑色准确定义是 x 的颜色为黑色或者 x 用“双黑”理解。每次循环先判断x是父结点的左孩子还是右孩子然后取出兄弟结w分四种情况处理。下面以x是左孩子为例。四种情况的处理动作如下表情况现象处理动作情况1兄弟 w 为红色w 变黑父变红左旋父更新 w 后继续处理情况2w 是黑色且 w 的两个孩子都是黑色w 染红x 上移到父结点继续循环情况3w 是黑色且 w 的左孩子红、右孩子黑w 的左孩子变黑w 变红右旋 w更新 w情况4w 是黑色且 w 的右孩子红w 继承父颜色父变黑w 的右孩子变黑左旋父x 置为根结束情况1 为什么要先处理因为 w 是红色时w 的两个孩子一定是黑色但直接套用后面的黑色兄弟情况会出错。处理办法是先旋转让某个黑色的子结点成为新兄弟这样问题就转换成了“兄弟是黑色”的几种情况。情况2 的核心是“父结点吸收双重黑色”。把兄弟 w 染红相当于 w 那边也少了一个黑色父结点的左右子树重新平衡于是双重黑色上移到父结点让父结点继续承担这个额外黑色。如果父本来是红色那它变成黑色后循环结束如果父本来就是黑色那双黑继续往上走。情况3 其实是为情况4 做铺垫。兄弟 w 虽然黑但它的右孩子是黑、左孩子是红直接套情况4 的旋转不行所以先把 w 右旋一次让红孩子变成 w 的右孩子再走情况4。情况4 是最终解决的一步。通过一次旋转把兄弟路径上的黑色数量重新分配同时把 x 的额外黑色消掉循环可以直接结束。代码实现时我用了 NIL 哨兵所以比普通教材稍微多几个针对nil_的保护防止把哨兵染红。具体看这段removeFixUpvoid removeFixUp(Node* x) { while (x ! root_ x-color BLACK) { if (x x-parent-left) { Node* w x-parent-right; if (w-color RED) { // 情况1: 兄弟红 w-color BLACK; x-parent-color RED; leftRotate(x-parent); w x-parent-right; } // 兄弟为哨兵nil时认为它两个孩子都是黑色 if (w nil_ || (w-left-color BLACK w-right-color BLACK)) { // 情况2: 兄弟黑侄子全黑 if (w ! nil_) w-color RED; x x-parent; } else { if (w-right-color BLACK) { // 情况3: 左红右黑先变成情况4 w-left-color BLACK; w-color RED; rightRotate(w); w x-parent-right; } // 情况4: 右孩子红 w-color x-parent-color; x-parent-color BLACK; w-right-color BLACK; leftRotate(x-parent); x root_; } } else { // 对称情况 Node* w x-parent-left; if (w-color RED) { w-color BLACK; x-parent-color RED; rightRotate(x-parent); w x-parent-left; } if (w nil_ || (w-right-color BLACK w-left-color BLACK)) { if (w ! nil_) 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; }这里最关键的坑就是w nil_。当兄弟是哨兵 NIL 结点时它的颜色是黑左右孩子也必须是黑但如果按标准情况2 去执行w-color RED会把哨兵染红后续所有判断直接崩坏。所以这段代码里遇到兄弟为 NIL 时不修改哨兵颜色只把双重黑色上移到父结点。4.4 删除复杂度与旋转上限删除修复的循环可能一路上升到根所以整体复杂度仍是O(log n)。但真正发生旋转的次数是有限的情况1 最多一次情况3 最多一次情况4 一次后循环结束情况2 本身不旋转。因此红黑树删除操作最多只需要 3 次旋转。这一点是红黑树在工程上比 AVL 更占优势的关键原因后面也会再展开。5. 完整可运行的 C 实现与自测5.1 工具函数验证颜色规则与黑高手写红黑树不验证等于白写。我强烈建议你写一个isValid函数每次插入删除后都跑一遍把非法情况立刻暴露出来。最省事的验证方式就是递归检查下面几件事红色结点的孩子不能是红色。从任意结点出发左右叶子路径的黑高必须相同。根必须是黑色。bool isValidTree(Node* x, int height) { if (x nil_) { height 1; return true; } if (x-color RED (x-left-color RED || x-right-color RED)) { return false; } int leftH 0, rightH 0; if (!isValidTree(x-left, leftH)) return false; if (!isValidTree(x-right, rightH)) return false; if (leftH ! rightH) return false; height leftH (x-color BLACK ? 1 : 0); return true; } bool isValid() { if (root_-color ! BLACK) return false; int h 0; return isValidTree(root_, h); }这个函数检查完以后只要返回true至少证明你的树满足红黑树五条性质。我测试过程中遇到的大部分旋转写错、变色漏改都能靠它抓出来。5.2 中序遍历与控制台打印验证有序性最直接的方法是中序遍历。红黑树是二叉搜索树中序遍历结果一定是升序的。void inorder(Node* x) { if (x nil_) return; inorder(x-left); std::cout x-key (x-color RED ? (R) : (B)) ; inorder(x-right); } void inorderPrint() { inorder(root_); std::cout std::endl; }输出时用(R)和(B)标记颜色方便肉眼检查是否存在连续红。5.3 集成测试插入删除后反复验证下面这段代码可以直接编译运行作为红黑树实现的基本自测int main() { RBTree tree; std::vectorint keys {7, 3, 18, 10, 22, 8, 11, 26, 2, 6, 13}; for (int k : keys) { tree.insert(k); if (!tree.isValid()) { std::cout insert k failed std::endl; return 1; } } tree.inorderPrint(); std::cout valid after insert: tree.isValid() std::endl; std::vectorint del {3, 7, 18, 2}; for (int k : del) { tree.remove(k); if (!tree.isValid()) { std::cout remove k failed std::endl; return 1; } } tree.inorderPrint(); std::cout valid after remove: tree.isValid() std::endl; return 0; }更严格一点可以随机插入 1 到 1000 的数字再随机删除每步都调用isValid校验。我自己的习惯是再拿std::set做对拍同一个操作序列同时打到红黑树和std::set上每一步检查中序遍历结果是否完全一致。这个方法比任何单一测试都更能暴露边界问题。6. 面试追问与答题模板6.1 “有了 AVL为什么还要红黑树”这是红黑树面试中最经典的问题没有之一。AVL 树也属于自平衡二叉搜索树它通过严格的平衡因子保证左右子树高度差不超过 1查找性能理论上更稳。但 AVL 的代价在插入和删除时的调整太频繁删除时最坏可能需要O(log n)次旋转这在写多读少的场景里是很大的开销。红黑树放宽了平衡要求只保证最长路径不超过最短路径的两倍换来的是“调整成本更低”。红黑树插入最多旋转 2 次删除最多旋转 3 次虽然颜色修复的循环可能往上走但实际结构变化很少整体操作摊还下来性价比很高。维度AVL红黑树平衡程度严格左右子树高度差不超过1宽松最长不超过最短2倍查询性能略优略逊但常数差异很小插入旋转最多2次最多2次删除旋转最坏 O(log n) 次最多3次适用场景读多写少读写均衡、频繁插入删除所以工程结论很清晰C 标准库的关联容器、Linux 内核、Java 的TreeMap等大量使用红黑树因为现实场景往往是“有读有写”红黑树在读写之间取了一个更好的平衡点。6.2 “红黑树和哈希表怎么选”这道题也是高频。红黑树和哈希表都能做关联容器但适用场景差别很大。红黑树最大的优势是有序。它支持中序遍历可以按顺序输出所有元素可以快速找前驱、后继也可以做范围查询比如“找出所有大于 10 小于 50 的键”。哈希表做不到有序遍历它查找元素平均复杂度是O(1)但遍历结果是随机的。哈希表的劣势也很明显需要设计好的哈希函数处理冲突还可能发生扩容如果哈希函数选得不好或者数据被恶意构造最坏情况会退化到O(n)。红黑树没有这些问题它在任何输入下都能保证最坏O(log n)。C 里的选择其实已经给出了答案需要有序就用map/set底层红黑树不需要有序且对性能敏感就用unordered_map/unordered_set底层哈希表。面试时你可以结合这个例子回答一般能拿高分。如果再往下聊到磁盘场景还可以顺势提一下 B/B 树因为它针对磁盘多路 IO 做了优化每个结点可以存多个键能显著减少磁盘随机访问次数。6.3 面试高频追问速查表这里整理几个我面试别人时常追问的问题和对应的答题要点。追问答题要点红黑树能严格保证 O(log n) 吗不能严格到 log n但能保证树高 O(log n)因为最长路径不超过最短路径 2 倍。为什么新插入结点是红色红色不会增加黑高只可能破坏连续红修复成本低。旋转会改变二叉搜索树顺序吗不会。旋转只改变局部父子关系中序遍历顺序不变。插入最多旋转几次删除呢插入最多 2 次删除最多 3 次。根是红色怎么办修复循环结束后强制把根染成黑色因为根变黑不破坏任何性质。为什么需要 NIL 哨兵统一叶子结点的处理避免大量判空让修复代码逻辑更干净。红黑树能用来做区间查询吗能。中序遍历天然有序再配合前驱后继就能做范围遍历。这些问题本质上是考察你有没有真正理解红黑树的“原理”而不是背代码。所以我建议每写一步代码都想想这一步在性质层面解决了什么问题。7. 常见 Bug 与调试心得7.1 手写红黑树最容易踩的 5 个坑第一个坑是 NIL 哨兵的左右孩子没有指向自身。没有踩过的人可能不理解但删除修复代码里会频繁访问w-left-color这样的表达式如果 NIL 的孩子是nullptr程序直接崩。解决方法是初始化时把nil_-left nil_-right nil_写清楚。第二个坑是旋转和删除后根结点没有更新。左旋右旋里如果 x 是根必须把root_改成 ytransplant里如果 u 是根必须把root_改成 v。漏了这一步根会飘到奇怪的地方所有isValid校验都会失败。第三个坑是删除时把y和z弄混。z是键值对要删的结点y是真正被移动/删除的结点最后应该delete z。我见过不少人写成delete y结果把树上保留的结点删了内存泄漏和悬垂指针一起爆发。第四个坑是在统一哨兵设计下把 NIL 染红。删除修复的情况2 中如果兄弟是 NIL不能执行w-color RED否则哨兵变成红色所有后续判断全部失真。处理办法是单独判断兄弟是否为 NIL是的话跳过染红直接把额外黑色上推到父结点。第五个坑是修复循环没有正确向上传递。插入修复里z z-parent-parent删除修复里x x-parent这些赋值漏掉或者写错位置循环就会陷入死循环或者提前退出导致性质没修复。出现这种情况时建议手动画出当前树把z或x的移动路径标出来问题通常一眼就能看出来。7.2 推荐的自测套路红黑树这种数据结构不靠随机测试真的很难保证正确。我的自测套路一般三层第一层固定数据。插入一组已知数据肉眼观察中序遍历是不是升序isValid是否返回true。再按特定顺序删除同样验证。第二层随机数据对拍。生成几百个随机数重复执行“插入再删除”每步都校验红黑树性质和std::set的一致性。这个测试能把最常见的旋转 bug 逼出来。第三层边界构造。只插入递增序列比如1, 2, 3, ..., 100看旋转和变色是否正常只删除最大最小值删除到只剩一个结点删除不存在的键。这些边界场景最容易暴露根结点更新和 NIL 处理的问题。编译时建议加上-fsanitizeaddress红黑树代码内存操作密集AddressSanitizer 能帮你捕获释放后访问、数组越界、野指针等问题。7.3 给准备面试的朋友的建议红黑树这种东西纯看永远学不会一定得动手写。我建议的练习顺序是先默写五条性质再单独写左旋右旋然后写插入修复最后才碰删除修复。不要一上来就死记整个类那样面试时很容易脑子空白。真正面试时先在白板上把树画出来再写代码。画图有两个好处第一你自己思路更清晰第二面试官能实时看到你的思考过程。写删除修复前可以主动说一句“我把 NIL 哨兵的处理单独判断一下”面试官通常会很认可这种对边界的敏感。如果你时间紧删除修复实在背不下来也至少要能说清楚框架兄弟红先转黑兄弟黑看侄子侄子全黑就上移左红右黑先转右右红就直接旋转变色收尾。面试官更多时候想确认的是“你有没有真正理解”而不是“你代码默写得像不像原书”。能把思路说清楚再配合一个完整实现红黑树这道题基本就稳了。我自己准备红黑树时还有一个很笨但很有效的心得把插入和删除的每一条规则用中文写在一张纸上挂在显示器旁边每次写完代码就对一遍。写多了之后你会发现这些规则不是要背的条文而是一套完整的“如何在不破坏黑高的前提下调整树形”的系统。理解到这一层面试时你就不是在背红黑树而是在讲一个关于平衡的逻辑故事。
红黑树这个数据结构在 C 后端和基础架构岗位的面试里几乎成了标配考点。C 标准库里的map、multimap、set、multiset底层就是红黑树Linux 内核的调度器、内存管理里也有它的身影。你只要翻几家公司的后端 JD十有八九会把红黑树写进加分项面试现场手写红黑树的概率比你想象中高得多。这篇博文我打算用图解的方式把它彻底讲透从 5 条性质讲起把左旋右旋、插入修复、删除修复全部吃透再给出一份可以直接跑的 C 实现最后把这些年我面试别人时最常追问的问题和答题要点一并整理出来。先把丑话说在前面红黑树不是一道“背熟性质就能写出来”的题。我见过太多候选人能把五条性质背得滚瓜烂熟一让他们在白板上写删除修复整个人就卡住了。所以这篇文章不打算只给结论每一处旋转、变色都会解释为什么这么干并且会把容易踩的坑标出来。读完之后你不仅能手写出来还能说清楚每一步背后的取舍这才是面试官真正想看到的。1. 面试官为什么总爱考红黑树1.1 红黑树到底解决什么问题普通二叉搜索树BST的问题在于它的复杂度完全依赖输入顺序。拿同一组数据举例如果按7, 3, 18, 10这样的顺序插入树还比较像样但如果按1, 2, 3, 4, 5, 6递增插入BST 会直接退化成一条链表。此时查找一个元素的最坏情况要遍历所有结点时间复杂度从理想的O(log n)恶化到O(n)。红黑树本质上还是一棵二叉搜索树但它额外给每个结点增加了红黑颜色并通过一组规则约束整棵树的形态保证从根到任意叶子结点的路径不会比最短路径长一倍以上。这个约束让树的高度始终保持在O(log n)查找、插入、删除都可以在最多对数时间内完成。简单理解BST 是“可能歪”的树红黑树是“保证不会歪太狠”的树。打个比方。普通二叉搜索树就像一条没有任何秩序管理的排队队伍谁都可以插到自己喜欢的位置最后队伍可能扭成一团。红黑树等于是给每个人发了一张红色或黑色的牌子并且定了几条纪律红色牌子不能连续出现每条分支出口上的黑色牌子数量必须一样。有了这几条队伍再怎么插人整体形状都不会失控。1.2 五条规则和“黑高”的直觉红黑树的全部规则就下面五条每个结点要么是红色要么是黑色。根结点必须是黑色。所有叶子结点都是黑色。这里的叶子指 NIL 哨兵结点不是普通意义上的左右孩子为空的空指针。红色结点的两个子结点都必须是黑色。换句话说不能出现连续两个红色结点。从任一结点到它每个叶子结点的所有路径包含相同数目的黑色结点。第 5 条引出了“黑高”的概念。黑高就是从某个结点出发可以不包含该结点也可以包含取决于教材定义只要整篇文章自洽就行到达叶子结点路径上的黑色结点数量。性质 5 要求同一个结点的所有叶子路径黑高一致。有了性质 4 和性质 5可以得到一个很关键的结果一条路径上红色结点数量最多不超过黑色结点数量否则就会出现连续红色。那么最长的路径无非是“黑红黑红”交替长度最多是纯黑路径的 2 倍。这个“最长不超过最短 2 倍”的约束让红黑树不需要像 AVL 那样严格追求绝对平衡也能把高度限制在O(log n)并且付出的调整代价更小。这是红黑树工程上更好用的最核心原因。2. 从零手写红黑树结点、哨兵、左旋与右旋2.1 结点定义与哨兵结点设计先定义结点。我用一个最简单的int key来表示键值实际工程中你可以换成任意可比较类型enum Color { RED, BLACK }; struct Node { int key; Color color; Node *left, *right, *parent; explicit Node(int k) : key(k), color(RED), left(nullptr), right(nullptr), parent(nullptr) {} };注意构造函数里颜色默认是RED。后面会解释为什么新结点默认红色。红黑树的代码实现里最大的坑之一在于空指针处理。如果直接用nullptr表示空子树那么删除修复时会出现大量“判空”、“取兄弟”、“看侄子颜色”的分支代码又臭又容易漏。我的做法是引入一个 NIL 哨兵结点所有原本是空指针的位置都指向它。它永远为黑色所有叶子都挂在它下面。class RBTree { private: Node* nil_; Node* root_; public: RBTree() { nil_ new Node(0); nil_-color BLACK; nil_-left nil_-right nil_; nil_-parent nullptr; root_ nil_; } ~RBTree() { clear(root_); delete nil_; } };这里有个非常容易踩的坑初始化 NIL 结点时left和right必须指向它自己而不是nullptr。为什么因为后续修复代码里经常要访问某个结点的左孩子颜色、右孩子颜色比如w-left-color。如果 NIL 的孩子是nullptr访问就崩了如果 NIL 的孩子指向自己那nil_-left-color就是黑色代码天然安全。parent则不需要指向自己因为在各种插入删除过程中NIL 的parent会被动态设置成它的实际父结点等用到时再读取。2.2 左旋与右旋旋转为什么不会破坏顺序红黑树调整的核心操作就是旋转。旋转不改变中序遍历结果只改变局部父子关系本质上是把某个结点和它的左孩子或右孩子交换上下位置同时保持二叉搜索树的有序性。左旋的示意图x y / \ / \ A y x C / \ / \ B C A B左旋时x 的右孩子 y 升上来到 x 的位置x 变成 y 的左孩子而 y 原来的左孩子 B 过继给 x 当右孩子。为什么这样不破坏有序性因为左旋前 B 在 y 的左子树满足y B x左旋后 B 成为 x 的右子树仍然满足x B y中序顺序完全没变。右旋是左旋的镜像x y / \ / \ y C A x / \ / \ A B B C代码实现void leftRotate(Node* x) { Node* y x-right; // y 是 x 的右孩子 x-right y-left; // y 的左孩子过继给 x if (y-left ! nil_) y-left-parent x; y-parent x-parent; // y 接管 x 的位置 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 变成 y 的左孩子 x-parent y; }右旋实现基本对称void rightRotate(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-right) { x-parent-right y; } else { x-parent-left y; } y-right x; x-parent y; }写旋转代码最容易漏的点是根结点更新。如果 x 本身就是根x-parent是 NIL必须把root_更新成 y否则旋转后整棵树就没根了。另一个容易漏的点是旋转前一定要确认 y 不是 NIL否则解引用会崩实际调用旋转时x 的孩子必然是真实结点所以这几段代码里不额外校验。2.3 查找、最小值与后继后面删除要用这些基础操作看起来简单但删除时要依赖它们所以先过一遍。Node* searchNode(int key) const { Node* cur root_; while (cur ! nil_ cur-key ! key) { if (key cur-key) { cur cur-left; } else { cur cur-right; } } return cur nil_ ? nullptr : cur; } Node* minimum(Node* x) const { while (x-left ! nil_) x x-left; return x; } Node* successor(Node* x) const { if (x-right ! nil_) { return minimum(x-right); } Node* y x-parent; while (y ! nil_ x y-right) { x y; y y-parent; } return y; }后继的逻辑理解透如果一个结点有右子树那么下一个比它大的结点一定是右子树里最小的那个如果没有右子树就要向上找“自己是左孩子”的祖先第一个满足这个条件的祖先就是后继。这个操作在删除“有两个孩子”的结点时很关键。3. 插入操作先按普通 BST 插再变色旋转修复3.1 为什么新结点必须是红色插入的总体思路分两步先按普通二叉搜索树的方式把新结点挂到叶子位置然后通过变色和旋转修复红黑树性质。那么新结点应该设成什么颜色如果设成黑色那么它所在路径的黑高立刻比别的路径多 1直接破坏性质 5。修复性质 5 的成本很高意味着很可能需要一路向上调整。反过来如果设成红色那么它不会影响黑高唯一可能破坏的是性质 4——红色结点的子结点不能为红也就是新结点和它的父结点碰巧都是红色时才会出问题。父红这种失衡可以通过局部变色和旋转解决成本更低。所以新结点默认红色这是经过权衡的设计不是随意定的。void insert(int key) { Node* z new Node(key); Node* y nil_; Node* x root_; while (x ! nil_) { y x; if (z-key x-key) { x x-left; } else { x x-right; } } z-parent y; if (y nil_) { root_ z; } else if (z-key y-key) { y-left z; } else { y-right z; } z-left nil_; z-right nil_; z-color RED; insertFixUp(z); }插入后新结点是红色左右孩子都指向 NIL。接下来进入修复流程insertFixUp。3.2 叔结点为红变色上推插入修复的核心对象是当前红色结点z。如果z的父结点是黑色一切正常什么都不用做。只有当父结点也是红色时才需要处理。因为红黑树不允许父红子红所以祖父结点一定是黑色。这时看叔结点的颜色。先看叔结点是红色的情况。设父为p叔为u祖父为g并且 g 是黑色g黑 / \ p红 u红 / z红此时脏的不是一处而是“p 和 z 连续红”。修复办法是把黑色从祖父 g 拉下来让 p 和 u 都变黑g 变红。这样从 g 到下面每条路径的黑色数量没有变黑高保持平衡但 g 变成了红色g 又要和它自己的父结点重新检查是否连续红所以把z上移到 g继续循环。g红 / \ p黑 u黑 / z红这也是插入修复里唯一需要向上传播的情况条件是叔结点为红。如果叔结点是黑色的处理方式完全不同。3.3 叔结点为黑先转“外侧”再旋转变色当叔结点是黑色或者不存在NIL 算黑色时不可能再靠变色把问题一次性解决需要用旋转。这里又分两种子情况以父是祖父的左孩子为例右对称同理。情况一z是父结点的内侧孩子。比如父是祖父的左孩子z 是父的右孩子。这时先把z和父做一个左旋变成外侧形态但此时 z 变成了父的父结点原来的父变成了 z 的左孩子于是需要把当前待处理的z指针换成原来的父再用下面的外侧处理。情况二z是父结点的外侧孩子。比如父是祖父的左孩子z 也是父的左孩子。操作是父变黑祖父变红然后对祖父做一次右旋。旋转后原父成为子树的新根黑色祖父变红后成为原父的右孩子整棵子树的黑高保持不变且不再存在连续红。调整前: g黑 / \ p红 T黑 / z红 调整后: p黑 / \ z红 g红 \ T黑插入修复最多产生两次旋转内侧情况先旋转一次变成外侧外侧情况再旋转一次完成修复叔红的上推循环本身不旋转。因此红黑树插入操作的旋转次数上界是 2这是一个经常被面试官追问的点。3.4 插入修复的 C 实现void insertFixUp(Node* z) { while (z-parent-color RED) { if (z-parent z-parent-parent-left) { Node* y z-parent-parent-right; // 叔结点 if (y-color RED) { // 情况1叔红变色上推 z-parent-color BLACK; y-color BLACK; z-parent-parent-color RED; z z-parent-parent; } else { // 情况2z 是内侧孩子先转成外侧 if (z z-parent-right) { z z-parent; leftRotate(z); } // 情况3外侧孩子变色 右旋祖父 z-parent-color BLACK; z-parent-parent-color RED; rightRotate(z-parent-parent); } } else { // 镜像父是祖父的右孩子 Node* 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; }循环结束后特别把根染黑。这一步很有必要可能有一路变色把根变成了红色而性质 2 要求根必须是黑色最后强制兜底。由于整棵树的每条路径黑色数量不减把根从红变黑也不会破坏性质 5所以直接染黑永远安全。4. 删除操作传说中的硬骨头4.1 删除一个结点的 BST 操作删除比插入复杂因为它不仅要删还要在删完之后处理可能被破坏的性质 5。先回顾普通 BST 的删除逻辑如果待删结点没有左孩子直接用右孩子顶替它。如果待删结点没有右孩子直接用左孩子顶替它。如果两个孩子都在找右子树的最小结点作为后继用后继值覆盖待删结点然后转去删除后继。因为右子树最小结点一定有左子树为空所以这种情况会退化到前面某一种。红黑树删除也是这个骨架但要多记录两个重要变量实际被移动位置的结点y、实际被移动位置之前的颜色。如果y原本是黑色删除或者移动后那条路径少了一个黑色必须执行修复。void remove(int key) { Node* z searchNode(key); if (z nullptr) return; Node* y z; Node* x; Color yOriginalColor 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); yOriginalColor 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 (yOriginalColor BLACK) { removeFixUp(x); } delete z; }transplant负责把一棵子树顶到另一棵子树的位置上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; }删除代码里y是真正被删除或者被移动的结点z是键值对要被移除的结点两者千万别搞混。一个常见的错误是最后delete y结果把原来树上还在的结点删了树结构直接乱掉。4.2 “双黑”到底是什么意思如果一个黑色结点被删掉相当于这条路径少了一个黑色。为了直观理解修复过程可以把顶替上来的结点x看成“双黑”它原本有自己的颜色同时还要替被删的黑色结点多背一个黑色。修复的目标就是通过旋转和变色把这个额外的黑色从某个红色结点转移到树上某个位置后消掉或者把额外黑色上推到根。这个说法虽然不严谨但非常好用。面试时你说“现在 x 是双黑需要通过几种情况消掉双黑”面试官通常都会点头因为他们知道你已经理解了删除修复的本质。4.3 兄弟结点的四种情况与修复删除修复循环的条件是x不是根并且x是黑色准确定义是 x 的颜色为黑色或者 x 用“双黑”理解。每次循环先判断x是父结点的左孩子还是右孩子然后取出兄弟结w分四种情况处理。下面以x是左孩子为例。四种情况的处理动作如下表情况现象处理动作情况1兄弟 w 为红色w 变黑父变红左旋父更新 w 后继续处理情况2w 是黑色且 w 的两个孩子都是黑色w 染红x 上移到父结点继续循环情况3w 是黑色且 w 的左孩子红、右孩子黑w 的左孩子变黑w 变红右旋 w更新 w情况4w 是黑色且 w 的右孩子红w 继承父颜色父变黑w 的右孩子变黑左旋父x 置为根结束情况1 为什么要先处理因为 w 是红色时w 的两个孩子一定是黑色但直接套用后面的黑色兄弟情况会出错。处理办法是先旋转让某个黑色的子结点成为新兄弟这样问题就转换成了“兄弟是黑色”的几种情况。情况2 的核心是“父结点吸收双重黑色”。把兄弟 w 染红相当于 w 那边也少了一个黑色父结点的左右子树重新平衡于是双重黑色上移到父结点让父结点继续承担这个额外黑色。如果父本来是红色那它变成黑色后循环结束如果父本来就是黑色那双黑继续往上走。情况3 其实是为情况4 做铺垫。兄弟 w 虽然黑但它的右孩子是黑、左孩子是红直接套情况4 的旋转不行所以先把 w 右旋一次让红孩子变成 w 的右孩子再走情况4。情况4 是最终解决的一步。通过一次旋转把兄弟路径上的黑色数量重新分配同时把 x 的额外黑色消掉循环可以直接结束。代码实现时我用了 NIL 哨兵所以比普通教材稍微多几个针对nil_的保护防止把哨兵染红。具体看这段removeFixUpvoid removeFixUp(Node* x) { while (x ! root_ x-color BLACK) { if (x x-parent-left) { Node* w x-parent-right; if (w-color RED) { // 情况1: 兄弟红 w-color BLACK; x-parent-color RED; leftRotate(x-parent); w x-parent-right; } // 兄弟为哨兵nil时认为它两个孩子都是黑色 if (w nil_ || (w-left-color BLACK w-right-color BLACK)) { // 情况2: 兄弟黑侄子全黑 if (w ! nil_) w-color RED; x x-parent; } else { if (w-right-color BLACK) { // 情况3: 左红右黑先变成情况4 w-left-color BLACK; w-color RED; rightRotate(w); w x-parent-right; } // 情况4: 右孩子红 w-color x-parent-color; x-parent-color BLACK; w-right-color BLACK; leftRotate(x-parent); x root_; } } else { // 对称情况 Node* w x-parent-left; if (w-color RED) { w-color BLACK; x-parent-color RED; rightRotate(x-parent); w x-parent-left; } if (w nil_ || (w-right-color BLACK w-left-color BLACK)) { if (w ! nil_) 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; }这里最关键的坑就是w nil_。当兄弟是哨兵 NIL 结点时它的颜色是黑左右孩子也必须是黑但如果按标准情况2 去执行w-color RED会把哨兵染红后续所有判断直接崩坏。所以这段代码里遇到兄弟为 NIL 时不修改哨兵颜色只把双重黑色上移到父结点。4.4 删除复杂度与旋转上限删除修复的循环可能一路上升到根所以整体复杂度仍是O(log n)。但真正发生旋转的次数是有限的情况1 最多一次情况3 最多一次情况4 一次后循环结束情况2 本身不旋转。因此红黑树删除操作最多只需要 3 次旋转。这一点是红黑树在工程上比 AVL 更占优势的关键原因后面也会再展开。5. 完整可运行的 C 实现与自测5.1 工具函数验证颜色规则与黑高手写红黑树不验证等于白写。我强烈建议你写一个isValid函数每次插入删除后都跑一遍把非法情况立刻暴露出来。最省事的验证方式就是递归检查下面几件事红色结点的孩子不能是红色。从任意结点出发左右叶子路径的黑高必须相同。根必须是黑色。bool isValidTree(Node* x, int height) { if (x nil_) { height 1; return true; } if (x-color RED (x-left-color RED || x-right-color RED)) { return false; } int leftH 0, rightH 0; if (!isValidTree(x-left, leftH)) return false; if (!isValidTree(x-right, rightH)) return false; if (leftH ! rightH) return false; height leftH (x-color BLACK ? 1 : 0); return true; } bool isValid() { if (root_-color ! BLACK) return false; int h 0; return isValidTree(root_, h); }这个函数检查完以后只要返回true至少证明你的树满足红黑树五条性质。我测试过程中遇到的大部分旋转写错、变色漏改都能靠它抓出来。5.2 中序遍历与控制台打印验证有序性最直接的方法是中序遍历。红黑树是二叉搜索树中序遍历结果一定是升序的。void inorder(Node* x) { if (x nil_) return; inorder(x-left); std::cout x-key (x-color RED ? (R) : (B)) ; inorder(x-right); } void inorderPrint() { inorder(root_); std::cout std::endl; }输出时用(R)和(B)标记颜色方便肉眼检查是否存在连续红。5.3 集成测试插入删除后反复验证下面这段代码可以直接编译运行作为红黑树实现的基本自测int main() { RBTree tree; std::vectorint keys {7, 3, 18, 10, 22, 8, 11, 26, 2, 6, 13}; for (int k : keys) { tree.insert(k); if (!tree.isValid()) { std::cout insert k failed std::endl; return 1; } } tree.inorderPrint(); std::cout valid after insert: tree.isValid() std::endl; std::vectorint del {3, 7, 18, 2}; for (int k : del) { tree.remove(k); if (!tree.isValid()) { std::cout remove k failed std::endl; return 1; } } tree.inorderPrint(); std::cout valid after remove: tree.isValid() std::endl; return 0; }更严格一点可以随机插入 1 到 1000 的数字再随机删除每步都调用isValid校验。我自己的习惯是再拿std::set做对拍同一个操作序列同时打到红黑树和std::set上每一步检查中序遍历结果是否完全一致。这个方法比任何单一测试都更能暴露边界问题。6. 面试追问与答题模板6.1 “有了 AVL为什么还要红黑树”这是红黑树面试中最经典的问题没有之一。AVL 树也属于自平衡二叉搜索树它通过严格的平衡因子保证左右子树高度差不超过 1查找性能理论上更稳。但 AVL 的代价在插入和删除时的调整太频繁删除时最坏可能需要O(log n)次旋转这在写多读少的场景里是很大的开销。红黑树放宽了平衡要求只保证最长路径不超过最短路径的两倍换来的是“调整成本更低”。红黑树插入最多旋转 2 次删除最多旋转 3 次虽然颜色修复的循环可能往上走但实际结构变化很少整体操作摊还下来性价比很高。维度AVL红黑树平衡程度严格左右子树高度差不超过1宽松最长不超过最短2倍查询性能略优略逊但常数差异很小插入旋转最多2次最多2次删除旋转最坏 O(log n) 次最多3次适用场景读多写少读写均衡、频繁插入删除所以工程结论很清晰C 标准库的关联容器、Linux 内核、Java 的TreeMap等大量使用红黑树因为现实场景往往是“有读有写”红黑树在读写之间取了一个更好的平衡点。6.2 “红黑树和哈希表怎么选”这道题也是高频。红黑树和哈希表都能做关联容器但适用场景差别很大。红黑树最大的优势是有序。它支持中序遍历可以按顺序输出所有元素可以快速找前驱、后继也可以做范围查询比如“找出所有大于 10 小于 50 的键”。哈希表做不到有序遍历它查找元素平均复杂度是O(1)但遍历结果是随机的。哈希表的劣势也很明显需要设计好的哈希函数处理冲突还可能发生扩容如果哈希函数选得不好或者数据被恶意构造最坏情况会退化到O(n)。红黑树没有这些问题它在任何输入下都能保证最坏O(log n)。C 里的选择其实已经给出了答案需要有序就用map/set底层红黑树不需要有序且对性能敏感就用unordered_map/unordered_set底层哈希表。面试时你可以结合这个例子回答一般能拿高分。如果再往下聊到磁盘场景还可以顺势提一下 B/B 树因为它针对磁盘多路 IO 做了优化每个结点可以存多个键能显著减少磁盘随机访问次数。6.3 面试高频追问速查表这里整理几个我面试别人时常追问的问题和对应的答题要点。追问答题要点红黑树能严格保证 O(log n) 吗不能严格到 log n但能保证树高 O(log n)因为最长路径不超过最短路径 2 倍。为什么新插入结点是红色红色不会增加黑高只可能破坏连续红修复成本低。旋转会改变二叉搜索树顺序吗不会。旋转只改变局部父子关系中序遍历顺序不变。插入最多旋转几次删除呢插入最多 2 次删除最多 3 次。根是红色怎么办修复循环结束后强制把根染成黑色因为根变黑不破坏任何性质。为什么需要 NIL 哨兵统一叶子结点的处理避免大量判空让修复代码逻辑更干净。红黑树能用来做区间查询吗能。中序遍历天然有序再配合前驱后继就能做范围遍历。这些问题本质上是考察你有没有真正理解红黑树的“原理”而不是背代码。所以我建议每写一步代码都想想这一步在性质层面解决了什么问题。7. 常见 Bug 与调试心得7.1 手写红黑树最容易踩的 5 个坑第一个坑是 NIL 哨兵的左右孩子没有指向自身。没有踩过的人可能不理解但删除修复代码里会频繁访问w-left-color这样的表达式如果 NIL 的孩子是nullptr程序直接崩。解决方法是初始化时把nil_-left nil_-right nil_写清楚。第二个坑是旋转和删除后根结点没有更新。左旋右旋里如果 x 是根必须把root_改成 ytransplant里如果 u 是根必须把root_改成 v。漏了这一步根会飘到奇怪的地方所有isValid校验都会失败。第三个坑是删除时把y和z弄混。z是键值对要删的结点y是真正被移动/删除的结点最后应该delete z。我见过不少人写成delete y结果把树上保留的结点删了内存泄漏和悬垂指针一起爆发。第四个坑是在统一哨兵设计下把 NIL 染红。删除修复的情况2 中如果兄弟是 NIL不能执行w-color RED否则哨兵变成红色所有后续判断全部失真。处理办法是单独判断兄弟是否为 NIL是的话跳过染红直接把额外黑色上推到父结点。第五个坑是修复循环没有正确向上传递。插入修复里z z-parent-parent删除修复里x x-parent这些赋值漏掉或者写错位置循环就会陷入死循环或者提前退出导致性质没修复。出现这种情况时建议手动画出当前树把z或x的移动路径标出来问题通常一眼就能看出来。7.2 推荐的自测套路红黑树这种数据结构不靠随机测试真的很难保证正确。我的自测套路一般三层第一层固定数据。插入一组已知数据肉眼观察中序遍历是不是升序isValid是否返回true。再按特定顺序删除同样验证。第二层随机数据对拍。生成几百个随机数重复执行“插入再删除”每步都校验红黑树性质和std::set的一致性。这个测试能把最常见的旋转 bug 逼出来。第三层边界构造。只插入递增序列比如1, 2, 3, ..., 100看旋转和变色是否正常只删除最大最小值删除到只剩一个结点删除不存在的键。这些边界场景最容易暴露根结点更新和 NIL 处理的问题。编译时建议加上-fsanitizeaddress红黑树代码内存操作密集AddressSanitizer 能帮你捕获释放后访问、数组越界、野指针等问题。7.3 给准备面试的朋友的建议红黑树这种东西纯看永远学不会一定得动手写。我建议的练习顺序是先默写五条性质再单独写左旋右旋然后写插入修复最后才碰删除修复。不要一上来就死记整个类那样面试时很容易脑子空白。真正面试时先在白板上把树画出来再写代码。画图有两个好处第一你自己思路更清晰第二面试官能实时看到你的思考过程。写删除修复前可以主动说一句“我把 NIL 哨兵的处理单独判断一下”面试官通常会很认可这种对边界的敏感。如果你时间紧删除修复实在背不下来也至少要能说清楚框架兄弟红先转黑兄弟黑看侄子侄子全黑就上移左红右黑先转右右红就直接旋转变色收尾。面试官更多时候想确认的是“你有没有真正理解”而不是“你代码默写得像不像原书”。能把思路说清楚再配合一个完整实现红黑树这道题基本就稳了。我自己准备红黑树时还有一个很笨但很有效的心得把插入和删除的每一条规则用中文写在一张纸上挂在显示器旁边每次写完代码就对一遍。写多了之后你会发现这些规则不是要背的条文而是一套完整的“如何在不破坏黑高的前提下调整树形”的系统。理解到这一层面试时你就不是在背红黑树而是在讲一个关于平衡的逻辑故事。
