1. 项目概述这颗树到底在学什么聊红黑树尤其是用C从零手写红黑树这件事我估摸着每个科班出身的开发者在学习数据结构时都绕不开它。不管你是准备面试、刷算法题还是纯粹想搞懂STL里map和set的底层原理红黑树都是躲不掉的一座山。这篇内容就是结合我自己当年从背诵性质到手写实现的全过程把红黑树插入、删除、旋转、变色这些核心机制用一个能落地的方式讲清楚并且附上一套完整的C实现思路。先给还没入门的读者一句话概括红黑树是一种自平衡的二叉搜索树它通过给节点增加红/黑颜色属性以及一组约束条件保证树的高度始终接近O(log n)。也就是说无论你怎么插入、删除数据树都不会退化成一个链表所有操作的性能都能稳定在对数级。STL中的std::map、std::setLinux内核的CFS调度器、Java的TreeMap底层都有它的身影。所以这棵树绝不是面试官拿来刁难你的玩具而是实实在在的工业级数据结构。这篇内容适合谁看三类人第一类是正在学C数据结构的学生想从原理到代码彻底吃透红黑树第二类是准备面试的开发者需要快速梳理插入删除的修复逻辑和面试追问点第三类是已经会用STL但好奇底层实现、想自己动手写一遍的工程师。我会从性质推导开始把为什么需要旋转、为什么要有颜色约束、插入删除各有什么坑一点一点拆开讲。后半部分给出完整实现和调试经验确保你合上文章也能自己敲出一棵可用的红黑树。2. 核心思路解析红黑树的性质与平衡逻辑2.1 五条性质每一句都不是废话红黑树的定义标准说法是一颗二叉搜索树每个节点上增加一个存储位表示节点的颜色可以是红色或黑色并且满足以下五条性质每个节点要么是红色要么是黑色。根节点是黑色的。每个叶子节点NIL节点是黑色的。如果一个节点是红色的则它的两个子节点都是黑色的即不存在两个连续的红色节点。对每个节点从该节点到其所有后代叶节点的简单路径上均包含相同数目的黑色节点。当年学到这里我的第一个反应是记这玩意儿干嘛所有教材都用这五条性质堆出一大堆证明看着头晕。直到自己动手实现并且写了个检验函数去验证才发现每条性质都有它的实际用途。性质2保证了根节点黑色这是后面一系列推论的基础。性质4和性质5是红黑树的灵魂性质4限制了红色节点不能连续出现避免某条路径上颜色紧凑堆积性质5则强制任意路径上黑色节点数量一致。这两条合起来最关键的推论是从根到叶子的最长路径不超过最短路径的两倍。为什么最短路径是全黑路径最长路径是红黑交替路径因为红色不能连续红色节点数量最多等于黑色节点数量所以最长路径的节点数最多是最短路径的两倍。这个最长不超过最短两倍的约束不像AVL树那样要求左右子树高度差小于等于1那么严格但也足够保证树高是O(log n)而且调整时需要的旋转次数更少。我自己理解红黑树时更喜欢用粗平衡来概括它不追求完美平衡只保证不会出现某一条路径特别长的情况。就像现实中排队的护栏不要求每个人严格对齐但要求不能有人插队太离谱。这个宽松但不失控的特性就是红黑树能在插入删除频繁的场景下综合性能优于AVL树的原因。2.2 黑高、旋转与颜色翻转的直觉理解要真正看懂红黑树的操作还得引入一个概念黑高。节点的黑高指从该节点出发到达叶子节点所经过的黑色节点数。性质5其实就是在说一棵红黑树中每个节点的所有子树路径黑高必须一致。当插入或删除一个节点导致某些路径的黑高发生变化或者出现了连续的红色节点违反性质4时我们就需要调整。调整的手段主要有两种一种是对节点重新着色另一种是旋转。旋转这个词听起来高大上本质上就是在保持二叉搜索树中序遍历顺序不变的前提下调整父节点和子节点的上下关系。左旋是把某个节点的右孩子提上来当父节点右旋是把左孩子提上来当父节点。你不需要背旋转的方向只需要记住一句话中序遍历不能变谁占谁的位置要符合搜索树规则。我在初学阶段花了很多时间纠结左旋右旋到底哪边上去后来发现写代码时直接在纸上画一颗失衡的小树比死记结论高效得多。插入修复的核心矛盾是父节点是红色违反了性质4解决方案分三大类叔叔节点是红色就做颜色翻转叔叔节点是黑色且当前节点与父节点方向一致就做单旋加变色叔叔节点是黑色且方向不一致就先做一次旋转变成方向一致再按上一种情况处理。删除修复则围绕被删节点是黑色导致黑高失衡展开情况会更多我后面用单独章节逐个拆。这些操作背后的道理其实是一致的我们不想让树在每次操作后都重构成完美平衡而是用局部的小修小补——最多三次旋转、O(log n)次变色——让整棵树重新满足五条性质。局部性的好处是性能稳定不需要像某些平衡树那样做全局重排这也是它在工程中受欢迎的根本原因。3. 核心机制拆解插入、删除与修复流程3.1 插入的4种情况从叔叔颜色入手分类先把插入的大框架说清楚红黑树首先是一颗二叉搜索树插入新节点时按BST规则找到空位放下然后新节点默认涂成红色。为什么默认红色因为红色节点不会影响路径上的黑高性质5天然不会被破坏只需要处理性质4不能连续两个红色就行了。如果是黑节点每条新路径的黑高都变了修复起来代价更大。插入后分下面几种情况处理设当前节点为cur父节点parent祖父节点grandparent叔叔节点unclecur是根节点直接把颜色改成黑色结束。parent是黑色不需要任何操作插入完成。parent是红色且uncle是红色这是最简单的一类。把parent和uncle变成黑色把grandparent变成红色然后把cur指向grandparent继续向上处理。因为grandparent变红了它有可能和更上层的红色节点冲突所以要往上迭代。这里有个容易忽视的细节祖父节点变红后如果它就是根节点那下一轮会变成情况1把根染黑黑高刚好加1整体性质不变。parent是红色但uncle是黑色或不存在这时要分方向讨论。如果cur是parent的左孩子且parent是grandparent的左孩子就是LL型对grandparent右旋然后parent变黑、grandparent变红。如果cur是parent的右孩子且parent是grandparent的右孩子就是RR型对称左旋处理。如果方向不一致比如cur是parent的右孩子但parent是grandparent的左孩子就是LR型先对parent左旋变成LL型再用LL型的处理方案。RL型同理对称。我自己当初困惑最多的就是情况4的方向判断。一个实用的经验是先判断cur和parent的方向是否一致如果不一致第一步旋转是为了让它们一致如果一致直接旋转祖父节点然后变色。这个规律可以这样记不一致先转一次变成一致一致后转祖父再变色总共最多转两次。上面是针对插入的完整套路。总结成流程图的话就是变色向上推叔叔红、局部单旋叔叔黑且同向、先局部后整体双旋叔叔黑且反向三类情况覆盖所有可能性。面试时如果你能把这个分类逻辑讲清楚提问者基本就会觉得你真懂了。3.2 删除修复比插入复杂在哪删除操作分为两大步第一步按二叉搜索树规则删除节点第二步修复红黑树性质。第二步才是真正的重头戏。先补充一个背景知识点二叉搜索树删除节点时如果被删节点有两个孩子通常用前驱节点左子树中最大节点或者后继节点右子树中最小节点的值来替换然后删除那个前驱或后继节点。所以真正的物理删除总是发生在最多只有一个孩子的节点上。红黑树删除也一样我们关注的是那个真正被删掉的节点颜色。如果真正删掉的节点是红色事情就好办因为红色节点的存在与否不影响路径黑高也不会造成连续红色它的父子节点都是黑色直接删掉即可不需要修复。如果真正删掉的节点是黑色这就麻烦了。删掉一个黑色节点会导致经过该节点的所有路径黑高减1性质5被破坏。红黑树把这称为当前节点有了额外的黑或者说双重黑状态——这是一种概念化的说法你把额外缺失的黑想象成压在替代节点上后续处理的目标就是把这个额外的黑消除。删除修复的循环条件一般是当前节点cur存在、不是根节点、且cur是黑色。每次迭代关注cur的兄弟节点sibling。网上很多博客把删除修复分成好几类我按自己的归纳给大家整理成一套更易记的版本sibling是红色这意味着parent是黑色。把sibling变黑parent变红然后朝cur所在方向旋转parent得到新的sibling此时sibling一定是黑色的。这一步的目的是把情况转化为sibling为黑的情形且不改变黑色节点总数。sibling是黑色且sibling的两个孩子都是黑色此时可以把sibling变红把问题向上抛给parent。为什么可以这样因为sibling路径上减少一个黑正好和cur这边缺少一个黑抵消局部恢复黑高但parent这个子树的整体黑高比正常少了1所以cur变为parent继续循环。sibling是黑色且sibling的远侄子外侧孩子是黑色、近侄子内侧孩子是红色这时可以分两步处理——先针对sibling做一次旋转转换为情况4再进行后续的变色与旋转。这个先转换再处理的思路和插入修复中的先局部旋转再整体旋转如出一辙。sibling是黑色且sibling的远侄子外侧孩子是红色这是最理想的情况。直接把sibling的颜色设为parent的颜色parent变黑sibling的远侄子变黑然后旋转parent把那个多的黑消除。旋转后原来parent位置的节点继承了parent的颜色保持了局部颜色不变同时删掉的那条路径补回了一个黑问题解决。插一句重要提醒删除修复千万不要死记硬背每种情况的代码否则换一个实现细节你就懵了。我建议动手画图把哪条路径少了一个黑标出来然后逐种情况看旋转和变色如何让少掉的黑被补回来。我之前还把几种case画成卡片贴在显示器边上写代码时对照卡片推理效率比自己硬推高很多。3.3 左旋右旋的代码级细节旋转是整个红黑树操作的基础原子动作。左旋意味着将当前节点x的右孩子y提升为父节点x变成y的左孩子y原来的左孩子β变成x的右孩子。这里有个容易被忽略的细节β子树在旋转前后的中序遍历位置保持在x和y之间代码里要把y.left传给x.right同时如果x.parent为空还要更新root。右旋完全对称。写旋转函数时我习惯用一个公共辅助函数update_parent连接新关系避免在每个分支里重复处理parent指针。以下几点是我实际调试时踩过的坑旋转后一定要更新原来节点和替代节点的parent指针少了这一步树会直接断链。如果旋转的子树的根节点是整棵树的根要把root重新赋值。旋转只是结构重排颜色不变变色的逻辑一定要放在旋转操作之外单独写职责分开不容易错。以下是我实现中用到的旋转函数省略了模板和哨兵节点的定义核心逻辑如下// 左旋节点x假设x.right不为空 void leftRotate(Node* x) { Node* y x-right; // y的左子树交给x作为右子树 x-right y-left; if (y-left ! nullptr) { y-left-parent x; } // y顶替x的位置 y-parent x-parent; if (x-parent nullptr) { root y; } else if (x x-parent-left) { x-parent-left y; } else { x-parent-right y; } // x成为y的左孩子 y-left x; x-parent y; }右旋函数不过是把left和right对调就不再重复贴了。写的时候切记不能简单复制粘贴再改名字你得在脑子里把每一行的指针关系重新走一遍不然左右孩子搞反了Bug会非常难查。4. 实操过程用C从零实现一颗红黑树4.1 节点设计哨兵节点与空指针的选择写红黑树的第一个设计决策是叶子节点用nullptr还是用一个哨兵节点NIL《算法导论》里用哨兵NIL节点把所有空指针替换掉好处是删除修复代码里可以直接访问空节点的颜色而不用担心空指针解引用。但在实际工程代码里NULL节点本身是黑色只要在代码里注意判空用nullptr完全可行而且更直观。不过删除修复时的兄弟节点的孩子是否为空会频繁出现如果没有哨兵节点每次都要判断孩子是不是nullptr代码会臃肿不少。所以我个人建议实现删掉修复逻辑时在类内部定义一个静态的黑色空节点nil所有叶子的空指针指向它。这不仅简化了代码也让调试时打印树结构更统一。节点的数据结构可以这样设计struct RBNode { int key; // 键值 bool color; // true表示黑色false表示红色 RBNode* left; RBNode* right; RBNode* parent; RBNode(int k) : key(k), color(false), left(nullptr), right(nullptr), parent(nullptr) {} };颜色用bool还是枚举我建议面试或学习阶段用带名字的枚举比如const bool RED false / BLACK true这样写出来的代码可读性更好。实际STL的实现里用的是一个整型color字段那是因为要兼容空节点与内存布局优化咱们学习阶段没必要追求那种极致。4.2 插入修复的完整实现插入的第一步是普通BST插入这个不用多说从根节点往下走遇到比当前节点小的往左大的往右直到空位。插入新节点时颜色初始化为红色。关键代码是insertFixup我贴一个经过调试的版本void insertFixup(RBNode* cur) { // 循环处理父节点存在且为红色 while (cur-parent cur-parent-color RED) { RBNode* parent cur-parent; RBNode* grand parent-parent; // 父节点是红色祖父一定存在 if (parent grand-left) { RBNode* uncle grand-right; if (uncle uncle-color RED) { // 情况3叔叔是红色变色继续向上 parent-color BLACK; uncle-color BLACK; grand-color RED; cur grand; } else { // 叔叔黑 if (cur parent-right) { // LR型先左旋父节点转化为LL型 leftRotate(parent); cur parent; // 注意原parent变成了左孩子 parent cur-parent; } // LL型右旋祖父变色 rightRotate(grand); swap(parent-color, grand-color); // 此时parent成为新的子树根继续下一次循环会自动退出 cur parent; } } else { // 对称处理parent是grand-right RBNode* uncle grand-left; if (uncle uncle-color RED) { parent-color BLACK; uncle-color BLACK; grand-color RED; cur grand; } else { if (cur parent-left) { rightRotate(parent); cur parent; parent cur-parent; } leftRotate(grand); swap(parent-color, grand-color); cur parent; } } } root-color BLACK; }这个代码里有几个值得注意的细节。第一while循环的判断条件是cur-parent存在且为红色一旦父节点是黑色就可以退出因为性质4已经恢复。第二在LR型转换中我先leftRotate(parent)此时cur还是原来那个新插入节点leftRotate之后cur的parent变成了原来是parent的那个节点而cur变成了原来parent的右孩子我写的时候在这里容易绕晕所以代码里做了cur parent; parent cur-parent这步修正。注释一定要写清楚不然隔段时间回看你自己的代码都不认识。第三最后一行强制把根节点染黑这保证了性质2同时也处理了插入到空树的情况。验证插入是否正确最快的办法是对插入完的一棵树进行中序遍历看是否有序再递归检查红黑树五条性质是否全部成立。手动写一个bool isValid()校验函数遍历整棵树统计黑高有任何一处不一致就返回false。这一步看起来费时间但能帮你省下大量人力调试时间。我写树结构时最忌讳的bug是parent指针没有正确更新导致树的结构明明对但向上回溯时走到了错误节点。4.3 BST删除与红黑修复的整合删除函数分为两块BST删除部分找到真正删除节点然后用替换节点顶替它的位置红黑修复部分用deleteFixup处理额外黑的问题。先把物理删除的框架写清楚void deleteNode(int key) { RBNode* target search(root, key); if (target nullptr) return; RBNode* child nullptr; // 真正被删节点的唯一孩子 RBNode* delNode target; // 真正被物理删除的节点 bool delColor target-color; if (target-left nullptr) { // 只有右孩子或没有孩子 child target-right; transplant(target, target-right); } else if (target-right nullptr) { child target-left; transplant(target, target-left); } else { // 有两个孩子找到后继节点 RBNode* succ minimum(target-right); delColor succ-color; child succ-right; if (succ-parent target) { // 后继就是target直接右孩子此时child的parent已在transplant中处理 } else { transplant(succ, succ-right); succ-right target-right; succ-right-parent succ; } transplant(target, succ); succ-left target-left; succ-left-parent succ; succ-color target-color; // 颜色换给替代节点 delete target; } if (delColor BLACK child ! nullptr) { deleteFixup(child); } }这里的transplant函数就是是把一棵子树替换到另一个位置逻辑相当于是让v顶替u的位置并把u的parent关系正确接上。实际使用中还有一个容易踩坑的点在后继节点的父节点等于target的情形中child的parent没有在transplant里更新需要在deleteFixup之前手动设置child-parent succ否则修复循环里的parent指针会指向错误位置。deleteFixup的具体实现和插入修复长度相当核心思路是前面所说的四种情况。我贴一下框架性的代码方便读者对照理解void deleteFixup(RBNode* cur) { while (cur ! root cur-color BLACK) { RBNode* parent cur-parent; if (cur parent-left) { RBNode* sibling parent-right; if (sibling nullptr) break; // 情况1sibling是红色 if (sibling-color RED) { sibling-color BLACK; parent-color RED; leftRotate(parent); sibling parent-right; } // 情况2sibling的两个孩子都是黑色 if (isBlack(sibling-left) isBlack(sibling-right)) { sibling-color RED; cur parent; } else { // 情况3远侄子黑、近侄子红先做转换 if (isBlack(sibling-right)) { if (sibling-left) sibling-left-color BLACK; sibling-color RED; rightRotate(sibling); sibling parent-right; } // 情况4远侄子红旋转主干 sibling-color parent-color; parent-color BLACK; if (sibling-right) sibling-right-color BLACK; leftRotate(parent); cur root; // 直接结束 } } else { // 对称处理left和right互换 } } cur-color BLACK; }因为对称分支和左边完全镜像我就没有全量展开但读者在写自己的版本时一定要把两边都写完整。删除修复最隐蔽的问题在于在情况2中把sibling变红并向上递归后cur可能是root这种情况下循环条件会退出但如果cur是root且它的颜色是黑色最后一行cur-color BLACK没有意义但也不会出错所以很多实现为了稳妥总是将所有路径都涂黑。如果是直接开发工程我强烈建议不要自己实现红黑树直接用std::map或std::set。自己手写是为了理解原理不是为了替换标准库。真到了需要自定义平衡树的时候比如需要按节点访问、需要统计区间等也得用成熟的第三方库或算法导论中的源码为蓝本不要真从空文件开始推。5. 工程视角红黑树在C生态中的落地与对比5.1 STL中map与set的底层设计C STL里std::map和std::set几乎可以确定是基于红黑树实现的标准并未硬性规定但所有主流编译器都是这样。关于STL红黑树的实现细节有一个很多人不知道的知识点它用一个header节点代替根节点的父指针让迭代器在和--操作时不需要判断根节点的情况。这个header节点不存实际数据它的left指向真正的根节点整棵树的Header节点之所以出现是为了实现标准库迭代器的past-the-end语义。如果你去看libstdc的源码会发现它内部叫_Rb_tree插入删除都封装在_M_insert_和_M_erase_系列函数里。我最开始看这台源码时完全看不懂因为它为了极致的性能把很多通用型逻辑都内联掉了。不过从源码里我们能学到几个工程化的点尽量不递归而用循环迭代实现插入删除避免调用栈过深尽量复用左右旋的代码逻辑把颜色和树结构调整分开封装。这些思想值得用到我们自己的项目里。我在实际项目中经常被问到一个问题既然map是红黑树为什么unordered_map查找更快却还是有人选map答案在于有序性。map能够按key顺序遍历且支持lower_bound/upper_bound这类区间查询而unordered_map做不到。你对数据有区间遍历或顺序统计的需求map就是更合理的选择。5.2 红黑树与AVL树、B树的对比面试必考的一个追问是红黑树和AVL树怎么选这个问题的标准答案要从操作分布来谈。AVL树平衡更严格左右子树高度差不超过1查询更快一点因为树高更矮但它插入删除时的旋转频率更高最多可能要回溯到根节点。红黑树允许一定程度的不完美平衡插入删除时最多三次旋转就能修复因此更适合写多读少的场景。换句话说查询密集选AVL修改密集选红黑。另一个常见的搜索热词是B树是红黑树吗。当然不是。红黑树是内存中的二叉搜索树节点最多有两个孩子B树是多路平衡搜索树每个节点可以有很多孩子叶子节点之间还有链表连接用于范围遍历。B树的核心价值在于减少磁盘IO次数适合数据库索引红黑树的核心价值在于内存数据结构的稳定性能。红黑树在数据库场景中不是不能用但节点高度相对较高且局部性差对磁盘不友好。从工程平衡性来说红黑树之所以能在STL中胜出本质上是因为它把高效查询高效插入高效删除有序遍历内存占用可控这几个指标均衡在了一个可接受的范围内。单项最优不一定需要它但综合最优它常常是最佳解。5.3 排查与调试如何验证自己写的树没问题调试红黑树靠printf打印不可行因为树形结构一旦失衡肉眼根本看不出来。我的标准调试流程分三步。第一步实现一个树形打印函数把每层节点缩进显示并标记颜色。这个函数本身可以写得很土但非常管用。以下是简化版void printTree(RBNode* node, int depth) { if (node nullptr) return; printTree(node-right, depth 1); std::cout std::string(depth * 4, ) node-key (node-color ? (B) : (R)) \n; printTree(node-left, depth 1); }这样打印出来的树虽然倒着但结构一眼就能看明白。第二种调试利器是写一个完整校验函数每次插入或删除之后都递归检查五条性质是否成立。如果校验失败用一个断言把操作序列标记下来快速定位是插入第几个节点出错的。第三准备好一份可直接复用的乱序测试数据从1到N随机打乱逐次插入每次插入后校验然后随机删除一部分节点再次校验。这个过程能覆盖绝大多数边界情况。我自己踩过的一个经典bug是删除修复时忘记在右旋左旋之后更新待检查节点的parent指针导致后续循环里的parent是一个野指针程序直接崩溃。调试了半天最后靠多打印几行parent地址才发现了问题。所以建议读者在写树结构时专门写一个assert语句检查当前节点的parent是正确指向它的比如assert(node-parent-left node || node-parent-right node)在debug模式下每步都检查。5.4 常见追问与高频面试问题这部分专门给准备面试的读者整理一下我在帮人模拟面试时被问过的红黑树相关问题以及我回答时使用的思路。问红黑树的五个性质是什么这条是必考的回答时最好再加一句最长路径不超过最短路径的两倍来显示你真正理解了性质4和性质5的组合效果。问为什么插入的新节点是红色这个问题如果只说因为不改黑高还不够你还可以补充如果插入黑色节点就一定会违反每条路径黑高相同的性质而插入红色节点有可能不违反任何性质。根据概率插入红色节点有接近一半的概率不需要调整父节点是黑色这是最省事的选择。问红黑树和AVL树谁更快不要直接回答红黑树快要看场景。严格说查询上AVL可能略快插入删除上红黑树更优。你最好举一个有说服力的例子用红黑树实现std::map是因为map既需要频繁插入删除又需要有序遍历红黑树在这个综合维度下胜出。问为什么工业界用红黑树而不用2-3树其实红黑树和2-3树有直接关系红黑树的红节点可以理解为与父节点融合成一个3-节点所以红黑树本质上就是2-3树的二叉化编码。你点出这层关系面试官会觉得你有深入思考过。问为什么数据库不用红黑树索引关键点是磁盘IO和页存储。B树的节点对应一页数据查询路径更短且能顺序扫描叶子节点而红黑树每个节点独立分散随机IO代价高。这个问题即使不考也要能答因为它考察你对数据规模的理解。5.5 避坑清单与个人建议最后分享几个我实际开发中的经验教训希望能给读者节省点时间。第一手写红黑树前的准备先把二叉搜索树的插入和删除写得滚瓜烂熟。红黑树本质上就是BST加两个修复步骤BST的基础不牢固改红黑树代码一定会出错。不要上来就啃红黑树否则你会在为什么删不掉这个节点这种低级问题上浪费一整天。第二代码风格的统一所有节点都用Color字段并且提供isBlack/checkNode辅助函数不要在代码里散落裸判断。把颜色是否合法封装成函数你这个树很大概率会改坏但这种封装能让错误在某一个函数里暴露出来而不是悄悄蔓延。第三写代码时永远假设parent指针会出错。在插入和删除修复逻辑中每次旋转之后手动确认节点关系某个节点的parent是否还是原来的parent旋转后child是否还在原来位置。这个习惯能直接避免一大类难以追踪的Bug。第四测试时间不能省。我建议写完红黑树后至少跑两个用例第一个是从空树开始连续插入1到1000每插入一个就执行完整校验函数第二个是插入全部数字后随机删除其中500个数字每删除一个也要校验。如果这两轮跑完没有断言失败那基本可以认为实现是可用的。第五不要迷信网上的红黑树删除代码。我搜到过很多版本有些是伪代码有些虽然能跑但思路非常绕。我的建议是以《算法导论》第13章的伪代码为蓝本自己翻译成C。翻译的过程其实就是最好的理解过程。那些现成的代码可以作为对照参考但别直接复制粘贴否则你永远搞不懂里面的坑。我写红黑树的体会是最难的不是理解性质本身而是在各种旋转和变色之间保持头脑清晰。一旦你能在纸上把插入6个节点后的树长什么样画出来再把这些图和代码里的步骤一一对应这棵树就算真的拿下了。希望这篇文章能帮你少走一点弯路早日写出自己那棵能跑的红黑树。