rbtree.cpp

红黑树节点插入程序。可以在红黑树中插入新节点

#include<iostream>
#include<algorithm>
using namespace std;
enum color{red,black};
struct Element{ int key ;};
enum status{ok,rbr,brb,rrb,brr};
 struct RBtree{
	Element root;
	RBtree* leftSubtree;
	RBtree *rightSubtree;
	int color;
};
struct InsReturn{
	RBtree *newTree;
    int status;
};
void colorflip(RBtree* oldTree){
	oldTree->color=red;
	oldTree->leftSubtree->color  =black;
	oldTree->rightSubtree->color  =black;
}
RBtree *rebalLeft(RBtree* oldTree,int leftStatus){
	RBtree *l,*m,*r,*lr,*rl;
	if(leftStatus==rrb){
		r=oldTree;
		m=oldTree->leftSubtree ;
		l=m->leftSubtree ;
		rl=m->rightSubtree ;
		r->leftSubtree =rl;
		m->rightSubtree =r;
	}
	else{
		r=oldTree;
		l=oldTree->leftSubtree ;
		m=l->rightSubtree ;
		lr=m->leftSubtree ;
		rl=m->rightSubtree ;
		r->leftSubtree =rl;
		l->rightSubtree =lr;
		m->rightSubtree =r;
		m->leftSubtree =l;
	}
	l->color =red;
	r->color =red;
	m->color =black;
	return m;
}
InsReturn *repairLeft(RBtree *oldTree,InsReturn *ansLeft){
	InsReturn *ans=new InsReturn();
	if(ansLeft->status==ok){
		ans->newTree=oldTree;
		ans->status=ok;
	}
	else{
		oldTree->leftSubtree=ansLeft->newTree;
		if(ansLeft->status==rbr){
			ans->newTree=oldTree;
			ans->status=ok;
		}
		else if(ansLeft->status ==brb){
			if(oldTree->color==black)
				ans->status =ok;
			else
				ans->status=rrb;
			ans->newTree =oldTree;
		}
		else if(oldTree->rightSubtree !=NULL&&oldTree->rightSubtree ->color==red){
			colorflip(oldTree);
			ans->newTree =oldTree;
			ans->status =brb;
		}
		else{
			ans->newTree =rebalLeft(oldTree,ansLeft->status );
			ans->status =rbr;
		}
	}
	return ans;
}
RBtree *rebalRight(RBtree* oldTree,int rightStatus){
	RBtree *l,*m,*r,*lr,*rl;
	if(rightStatus==rrb){
		l=oldTree;
		r=oldTree->rightSubtree ;
		m=r->leftSubtree ;
		rl=m->rightSubtree ;
		lr=m->rightSubtree ;
		r->leftSubtree =rl;
		l->rightSubtree =lr;
		m->rightSubtree =r;
		m->leftSubtree =l;
	}
	else{
     	l=oldTree;
		r=oldTree->rightSubtree ;
		m=r->leftSubtree ;
		lr=m->rightSubtree ;
		l->rightSubtree =lr;
		m->leftSubtree =l;
	}
	l->color =red;
	r->color =red;
	m->color =black;
	return m;
}
InsReturn *repairRight(RBtree *oldTree,InsReturn *ansRight){
	InsReturn *ans=new InsReturn();
	if(ansRight->status==ok){
		ans->newTree=oldTree;
		ans->status=ok;
	}
	else{
		oldTree->rightSubtree=ansRight->newTree;
		if(ansRight->status==rbr){
			ans->newTree=oldTree;
			ans->status=ok;
		}
		else if(ansRight->status ==brb){
			if(oldTree->color==black)
				ans->status =ok;
			else
				ans->status=brr;
			ans->newTree =oldTree;
		}
		else if(oldTree->leftSubtree !=NULL&&oldTree->leftSubtree ->color==red){
			colorflip(oldTree);
			ans->newTree =oldTree;
			ans->status =brb;
		}
		else{
			ans->newTree =rebalRight(oldTree,ansRight->status );
			ans->status =rbr;
		}
	}
	return ans;
}
InsReturn* rbtIns(RBtree *oldRBtree,Element newNode){
	InsReturn *ans,*ansLeft,*ansRight;
	if(oldRBtree==NULL){
		ans=new InsReturn();
		RBtree *newtree=new RBtree();
		newtree->root=newNode;
		newtree->color =red;
		newtree->leftSubtree =NULL;
		newtree->rightSubtree =NULL;
		ans->newTree=newtree;
		ans->status=brb;
	}
	else{
		if(newNode.key<oldRBtree->root.key){
			ansLeft=rbtIns(oldRBtree->leftSubtree,newNode);
			ans=repairLeft(oldRBtree,ansLeft);
		}
		else{
			ansRight=rbtIns(oldRBtree->rightSubtree,newNode);
			ans=repairRight(oldRBtree,ansRight);
		}
	}
	return ans;

}
RBtree *rbtInsert(RBtree *oldRBtree,Element newNode){
	InsReturn *ans=rbtIns(oldRBtree,newNode);
	if(ans->newTree->color!=black)
		ans->newTree->color=black;
	return ans->newTree;
}
void BST(RBtree *oldtree){

	if(oldtree){
	   
	   BST(oldtree->leftSubtree );
	   cout<<oldtree->root.key<<" ";
	   BST(oldtree->rightSubtree );
	}
}
void main(){
	RBtree *oldRBtree=NULL;
    
	int i=0;
	Element arr[4];
		arr[0].key=40;
		arr[1].key =20;
		arr[2].key =30;
		arr[3].key =60;
	while(i<4){
		oldRBtree=rbtInsert(oldRBtree,arr[i++]);
	}
    BST(oldRBtree);
}