目录
前言
Part1. 前置知识
Part2. 删除逻辑分析（一开始删除的情况，非向上调整）
Part2.1. 删除
Part2.2. 调整
Part3. 删除的四大情况（删除节点为黑，替代节点为nullptr）
Part3.1. w为红
Part3.2. w为黑，左右子均为黑
Part3.3. w为黑，右子为红，左子不论
Part3.4. w为黑，左子为红，右子为黑
Part3.5. w在p的左边
Part4. 删除代码实现
Part5. 结语
前言
之前我们讲了关于红黑树的插入，判断操作。接下来，我们来看看红黑树最复杂的接口--删除吧。
let's go!!!!!!!!!
Part1. 前置知识
上篇文章：【知识讲解】 红黑树的基本接口讲解（插入、判断等等）-CSDN博客
上篇文章我们讲述了两个推论和具体情况的处理，具体怎么得到的可以看上篇文章，这里简要的给出结论。
这里给出了再调整过程中的最小调整单元，这里的c可以理解为具体出问题的节点（插入中的p，由于p为红色导致连红），p为c的父亲节点，w为c的兄弟节点。我们假设h(x)为从x节点到nullptr路径上的黑色节点数目。则我们有：
推论<1>：对于一个节点x，它的两个子树的h一定相同。（例：h(c)=h(w)）
推论<2>：调整前h(p)，调整后为h(p2)。则若h(p)=h(p2)，且p的颜色不变，满足推论<1>的情况下，就不用向上调整。
具体情况处理：我们要穷尽所有可能出现的情况，且要尽量简要的方式达到正确的效果，于是我们穷举与出问题的节点(c)最密切的节点(w)的所有情况，这样就一定可以满足上面的要求。
Part2. 删除逻辑分析（一开始删除的情况，非向上调整）
Part2.1. 删除
删除操作主要分为两个阶段：删除和调整。删除阶段就是二叉搜索树的删除逻辑，具体可以看：【知识讲解】 二叉搜索树的相关知识与实现-CSDN博客
我们设待删除的节点为d，根据二叉搜索树删除的逻辑我们知道，删除一共就只有三个情况，即：d有右子无左子，d有左子无右子，d为叶子节点。（d有两个子的情况可以通过转化法转化为上面的三种情况之一）
Part2.2. 调整
那删除我们知道了，我们怎么调整呢？首先根据红黑树的规则，每个节点非黑即红，所以我们来分类讨论一下：
当删除的节点为红色时，我们删除它不会违反任何规则，直接就可以删除。
当删除的节点为黑色时，我们删除它会导致这个路径的黑高(h)减一，导致其父亲结点的左右子树的h不相同，违反红黑树黑高相同的规则，要调整。
所以我们调整的第一个大逻辑就有了，当我们删除的结点的颜色为红色，我们不用进行任何调整，直接就可以结束，关键在于，当我们删除的是黑节点怎么办？
首先在删除后一定会有一个代替他的节点（nullptr也算），根据上面删除的逻辑，我们可以得出这个代替节点一定不会是黑色的，为啥？因为d不可能同时存在左右两个子，所以要是一边有黑节点，那另一边是无法平衡的，所以代替节点一定不为黑。
其次，当代替节点为红的时候，我们只要把这个红色染黑，调整就结束了，相当于红色变为黑色，把那个删除的黑色给补回来了。
所以我们调整就又多了一种情况，就是当删除后其代替节点为红时，将其染黑，结束调整。
综上，我们得到了两种情况，就是当删除节点为红和代替节点为红，接下来，我们来分析一下其他的情况。
现在，代替节点不为红、黑。所以只能为nullptr(由于nullptr也为黑，故前面的黑应该是存在且为黑)。
现在比较好解决的情况已经排除了，我们来看复杂的情况，就是替代节点为nullptr。
首先先明确删除后问题出在哪？出在删除的地方少一个黑节点，导致违反了红黑树的规则，所以我们的目标就是把这个给补回来，而我们肯定不能无中生有一个黑节点，所以我们从哪补充？自然是红节点染色。
所以我们的思路就有了，我们要红节点通过染色的方式，补充失去的黑节点。而这个红节点在哪会有呢？w?不会，就算w是红节点，我们也无法通过旋转、染色的方式调整好，所以补充的节点只能出在w的子节点中，这样我们才能通过旋转的方式将这个转嫁到失去黑节点的地方，所以我们在细分情况的时候，要根据w的子节点来。
其次，我们来分析一下h(w)为多少？为一。为什么？首先我们一开始删除的节点为黑（为红就直接结束了），其次替代节点为nullptr，所以h(w)为一，因为一开始h(c)这边就为一，而他们在删除前为红黑树，依据推论<1>，右边也为一。
综上，我们来总结一下情况吧。
<1> 删除节点为红，直接删除结束。
<2> 删除节点为黑，替代节点为红，删除后将其染为红色，结束。
<3> 删除节点为黑，替代节点为nullptr，由此引申出h(w)为固定的一，穷举w的孩子的情况，调整。
逻辑理顺了，我们来看看具体的情况吧。
Part3. 删除的四大情况（删除节点为黑，替代节点为nullptr）
四大情况具体是什么呢？我们来列一下：
<1> w为红（w的颜色会影响他的孩子的颜色，所以要考虑他为红的情况）
<2> w为黑，左右子均为黑
<3> w为黑，右子为红，左子不论
<4> w为黑，左子为红，右子为黑
（p.s. nullptr也算是黑色节点）
Part3.1. w为红
我们先来看图来看一下整个过程
这里x那个三角形可以视为我们需要补充黑的节点。
由于w为红，所以其无法补充黑节点，所以我们要旋转将w转化为黑来处理（因为w为红，孩子不可能为红，所以无法补充新的黑）。
Part3.2. w为黑，左右子均为黑
这里要分为两个状况，当p为红色时，h(p)=1,这时候只要把p、w染色就可以解决。当p为黑色时，我们无法靠现有的条件来调整，我们只能寄希望于上面的树，交给上面来完成，也就是p作为新的x向上调整。
Part3.3. w为黑，右子为红，左子不论
这样，我们在不改变最上面那个节点的颜色下，补全了缺失的黑节点，这样就调整完成了。
Part3.4. w为黑，左子为红，右子为黑
当红色节点在w的右边时，我们可以通过局部的旋转转化为上面情况三来处理。
Part3.5. w在p的左边
和上面的情况镜像对称。
Part4. 删除代码实现
bool erase(const K& key)
{
Node* z = find(key);//找到要删除的节点
Node* x = nullptr;//替代节点
if (z == nullptr)
{
return false;
}
colour col = z->_col;//删除的结点的颜色
Node* parent = z->_parent;
int lor = 0;//看删除的节点是在p的哪边
if (z->_left == nullptr&&z->_right!=nullptr)//二叉搜索树的删除逻辑
{
if (z->_parent == nullptr)
{
_root = z->_right;
z->_right->_parent = nullptr;
z->_right->_col = BLACK;
delete z;
return true;
}
if (z->_parent->_left == z)
{
z->_parent->_left = z->_right;
lor = -1;//更新lor 区分情况
}
else
{
z->_parent->_right = z->_right;
lor = 1;
}
x = z->_right;
z->_right->_parent = z->_parent;
delete z;
}
else if (z->_left != nullptr && z->_right == nullptr)
{
if (z->_parent == nullptr)
{
_root = z->_left;
z->_left->_parent = nullptr;
z->_left->_col = BLACK;
delete z;
return true;
}
if (z->_parent->_left == z)
{
z->_parent->_left = z->_left;
lor = -1;
}
else
{
z->_parent->_right = z->_left;
lor =1;
}
x = z->_left;
z->_left->_parent = z->_parent;
delete z;
}
else if (z->_left == nullptr && z->_right == nullptr)
{
if (z->_parent == nullptr)
{
delete z;
_root = nullptr;
return true;
}
if (z->_parent->_left == z)
{
z->_parent->_left = nullptr;
lor = -1;
}
else
{
z->_parent->_right = nullptr;
lor = 1;
}
x = nullptr;
delete z;
}
else
{
Node* y = z->_right;
while (y->_left != nullptr)
{
y = y->_left;
}
z->_kv = y->_kv;
col = y->_col;
parent = y->_parent;
if (y->_parent->_left == y)
{
y->_parent->_left = y->_right;
lor = -1;
}
else
{
y->_parent->_right = y->_right;
lor = 1;
}
x = y->_right;
if (y->_right != nullptr)
{
y->_right->_parent = y->_parent;
}
delete y;
}
if (col == RED)//如果删除的节点为红色 不用后续的调整了
{
return true;
}
Node* w = nullptr;//兄弟节点
if (lor == 1)
{
w = parent->_left;//看兄弟节点的位置
}
else
{
w = parent->_right;
}
while (x != _root && (x==nullptr||x->_col==BLACK))//当x为红色就不用循环 退出 当然当x为根节点时也要退出
{
if (lor == -1)
{
if (w->_col == RED)//情况一
{
w->_col = BLACK;
parent->_col = RED;
Node* tem = w->_left;
RotateL(parent);
w = tem;
}
else if (w->_col == BLACK&&(w->_left==nullptr||w->_left->_col==BLACK)&&(w->_right==nullptr||w->_right->_col==BLACK))//情况二
{
w->_col = RED;
x = parent;
if (x == _root)
{
break;
}
else
{
if (x->_parent->_left == x)
{
w = x->_parent->_right;
lor = -1;
}
else
{
w = x->_parent->_left;
lor = 1;
}
parent = x->_parent;
}
}
else if (w->_col == BLACK && w->_left != nullptr && w->_left->_col == RED && (w->_right == nullptr || w->_right->_col == BLACK))//情况四
{
w->_left->_col = BLACK;
w->_col = RED;
Node* tem = w->_left;
RotateR(w);
w = tem;
}
else if (w->_col == BLACK && w->_right != nullptr && w->_right->_col == RED)//情况三
{
w->_col = parent->_col;
parent->_col = BLACK;
w->_right->_col = BLACK;
RotateL(parent);
x = _root;//定为_root退出循环
}
}
else//镜像对称
{
if (w->_col == RED)
{
w->_col = BLACK;
parent->_col = RED;
Node* tem = w->_right;
RotateR(parent);
w = tem;
}
else if (w->_col == BLACK && (w->_left == nullptr || w->_left->_col == BLACK) && (w->_right == nullptr || w->_right->_col == BLACK))
{
w->_col = RED;
x = parent;
if (x == _root)
{
break;
}
else
{
if (x->_parent->_left == x)
{
w = x->_parent->_right;
lor = -1;
}
else
{
w = x->_parent->_left;
lor = 1;
}
parent = x->_parent;
}
}
else if (w->_col == BLACK && w->_right != nullptr && w->_right->_col == RED && (w->_left == nullptr || w->_left->_col == BLACK))
{
w->_right->_col = BLACK;
w->_col = RED;
Node* tem = w->_right;
RotateL(w);
w = tem;
}
else if (w->_col == BLACK && w->_left != nullptr && w->_left->_col == RED)
{
w->_col = parent->_col;
parent->_col = BLACK;
w->_left->_col = BLACK;
RotateR(parent);
x = _root;
}
}
}
if (x != nullptr) {
x->_col = BLACK;//为情况二p为红色情况服务
}
_root->_col = BLACK;//确保_root为黑节点
return true;
}
用码道免费领 1 个月 Token
cpp
运行
Part5. 结语
这篇文章我们认识到了红黑树删除的实现，接下来，小编会带来map和set的模拟实现，敬请期待~
最后，祝大家可以：春风得意马蹄疾，一日看尽长安花！
最后的最后，要是觉得本文还可以的话，可以点点赞，关注小编一波，谢谢大家！~