redblacktree.cpp

红黑树：输入：在同一目录下的redblacktree.txt文件中输入十个大于0的数值

/*************************************************************************************

   题 目：红黑树的实现
   作 者：朱       磊
   学 号：SA04225140
   描 述：从文件"redblacktree.txt"读取制定数量的节点，输出其排列的红黑树，并计算此红
          黑树的黑高度，其中包括红黑树的插入和删除
   版 本：1.0
   日 期：2004年12月9日

****************************************************************************************/

#include<stdio.h>
#include<stdlib.h>

#define RED   1
#define BLACK 2
#define NIL   0
//设定节点个数
#define NUM   10

FILE * OpenFile;//文件指针
struct RedBlackTree{//红黑树结构
	int Key;//关键值
	char color;//颜色
	struct RedBlackTree *Parent;//父节点
	struct RedBlackTree *Left;//左节点
	struct RedBlackTree *Right;//右节点
};
int intKey[NUM] = {0};//从文件中读取关键值存入此数组
int i;//循环控制变量
struct RedBlackTree * Root;//记录根节点
struct RedBlackTree * NewPoint;//建立新的节点
struct RedBlackTree  nil = {NIL,BLACK,NIL,NIL,NIL};//外部节点

///////////////////////////////////////////////////////////////////////////////
//                              左旋                                         //
///////////////////////////////////////////////////////////////////////////////

void LeftRotation(struct RedBlackTree * x)
{
	struct RedBlackTree * y;

	y = x->Right;
	x->Right = y->Left;
	y->Left->Parent = x;
	y->Parent = x->Parent;
	if(x->Parent == NIL)
		Root = y;
	else {
		if(x == x->Parent->Left)
			x->Parent->Left = y;
		else x->Parent->Right = y;
	}
	y->Left = x;
	x->Parent = y;
}

///////////////////////////////////////////////////////////////////////////////
//                                  右 旋                                    //
///////////////////////////////////////////////////////////////////////////////
void RightRotation(struct RedBlackTree * x)
{
	struct RedBlackTree * y;

	y = x->Left;
	x->Left = y->Right;
	y->Right->Parent = x;
	y->Parent = x->Parent;
	if(x->Parent == NIL)
		Root = y;
	else {
		if(x == x->Parent->Left)
			x->Parent->Left = y;
		else x->Parent->Right = y;
	}
	y->Right = x;
	x->Parent = y;
}

//////////////////////////////////////////////////////////////////////////////
//                              红黑树插入调整                              //
//////////////////////////////////////////////////////////////////////////////                  
void RedBlackTreeInsertFixup(struct RedBlackTree * z)
{
	struct RedBlackTree * y;

	while((z != Root)&& (z->Parent->color == RED)){
		if(z->Parent == z->Parent->Parent->Left){
			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;
					LeftRotation(z);
				}
				z->Parent->color = BLACK;
				z->Parent->Parent->color = RED;
				RightRotation(z->Parent->Parent);
			}
		}else{
			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;
					RightRotation(z);
				}
				z->Parent->color = BLACK;
				z->Parent->Parent->color = RED;
				LeftRotation(z->Parent->Parent);
			}
		}
	}
	Root->color = BLACK;
}

/////////////////////////////////////////////////////////////////////////////	
//                               红黑树插入                                //
/////////////////////////////////////////////////////////////////////////////
void RedBlackTreeInsert(struct RedBlackTree * z)
{
	struct RedBlackTree * x;
	struct RedBlackTree * y;
	x = Root;
	y = NIL;
 
	while(x->Key != NIL){
		y = x;
		if(z->Key < x->Key)
			x = x->Left;
		else x = x->Right;
	}

	z->Parent = y;
	if(y == NIL)
		Root = z;
	else{
		if(z->Key < y->Key)
			y->Left = z;
		else y->Right = z;
	}

	z->Left = &nil;
	z->Right = &nil;
	z->color = RED;

	RedBlackTreeInsertFixup(z);
}

///////////////////////////////////////////////////////////////////////////
//                     查找以给定节点为根节点的树的最小值                //
///////////////////////////////////////////////////////////////////////////

struct RedBlackTree* TreeMinimum(struct RedBlackTree *x)
{
	while(x->Left != &nil)
		x = x->Left;
	return x;
}
///////////////////////////////////////////////////////////////////////////
//                        查找红黑树给定节点的后继                       //
///////////////////////////////////////////////////////////////////////////
struct RedBlackTree* TreeSuccessor(struct RedBlackTree *x)
{
	struct RedBlackTree *y;
	
	if(x->Right != &nil)
		return TreeMinimum(x->Right);
	if(x == Root)
		return (x->Left);
	y = x->Parent;
	while((y != Root) && (x == y->Right))
	{
		x = y;
		y = y->Parent;
	}
	if(y == Root->Left)
		return y->Parent;
	return y;
}


///////////////////////////////////////////////////////////////////////////
//                               红黑树删除调整                          //
///////////////////////////////////////////////////////////////////////////

void RedBlackTreeDeleteFixup(struct RedBlackTree *x)
{
	struct RedBlackTree *w;

	while((x != Root) && (x->color == BLACK)){
		if(x == x->Parent->Left){
			w = x->Parent->Right;
			if(w->color == RED){
				w->color = BLACK;//Case 1
				x->Parent->color = RED;
				LeftRotation(x->Parent);
				w = x->Parent->Right;
			}
			if((w->Left->color == BLACK) && (w->Right->color == BLACK)){//Case 2
				w->color = RED;
				x = x->Parent;
			}else{
				if(w->Right->color == BLACK){//Case 3
					w->Left->color = BLACK;
					w->color = RED;
					RightRotation(w);
					w = x->Parent->Right;
				}
				w->color = x->Parent->color;//Case 4
				x->Parent->color = BLACK;
				w->Right->color = BLACK;
				LeftRotation(x->Parent);
				x = Root;
			}
		}else{
			w = x->Parent->Left;
			if(w->color == RED){
				w->color = BLACK;//Case 1
				x->Parent->color = RED;
				RightRotation(x->Parent);
				w = x->Parent->Left;
			}
			if((w->Right->color == BLACK) && (w->Left->color == BLACK)){//Case 2
				w->color = RED;
				x = x->Parent;
			}else{
				if(w->Left->color == BLACK){//Case 3
					w->Right->color = BLACK;
					w->color = RED;
					LeftRotation(w);
					w = x->Parent->Left;
				}
				w->color = x->Parent->color;//Case 4
				x->Parent->color = BLACK;
				w->Left->color = BLACK;
				RightRotation(x->Parent);
				x = Root;
			}
		}
	}
	x->color = BLACK;
}

///////////////////////////////////////////////////////////////////////////
//                               红黑树的删除                            //
///////////////////////////////////////////////////////////////////////////
struct RedBlackTree* RedBlackTreeDelete(struct RedBlackTree *z)
{
	struct RedBlackTree *y;
	struct RedBlackTree *x;

	if((z->Left == &nil) || (z->Right == &nil))
		y = z;
	else
		y = TreeSuccessor(z);
	if(y->Left != &nil)
		x = y->Left;
	else 
		x = y->Right;
	x->Parent = y->Parent;
	if(y->Parent == &nil)
		Root = x;
	else{
		if(y == y->Parent->Left)
			y->Parent->Left = x;
		else
			y->Parent->Right = x;
	}
	if(y != z)
		z->Key = y->Key;
	if(y->color == BLACK)
		RedBlackTreeDeleteFixup(x);
	return y;
}


///////////////////////////////////////////////////////////////////////////
//                          递归输出(先序输出)                           //
///////////////////////////////////////////////////////////////////////////
void Print(struct RedBlackTree *z)
{
	if(z == &nil){
		printf("nil.黑色");
	}else{
		printf("%d.",z->Key);
		if(z->color == RED)
		    printf("红色");
		else
			printf("黑色");
		printf("(");
		Print(z->Left);
		printf(" , ");
		Print(z->Right);
		printf(")");
	}
}

///////////////////////////////////////////////////////////////////////////
//                              计算给定节点的黑高度                     //
///////////////////////////////////////////////////////////////////////////

int BlackHeight(struct RedBlackTree *z)
{
	int intBlackHeight = 0;

	z = z->Left;
	while(z != &nil)
	{
		if(z->color == BLACK)
		     intBlackHeight++;
		z = z->Left;
	}
    intBlackHeight++;
	return intBlackHeight;
}

///////////////////////////////////////////////////////////////////////////
//                           红黑树查找，返回指向关键值的指针            //
///////////////////////////////////////////////////////////////////////////
struct RedBlackTree* RedBlackSearch(int key)
{
	struct RedBlackTree* x;

	x = Root;
	while(x->Key != key)
	{
		if(x->Key > key)
			x = x->Left;
		else
			x = x->Right;
	}
	return x;
}

///////////////////////////////////////////////////////////////////////////
//                                   主函数                              //
///////////////////////////////////////////////////////////////////////////
void main(void)
{
	int key;//记录删除值

	OpenFile = fopen("redblacktree.txt","r");//打开文件
	if(OpenFile == NULL)
		printf("File could not open!");//打开失败
	else{
		printf("读取顺序是：\n");
		for(i = 0;i < NUM;i++)//读取数值
		{
			fscanf(OpenFile,"%d",&intKey[i]);
			printf(" %d",intKey[i]);
        }
	}

	NewPoint = (struct RedBlackTree *)malloc(sizeof(struct RedBlackTree));//把第一个节点指定为根节点，并负初值
	NewPoint->Key = intKey[0];
	NewPoint->color = BLACK;
	NewPoint->Left = &nil;
	NewPoint->Right = &nil;
	NewPoint->Parent = NIL;
	Root = NewPoint;
	for(i = 1;i < NUM;i++){//按顺序插入各节点
		NewPoint = (struct RedBlackTree *)malloc(sizeof(struct RedBlackTree));
	    NewPoint->Key = intKey[i];
		RedBlackTreeInsert(NewPoint);
	}
	fclose(OpenFile);
	printf("\n\n\n红黑树为(先序输出)：\n\n");
	//输出
	Print(Root);
	printf("\n\n\n红黑树的黑高度是：  ");
	printf("%d\n",BlackHeight(Root));
	printf("\n输入删除的关键值(不要出错):\n");//删除操作
	scanf("%d",&key);
    RedBlackTreeDelete(RedBlackSearch(key));
	printf("\n删除后的结果是：\n");
	Print(Root);
	printf("\n\n\n红黑树的黑高度是：  ");
	printf("%d\n",BlackHeight(Root));
	getchar();
	getchar();
}