红黑树.cpp

本程序实现了红黑树的插入,删除等算法,学习红黑树的可以下载看看,很有价值哦!

#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#include<iostream.h>
#include <time.h>
#include<windows.h>

struct RB_Tree
{
	char color;
	long key;
	struct RB_Tree *left;
	struct RB_Tree *right;
	struct RB_Tree *p;
};

struct Tree
{
	struct RB_Tree *Root;
	struct RB_Tree *NIL;
};
///////////////////////////////////////////////////////////////////////////////////////////

long Random_Int(long low, long high)
{
    return (long)(double(high-low+1)*rand()/(RAND_MAX+1.0)) + low;
}
///////////////////////////////////////////////////////////////////////////////////////////

void LEFT_ROTATE(Tree *T,RB_Tree *x)
{
	RB_Tree *y=NULL;
	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(Tree *T,RB_Tree *x)
{
	RB_Tree *y=NULL;
	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_FIXUP(Tree *T,RB_Tree *z)
{
	
	RB_Tree *y=NULL;
	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(T,z);
				}
				z->p->color='B';
				z->p->p->color='R';
				RIGHT_ROTATE(T,z->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(T,z);
				}
				z->p->color='B';
				z->p->p->color='R';
				LEFT_ROTATE(T,z->p->p);
			}
		}
	}
	T->Root->color='B';
}
/////////////////////////////////////////////////////////////////////////////////////////

void RB_INSERT(Tree *T,RB_Tree *z)
{
	RB_Tree *x;
	RB_Tree *y;
	y=T->NIL;
	x=T->Root;
	while(x!=T->NIL)
	{
		y=x;
		if(z->key<x->key)
			x=x->left;
		else
			x=x->right;
	}
	z->p=y;
	if(y==T->NIL)
		T->Root=z;
	else if(z->key<y->key)
		y->left=z;
	else
		y->right=z;
	z->left=T->NIL;
	z->right=T->NIL;
	z->color='R';
	RB_INSERT_FIXUP(T,z);
}
/////////////////////////////////////////////////////////////////////////////////////////

RB_Tree* TREE_MINIMUM(Tree *T,RB_Tree *x)
{
	while(x->left!=T->NIL)
		x=x->left;
	return x;
}
/////////////////////////////////////////////////////////////////////////////////////////

RB_Tree* TREE_SUCCESSOR(Tree *T,RB_Tree *x)
{
	RB_Tree *y;
	if(x->right!=T->NIL)
		return TREE_MINIMUM(T,x->right);
	y=x->p;
	while(y!=T->NIL && x==y->right)
	{
		x=y;
		y=y->p;
	}
	return y;
}
/////////////////////////////////////////////////////////////////////////////////////////

void RB_DELETE_FIXUP(Tree *T,RB_Tree *x)
{
	RB_Tree *w;
	while(x!=T->Root && x->color=='B')
	{
		if(x==x->p->left)
		{
			w=x->p->right;
			if(w->color=='R')
			{
				w->color='B';
				x->p->color='R';
				LEFT_ROTATE(T,x->p);
				w=x->p->right;
			}
			if(w->left->color=='B' && w->right->color=='B')
			{
				w->color='R';
				x=x->p;
			}
			else
			{
				if(w->right->color=='B')
				{
					w->left->color='B';
					w->color='R';
					RIGHT_ROTATE(T,w);
					w=x->p->right;
				}
				w->color=x->p->color;
				x->p->color='B';
				w->right->color='B';
				LEFT_ROTATE(T,x->p);
				x=T->Root;
			}
		}
		else
		{
			w=x->p->left;
			if(w->color=='R')
			{
				w->color='B';
				x->p->color='R';
				RIGHT_ROTATE(T,x->p);
				w=x->p->left;
			}
			if(w->right->color=='B' && w->left->color=='B')
			{
				w->color='R';
				x=x->p;
			}
			else
			{
				if(w->left->color=='B')
				{
					w->right->color='B';
					w->color='R';
					LEFT_ROTATE(T,w);
					w=x->p->left;
				}
				w->color=x->p->color;
				x->p->color='B';
				w->left->color='B';
				RIGHT_ROTATE(T,x->p);
				x=T->Root;
			}
		}
	}
	x->color='B';
}
/////////////////////////////////////////////////////////////////////////////////////////

RB_Tree* RB_DELETE(Tree *T,RB_Tree *z)
{
	RB_Tree *y;
	RB_Tree *x;
	if(z->left==T->NIL || z->right==T->NIL)
		y=z;
	else 
		y=TREE_SUCCESSOR(T,z);
	if(y->left!=T->NIL)
		x=y->left;
	else
		x=y->right;
	x->p=y->p;
	if(y->p==T->NIL)
		T->Root=x;
	else
	{
		if(y==y->p->left)
			y->p->left=x;
		else
			y->p->right=x;
	}
	if(y!=z)
		z->key=y->key;
	if(y->color=='B')
		RB_DELETE_FIXUP(T,x);
	return y;
}
/////////////////////////////////////////////////////////////////////////////////////////

RB_Tree* RB_Tree_SERCH(Tree *T,long k)
{
	RB_Tree *x;
	x=T->Root;
	while(x!=T->NIL && k!=x->key)
	{
		if(k<x->key)
			x=x->left;
		else
			x=x->right;
	}
	if(x==T->NIL)
		return NULL;
	else
		return x;
}
/////////////////////////////////////////////////////////////////////////////////////////

long print(RB_Tree *T)
{
	printf("%-10d%c\t",T->key,T->color);
	return 1;
}
/////////////////////////////////////////////////////////////////////////////////////////

int InOrder_Traverse(RB_Tree *T)
{
	if(T->key!=-1)
	{
		if(InOrder_Traverse(T->left))
			if(print(T))
				if(InOrder_Traverse(T->right))
					return 1;
		return 0;
	}
	else
		return 1;
}
/////////////////////////////////////////////////////////////////////////////////////////

int PreOrder_Traverse(RB_Tree *T)
{
	if(T->key!=-1)
	{
		if(print(T))
			if(InOrder_Traverse(T->left))
				if(InOrder_Traverse(T->right))
					return 1;
		return 0;
	}
	else 
		return 1;
}
/////////////////////////////////////////////////////////////////////////////////////////

void main()
{
	while(1)
	{
		LARGE_INTEGER  litmp ;
		LONGLONG  QPart1,QPart2 ;
		double time=0;
		int *NUM,*A;
		RB_Tree *z;
		Tree *T;
		long n=0;
		long k=0;
		T=(struct Tree *)malloc(sizeof(struct Tree));
		T->NIL=(struct RB_Tree *)malloc(sizeof(struct RB_Tree));
		T->Root=T->NIL;
		T->NIL->color='B';
		T->NIL->key=-1;
		T->NIL->left=NULL;
		T->NIL->right=NULL;
		T->NIL->p=NULL;
		printf("\n\n输入红黑树的节点个数：");
		scanf("%d",&n);
		NUM=(int *)malloc((3*n)*sizeof(int));
		for(int i=1;i<=n;i++)
			NUM[i]=0;
		A=(int *)malloc(n*sizeof(int));
		for(i=1;i<=n;i++)
		{
			A[i]=Random_Int(1,3*n);
			while(NUM[A[i]]==1)
				A[i]=Random_Int(1,3*n);
			NUM[A[i]]=1;
			
		}
		for(i=1;i<=n;i++)
		{
			z=(struct RB_Tree *)malloc(sizeof(struct RB_Tree));
			z->key=A[i];
			QueryPerformanceCounter(&litmp) ;
			QPart1 = litmp.QuadPart ;
			RB_INSERT(T,z);
			QueryPerformanceCounter(&litmp) ; 
			QPart2 = litmp.QuadPart ;
			time+=(double)(QPart2 - QPart1);
		}
		printf("插入%d个节点所需时间为:%fus",n,time);
		time=0;
		for(i=1;i<=n;i++)
		{
			k=A[i];
			QueryPerformanceCounter(&litmp) ;
			QPart1 = litmp.QuadPart ;
			z=RB_Tree_SERCH(T,k);
			QueryPerformanceCounter(&litmp) ; 
			QPart2 = litmp.QuadPart ;
			time+=(double)(QPart2 - QPart1);
		}
		printf("\n查找%d个节点所需时间为:%fus",n,time);
		/*printf("\n***********************中序遍历结果***************************\n");
		InOrder_Traverse(T->Root);
		printf("*************************先序遍历结果***************************\n");
		PreOrder_Traverse(T->Root);
		printf("\n**************************************************************\n");*/
		time=0;
		for(i=1;i<=n;i++)
		{
			k=A[i];
			z=RB_Tree_SERCH(T,k);
			QueryPerformanceCounter(&litmp) ;
			QPart1 = litmp.QuadPart ;
			RB_DELETE(T,z);
			QueryPerformanceCounter(&litmp) ;
			QPart2 = litmp.QuadPart ;
			time+=(double)(QPart2 - QPart1);
		}
		printf("\n删除%d个节点所需时间为:%fus",n,time);
		/*printf("\n***************删除关键字为%d的节点后中序遍历结果****************\n",k);
		InOrder_Traverse(T->Root);
		printf("\n***************删除关键字为%d的节点后先序遍历结果****************\n",k);
		PreOrder_Traverse(T->Root);*/
	}
}