rbtrees.cpp

四个小算法。红黑树

#include "stdlib.h"
#include "stdio.h"
#include "time.h"
#define BLACK 0
#define RED 1

struct node{
	int low;
	int high;
	int max;
	node *left;
	node *right;
	node *parent;
	int color;
};
node * left_rotate(node *root,node *z);
node * right_rotate(node *root,node *z);
node * RB_insert(node *root,node *z);
node * insert_fixup(node *root,node *z);
node *RB_delete(node *root,node *z);
node *delete_fixup(node *root,node *z);
node *tree_successor(node *z);
node *tree_minimun(node *z);
node *interval_search(node *root,int low ,int high);
int adjustmax(node *root);
void display(node *root);
node *search(node *root,int value);
node *NIL,*root;
FILE *outfile;
node * left_rotate(node *root,node *x){
	node *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;
	return root;
}
node * right_rotate(node *root,node *x){
	node *y=x->left;
	x->left=y->right;
	y->right->parent=x;
	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;
	return root;
}
node *RB_insert(node *root, node *z){
	node *x,*y;
	y=NIL;
	x=root;
	while(x!=NIL){
		y=x;
		if(x!=root){
			fprintf(outfile,"(%d %d) parent %d ",x->low,x->high,x->parent->low);			
		}
		else{
			fprintf(outfile,"(%d %d) root ",x->low,x->high);
		}
		if(x->color==BLACK){
			fprintf(outfile," black\n");
		}
		else{
			fprintf(outfile," red\n");
		}
		if(z->low<x->low){
			fprintf(outfile,"go left:");
			x=x->left;
		}
		else{
			fprintf(outfile,"go right:");
			x=x->right;
		}
	}
	z->parent=y;
	if(y==NIL){
		fprintf(outfile,"(%d %d) root\n",z->low,z->high);
		root=z;
	}
	else {
		fprintf(outfile,"insert(%d %d)\n",z->low,z->high);
		if(z->low<y->low){
		y->left=z;
		}
		else{
			y->right=z;
		}
	}
	root=insert_fixup(root,z);
	return root;
}
node * insert_fixup(node *root,node *z){
	fprintf(outfile,"insert fix up\n");
	while(z->parent!=NIL&&z->parent->color==RED){
		node *parent,*grand,*uncle;
		parent=z->parent;
	    grand=parent->parent;
		fprintf(outfile,"(%d %d) parent %d\n ",z->low,z->high,z->parent->low);
		if(parent==grand->left){
			uncle=grand->right;
			if(uncle->color==RED){
				parent->color=BLACK;
				uncle->color=BLACK;
				grand->color=RED;
				z=grand;
			//	printf("case 1\n");
			}
			else if(z==parent->right){
				z=parent;
			//	printf("case 2\n");
				root=left_rotate(root,z);
			}
			else{
				parent->color=BLACK;
				grand->color=RED;
				root=right_rotate(root,grand);
			//	printf("case 3\n");
			}
		}
		else{
			uncle=grand->left;
			if(uncle->color==RED){
		//		printf("case 1\n");
				parent->color=BLACK;
				uncle->color=BLACK;
				grand->color=RED;
				z=grand;
			}
			
			else if(z==parent->left){
		//		printf("case 2\n");
				z=parent;
				right_rotate(root,z);
			}
			else{
		//		printf("case 3\n");
				parent->color=BLACK;
				grand->color=RED;
				left_rotate(root,grand);
			}
		}
	}
	root->color=BLACK;
	return root;
}
void display(node *root){
	printf("the node information of the tree is\n");
	node *z;
	int len=0;
	node *queue[10];
	queue[0]=root;
	if(root!=NIL){
		len=1;
	}
	while(len>=1){
		int i=0;
		z=queue[0];
		len--;
		for(i=0;i<len;i++){
			queue[i]=queue[i+1];
		}
		if(z!=root){ 
			if(z->color==BLACK)
				printf("(%d %d) black max is %d parent's low is %d\n",z->low ,z->high,z->max,z->parent->low);
			else
				printf("(%d %d) red max is %d parent's low is %d\n",z->low ,z->high,z->max,z->parent->low);
		}
		else{
			if(z->color==BLACK)
				printf("(%d %d) black max is %d root\n",z->low ,z->high,z->max);
			else
				printf("(%d %d) red max is %d root\n",z->low ,z->high,z->max);
		}
		if(z->left!=NIL){
			queue[len]=z->left;
			len++;
		}
		if(z->right!=NIL){
			queue[len]=z->right;
			len++;
		}
	}
}
node *search(node *root,int value){

	while(root!=NIL&&root->low!=value){
		if(root->low<value){
			root=root->right;
		}
		else{
			root=root->left;
		}
	}
	return root;
}
int adjustmax(node *root){
	node *x=root;
	int max_left(0),max_right(0),max(0);
	if(x!=NIL){
		if(x->left!=NIL){
			max_left=x->left->max;
			if(max_left<0){
				max_left=adjustmax(x->left);
			}
		}
		if(x->right!=NIL){
			max_right=x->right->max;
			if(max_right<0){
				max_right=adjustmax(x->right);
			}
		}
		max=root->high;
		if(max_left>max){
			max=max_left;
		}
		if(max_right>max)
			max=max_right;
	}
	root->max=max;
	return max;
}
node *tree_successor(node *z){
	if(z->right!=NIL){
		return tree_minimun(z->right);
	}
	node *y;
	y=z->parent;
	while(y!=NIL&&z==y->right){
		z=y;
		if(z!=root){ 
			if(z->color==BLACK)
				fprintf(outfile,"(%d %d) black max is %d parent's low is %d\n",z->low ,z->high,z->max,z->parent->low);
			else
				fprintf(outfile,"(%d %d) red max is %d parent's low is %d\n",z->low ,z->high,z->max,z->parent->low);
		}
		else{
			if(z->color==BLACK)
				fprintf(outfile,"(%d %d) black max is %d root\n",z->low ,z->high,z->max);
			else
				fprintf(outfile,"(%d %d) red max is %d root\n",z->low ,z->high,z->max);
		}
		y=y->parent;
	}
	return y;
}
node *tree_minimun(node *z){
	while(z->left!=NIL){
		z=z->left;
	}
	return z;
}
node *RB_delete(node *root,node *z){
	node *y,*x;
	fprintf(outfile,"\ndelete node (%d %d)\n",z->low ,z->high);
	if(z!=root){ 
		if(z->color==BLACK)
			fprintf(outfile,"(%d %d) black  parent %d\n",z->low ,z->high,z->parent->low);
		else
			fprintf(outfile,"(%d %d) red  parent %d\n",z->low ,z->high,z->parent->low);
	}
	else{
		if(z->color==BLACK)
			fprintf(outfile,"(%d %d) black max is %d root\n",z->low ,z->high,z->max);
		else
			fprintf(outfile,"(%d %d) red max is %d root\n",z->low ,z->high,z->max);
	}
	if(z->left==NIL||z->right==NIL){
		y=z;
	}
	else y=tree_successor(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->low=y->low;
		z->high=y->high;
	}
	if(y->color==BLACK){
		root=delete_fixup(root,x);
	}
	else{
		fprintf(outfile,"it dosn't need to fix up\n");
	}
	return root;
}
node *delete_fixup(node *root,node *x){
	node *w;
	fprintf(outfile,"delete fix up\n");
	while(x!=root&&x->color==BLACK){
		if(x==x->parent->left){
			w=x->parent->right;
			if(w->color==RED){
				w->color=BLACK;
				x->parent->color=RED;
				root=left_rotate(root,x->parent);
			}
			if(w->left->color==BLACK&&w->right->color==BLACK){
				w->color=RED;
				x=x->parent;
			}
			else if(w->right->color==BLACK){
				w->left->color=BLACK;
				w->color=RED;
				root=right_rotate(root,w);
				w=x->parent->right;
			}
			else{
				w->color=x->parent->color;
				x->parent->color=BLACK;
				w->right->color=BLACK;
				root=left_rotate(root,x->parent);
				x=root;
			}
		}
		else if(x=x->parent->right){
			w=x->parent->left;
			if(w->color==RED)
			{
				w->color=BLACK;
				x->parent->color=RED;
				root=right_rotate(root,x->parent);
				w=x->parent->left;
			}
			if((w->right->color==BLACK)&(w->left->color==BLACK))
			{
				w->color=RED;
				x=x->parent;
			}
			else if(w->left->color==BLACK)
			{
				w->right->color=BLACK;
				w->color=RED;
				root=left_rotate(root,w);
				w=x->parent->left;
			}
			else
			{
				w->color=x->parent->color;
				x->parent->color=BLACK;
				w->left->color=BLACK;
				root=right_rotate(root,x->parent);
				x=root;
			}
		}
		fprintf(outfile,"(%d %d) black parent %d\n",x->low,x->high,x->parent->low);
		if(w->color==BLACK){
			fprintf(outfile,"(%d %d) black parent %d\n ",w->low,w->high,w->parent->low);
		}
		else {
			fprintf(outfile,"(%d %d) red parent %d\n ",w->low,w->high,w->parent->low);
		}
	}
	x->color=BLACK;
	return root;
}

node* interval_search(node *root ,int low ,int high){
	node *x=root;
	bool overlap=false;
	if(x->low<high&&x->high>low){
		overlap=true;
	}
	while(x!=NIL&&overlap==false){
		if(x->left!=NIL&&x->left->max>=low){
			x=x->left;
		}
		else{
			x=x->right;
		}
		if(x->low<high&&x->high>low){
			overlap=true;
		}
	}
	if(x!=NIL){
	fprintf(outfile,"the node (%d %d) of the tree overlap the interval (%d %d)\n",x->low,x->high,low,high);
	}
	else{
		fprintf(outfile,"there isn't a node in the tree overlap the interval (%d %d)\n",low,high);
	}
	return x;
}

int main(){
	int i,j,num(0);
	node *z;
	NIL=(node *)malloc(sizeof(node));
	NIL->color=BLACK;
	NIL->low=0;
	NIL->high=0;
	NIL->max=0;
	NIL->left=NIL;
	NIL->right=NIL;
	NIL->parent=NIL;
	root=NIL;
	outfile=fopen("1073.out","wb");
    int interval[10][2]={{16,21},{8,9},{25,30},{5,8},{15,23},{17,19}, {26,26},{0,3},{6,10},{19,20}};
//	int interval[10][2]={{16,21},{8,9},{5,8},{15,23},{25,30}, {26,26},{0,3},{17,19}};
	fprintf(outfile,"%s\n","all the operation are based on the follow intervals");
	for(i=0;i<10;i++){
		if(interval[i][0]!=0||interval[i][1]!=0){
			num++;
			fprintf(outfile,"(%d %d)  ",interval[i][0],interval[i][1]);
		}
	}
	fprintf(outfile,"%c",'\n');
	for(i=0;i<num;i++){
		fprintf(outfile,"\ninsert node (%d %d)\n",interval[i][0],interval[i][1]);
		z=(node *)malloc(sizeof(node));
		z->color=RED;
		z->low=interval[i][0];
		z->high=interval[i][1];
		z->max=-1;
		z->left=NIL;
		z->right=NIL;
		z->parent=NIL;
		root=RB_insert(root,z);
	//	printf("root is (%d %d)\n",root->low,root->high);
	}
	adjustmax(root);
	printf("after insertion, ");
	display(root);
	srand(time(0));
	i=j=0;
	while(i==j){
		i=rand()%num;
		j=rand()%num;
	}
//	printf("%d %d\n",i,j);
//	fprintf(outfile,"\nsearch the node (%d %d)\n",interval[i][0],interval[i][1]);
	z=search(root,interval[i][0]);
    printf("\n\ndelete node (%d %d)\n",z->low,z->high);
	root=RB_delete(root,z);
	z=search(root,interval[j][0]);
	printf("delete node (%d %d)\n",z->low,z->high);
	root=RB_delete(root,z);
	adjustmax(root);
	printf("after deletion, ");
	display(root);
	fprintf(outfile,"\nsearch interval (8 25)\n");
	interval_search(root,8,25);
	printf("\nthe more information has been writen into a text file\n");
	return 0;
}