图解红黑树的删除

上篇说明了红黑树的插入操作，本篇继续记录红黑色的删除操作。

网上的关于红黑树的博客很多，关于删除后的调整操作缺漏情况的也很多，从其中学习了许多不同的版本，自己也理解不少，由此记录。若仍有缺漏错误，各位博友在观看的时候，也可以多评论交流。

红黑树的删除操作同插入一样，也分许多情况。

下面举例的情况全为删除节点为父节点的左孩子的条件下，删除节点为父节点的右孩子的情况为左孩子的镜像（结尾处再说明操作）

1. 删除的节点不是叶子节点。

        解决方法很简单，同普通的二叉树的删除一样。找到删除节点的后继或者前驱，将后继或前          驱节点的值赋予删除节点，将删除的节点转移为后继或前驱节点。直到删除的节点为叶子节            点。

2. 删除的节点为叶子节点。

         2.1 兄弟为黑

                2.1.1 右侄子为红

                该情况优先级最高，无须在意左侄子的是否存在以及颜色。将兄弟节点变为                    父节点的颜色，将父节点和右侄子变为黑色，左旋父节点。

                2.1.2 左侄子为红

                通过将左侄子和兄弟节点互换颜色，右旋兄弟节点。转化为情况 2.1.1

                2.1.3 双侄子为黑

                  调整方法很简单，直接将兄弟节点颜色变为红色，但未完全解决。需要将父节点向上                      递归，直到遇到根或红色节点，将根或红色节点变为黑色才解决。

         2.2 兄弟为红

                   将兄弟节点和父节点互换颜色，左旋父节点，回归情况2.1的三种。

若删除节点为父节点右孩子（左孩子的镜像）

        黑兄弟，红右侄：兄侄换色，左旋兄。转化为红左侄的情况。

        黑兄弟，红左侄：兄染父色，父侄黑，右旋父。

        黑兄弟，双黑侄：兄变红，父递归，直遇根或红。

        红兄弟: 兄父互换颜色，右旋父。

删除：

// 删除
bool RBT::Delete(keyType key) {
	if (NULL == Root) {
		return false;
	}
	RBTNode* T = Root;
	// 寻找待删节点，直到待删节点为叶子节点
	while (T) {
		if (key < T->Key) {
			if (NULL == T->Left) return false;
			T = T->Left;
		}
		else if (key > T->Key) {
			if (NULL == T->Right) return false;
			T = T->Right;
		}
		else {
			if (NULL == T->Left&&NULL == T->Right) {	// 叶子节点
				break;
			}
			else if (NULL != T->Right) {	// 寻找删除节点的后继
				RBTNode* N = T->Right;
				while (N->Left) N = N->Left;
				T->Key = N->Key;
				key = N->Key;
				T = T->Right;
			}
			else {							// 寻找删除节点的前驱
				RBTNode* N = T->Left;
				while (N->Right) N = N->Right;
				T->Key = N->Key;
				key = N->Key;
				T = T->Left;
			}
		}
	}
	RBTNode* N = T;				// 记录删除节点
	RBTNode* P = T->Parent;		// 父节点
	RBTNode* U = NULL;			// 兄弟节点
	while (Root != T && BLACK == T->Color) {
		P = T->Parent;
		// 1、 待删节点为父节点的左孩子
		if (T == P->Left) {
			U = P->Right;	// 兄弟节点
			// 1.1 黑兄弟
			if (BLACK == U->Color) {
				// 1.1.1 红右侄（优先级高）
				if (U->Right&&RED == U->Right->Color) {
					//P->Left = NULL;				// 删掉节点
					U->Color = P->Color;		// 兄弟染父色
					P->Color = BLACK;			// 父变黑
					U->Right->Color = BLACK;	// 侄变黑	
					LRotate(*this, P);			// 左旋父节点
					break;
				}
				// 1.1.2 红左侄
				else if (U->Left&&RED == U->Left->Color) {
					U->Color = RED;			// 兄弟、侄子互换颜色
					U->Left->Color = BLACK;	
					RRotate(*this, U);		// 右旋兄弟
											// 转换为情况 1.1.1
				}
				// 1.1.3 黑双侄
				else {
					//P->Left = NULL;		// 删掉待删节点
					U->Color = RED;		// 兄弟变红
					if (Root == P || RED == P->Color) {		// 遇根或红，结束向上调整
						P->Color = BLACK;
						break;
					}
					T = P;
				}
			}
			// 1.2 红兄弟
			else if (RED == U->Color) { 
				U->Color = P->Color;	// 兄弟、父节点互换颜色
				P->Color = RED;			
				LRotate(*this, P);		// 左旋父节点
										// 回归 1.1 三种情况
			}
		}
		// 2、 待删节点为父节点的右孩子（镜像）
		else {
			U = P->Left;
			// 2.1 黑兄弟
			if (BLACK == U->Color) {
				// 2.1.1 红左侄
				if (U->Left&&RED == U->Left->Color) {
					U->Color = P->Color;	// 兄弟节点颜色变为父节点颜色
					P->Color = BLACK;		// 父节点和侄子节点颜色变为黑
					U->Left->Color = BLACK;	
					RRotate(*this, P);		// 右旋父节点
					break;
				}
				// 2.1.2 红右侄
				else if (U->Right&&RED == U->Right->Color) {
					U->Right->Color = U->Color;		// 兄弟、侄子互换颜色
					U->Color = RED;
					LRotate(*this, U);		// 左旋兄弟节点
											// 回归情况 2.1.1
				}
				// 2.1.3双黑侄
				else {
					U->Color = RED;		// 兄弟变红 
					if (Root == P || RED == P->Color) {
						P->Color = BLACK;
						break;
					}
					cout << "双黑侄递归" << endl;
					T = P;
				}
			}
			// 2.2 红兄弟
			else {
				U->Color = P->Color;	// 兄弟、父节点互换颜色
				P->Color = RED;
				RRotate(*this, P);		// 右旋父节点
										// 回归 2.1 三种情况
			}
		}
	}
	if (Root == N) {	// 待删节点为根
		Root = NULL;
		return true;
	}
	// 删除节点
	if (N == N->Parent->Left) N->Parent->Left = NULL;
	else N->Parent->Right = NULL;
	return true;
}

层次遍历：

 //层次遍历
void Traverse(RBT& Tree) {
	if (NULL == Tree.Root) {
		return;
	}
	RBTNode* T = Tree.Root;
	queue<RBTNode*> NODE;
	NODE.push(T);
	while (!NODE.empty()) { 
		T = NODE.front();
		NODE.pop();
		cout << T->Key;
		T->Color == RED ? cout << "红  " : cout << "黑  ";
		if (T->Left) NODE.push(T->Left);
		if (T->Right) NODE.push(T->Right);
	}
	cout << endl;
}