rbt.cpp

这是一个用c语言实现了实现区间数相关操作的程序

#include <iostream>
#include <cstdlib>
using namespace std;
typedef int KEY;
enum  NODECOLOR{RED,BLACK};  
typedef struct filed  
{
	int low;
	int high;
}  Field;

typedef struct RBTree 
{
	NODECOLOR color;
	int key;
	int size;                    
	int max; 
    Field field;    
	RBTree * left;   
	RBTree * right;    
	RBTree * parent; 
}  *PRBTree;



char* color[] = {"RED", "BLACK"};
void Left_Rotate(PRBTree &root,PRBTree x)   
{
	PRBTree y;
	y = x->right;
	if(!y)
		return;
	x->right = y->left;
	if (y->left!=NULL)
    	y->left->parent = x;
	y->parent = x->parent;

	if (x==root )
	{
		root = y;
	}
	else if (x == x->parent->left)
	{
	    x->parent->left = y;
	}
	else
		x->parent->right = y;

	y->left = x;
	x->parent = y;
	y->size = x->size;              
	if(x->left==NULL&&x->right!=NULL)
		x->size = x->right->size + 1;  
	else if(x->right==NULL && x->left !=NULL)
		x->size = x->left->size + 1;
	else if(x->left!=NULL&&x->right!=NULL)
		x->size = x->left->size + x->right->size +1;
	else if(x->left==NULL && x->right ==NULL)
		x->size = 1;
}

///////////////////////////////////////////////////////////
void Right_Rotate(PRBTree &root,PRBTree x)       
{
   RBTree *y;
   y = x->left;
   if(!y)
	   return;
   x->left = y->right;
   if(y->right!=NULL)
	   y->right->parent = x;
   y->parent = x->parent;

   if (x==root)
	  root = y;
   else if (x == x->parent->left)
	   x->parent->left = y;
   else
	   x->parent->right = y;

   y->right = x;
   x->parent = y;
   y->size = x->size;
   if(x->left==NULL&&x->right!=NULL)  
		x->size = x->right->size + 1;  
   else if(x->right==NULL && x->left !=NULL)
		x->size = x->left->size +1;
   else if(x->left!=NULL&&x->right!=NULL)
		x->size = x->left->size + x->right->size + 1;
   else if(x->left==NULL && x->right ==NULL)
		x->size = 1;
}
//////////////////////////////////////////////////////
PRBTree RB_insert_fixup(PRBTree root,PRBTree z) 
{  
	PRBTree  y;
		while((root!=z)&&(z->parent->color == RED))  
		{
			if(z->parent ==z->parent->parent->left)  

			{
				y = z->parent->parent->right;      
				if( y != NULL && 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;
						Left_Rotate(root,z);        
					}
					z->parent->color = BLACK;      
					z->parent->parent->color = RED;
					Right_Rotate(root,z->parent->parent);
				}
			}
			else                                            
			{
				y = z->parent->parent->left;
				if( y != NULL && 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;
						Right_Rotate(root,z);            
					}
					z->parent->color = BLACK;
					z->parent->parent->color = RED;          
					Left_Rotate(root,z->parent->parent);
				}
			}
		} 


	 root->color = BLACK;   
	 return root;
}

///////////////////////////////////////////////////////////////////////
PRBTree RB_insert(PRBTree root,KEY key,KEY high)  
{   
	PRBTree  y , x;
	PRBTree z;
	if(!(z = (RBTree *)malloc(sizeof(RBTree))))  
		{
			cout<<"memory out"<<endl;
			exit(1);
		}

		z->key = key; 
		(z->field).low = key;
		(z->field).high = high;
		z->max = high;
		z->size = 1;
	y = NULL;
	x = root;
	while (x != NULL)
	{
		y = x;
		if (z->key < x->key)
			if(x->left!=NULL)
			{   
				x->size = x->size + 1; 
				x = x->left;
			}
			else
			{	
	            x->size = x->size + 1; 
				break;
			}
		else
			if(x->right!=NULL)
			{
				x->size = x->size + 1; 
				x = x->right;
			
			}
			else
			{
				x->size = x->size + 1; 
				break;
			}
		
         
	}

	z->parent = y;

	if (y==NULL)
	{
		root = z;
	}
	else if (z->key < y->key)
	{
		y->left = z;
	}
	else
	{
		y->right = z;
	}

	z->left = NULL;
	z->right = NULL;
	z->color = RED;
	return RB_insert_fixup(root,z);   

}
///////////////////////////////////////////////////////////////////////////////
void Fixtree(PRBTree &x)  
{
	KEY max;
	if (x->left != NULL)
		Fixtree(x->left);
	if (x->right != NULL)
		Fixtree(x->right);	
	if (x->left == NULL && x->right !=NULL)
	{
		x->max = (((x->field).high) >= (x->right->max)) ? ((x->field).high) : (x->right->max) ;
	}
	else if(x->left != NULL && x->right == NULL)
	{
		x->max = (((x->field).high) >= (x->left->max)) ? ((x->field).high) : (x->left->max) ;
	}
	else if(x->left != NULL && x->right !=NULL)
	{
		max = (((x->field).high) >= (x->left->max)) ? ((x->field).high) : (x->left->max) ;
		x->max = (max >= (x->right->max)) ? max : (x->right->max) ;
	}

}
///////////////////////////////////////////////////////////////////////////////////
void Print(PRBTree x)   
{
	cout<<"key: "<<x->key<<"\tlow: "<<(x->field).low;
	cout<<"\thigh: "<<(x->field).high<<"\tmax: "<<x->max;
	cout<<"\tcolor: "<<color[x->color]<<"  parent: ";
	if(x->parent!=NULL)
		cout<<x->parent->key;
	else
		cout<<"NULL";
	cout<<"\tleft: ";
    if(x->left!=NULL)
		cout<<x->left->key;
	else
		cout<<"NULL";
	cout<<"\tright: ";
	if(x->right!=NULL)
		cout<<x->right->key;
	else
		cout<<"NULL";
	cout<<"\tsize:"<<x->size;
	if(x->left==NULL&&x->right==NULL)
		cout<<"\tis Leaves";
	if(x->parent==NULL)
		cout<<"\tis root";
	cout<<endl;	
}
//////////////////////////////////////////////////////////////////////////////////////
void Visittree(PRBTree root)      
{    
	PRBTree x = root;
   
    if (x != NULL)
    {
		if (x->left)
			Visittree(x->left);
		Print(x);
		if (x->right)
			Visittree(x->right);	   
	    
	}
}
/////////////////////////////////////////////////////////////////////////////////////
PRBTree Interval_Search(PRBTree T, Field i) 
{
	PRBTree x = T; 
    int flag = 0 ;   

	if ((i.low <= (x->field).high) && ((x->field).low <= i.high))  
		flag = 1;
	while(x != NULL && flag == 0)
	{
		if((x->left !=NULL) && (x->left->max >= i.low))
			x = x->left ;
		else
			x= x->right;


		if ((i.low <= (x->field).high) && ((x->field).low <= i.high))  
			flag = 1;
		
	}
   
	return x;   

}
////////////////////////////////////////////////////////////////////////////////
int main()
{
	PRBTree  root=NULL;  
	PRBTree  returnvalue;
	int key,high;
	Field  interval;
	cout<<"please input information key and high :"<<endl;
	cout<<" key=-1(表示结束输入)"<<endl;
    cout<<"key:";
	cin>>key;
   
	if (key!=-1)
	{
		cout<<"high:";
		cin>>high ;
	}
	cout<<endl;

	while (key!=-1)
	{  	
		while(key >= high)  
		{
			cout<<"input error! key should smaller than high! \n";
			cout<<"please input low, high  again: \n";
			cout<<"key:";
			cin>>key;
		    if(key==-1)
				break;
			cout<<"high:";
			cin>>high ;
		} //endwhile             
	  	root = RB_insert(root,key,high);	   
		cout<<"please input key and high:"<<endl;
	    cout<<"key:";
		cin>>key;
		 if (key==-1)
			break;
		cout<<"high:";
		cin>>high ;

	    cout<<endl;
	}  //endwhile

	if(root)
		Fixtree(root);     
	else
	{
		cout<<"no node !!";
		exit(0);
	}

	int i;
	cout<<"please input node information(0——显示树/1——查找结点):";
	cin>>i;
	if(!i)
	{
		Visittree (root);  
		cout<<endl;
	}
	else
	{
		cout<<"please input a interval to search(low, high): \n";
		cout<<"low:";
		cin>>interval.low;
		cout<<"high:";
		cin>>interval.high ;
		while(interval.low >= interval.high)  
		{
			cout<<"input error,low should be smaller than high! \n";
			cout<<"please input low, high: \n";
			cout<<"low:";
			cin>>interval.low;
			cout<<"high:";
			cin>>interval.high ;
		}
		if (returnvalue = Interval_Search(root, interval))   
			cout<<"the result node key is "<<returnvalue->key<<endl;
		else
			cout<<"there is no interval !"<<endl;
	}
	return 0;
}