一起学习交流~

红黑树-03-删除和调整(难点)

算法 laomuji 10个月前 (12-10) 805次浏览 已收录 0个评论

一、前言

红黑树的删除和普通二叉搜索树一样,但删除后可能会导致树不平衡,需要对红黑树进行调整

调整的情况非常非常多,非常非常复杂,且验证起来很麻烦

我是在这个网站来测试各种情况的

https://www.cs.usfca.edu/~galles/visualization/RedBlack.html

如果觉得难度太大,可以放弃

中间推测了太多次,画了又删,头都大了

所以没有存图片全文字讲解

二、删除

首先 当作一个二叉搜索树的删除

但是先不要删除,先找到需要删除的节点

然后根据该节点和附近节点的情况进行调整

我先给个例子代码:

	/*
		红黑树删除
		删除方式和普通二叉树一样,只不过多了调整
	*/
	int remove(T value) {
		int isRemove = 0;
		Node* adjustNode = nullptr;
		root = removeNode(root, value, isRemove, &adjustNode);
		if (isRemove)count--;
		if (adjustNode != nullptr) {
			removeFixUp(adjustNode);
		}
		return isRemove;
	}
	/*
		找到需要删除的节点
	*/
	Node* removeNode(Node* currentNode,T value,int& isRemove, Node** adjustNode) {
		//如果找到了就停止循环
		if (isRemove)return currentNode;
		if (currentNode == nullptr)return currentNode;
		if (currentNode->value > value) {
			//往左边找
			currentNode->left = removeNode(currentNode->left, value,isRemove, adjustNode);
		}
		else if (currentNode->value < value) {
			//往右边找
			currentNode->right = removeNode(currentNode->right, value,isRemove, adjustNode);
		}
		else {

			//如果两个孩子都不为空,则转变为删除左孩子中最大的值
			if (currentNode->left != nullptr && currentNode->right != nullptr) {
				Node* leftMaxChild = currentNode->left;
				while (leftMaxChild->right != nullptr)
				{
					leftMaxChild = leftMaxChild->right;
				}
				//找到左孩子中最大的,把当前值设置为该值
				currentNode->value = leftMaxChild->value;

				//把左孩子中最大的删除
				currentNode->left = removeNode(currentNode->left, leftMaxChild->value, isRemove, adjustNode);
			}
			else 
			{
				//此时当前节点只有一个或者0个孩子
				*adjustNode = currentNode;//标记需要调整
				isRemove = 1;//标记找到需要删除的节点,无需再寻找
			}
		}
		return currentNode;
	}

三、分析

首先,来分析一下,有哪些情况需要处理

我写了一个很烂的代码来查看有哪些情况不会出现

	void search() {
		if (root == nullptr)return;
		Node* temp = root;
		queue<Node*>que;
		que.push(temp);
		int r = 0;//红色无子
		int rr = 0;//红色1红子
		int rrr = 0;//红色2红子
		int rb = 0;//红色1黑子
		int rbb = 0;//红色2黑子
		int rbr = 0;//红色1黑子1红子

		int b = 0;//黑色无子
		int bb = 0;//黑色1黑子
		int bbb = 0;//黑色2黑子
		int br = 0;//黑色1红子
		int brr = 0;//黑色2红子
		int bbr = 0;//黑色1黑子1红子

		while (que.size())
		{
			Node* data = que.front();
			que.pop();
			if (data->color == COLOR::RED) {
				if (data->left == nullptr && data->right == nullptr) r++;
				if (data->left != nullptr && data->right == nullptr && data->left->color == COLOR::RED) rr++;
				if (data->left == nullptr && data->right != nullptr && data->right->color == COLOR::RED) rr++;
				if (data->left != nullptr && data->right != nullptr && data->left->color == COLOR::RED && data->right->color == COLOR::RED) rrr++;
				if (data->left != nullptr && data->right == nullptr && data->left->color == COLOR::BLACK) rb++;
				if (data->left == nullptr && data->right != nullptr && data->right->color == COLOR::BLACK) rb++;
				if (data->left != nullptr && data->right != nullptr && data->left->color == COLOR::BLACK && data->right->color == COLOR::BLACK) rbb++;
				if (data->left != nullptr && data->right != nullptr &&(
						(data->left->color == COLOR::BLACK && data->right->color == COLOR::RED)||
						(data->left->color == COLOR::RED && data->right->color == COLOR::BLACK))) rbr++;
			}
			else if (data->color == COLOR::BLACK) {
				if (data->left == nullptr && data->right == nullptr) b++;
				if (data->left != nullptr && data->right == nullptr && data->left->color == COLOR::RED) br++;
				if (data->left == nullptr && data->right != nullptr && data->right->color == COLOR::RED) br++;
				if (data->left != nullptr && data->right != nullptr && data->left->color == COLOR::RED && data->right->color == COLOR::RED) brr++;
				if (data->left != nullptr && data->right == nullptr && data->left->color == COLOR::BLACK) bb++;
				if (data->left == nullptr && data->right != nullptr && data->right->color == COLOR::BLACK) bb++;
				if (data->left != nullptr && data->right != nullptr && data->left->color == COLOR::BLACK && data->right->color == COLOR::BLACK) bbb++;
				if (data->left != nullptr && data->right != nullptr && (
					(data->left->color == COLOR::BLACK && data->right->color == COLOR::RED) ||
					(data->left->color == COLOR::RED && data->right->color == COLOR::BLACK))) bbr++;
			}
			else{
				cout << "?" << endl;
			}
			if (data->left != nullptr)que.push(data->left);
			if (data->right != nullptr)que.push(data->right);
		}
		cout << "单红节点" << r << endl;
		cout << "红红节点" << rr << endl;
		cout << "红红红节点" << rrr << endl;
		cout << "红黑节点" << rb << endl;
		cout << "红黑黑节点" << rbb << endl;
		cout<<"红黑红节点" << rbr << endl;

		cout<<"单黑节点" << b << endl;
		cout<<"黑黑节点" << bb << endl;
		cout<<"黑黑黑节点" << bbb << endl;
		cout<<"黑红节点" << br << endl;
		cout<<"黑红红节点" << brr << endl;
		cout<<"黑黑红节点:" << bbr << endl;
	}

四、调整

0.前提

被删除节点有两个孩子的情况不会出现

因为我们在删除的时候,

已经转化为了删除左孩子中最大的值


1.被删除节点 两个孩子都不为空

分析:

前提已经说了,所以不会出现这种情况,会转化为下面的情况

解决方案:

不会出现这种情况,不需要调整


2.被删除节点 是红色节点

分析:

红黑树不可能父亲和孩子都为红色,

所以 当前节点只可能是:

1.有两个黑孩子的红色节点

2.红色的叶子节点

因为前提,所以不可能出现两个孩子的情况

所以,只可能是 红色的叶子节点

删除一个红色的叶子节点,不会影响红黑树的黑高,所以无需处理

解决方案:

直接删除即可,不需要调整


3.被删除节点 一个孩子为空,一个孩子不为空

分析:

因为一个孩子为空,所以这边黑高为1

另外一个孩子非空,但黑高为1,那么这个节点只能是红色

红色和红色冲突,所以被删除节点只能是黑色

所以可以得到以下结论,

若一个节点的一个孩子为空,另一个非空

那么这个节点一定为黑色,孩子一定为红色

解决方案:

把孩子变为黑色后替换需要删除的节点即可


4.被删除的节点是黑色叶子节点

这种情况非常复杂,

很多教材上提出了双黑节点(DB,double black),即把一个黑色当作两个黑色处理

需要考虑:

父节点,兄弟节点,兄弟的左孩子,兄弟的右孩子

这四个节点一共有16种情况,

0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111

用1表示红0表示黑

根据红色树的性质,父亲和孩子不可能都为红,

所以剩下9种情况

0000
0001
0010
0011
0100
1000
1001
1010
1011
0100


首先来处理中间最为特殊的,兄弟节点为红的情况

0100

分析:

兄弟节点为红,无论怎么调整颜色都无法消除黑高不平衡

所以需要利用兄弟节点的红色和旋转来调整为其它情况

解决方案:

兄弟节点和父节点交换颜色,并旋转兄弟节点到父节点(交换颜色防止与祖父节点冲突)

此时情况就变为1000,1001,1010,1011四种情况


再来处理最简单的情况

1000

分析:

父节点为红色,两边黑高假设为n

当删除后,变成了n-1,n

将兄弟变为红色,会变为n-1,n-1

但父亲也为红,造成了双红冲突,需要把父亲变为黑色

父亲变为黑色后,两边就又变成了n

解决方案:

父亲和兄弟交换颜色


接下来是最麻烦的情况

0000

分析:

删除节点后,少了一个黑色,所以兄弟节点需要变红,也减少一个黑色

父节点的两个孩子黑高都减少了1,

所以需要把父节点作为双黑节点,此时黑高才平衡

但节点颜色只能是红或黑,不能是两个黑

所以需要把父节点作为需要调整的节点,向上递归

最坏情况到根节点,但根节点多了一个黑色相当于所有孩子都多了一个黑色,也是平衡的

解决方案:

把兄弟节点设为红色,再把父节点作为双黑节点向上递归(唯一需要向上递归的情况)


剩下的情况

1001,1010,1011
0001,0010,0011

实际上只是父节点的颜色不同,

而为了不影响祖父节点,调整后新的父节点颜色一定要和旧的一致

此时就变成了3种情况

1.兄弟的左孩子为红

2.兄弟的右孩子为红

3.兄弟的两个孩子都为红

当兄弟的孩子有两个为红时,可以直接旋转兄弟节点,结果是平衡的

当兄弟的孩子只有一个为红时,与兄弟是否同方向,需要旋转的方式不同

同向直接旋转兄弟到父节点就平衡,不同向需要旋转兄弟的孩子到父节点才平衡

于是又可以简化为2种情况

兄弟有同方向的红孩子

解决方案:

交换兄弟节点和父节点的颜色

把兄弟的同方向的红孩子变黑

把兄弟节点旋转到父节点

兄弟没有同方向的红孩子

解决方案:

交换兄弟的不同方向的红孩子和父节点的颜色,

把父节点变为黑色

把兄弟的不同方向的孩子通过两次旋转,旋转到父节点


此时,就已经处理了红黑树删除调整的所有情况

五、代码

/*
		删除调整
	*/
	void removeFixUp(Node*node) {
		//被删除的节点有两个孩子的情况已经被排除了

		//若删除的是根节点,那么根节点一定有1或0个孩子
		if (node == root) {
			if (node->left != nullptr)root = node->left;
			else if (node->right != nullptr)root = node->right;
			else root = nullptr;
			delete node;
			return;
		}

		//若当前节点为红色,则只可能是叶子节点,或者有两个孩子的节点(已经排除这种情况了)
		if (node->color == COLOR::RED) {
			if (node == node->parent->left) node->parent->left = nullptr;
			else node->parent->right = nullptr;
			delete node;
			return;
		}

		//若被删除的节点一个孩子为空,另一个孩子非空(经过推测和验证,只存在当前为黑,孩子为红的情况)
		if (node->left == nullptr && node->right != nullptr) {
			node->right->color = COLOR::BLACK;
			node->right->parent = node->parent;
			if (node == node->parent->left) node->parent->left = node->right;
			else node->parent->right = node->right;
			delete node;
			return;
		}
		if (node->left != nullptr && node->right == nullptr) {
			node->left->color = COLOR::BLACK;
			node->left->parent = node->parent;
			if (node == node->parent->left) node->parent->left = node->left;
			else node->parent->right = node->left;
			delete node;
			return;
		}
		//备份需要删除的节点
		Node* saveNode = node;
		//剩下的情况就只有黑色的叶子节点了
		//删除黑色叶子节点,此时变为双黑节点(DB,double black),需要自下向上递归调整
		while (node->color == COLOR::BLACK && node->parent != nullptr)
		{
			Node* parent = node->parent;
			Node* brother = nullptr;
			if (node == parent->left) brother = parent->right;
			else brother = parent->left;


			//兄弟节点为红色,最为特殊,需要转换为下面的父亲为红的4种情况
			if (brother->color == COLOR::RED) {
				brother->color = COLOR::BLACK;
				parent->color = COLOR::RED;
				if (brother == parent->left)rightRotate(brother);
				else leftRotate(brother);
				//不需要向上递归,但是需要更新亲戚
				continue;
			}

			//下面的情况,兄弟节点一定为黑色了
			//父节点为黑色,一共有4种情况
			//父节点为红色,一共有4种情况
			//但其中6种情况可以视为相同的3种情况(只有父节点的区别)
			Node* brotherLeft = brother->left;
			Node* brotherRight = brother->right;

			//先处理2种特殊情况
			//父节点颜色不同,处理方式也不同
			if (parent->color == COLOR::BLACK) {
				//两个黑孩子
				if ((brotherLeft == nullptr || brotherLeft->color == COLOR::BLACK) &&
					(brotherRight == nullptr || brotherRight->color == COLOR::BLACK)) {
					brother->color = COLOR::RED;
					node = parent;
					//需要向上递归处理双黑
					continue;
				}
			}
			else {

				//两个黑孩子
				if ((brotherLeft == nullptr || brotherLeft->color == COLOR::BLACK)&&
					(brotherRight == nullptr || brotherRight->color == COLOR::BLACK)) {
					parent->color = COLOR::BLACK;
					brother->color = COLOR::RED;
					//删除
					break;
				}
			}

			//剩下3种情况,又可以变为2种情况
			//有同向的红孩子,没有同向的红孩子
			if (brother == parent->left) {
				if (brotherLeft != nullptr && brotherLeft->color == COLOR::RED) {
					//有同向的红孩子
					swap(brother->color, parent->color);
					brotherLeft->color = COLOR::BLACK;
					rightRotate(brother);
					break;
				}
				else if (brotherRight != nullptr && brotherRight->color == COLOR::RED) {
					//没有同向的红孩子
					swap(brotherRight->color, parent->color);
					parent->color = COLOR::BLACK;
					leftRotate(brotherRight);
					rightRotate(brotherRight);
					break;
				}
			}
			else {
				if (brotherRight != nullptr && brotherRight->color == COLOR::RED) {
					//有同向的红孩子
					swap(brother->color, parent->color);
					brotherRight->color = COLOR::BLACK;
					leftRotate(brother);
					break;
				}
				else if(brotherLeft != nullptr && brotherLeft->color == COLOR::RED){
					//没有同向的红孩子
					swap(brotherLeft->color, parent->color);
					parent->color = COLOR::BLACK;
					rightRotate(brotherLeft);
					leftRotate(brotherLeft);
					break;
				}
			}
			cout << "如果看到这句话,那就代表代码错误了" << endl;
		}
		//当调整完毕 开始删除
		if (saveNode == saveNode->parent->left)saveNode->parent->left = nullptr;
		else saveNode->parent->right = nullptr;
		delete saveNode;
	}
喜欢 (4)
订阅评论
提醒
guest
0 评论
内联反馈
查看所有评论