[数据结构与算法]红黑树的个人总结

二叉查找树

特性:

• 某结点的左子树结点值仅包含小于该结点值
• 某结点的右子树结点值仅包含大于该结点值
• 左右子树每个也必须是二叉查找树

而二叉查找树存在一种极端情况，树的一条腿无线长，不够平衡，此时查找效率和普通链表没有区别。

红黑树

红黑树首先是一个二叉查找树，在二叉查找树的特性基础上引入了新的规则，使其可以摒弃极端情况，达到自平衡的目的。

特性:

1. 每个结点或者是黑色，或者是红色。
2. 根结点是黑色。
3. 每个叶子结点（NULL）是黑色。 [注意：这里叶子结点，是指为空的叶子结点！]
4. 如果一个结点是红色的，则它的子结点必须是黑色的。
5. 从一个结点到该结点的子孙结点的所有路径上包含相同数目的黑结点。

注意：

• 特性3中的叶子结点，是指为空(NIL或null)的结点。
• 特性5确保没有一条路径会比其他路径长出俩倍。因而，红黑树是相对是接近平衡的二叉树。

红黑树的查找过程和二叉查找树一致，而插入和删除操作会破坏红黑树的特性，因此需在插入删除操作后（该树仍然是一颗二叉查找树），再进行自平衡的操作，来维护红黑树的特性。
自平衡包含两种操作：变色和旋转。（任何的旋转和变色操作，都不会改变它仍然是一颗二叉查找树的事实，基于此原则理解左旋操作和右旋操作）

插入

一：将红黑树当作一颗二叉查找树，将结点插入。
二：将插入的结点着色为"红色"。（不会增加黑色结点，遵循特性五）
三：自平衡

自平衡主要分为7种情况：
1. 插入为根结点
处理：结点直接设置为黑色

2. 插入结点的父结点为黑结点
处理：不违背红黑树的特性，不做处理

3. 插入结点的父结点为红结点，此时看叔叔结点，分为两种情况：

3.1 叔叔结点为红结点

处理：
将 parent 和 uncle 标记为黑色
将 grand parent (祖父) 标记为红色
将grand parent (祖父)设为当前结点，继续处理。

3.2 叔叔结点为黑结点或者不存在（不存在相当于黑色）
此时看父结点和当前结点所在位置分为4种情况：
左左 (parent是左子树，当前结点是左子树)
左右 (parent是左子树，当前结点是右子树)
右右 (parent是右子树，当前结点是右子树)
右左 (parent是右子树，当前结点是左子树)

3.2.1左左
处理：右旋祖父结点，然后变色

3.2.2左右
处理：左旋父结点（变为左左），不需变色，然后按照左左继续调整

3.2.3右右
处理：左旋祖父结点，然后变色

3.2.4右左
处理：右旋父结点（变为右右），不需变色，然后按照右右继续调整

总结：
插入的核心思路是：

1. 将红色的结点向上移动，直到父结点为黑色（情况2），或者成为根结点（情况1）。也就是说，第三种情况的所有步骤的目的都是变为前两种情况。（例如左左情况下的右旋然后变色的操作，就是将当前结点的红色移动到祖父结点，右右情况同理。而左右和右左是先变为左左和右右然后再操作）。
2. 移动后的变色操作是为了保证特性4和5，使结点的黑色层数不变。只有一种会增加红黑树黑色结点层数的插入情景，就是当前结点为根结点，由红色变为黑色（包括移动过程中当前结点是根结点的情况，例如3.1的情况下，祖父结点设为当前结点，而祖父结点又恰好为根结点，此时按照情况1，直接设为黑结点，红黑树黑色结点层数加1）

void rb_tree_insert_rebalance(NodePtr x, NodePtr& root)
{
	rb_tree_set_red(x);  // 新增结点为红色
	while (x != root && rb_tree_is_red(x->parent))
	{
		auto uncle = x->parent->parent->right;
		if (uncle != nullptr && rb_tree_is_red(uncle))//3.1: 叔叔结点为红
		{ 
			rb_tree_set_black(x->parent);
			rb_tree_set_black(uncle);
			x = x->parent->parent;
			rb_tree_set_red(x);
		}
		else// 无叔叔结点或叔叔结点为黑
		{ 
			if (rb_tree_is_lchild(x->parent)) // 父结点是左子结点
			{ 
				if (!rb_tree_is_lchild(x)) // 3.2.2: 左右，转为左左
				{ 
					x = x->parent;
					rb_tree_rotate_left(x, root);
				}
				// 3.2.1：左左
				rb_tree_set_black(x->parent);
				rb_tree_set_red(x->parent->parent);
				rb_tree_rotate_right(x->parent->parent, root);
				break;
			}
			else // 父结点是右子结点，对称处理
			{
				if (rb_tree_is_lchild(x)) // 3.2.4: 右左，转为右右
				{ 
					x = x->parent;
					rb_tree_rotate_right(x, root);
				}
				// 3.2.3：右右
				rb_tree_set_black(x->parent);
				rb_tree_set_red(x->parent->parent);
				rb_tree_rotate_left(x->parent->parent, root);
				break;
			}
		}
	}

	rb_tree_set_black(root);  // 根结点永远为黑
}

删除

删除情况较为复杂，按照二叉查找树删除，共分为3种情况，每种情况再判断删除结点的颜色，根据颜色判断是否需要平衡处理。自平衡共包含9种情况

一：查找要删除的结点

1. 删除结点为叶结点
1.1 结点为红色
处理：不违背红黑树的特性,直接删除

1.2 结点为黑色
处理：删除后做自平衡处理，此结点设为x（结点为null，默认黑色）

2. 删除结点有一个子结点
2.1 删除结点为红色
处理：子结点直接替换删除结点

2.2 删除结点为黑色
处理：子结点替换删除结点后，做自平衡处理，子结点设为x

3. 删除结点有两个子结点
处理：
a. 先找出它的后继结点（后继结点是大于删除结点的最小结点，也是删除结点的右子树种最左结点。就意味着"后继结点"要么没有子结点，要么只有一个子结点）；
b. 然后后继结点替换删除结点并将颜色设为删除结点的颜色，后继结点的右子结点替换后继结点（不存在左子结点，右子结点可能为NULL），相当于实际删除的颜色是后继结点的。

3.1 后继结点颜色为红色
处理：不违背红黑树的特性，不做处理

3.2后继结点为黑色
处理：将后继结点的右子结点设为x。

二：自平衡（调整结点颜色和位置）

以下x为左子结点的情况，右子结点则操作对称
1. x为红色
处理：直接将x设为黑色，红黑树平衡（相当于最终删除的是红色）

2. x为黑色
2.1 x的兄弟是黑色
2.1.1 x的兄弟的子结点都是黑色
处理：brother设为红色，将parent作为x继续处理

2.1.2 x的兄弟的右子结点是红色，左子结点任意
处理：
a. brother和parent颜色互换（保证子结点的黑色层数）
b. 将brother右子结点变为黑色
c. 对parent左旋

2.1.3 x的兄弟的右子结点是黑色，左子结点为红色
a. brother设为红色
b. 左子结点设为黑色
c. 对brother右旋，得到2.1.2

2.2 x的兄弟是红色（则兄弟的父子一定都是黑色）
处理：
a. brother和parent颜色互换（保证子结点的黑色层数）
b. 对parent左旋，得到2.1.1

总结：
自平衡的核心思路：
删除后自身所在分支黑色层数减1，如果想要解决就要从兄弟那借

1. 兄弟如果有红色子树，可以借（兄弟给个黑色，然后红色变为黑色，两边层数不变）；
2. 兄弟子树如果都是黑的，则不能借（因为借需要旋转，兄弟就会少一层，自身层数不变），此时需要兄弟变为红色，一起减一层，这样父结点下保持统一，但父结点整体比叔叔结点少一层，相当于问题抛给了父结点，继续对父结点处理，自平衡是自底向上的过程。

NodePtr rb_tree_erase_rebalance(NodePtr z, NodePtr& root, NodePtr& leftmost, NodePtr& rightmost)
{
	// y 是替换结点，指向最终要删除的结点
	auto y = (z->left == nullptr || z->right == nullptr) ? z : rb_tree_next(z);
	// x 是 y 的一个独子结点或 NIL 结点
	auto x = y->left != nullptr ? y->left : y->right;
	// xp 为 x 的父结点
	NodePtr xp = nullptr;
	
	// y != z 说明 z 有两个非空子结点，此时 y 指向 z 右子树的最左结点，x 指向 y 的右子结点。
	// 用 y 顶替 z 的位置，用 x 顶替 y 的位置，最后用 y 指向 z
	if (y != z)
	{
		z->left->parent = y;
		y->left = z->left;

		// 如果 y 不是 z 的右子结点，那么 z 的右子结点一定有左孩子
		if (y != z->right)
		{ 
			// x 替换 y 的位置
			xp = y->parent;
			if (x != nullptr)
				x->parent = y->parent;
			y->parent->left = x;
			y->right = z->right;
			z->right->parent = y;
		}
		else
		{
			xp = y;
		}

		// 连接 y 与 z 的父结点 
		if (root == z)
			root = y;
		else if (rb_tree_is_lchild(z))
			z->parent->left = y;
		else
			z->parent->right = y;
		y->parent = z->parent;
		mystl::swap(y->color, z->color);
		y = z;
	}
	// y == z 说明 z 至多只有一个孩子
	else
	{ 
		xp = y->parent;
		if (x)  
			x->parent = y->parent;
		
		// 连接 x 与 z 的父结点
		if (root == z)
			root = x;
		else if (rb_tree_is_lchild(z))
			z->parent->left = x;
		else
			z->parent->right = x;
		
		// 此时 z 有可能是最左结点或最右结点，更新数据
		if (leftmost == z)
			leftmost = x == nullptr ? xp : rb_tree_min(x);
		if (rightmost == z)
			rightmost = x == nullptr ? xp : rb_tree_max(x);
	}

	// 完成替换后，y 指向删除结点，x 指向替代结点（原y结点的位置），从 x 结点开始调整。
	if (!rb_tree_is_red(y)) // 删除结点为黑色，
	{ 
		while (x != root && (x == nullptr || !rb_tree_is_red(x))) // x 为黑色
		{
			if (x == xp->left) // 如果 x 为左子结点
			{ 
				auto brother = xp->right;
				if (rb_tree_is_red(brother)) //2.2 兄弟结点为红色，转为2.1
				{ 
					rb_tree_set_black(brother);
					rb_tree_set_red(xp);
					rb_tree_rotate_left(xp, root);
					brother = xp->right;
				}
				//2.1兄弟结点为黑色
				if ((brother->left == nullptr || !rb_tree_is_red(brother->left)) &&
				(brother->right == nullptr || !rb_tree_is_red(brother->right))) // 2.1.1两个子结点都为黑色或 NIL
				{ 
					rb_tree_set_red(brother);
					x = xp;
					xp = xp->parent;
				}
				else
				{ 
					if (brother->right == nullptr || !rb_tree_is_red(brother->right))// 2.1.3右子结点是黑色，左子结点为红色，转为2.1.2
					{ 
						if (brother->left != nullptr)
						rb_tree_set_black(brother->left);
						rb_tree_set_red(brother);
						rb_tree_rotate_right(brother, root);
						brother = xp->right;
					}
					// 2.1.2 右子结点为红色，左子结点任意
					brother->color = xp->color;
					rb_tree_set_black(xp);
					if (brother->right != nullptr)  
					rb_tree_set_black(brother->right);
					rb_tree_rotate_left(xp, root);
					break;
				}
			}
			else  // x 为右子结点，对称处理
			{ 
				auto brother = xp->left;
				if (rb_tree_is_red(brother))
				{ 
					rb_tree_set_black(brother);
					rb_tree_set_red(xp);
					rb_tree_rotate_right(xp, root);
					brother = xp->left;
				}
				if ((brother->left == nullptr || !rb_tree_is_red(brother->left)) &&
				(brother->right == nullptr || !rb_tree_is_red(brother->right)))
				{ 
					rb_tree_set_red(brother);
					x = xp;
					xp = xp->parent;
				}
				else
				{
					if (brother->left == nullptr || !rb_tree_is_red(brother->left))
					{ 
						if (brother->right != nullptr)
						rb_tree_set_black(brother->right);
						rb_tree_set_red(brother);
						rb_tree_rotate_left(brother, root);
						brother = xp->left;
					}
				
					brother->color = xp->color;
					rb_tree_set_black(xp);
					if (brother->left != nullptr)  
					rb_tree_set_black(brother->left);
					rb_tree_rotate_right(xp, root);
					break;
				}
			}
		}
		
		if (x != nullptr)
			rb_tree_set_black(x);
	}
	return y;
}

参考：
https://github.com/Alinshans/MyTinySTL
https://www.cnblogs.com/skywang12345/p/3245399.html
https://zhuanlan.zhihu.com/p/79980618