红黑树.cpp

常见算法

//红黑树插入法生成树，查找最大和最小数，查找前驱和后继，删除某节点，按顺序输出数
#include<iostream>
using std::cin;
using std::cout;
using std::endl;
#define N 10

enum col{R,B};
struct Red_Black
{
	enum col color ;
    struct Red_Black*father;
	struct Red_Black*left;
	struct Red_Black*right;
	int key;
};
#include"output.h" 
#define SIZE sizeof(struct Red_Black)
//===============================================
//                   左旋转
//===============================================
int LEFT_ROTATE(struct Red_Black*rootofRotate,struct Red_Black*point)
{
	struct Red_Black*Rson,*Rson_L;
    Rson=point->right;                                //Rson是point的右子，                                
    if (Rson==NULL)
	{
		cout<<"不符合旋转条件，不能左转！"<<endl;
		return 0;
    }
	Rson_L=Rson->left;      //Rson_L是point右子的左子。
	
	//Rson放在point的位置
    Rson->father=point->father; 
	if (point->father!=NULL)
	{
	                                             //Rson之父变为point之父。
	    if (point==point->father->left)              //如果point是左子，
		{                                            //Rson变为旋转后的左子
	        point->father->left=Rson;
		}
    	if (point==point->father->right)            //如果point是右子，
		{                                           //Rson变为旋转后的右子
		    point->father->right=Rson;
		}
	}
	//point放在Rson_L的位置
    Rson->left=point;
	point->father=Rson;
	//Rson_L取代Rson的位置
	if (Rson_L!=NULL)
	{
	    Rson_L->father=point;
	}
	point->right=Rson_L;
	return 0;
}
//=====================================================
//                        右旋转
//=====================================================
int RIGHT_ROTATE(struct Red_Black*rootofRotate,struct Red_Black*point)
{                                //rootofRotate是树的根，point是旋转的上节点。
     struct Red_Black*Lson,*Lson_R;
	 Lson=point->left;
	 
	 if(Lson==NULL)
	 {
		 cout<<"不符合条件，不能右旋转！"<<endl;
		 return 0;
	 }
     Lson_R=Lson->right;
	
	 //Lson取代point的位置
     Lson->father=point->father;
	     
	 if (point->father!=NULL)
	 { 
		 if(point==point->father->left)
		 {
			 point->father->left=Lson;
		 }
		 if(point==point->father->right)
		 {
			 point->father->right=Lson;
		 }
	 }
	 //point放在Lson的位置
     point->father=Lson;
	 Lson->right=point;
	 
	 
	 //Lson_R放在Lson的位置
	 if (Lson_R!=NULL) 
	 {
	     Lson_R->father=point;
	 }
	 point->left=Lson_R; 
	 return 0;
}

//=====================================================
//  插入一个元素，不管是否符合红黑树性质，并返回插入点//
//=====================================================
struct Red_Black*INSERT_RED_BLACK(int numin,struct Red_Black*rootofinsert)
{                                                   //rootofinsert是树的根结点
	struct Red_Black*root;
	
    //将数字插入树中，令插入的节点颜色为红色，这样不改变树的黑高度。
    root=rootofinsert;
	if (root==NULL)                        
	{
		root=(struct Red_Black*)malloc(SIZE); 
		root->key=numin;
	    root->color=R;
        root->left=NULL;
	    root->right=NULL; 
		root->father=NULL;                          //如果插入的是根部。
		return root;
		
	}
	if ((root->left==NULL)&&(numin<root->key))
	{
		root->left=(struct Red_Black*)malloc(SIZE);
		root->left->key=numin;
		root->left->color=R;
		root->left->left=NULL;
		root->left->right=NULL;
		root->left->father=root;
		return root->left;
	}
	if ((root->right==NULL)&&(numin>=root->key))
	{
		root->right=(struct Red_Black*)malloc(SIZE);
		root->right->left=NULL;
		root->right->color=R;
		root->right->key=numin;
		root->right->right=NULL;
		root->right->father=root;
		return root->right;
	}
	if (numin<root->key)
	{
		return INSERT_RED_BLACK(numin,root->left);
	}
	else
	{
        return INSERT_RED_BLACK(numin,root->right);
	}
}

//======================================================================
//保持红黑树性质不变，红节点的子不能为红，针对插入后改变红黑性质的操作。
//======================================================================
int THE_SAME_HIGHT(struct Red_Black*root,struct Red_Black*pointofbreak)     //pointofbreak节点表示插入的点.
{
    struct Red_Black*father,*Lson,*Rson,*uncle;
    if (pointofbreak->father==NULL)
	{
        pointofbreak->color=B;
		return 0;
    }
	//找叔父节点uncle。
	if (pointofbreak->father->father!=NULL)   
	{
	    if (pointofbreak->father==pointofbreak->father->father->left)
		{
			uncle=pointofbreak->father->father->right;
	    }
		if (pointofbreak->father==pointofbreak->father->father->right)
		{
			uncle=pointofbreak->father->father->left;
		}
	}
	else{uncle=NULL;}
	father=pointofbreak->father;
	Lson=pointofbreak->left;
	Rson=pointofbreak->right;
    if ((pointofbreak!=root)&&(father->color==B))
	{
		
    }
    return 0;
}
main()
{
	int i;
	int array[N]={34,43,45,13,23,43,54,23,65,21};
	struct Red_Black*root0,*root=NULL,*accept=(struct Red_Black*)malloc(SIZE),*find;
	cout<<"要处理的数是："<<endl;
	for (i=0;i<N;i++)
	{
		cout<<array[i]<<"  ";
	}
	cout<<endl;                              
	root=INSERT_RED_BLACK(array[0],root);  //取得根的指针，所以单独插入。
	for (i=1;i<N;i++)
	{
		root0=INSERT_RED_BLACK(array[i],root);
        
	}
	output_tree(root);
	cout<<endl;
	cout<<"找到的数是：";
	cin>>i;
	find=find_tree(i,root);
	cout<<find->key<<endl;
	RIGHT_ROTATE(root,find);
    LEFT_ROTATE(root,find);
	return 0;
}