红黑树的删除
文章目录
- 前言：
- 红黑树的构成规则
- 红黑树的删除
- 关键
- 思路
- 节点释放的时机！！！！
- X为红代码
- x为黑代码
- Swap代码
- 全部代码
- 随机插入测试
- 总结
前言：
博主收集的资料New Young，连载中。
博主收录的问题:New Young
转载请标明出处：New Young
求一个电脑可用的画图软件，电脑的画版画着累！
红黑树的构成规则
红黑是在二叉搜索树的基础上，添加一些规则的一种高效的数据结构
- 根节点是黑色
这里的根节点是整体这个树的根，不是左右子树的根
-
我们空节点是黑色的，称为NIL节点
-
如果一个节点是红色的，那么它的左右孩子必须是黑色的
特别的，左右孩子是2个NIL节点也可以
- 从根到每一个NILL节点的所有路径中，黑色节点个数必须一样
记住路径最终的尽头是NIL节点，这个是解决红黑树删除的关键。
该规则保证了，
红黑树中最长路径不超过最短路径的2倍。证明:
设所有路径中，相同的黑色节点个数为N。
最短路径可能是：全部是黑色节点
由规则3，一但路径中出现红色节点，那么它的下一个节点必然是黑色的。
最坏的情况是：一红一黑交叉出现，那么N个黑色节点，最多这条路径上是2*N-1个节点。
因此说：红黑树中最长路径不超过最短路径的2倍
红黑树的删除
虽然看到删除，你可能会认为删除后的修复情况非常多，其实可能是你对RBTree的规则未理解好的原因，RBTree的删除情况的修复其实不多，那么让我们开始学习它！
关键
- 直到NIL才算是路径，因此在每种情形中一定要保证到NIL的黑色节点数不变。这种保证，可以通过不用的红色节点变成黑色节点辅助，也可以通过让树的2端同时减少相同的黑色节点，整体是缺失，就借助树的祖先，重复上述黄色字体过程。
**默认用替代法中的向左找最大值分析问题**- 节点的释放时机要提前，否则通过祖先的帮助平衡RBTree的循环就会出问题如野指针问题，逻辑问题
思路
由删除使用的替代法可以知道，如果我们找到了那个替代节点X，那么X一定至少有一个孩子是NIL节点，如果不是这样，说明我们未正确找到替代节点。
接上面。
情形一：如果X是红色的，
由规则3,4它的左右孩子一定都为NIL节点。
处理方式：直接删除即可，红色节点不影响路径中黑色节点个数
情形二：X是黑色的
由规则3,4，它一定存在uncle，否则左右子树的NIL的黑色节点不平衡。至于uncle什么颜色，分析即可
（1）它如果X存在孩子，那一定是一个没有孩子的红色节点。
处理：删除X，让红色孩子变黑。
（2）X没有孩子，删除X后，左子树缺失一个黑色节点。那么我们可以尝试能否借助uncle中的红色节点，通过旋转，让左子树这边多一黑色节点，左右子树仍是平衡。
-
uncle是红色的，那么它的父亲一定是黑色的，且一定存在2个黑色的左右孩子，且左右孩子没有孩子。
处理：uncle在右边，uncle右旋后，父亲左旋，交换uncel和UR的颜色
uncle在左边，uncle左旋后，父亲右旋，交换uncel和UL的颜色
- uncle是黑色时，由规则3,4，如果uncle存在孩子一定为红色。通过旋转让红色节点上来。
- 存在红色孩子时
处理：
本质上是让红色节点代替父亲节点，让父亲节点变成黑色节点就可以达到左右树黑色节点平衡。
uncle在右边时
- 红色孩子在左边，uncle向右旋，parent左旋，UL着父亲颜色，父亲变黑。
- 红色孩子在右边，parent左旋，uncle着父亲颜色，父亲变黑，UR变黑
uncle在左边时
红色孩子在左边，parent右旋，uncke着父亲颜色，父亲变黑，UL变黑
- 红色孩子在右边，uncle左旋，uncle右旋，UR着父亲颜色，父亲变黑
- 不存在孩子时—是最复杂的情形。
1. 此时无论什么方式，都不能通过uncle来让左右子树平衡，父亲也不行，因此我们只能让uncle边红，让左右勉强达到平衡，但是整个树仍是缺失一个黑色节点，因此我们要向祖先寻求帮助，通过祖先的红色节点边黑色节点，来辅助平衡。这种通过祖先帮助，最坏到root，但是因为我们让uncle变红了，我们让root这个树整体所有路径都少一个黑色节点，整体还是平衡的。
节点释放的时机！！！！
最后一种树整体缺失x个黑色节点的情形，如果父亲仍是黑色，我们仍按照上述情形处理就会出问题，因此我们在进入循环前就要释放节点X，这个释放只有一次，之后对X的孩子进行分析。
这样情形就如下：----可能描述的不是很清楚，需要自己看博主的代码逻辑才能很好理解。
情形一：如果孩子为红
孩子变黑即可
情形二：孩子为空且X为红
这个要在进入循环前就处理，因为可能通过祖先节点的方式，平衡RBTree。
情形三：孩子为空且X为黑或者孩子为黑
- uncle为黑且存在红色节点
> **通过双旋或者单旋**
- uncle为空或者uncel为黑且uncke没有节点
>**uncle变红，进入下一层循环**
- uncle为红，
> **父亲进行单旋**
X为红代码
if (cur->_color == RED)
{
//如果为红色，那么左右孩子一定为空
Node* parent = cur->_parent;
if (parent)
{
if (parent->_left == cur)
{
parent->_left = nullptr;
}
else
{
parent->_right = nullptr;
}
}
else
{
cout << "该树不是红黑树" << endl;
assert(false);
}
delete cur;
return true;
}
x为黑代码
if (cur->_color == BLOCK)
//如果cur存在孩子，那它一定为红，且红色孩子没有左右孩子
//父亲可能存在，可能不存在
{
//要提前保证删除cur
Node* parent = cur->_parent;
Node* child = cur->_left;
if(cur->_right)
child = cur->_right;
if (parent)
{
if (parent->_left == cur)
{
parent->_left = child;
}
else
{
parent->_right = child;
}
}
else//说明删除的是根
{
if (child)//child存在就置黑
{
child->_color = BLOCK;
}
_root = child;
delete cur;
return true;
}
delete cur;//删除节点
cur = nullptr;
while (parent)
{
//第一次的parent不可能为空,为空程序是不会走到这里
//因为可能出现借助祖先节点的情况，
//child可红或者黑
if (child&&child->_color==RED)
//存在为红,直接将child变为黑色，
//不影响路径黑色节点个数
{
child->_color = BLOCK;
break;
}
else if(child==nullptr||(child && child->_color == BLOCK))
//child为nullptr或者child为黑，就看uncle了
{
//uncle一定存在，否则删除前就不是红黑树,因为如果不存在，
// 则删除那边的的路径上就多一个黑色节点
//1. uncle为红，uncle与父亲交换颜色，父亲变为黑色
//2. uncle为黑,
// 那么它要么没孩子节点，这时候直接将uncle变为黑色，通过祖先节点，再找一个黑色节点
// 要么它只能有一红色孩子节点，通过单旋/双旋将红色节点旋转到缺失的一边，变为黑色即可
//
Node* uncle = parent->_right;
if (child== parent->_right)
uncle = parent->_left;
if (uncle)
{
Node* UL = uncle->_left;
Node* UR = uncle->_right;
if (uncle == parent->_right)
{
if (uncle->_color == BLOCK)
{
if (UL && UL->_color == RED)
{
_reloveR(uncle);
_reloveL(parent);
UL->_color = parent->_color;
parent->_color = BLOCK;
break;
}
else if (UR && UR->_color == RED)
{
_reloveL(parent);
uncle->_color = parent->_color;
parent->_color = BLOCK;
UR->_color = BLOCK;
break;
}
else
{
uncle->_color = RED;
child = parent;
parent = parent->_parent;
}
}
else
//uncle为红色，父亲一定为黑，那么它必定有2个黑色孩子
///双旋，之后交换uncle和UL的颜色
{
_reloveR(uncle);
_reloveL(parent);
swap(uncle->_color, UR->_color);
break;
}
}
else if (uncle == parent->_left)
{
if (uncle->_color == BLOCK)
{
if (UL && UL->_color == RED)
{
_reloveR(parent);
uncle->_color = parent->_color;
parent->_color = BLOCK;
UL->_color = BLOCK;
break;
}
else if (UR && UR->_color == RED)
{
_reloveL(uncle);
_reloveR(parent);
UR->_color = parent->_color;
parent->_color = BLOCK;
break;
}
else
{
uncle->_color = RED;
child = parent;
parent = parent->_parent;
}
}
else
//uncle为红色，则父亲一定为黑色，那么它必定有2个黑色孩子
//双旋，之后交换uncle和UL的颜色
{
_reloveL(uncle);
_reloveR(parent);
swap(uncle->_color, UL->_color);
break;
}
}
}
//uncle不可能不存在
//
else{
assert(false);
}
}
else
{
assert(false);
}
}
}
Swap代码
void Swap(Node* root1, Node* root2)
{
assert(root1);
assert(root2);
//root1默认是要删除的节点，且root2的左右孩子必定为空
Node* parent1 = root1->_parent;
Node* parent2 = root2->_parent;
if (parent1)
{
//先处理父亲节点
if (root1 == parent1->_left)
{
parent1->_left = root2;
}
else
{
parent1->_right = root2;
}
}
else
{
_root = root2;
}
if (root2 == parent2->_left)
{
parent2->_left = root1;
}
else
{
parent2->_right = root1;
}
std::swap(root1->_parent, root2->_parent);
std::swap(root1->_left, root2->_left);
//交换后root1的左孩子为空
//调整左右孩子指向
if (root2->_left)
root2->_left->_parent = root2;
std::swap(root1->_right, root2->_right);
//交换后root1的右孩子为空
//调整左右孩子指向
if (root2->_right)
root2->_right->_parent = root2;
//交
std::swap(root1->_color, root2->_color);
}
全部代码
bool Erase(const T&data)
{
//定位节点
Node* cur = _root;
while (cur)
{
if (kot()(cur->_data) > kot()(data))
{
cur = cur->_left;
}
else if (kot()(cur->_data) < kot()(data))
{
cur = cur->_right;
}
else
{
break;
}
}
if (cur == nullptr)
{
cout << "RBT中不存在以" << kot()(data) << "为key的节点" << endl;
return false;
}
else
{
Node* del = cur;
//替代法
//那边存在，就向那边替代
if (cur->_right)
{
//向右找最小
Node* min = cur->_right;//max一定存在且不为空
while (min->_left)
{
min = min->_left;
}
this->Swap(cur, min);
}
else if (cur->_left)
{
//向左找最大
Node* max = cur->_left;//max一定存在且不为空
while (max->_right)
{
max = max->_right;
}
this->Swap(cur, max);
}
else//当成无孩子的节点，正常走流程
{
;
}
//定位的节点，至少有一边为nullptr
//走到这里说明，cur一定存在孩子节点且一定存在父亲节点
//情形一：
//红色，一定有父亲节点，否则就不为红色，
//父亲节点一定为黑，因此只需要链接好与父亲节点即可
if (cur->_color == RED)
{
//如果为红色，那么左右孩子一定为空
Node* parent = cur->_parent;
if (parent)
{
if (parent->_left == cur)
{
parent->_left = nullptr;
}
else
{
parent->_right = nullptr;
}
}
else
{
cout << "该树不是红黑树" << endl;
assert(false);
}
delete cur;
return true;
}
else if (cur->_color == BLOCK)
//如果cur存在孩子，那它一定为红，且红色孩子没有左右孩子
//父亲可能存在，可能不存在
{
//要提前保证删除cur
Node* parent = cur->_parent;
Node* child = cur->_left;
if(cur->_right)
child = cur->_right;
if (parent)
{
if (parent->_left == cur)
{
parent->_left = child;
}
else
{
parent->_right = child;
}
}
else//说明删除的是根
{
if (child)//child存在就置黑
{
child->_color = BLOCK;
}
_root = child;
delete cur;
return true;
}
delete cur;//删除节点
cur = nullptr;
while (parent)
{
//第一次的parent不可能为空,为空程序是不会走到这里
//因为可能出现借助祖先节点的情况，
//child可红或者黑
if (child&&child->_color==RED)
//存在为红,直接将child变为黑色，
//不影响路径黑色节点个数
{
child->_color = BLOCK;
break;
}
else if(child==nullptr||(child && child->_color == BLOCK))
//child为nullptr或者child为黑，就看uncle了
{
//uncle一定存在，否则删除前就不是红黑树,因为如果不存在，
// 则删除那边的的路径上就多一个黑色节点
//1. uncle为红，uncle与父亲交换颜色，父亲变为黑色
//2. uncle为黑,
// 那么它要么没孩子节点，这时候直接将uncle变为黑色，通过祖先节点，再找一个黑色节点
// 要么它只能有一红色孩子节点，通过单旋/双旋将红色节点旋转到缺失的一边，变为黑色即可
//
Node* uncle = parent->_right;
if (child== parent->_right)
uncle = parent->_left;
if (uncle)
{
Node* UL = uncle->_left;
Node* UR = uncle->_right;
if (uncle == parent->_right)
{
if (uncle->_color == BLOCK)
{
if (UL && UL->_color == RED)
{
_reloveR(uncle);
_reloveL(parent);
UL->_color = parent->_color;
parent->_color = BLOCK;
break;
}
else if (UR && UR->_color == RED)
{
_reloveL(parent);
uncle->_color = parent->_color;
parent->_color = BLOCK;
UR->_color = BLOCK;
break;
}
else
{
uncle->_color = RED;
child = parent;
parent = parent->_parent;
}
}
else
//uncle为红色，父亲一定为黑，那么它必定有2个黑色孩子
///双旋，之后交换uncle和UL的颜色
{
_reloveR(uncle);
_reloveL(parent);
swap(uncle->_color, UR->_color);
break;
}
}
else if (uncle == parent->_left)
{
if (uncle->_color == BLOCK)
{
if (UL && UL->_color == RED)
{
_reloveR(parent);
uncle->_color = parent->_color;
parent->_color = BLOCK;
UL->_color = BLOCK;
break;
}
else if (UR && UR->_color == RED)
{
_reloveL(uncle);
_reloveR(parent);
UR->_color = parent->_color;
parent->_color = BLOCK;
break;
}
else
{
uncle->_color = RED;
child = parent;
parent = parent->_parent;
}
}
else
//uncle为红色，则父亲一定为黑色，那么它必定有2个黑色孩子
//双旋，之后交换uncle和UL的颜色
{
_reloveL(uncle);
_reloveR(parent);
swap(uncle->_color, UL->_color);
break;
}
}
}
//uncle不可能不存在
//
else{
assert(false);
}
}
else
{
assert(false);
}
}
}
return true;
}
}
随机插入测试
void MapT()
{
srand(time(0));
int N = 15;//截图有限
vector<int> v;
for (int i = 0; i < N; ++i)
{
v.push_back(rand() % 20);
}
NY::Map<int, int > map;
for (auto e : v)
{
map.Insert(make_pair(e,e));
}
if (map.IsRBTree())
cout << "True" << endl;
else
cout << "False" << endl;
for (int i = 0; i < N; ++i)
{
cout << "删除 ("<<v[i]<<v[i]<<")前:" ;
map.Inorder();
cout << endl;
map.Erase(v[i]);
cout << "删除后:";
map.Inorder();
cout << endl;
cout << "##################################" << endl;
}
}
总结
如果熟悉了红黑树的规则，细致分析就不用担心红黑色的删除的情形。AVl的删除也是。
总体上：AVL的删除很单纯没有弯弯，RBTree删除要多耐心一点。