企业官网建设流程全解析

红黑树这名字，在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 五条性质里，真正决定平衡的是“黑高”

红黑树的五条性质，网上到处都有，但大多数文章只是列出来，没有解释哪条才是核心。我按自己的理解重新排一下：

1. 每个节点要么红，要么黑。
2. 根节点是黑的。
3. 每个叶子节点（NIL 哨兵）是黑的。
4. 如果一个节点是红的，那么它的两个子节点都是黑的（即红节点不能连续）。
5. 从任意节点出发，到其每个后代叶子节点的所有路径上，黑色节点的数量相同，这个数量叫“黑高”。

其中第 4 条和第 5 条才是关键。第 4 条保证了任何一条路径上红色节点不能连续出现，所以哪怕路径再长，红色节点最多和黑色节点交替排列。第 5 条保证了每条路径的黑色节点数相同。比如一棵黑高为 h 的树，最短路径就是一条全黑路径，长度为 h；最长路径就是红黑交替，长度为 2h。因此整棵树的高度被限制在 2log₂(n+1) 以内，查询、插入、删除的时间复杂度都是 O(log n)。

这里有个小细节值得注意：说到黑高，NIL 哨兵是算作黑色节点的。所以从根到叶子的路径长度里，叶子本身也算一个黑高度。初学红黑树的人经常在这个地方数错。

1.3 红黑树 vs AVL vs B树：选型表

搞清楚红黑树的定位之后，再看它和另外两种常见树的区别会更清楚。下面的表是我在实际工程选择时常用的参考：

所以红黑树的定位非常明确：它是内存里“增删查都很快”的通用型有序数据结构。如果你要用 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::less<K>> 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 都指向nil，parent 指向找到的父节点，颜色设为 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 是左孩子为例）：

1. 兄弟 w 是红色：把 w 染黑、父节点染红，左旋父节点。这一步把问题转化为兄弟是黑色的情况，因为红兄弟经过旋转之后变成了 x 的新兄弟，而且新兄弟是黑的。
2. 兄弟 w 是黑色，且 w 的两个孩子都是黑色：把 w 染红，把债务上移给父节点，令 x = parent。这是因为 x 和 w 两条路径都少一个黑，把 w 也变成“欠债”节点后，父节点变成双黑，问题向上传递。
3. 兄弟 w 是黑色，w 的左孩子是红色、右孩子是黑色：把 w 染红，w 的左孩子染黑，右旋 w。这一步把问题转化为第 4 种情况。
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::less<K>> 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; }