《算法导论》13.3 插入（含有C++代码）

2、和之前INSERT的区别有四：
第一，TREE-INSERT内的所有NIL都被T. nil代替。第二，RB-INSERT的第14~15行置z. left和z. right为T. nil, 以保持合理的树结构。第三，在第16行将z着为红色。第四，因为将z着为红色可能违反其中的-一条红黑性质，所以在RB INSERT中调用RB-INSERT-FIXUP(T, z)来保持红黑性质。

RB-INSERT-FIXUP(T,z)
while z.p.color == RED
	if z.p == z.p.p.left
		y=z.p.p.right
		if y.color == RED	//case 1
			z.p.color = BLACK
			y.color = BLACK
			z.p.p.color = RED
			z = z.p.p
		else if z == z.p.right //case 2
			z = z.p
			LEFT-ROTATE(T,z)
		z.p.color = BLACK	//case 3
		z.p.p.color =  RED	//case 3
		RIGHT-ROTATE(T,z.p.p)//case 3
	else(same as then clause with "right" and "left" exchanged)
T.root.color = BLACK

回忆一下五条规则：
a.每个结点或是红色的，或是黑色的。
b.根结点是黑色的。
c.每个叶结点(NIL)是黑色的。
d.如果一个结点是红色的，则它的两个子结点都是黑色的。
e.对每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点。

#include 
#include 
using namespace std;
struct RbTreeNode
{
	string color;
	RbTreeNode* left;
	RbTreeNode* right;
	RbTreeNode* parent;
	int value;
};
//引用哨兵机制
struct RbTree
{
	RbTreeNode* root;
	RbTreeNode* nil;
};
void left_rotate(RbTree* T, RbTreeNode* x)
{
	RbTreeNode* y = x->right;
	//将y的左子树移动成为x的右子树
	x->right = y->left;
	if (y->left != T->nil) {
		y->left->parent = x;
	}
	//x的parent变成y的parent
	y->parent = x->parent;
	//x为根结点
	if (x->parent == T->nil) {
		T->root = y;
	}
	//x为左孩子，就将其父亲的左孩子变为y；x为右孩子同理
	else if (x == x->parent->left) {
		x->parent->left = y;
	}
	else {
		x->parent->right = y;
	}
	//x成为y的左孩子，y成为x的父结点
	y->left = x;
	x->parent = y;
}
//右旋
void right_rotate(RbTree* T, RbTreeNode* y)
{
	//将x的右孩子设置为y的左孩子
	RbTreeNode* x = y->left;
	y->left = x->right;
	if (x->right != T->nil) {
		x->right->parent = y;
	}
	x->parent = y->parent;
	if (y->parent == T->nil) {
		T->root = x;
	}
	else if (y->parent->left == y) {
		y->parent->left = x;
	}
	else {
		y->parent->right = x;
	}
	x->right = y;
	y->parent = x;
}
//恢复颜色顺序
void RbInsertFixup(RbTree* T, RbTreeNode* z)
{
	while (z->parent->color == "red")
	{
		if (z->parent == z->parent->parent->left) {
			RbTreeNode* y = z->parent->parent->right;
			if (y->color == "red") {
				z->parent->color = "black";
				y->color = "black";
				z->parent->parent->color = "red";
				z = z->parent->parent;
			}
			else if (z == z->parent->right) {
				z = z->parent;
				left_rotate(T, z);
			}
			z->parent->color = "black";
			z->parent->parent->color = "red";
			right_rotate(T, z->parent->parent);
		}
		else {
				RbTreeNode* y = z->parent->parent->left;
				if (y->color == "red") {
					z->parent->color = "black";
					y->color = "black";
					z->parent->parent->color = "red";
					z = z->parent->parent;
				}
				else if (z == z->parent->left) {
					z = z->parent;
					right_rotate(T, z);
				}
				z->parent->color = "black";
				z->parent->parent->color = "red";
				left_rotate(T, z->parent->parent);
		}
	}
	T->root->color = "black";
}
//插入
void RbInsert(RbTree* T, RbTreeNode* z)
{
	RbTreeNode* y = T->nil;
	RbTreeNode *x = T->root;
	while (x != T->nil) {
		y = x;
		if (z->value < x->value) {
			x = x->left;
		}
		else {
			x = x->right;
		}
		z->parent = y;
		if (y == T->nil) {
			T->root = z;
		}else if(z->value<y->value) {
			y->left = z;
		}
		else {
			y->right = z;
		}
		z->left = T->nil;
		z->right = T->nil;
		z->color = "red";
		RbInsertFixup(T, z);
	}

}