红黑树的实现

实现红黑树的基本操作（初始化、插入、删除）

#include
#include

#define NODE_NUM 3
using namespace std;

int count=0;//用于红黑树输出时控制空格的多少
int a_node[200]; 
//红黑树节点
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;
};

//函数声明
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）;//删除后调整


//左旋
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;
}

//右旋转
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）;
}

//修正插入节点的红黑树
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个文件信息