• RBTree的删除

    文章目录

    前言：

    • 博主收集的资料New Young，连载中。

    • 博主收录的问题:New Young

    • 转载请标明出处：New Young

    • 本文的RBTree是有问题的，向祖先寻求帮助时，uncle为红色的情况代码不会实现，留给以后吧！

    红黑树的构成规则

    红黑是在二叉搜索树的基础上，添加一些规则的一种高效的数据结构

    1. 根节点是黑色

    这里的根节点是整体这个树的根，不是左右子树的根

    1. 我们空节点是黑色的，称为NIL节点

    2. 如果一个节点是红色的，那么它的左右孩子必须是黑色的

    特别的，左右孩子是2个NIL节点也可以

    1. 从根到每一个NILL节点的所有路径中，黑色节点个数必须一样

    • 记住路径最终的尽头是NIL节点，这个是解决红黑树删除的关键。

    • 该规则保证了，红黑树中最长路径不超过最短路径的2倍。

    证明:

    设所有路径中，相同的黑色节点个数为N。

    最短路径可能是：全部是黑色节点

    由规则3，一但路径中出现红色节点，那么它的下一个节点必然是黑色的。

    最坏的情况是：一红一黑交叉出现，那么N个黑色节点，最多这条路径上是2*N-1个节点。

    因此说：红黑树中最长路径不超过最短路径的2倍

    红黑树的删除

    虽然看到删除，你可能会认为删除后的修复情况非常多，其实可能是你对RBTree的规则未理解好的原因，RBTree的删除情况的修复其实不多，那么让我们开始学习它！

    关键

    1. 直到NIL才算是路径，因此在每种情形中一定要保证到NIL的黑色节点数不变。这种保证，可以通过不用的红色节点变成黑色节点辅助，也可以通过让树的2端同时减少相同的黑色节点，整体是缺失，就借助树的祖先，重复上述黄色字体过程。
    2. **默认用替代法中的向左找最大值分析问题**
    3. 节点的释放时机要提前，否则通过祖先的帮助平衡RBTree的循环就会出问题如野指针问题，逻辑问题

    思路

    由删除使用的替代法可以知道，如果我们找到了那个替代节点X，那么X一定至少有一个孩子是NIL节点，如果不是这样，说明我们未正确找到替代节点。

    接上面。

    情形一：如果X是红色的，

    由规则3,4它的左右孩子一定都为NIL节点。

    处理方式：直接删除即可，红色节点不影响路径中黑色节点个数

    在这里插入图片描述

    情形二：X是黑色的

    由规则3,4，它一定存在uncle，否则左右子树的NIL的黑色节点不平衡。至于uncle什么颜色，分析即可

    （1）它如果X存在孩子，那一定是一个没有孩子的红色节点。

    处理：删除X，让红色孩子变黑。
    在这里插入图片描述

    （2）X没有孩子，删除X后，左子树缺失一个黑色节点。那么我们可以尝试能否借助uncle中的红色节点，通过旋转，让左子树这边多一黑色节点，左右子树仍是平衡。

    1. uncle是红色的，那么它的父亲一定是黑色的，且一定存在2个黑色的左右孩子，且左右孩子没有孩子。

      处理：uncle在右边，uncle右旋后，父亲左旋，交换uncel和UR的颜色

      uncle在左边，uncle左旋后，父亲右旋，交换uncel和UL的颜色

    在这里插入图片描述

    1. uncle是黑色时，由规则3,4，如果uncle存在孩子一定为红色。通过旋转让红色节点上来。
      • 存在红色孩子时

    处理：

    本质上是让红色节点代替父亲节点，让父亲节点变成黑色节点就可以达到左右树黑色节点平衡。

    uncle在右边时

    1. 红色孩子在左边，uncle向右旋，parent左旋，UL着父亲颜色，父亲变黑。
    2. 红色孩子在右边，parent左旋，uncle着父亲颜色，父亲变黑，UR变黑

    uncle在左边时

    红色孩子在左边，parent右旋，uncke着父亲颜色，父亲变黑，UL变黑

    1. 红色孩子在右边，uncle左旋，uncle右旋，UR着父亲颜色，父亲变黑

    在这里插入图片描述

    • 不存在孩子时—是最复杂的情形。

    1. 此时无论什么方式，都不能通过uncle来让左右子树平衡，父亲也不行，因此我们只能让uncle边红，让左右勉强达到平衡，但是整个树仍是缺失一个黑色节点，因此我们要向祖先寻求帮助，通过祖先的红色节点边黑色节点，来辅助平衡。这种通过祖先帮助，最坏到root，但是因为我们让uncle变红了，我们让root这个树整体所有路径都少一个黑色节点，整体还是平衡的。

    ​

    在这里插入图片描述

    节点释放的时机！！！！

    最后一种树整体缺失x个黑色节点的情形，如果父亲仍是黑色，我们仍按照上述情形处理就会出问题，因此我们在进入循环前就要释放节点X，这个释放只有一次，之后对X的孩子进行分析。

    这样情形就如下：----可能描述的不是很清楚，需要自己看博主的代码逻辑才能很好理解。

    情形一：如果孩子为红

    孩子变黑即可

    情形二：孩子为空且X为红

    这个要在进入循环前就处理，因为可能通过祖先节点的方式，平衡RBTree。

    情形三：孩子为空且X为黑或者孩子为黑

    1. uncle为黑且存在红色节点
    >   **通过双旋或者单旋**

    • 1
    1. uncle为空或者uncel为黑且uncke没有节点
    >**uncle变红，进入下一层循环**

    • 1
    1. uncle为红，
    >   **父亲进行单旋**

    • 1

    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;
			}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24

    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);
					}

				}
			}	

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133
    • 134
    • 135
    • 136
    • 137
    • 138
    • 139
    • 140
    • 141
    • 142
    • 143
    • 144
    • 145
    • 146
    • 147
    • 148
    • 149
    • 150
    • 151
    • 152
    • 153
    • 154

    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);
	}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46

    全部代码

    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;
		}	
	}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133
    • 134
    • 135
    • 136
    • 137
    • 138
    • 139
    • 140
    • 141
    • 142
    • 143
    • 144
    • 145
    • 146
    • 147
    • 148
    • 149
    • 150
    • 151
    • 152
    • 153
    • 154
    • 155
    • 156
    • 157
    • 158
    • 159
    • 160
    • 161
    • 162
    • 163
    • 164
    • 165
    • 166
    • 167
    • 168
    • 169
    • 170
    • 171
    • 172
    • 173
    • 174
    • 175
    • 176
    • 177
    • 178
    • 179
    • 180
    • 181
    • 182
    • 183
    • 184
    • 185
    • 186
    • 187
    • 188
    • 189
    • 190
    • 191
    • 192
    • 193
    • 194
    • 195
    • 196
    • 197
    • 198
    • 199
    • 200
    • 201
    • 202
    • 203
    • 204
    • 205
    • 206
    • 207
    • 208
    • 209
    • 210
    • 211
    • 212
    • 213
    • 214
    • 215
    • 216
    • 217
    • 218
    • 219
    • 220
    • 221
    • 222
    • 223
    • 224
    • 225
    • 226
    • 227
    • 228
    • 229
    • 230
    • 231
    • 232
    • 233
    • 234
    • 235
    • 236
    • 237
    • 238
    • 239
    • 240
    • 241

    随机插入测试

    void MapT()
	{
		srand(time(0));
		int N = 15;//截图有限
		vector v;
		for (int i = 0; i < N; ++i)
		{
			v.push_back(rand() % 20);
		}
		NY::Map 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 << "删除 ("<
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31

    在这里插入图片描述

    总结

    如果熟悉了红黑树的规则，细致分析就不用担心红黑色的删除的情形。AVl的删除也是。
    工作中一般更多的是关注RBTree的删除思想

  • 相关阅读:
    宝塔安装python和openssl
    【Axure视频教程】滑动评分条
    NLP实战9：Transformer实战-单词预测
    Quartz重启服务会执行但再次执行前Trigger状态为Error的问题。Quartz不同环境的注意事项
    GPT的广泛应用会对互联网公司造成挑战吗？——探讨GPT在实际使用中的应用和影响
    前端面试宝典React篇12 React 的渲染异常会造成什么后果？
    ssh-keygen命令生成RSA、ed25519类型密钥对
    QCN9274|DBDC WiFi 7 Network Card: Qualcomm‘s Innovative Solution
    安全 创新 实践｜海泰方圆受邀参加“数字时代的网信创新与价值共创”技术交流研讨会
    springboot-基础-eclipse配置+helloword示例
  • 原文地址：https://blog.csdn.net/qq_55439426/article/details/126699686