#include
#include

#define?NODE_NUM?3
using?namespace?std;

int?count=0;//用于紅黑樹輸出時控制空格的多少
int?a_node[200];?
//紅黑樹節(jié)點(diǎn)
struct?rb_Tree_node
{
	int?key;
	char?color;
	struct?rb_Tree_node?*left;
	struct?rb_Tree_node?*right;
	struct?rb_Tree_node?*p;
};
//紅黑樹
struct?red_black_tree
{
	struct?rb_Tree_node?*root;
	struct?rb_Tree_node?*nil;
};

//函數(shù)聲明
void?left_rotate（struct?red_black_tree?*Tstruct?rb_Tree_node?*x）;//左旋
void?right_rotate（struct?red_black_tree?*Tstruct?rb_Tree_node?*x）;//右旋
void?rb_insert（struct?red_black_tree?*Tstruct?rb_Tree_node?*z）;//插入
void?rb_insert_fixup（struct?red_black_tree?*Tstruct?rb_Tree_node?*z）;//修正插入紅黑樹
struct?rb_Tree_node?*?rb_delete（struct?red_black_tree?*Tstruct?rb_Tree_node?*z）;//刪除
void?rb_delete_fixup（struct?red_black_tree?*Tstruct?rb_Tree_node?*x）;//刪除后調(diào)整


//左旋
void?left_rotate（struct?red_black_tree?*Tstruct?rb_Tree_node?*x）
{
	struct?rb_Tree_node?*y;
	y=x->right;
	x->right=y->left;
	if（y->left!=T->nil）
		y->left->p=x;
	y->p=x->p;
	if（x->p==T->nil）
		T->root=y;
	else?if（x==x->p->left）
		x->p->left=y;
	else
		x->p->right=y;
	y->left=x;
	x->p=y;
}

//右旋轉(zhuǎn)
void?right_rotate（struct?red_black_tree?*Tstruct?rb_Tree_node?*x）{
	struct?rb_Tree_node?*y;
	y=x->left;
	x->left=y->right;
	if（y->right!=T->nil）
		y->right->p=x;
	y->p=x->p;
	if（x->p==T->nil）
		T->root=y;
	else?if（x==x->p->right）
		x->p->right=y;
	else
		x->p->left=y;
	y->right=x;
	x->p=y;
}

//插入
void?rb_insert（struct?red_black_tree?*Tstruct?rb_Tree_node?*z）{
	struct?rb_Tree_node?*x;
	struct?rb_Tree_node?*y;
	y=T->nil;
	x=T->root;
	//查找插入位置
	while（x!=T->nil）{
		y=x;
		if（z->keykey）
			x=x->left;
		else
			x=x->right;
	}
	z->p=y;
	if（y==T->nil）
		T->root=z;
	else?if（z->keykey）
		y->left=z;
	else?
		y->right=z;
	z->left=T->nil;
	z->right=T->nil;
	z->color=‘R‘;
	rb_insert_fixup（Tz）;
}

//修正插入節(jié)點(diǎn)的紅黑樹
void?rb_insert_fixup（struct?red_black_tree?*Tstruct?rb_Tree_node?*z）{
	struct?rb_Tree_node?*y;
	while（z->p->color==‘R‘）{
		if（z->p==z->p->p->left）{
			y=z->p->p->right;
			if（y->color==‘R‘）{
				z->p->color=‘B‘;
				y->color=‘B‘;
				z->p->p->color=‘R‘;
				z=z->p->p;
			}
			else?{
				if（z==z->p->right）{
					z=z->p;
					left_rotate（Tz）;
				}
				z->p->color=‘B‘;
				z->p->p->color=‘R‘;
				right_rotate（Tz->p->p）;
			}
		}
		else{
			y=z->p->p->left;
			if（y->color==‘R‘）{
				z->p->color=‘B‘;
				y->color=‘B‘;
				z->p->p->color=‘R‘;
				z=z->p->p;
			}
			else?{
				if（z==z->p->left）{
					z=z->p;
					right_rotate（Tz）;
				}
				z->p->color=‘B‘;
				z->p->p->color=‘R‘;
				left_rotate（Tz->p->p）;
			}

		}
	}
	T->root->color=‘B‘;
}

//x為根的子樹中最小元素
struct?rb_Tree_node?*?tree_minimum（struct?red_black_tree?*Tstruct?rb_Tree_node?*x）{
	while（x->left!=T->nil）
		x=x->left;
	return?x;
}

//中序遍歷x的后繼
struct?rb_Tree_node?*?tree_successor（struct?red_black_tree?*Tstruct?rb_Tree_node?*x）{
	struct?rb

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----
?????目錄???????????0??2015-06-17?12:05??redBlackTree\
?????目錄???????????0??2015-06-17?12:05??redBlackTree\Debug\
?????文件???????42496??2015-06-14?11:28??redBlackTree\Debug\redBlackTree.exe
?????文件??????438372??2015-06-14?11:28??redBlackTree\Debug\redBlackTree.ilk
?????文件??????650240??2015-06-14?11:28??redBlackTree\Debug\redBlackTree.pdb
?????目錄???????????0??2015-06-17?12:05??redBlackTree\ipch\
?????目錄???????????0??2015-06-17?12:05??redBlackTree\ipch\redblacktree-928dac75\
?????文件????15335424??2015-06-17?10:36??redBlackTree\ipch\redblacktree-928dac75\redblacktree-6ac384f4.ipch
?????目錄???????????0??2015-06-17?12:05??redBlackTree\redBlackTree\
?????目錄???????????0??2015-06-17?12:05??redBlackTree\redBlackTree\Debug\
?????文件????????6296??2015-06-14?11:28??redBlackTree\redBlackTree\Debug\CL.read.1.tlog
?????文件?????????432??2015-06-14?11:28??redBlackTree\redBlackTree\Debug\CL.write.1.tlog
?????文件?????????714??2015-06-14?11:28??redBlackTree\redBlackTree\Debug\cl.command.1.tlog
?????文件???????????2??2015-06-14?11:28??redBlackTree\redBlackTree\Debug\link-cvtres.read.1.tlog
?????文件???????????2??2015-06-14?11:28??redBlackTree\redBlackTree\Debug\link-cvtres.write.1.tlog
?????文件???????????2??2015-06-14?11:28??redBlackTree\redBlackTree\Debug\link.3204-cvtres.read.1.tlog
?????文件???????????2??2015-06-14?11:28??redBlackTree\redBlackTree\Debug\link.3204-cvtres.write.1.tlog
?????文件???????????2??2015-06-14?11:28??redBlackTree\redBlackTree\Debug\link.3204.read.1.tlog
?????文件???????????2??2015-06-14?11:28??redBlackTree\redBlackTree\Debug\link.3204.write.1.tlog
?????文件???????????2??2015-06-14?11:28??redBlackTree\redBlackTree\Debug\link.3556-cvtres.read.1.tlog
?????文件???????????2??2015-06-14?11:28??redBlackTree\redBlackTree\Debug\link.3556-cvtres.write.1.tlog
?????文件???????????2??2015-06-14?11:28??redBlackTree\redBlackTree\Debug\link.3556.read.1.tlog
?????文件???????????2??2015-06-14?11:28??redBlackTree\redBlackTree\Debug\link.3556.write.1.tlog
?????文件???????????2??2015-06-14?11:28??redBlackTree\redBlackTree\Debug\link.6400-cvtres.read.1.tlog
?????文件???????????2??2015-06-14?11:28??redBlackTree\redBlackTree\Debug\link.6400-cvtres.write.1.tlog
?????文件???????????2??2015-06-14?11:28??redBlackTree\redBlackTree\Debug\link.6400.read.1.tlog
?????文件???????????2??2015-06-14?11:28??redBlackTree\redBlackTree\Debug\link.6400.write.1.tlog
?????文件????????3218??2015-06-14?11:28??redBlackTree\redBlackTree\Debug\link.command.1.tlog
?????文件????????6966??2015-06-14?11:28??redBlackTree\redBlackTree\Debug\link.read.1.tlog
?????文件?????????962??2015-06-14?11:28??redBlackTree\redBlackTree\Debug\link.write.1.tlog
?????文件???????60920??2015-06-14?11:28??redBlackTree\redBlackTree\Debug\main.obj
............此處省略24個文件信息