rbtree.h

基本的二叉树程序。可实现二叉树结点数据的插入

//Rbtree.h  Begin
#ifndef _RBTREE_H
#define _RBTREE_H
#include<iostream.h>
#include<stdlib.h>
template<class T>
class RBtree
{
public:
	enum Color{Red,Black};
private:
	class RBnode
	{
		T value;
		Color color;
		RBnode *p;
		RBnode *left;
		RBnode *right;
			RBnode():value(0),color(Red),p(NULL),left(NULL),right(NULL){};
		RBnode(const T &val):value(val),color(Red),p(NULL),left(NULL),right(NULL){};
		friend class RBtree<T>;
	public:
		void Print(int level)
		{
			for(int i=0;i<level;++i)			// puts spaces
				cout<<"         ";
			cout<<"|"<<value;					// formatted print - |value(color)
			if (color==Black)
				cout<<"(B)";
			else	
				cout<<"(R)";
			return;
		}
	};
	RBnode *ROOT;
	RBnode *NIL;
	int alive;				// for debugging purpesess only - not really neaded
public:
	RBtree():ROOT(new RBnode()),NIL(ROOT),alive(0){NIL->left=NIL->right=NIL->p=NIL;NIL->color=Black;}
	RBtree(const T &val):ROOT(new RBnode(val)),NIL(new RBnode()),alive(1)
	{
		NIL->color=Black;
		NIL->left=NIL->right=NIL->p=NIL;
		ROOT->left=ROOT->right=ROOT->p=NIL;
	}
	~RBtree(){if(ROOT!=NIL)	DeleteAll(ROOT);delete NIL;}
	void Insert(const T&);						// Inserting a new value to tree
	void Delete(const T&);						// Deleteing an onl value form tree
	RBnode *RBFind(const T &val)             // finding value in tree if found
// returnes node otherwise return NIL
	{					
		RBnode *tmp=ROOT;
		while((tmp!=NIL)&&(tmp->value!=val))
			tmp=val<tmp->value ? tmp->left : tmp->right;
		return tmp;
	}
	bool Find(const T &val)		// the same as above but returns true if found false if not
	{					
		RBnode *tmp=RBFind(val);
		return (tmp!=NIL);
	}
	RBnode* RBMax(RBnode* start){RBnode *tmp=start;while(tmp->right!=NIL)tmp=tmp->right;return tmp;}
//the max node in the tree
	RBnode* RBMin(RBnode* start){RBnode *tmp=start;while(tmp->left!=NIL)tmp=tmp->left;return tmp;}	
// the min node in the tree
	RBnode* RBPred(RBnode* start)
	{
		RBnode *tmp=start;
		if (tmp->left!=NIL)
			tmp=RBMax(tmp->left);
		else
		{
			RBnode *ptmp=tmp;
			tmp=tmp->p;
			while((tmp!=NIL)&&(ptmp!=tmp->right))
			{
				ptmp=tmp;
				tmp=tmp->p;
			}
		}
		return tmp;
	}
	RBnode* RBSucc(RBnode* start)
	{
		RBnode *tmp=start;
		if (tmp->right!=NIL)
			tmp=RBMin(tmp->right);
		else
		{
			RBnode *ptmp=tmp;
			tmp=tmp->p;
			while((tmp!=NIL)&&(ptmp!=tmp->left))
			{
				ptmp=tmp;
				tmp=tmp->p;
			}
		}
		return tmp;
	}
	void Print();						// prints a RBtree
	void RotateLeft(RBnode*);			// used in inset & delete functions
	void RotateRight(RBnode*);
	int NodeInsert(RBnode*);			// puts a node in the tree
	void FixDel(RBnode*);				// fixing the Delete proc
	T Succ(const T &val)				// printing the successor of sertain value
	{				
		RBnode *tmp=RBFind(val);
		if (tmp==NIL)
		{ 
			cout<<"value not found";
			return 0;
		}
		else
			tmp=RBSucc(tmp);
		return tmp->value;
	}

	T Pred(const T &val)				// the same for predecessor
	{		
		RBnode *tmp=RBFind(val);
		if (tmp==NIL)
		{
			cout<<"value not found";
			return 0;
		}
		else
			tmp=RBPred(tmp);
		return tmp->value;
	}
	
	T Max(const T &val){RBnode *tmp=RBMax(ROOT);return tmp->value;}	//prints max
	T Min(const T &val){RBnode *tmp=RBMin(ROOT);return tmp->value;}	//prints min
	void RBPrint(RBnode*,int);					// req func for printing RBtree
	void DeleteAll(RBnode*);					// deletes all of the RBtree (except the NIL);
};
template<class T>
void RBtree<T>::Insert(const T &val){
	RBnode* x=new RBnode(val),*y;
	if(NodeInsert(x)==1)
	{
		cout<<val<<" alread exist in tree"<<endl;
		return;
	}
	while ((x!=ROOT)&&(x->p->color==Red))
	{
		if (x->p==x->p->p->left)		// if x parent is left son
		{	
			y=x->p->p->right;			// checking x uncle	
			if (y->color==Red)			// if red case 1
			{			
				x->p->color=Black;
				y->color=Black;
				x->p->p->color=Red;
				x=x->p->p;
			}
			else
			{
				if (x==x->p->right)		//if x right the case 2
				{	
					x=x->p;
					RotateLeft(x);
				}
				x->p->color=Black;		// case 3
				x->p->p->color=Red;
				RotateRight(x->p->p);
			}
		}
		else
		{
				y=x->p->p->left;		// checking x uncle	
			if (y->color==Red)			// if red case 4
			{		
				x->p->color=Black;
				y->color=Black;
				x->p->p->color=Red;
				x=x->p->p;
			}
			else
			{
				if (x==x->p->left)		//if x right the case 5
				{	
					x=x->p;
					RotateRight(x);
				}
				x->p->color=Black;		// case 6
				x->p->p->color=Red;
				RotateLeft(x->p->p);
			}
		}
	}
	ROOT->color=Black;
	return;
}
template<class T>
void RBtree<T>::Delete(const T &val)
{
	RBnode *z,*y,*x;
	z=RBFind(val);
	if(z==NIL)
	{
		cout<<val<<" not found"<<endl;
		return;
	}
	--alive;
	if ((z->left == NIL)||(z->right==NIL))	// delteing from leaves
		y=z;
	else
		y=RBSucc(z);
	if (y->left!=NIL)
		x=y->left;
	else 
		x=y->right;
		x->p=y->p;
	if (y->p==NIL)
	{
		ROOT=x;
		x->p=NIL;
	}
	else
	{ 
		if (y==y->p->left)
			y->p->left=x;
		else
			y->p->right=x;
	}
	if (y!=z)				// if we changed the successor with z
		z->value=y->value;
	if (y->color==Black)
		FixDel(x);			// if we delted a Black node we have to rearrange the tree
	delete y;
	if (x==NIL)
		x->p=NIL;
	return;
}
template<class T>
void RBtree<T>::RotateLeft(RBnode* x)
{
	RBnode* y=x->right;
	x->right=y->left;
	if (y->left!=NIL)
		y->left->p=x;
	y->p=x->p;
	if (x->p==NIL)
		ROOT=y;
	else if (x==x->p->left)
		x->p->left=y;
	else
		x->p->right=y;
	y->left=x;
	x->p=y;
	return;
}
template<class T>
void RBtree<T>::RotateRight(RBnode* x)
{
	RBnode* y=x->left;
	x->left=y->right;
	if (y->right!=NIL)
		y->right->p=x;
	y->p=x->p;
	if (x->p==NIL)
		ROOT=y;
	else if (x==x->p->right)
		x->p->right=y;
	else
		x->p->left=y;
	y->right=x;
	x->p=y;
	return;
}
template<class T>
int RBtree<T>::NodeInsert(RBnode *x)
{
	RBnode *tmp1=ROOT,*tmp2=tmp1;
	if (ROOT==NIL)
	{				// in case that x is the 1st node
		ROOT=x;
		x->left=x->right=x->p=NIL;
		++alive;
		return 0;
	}		
	while((tmp1!=NIL)&&(tmp1->value!=x->value))
	{
		tmp2=tmp1;
		tmp1=x->value>tmp1->value ? tmp1->right : tmp1->left;
	}
	if (tmp1==NIL){				// if the item not in tree - add
		if (x->value>tmp2->value)
			tmp2->right=x;
		else
			tmp2->left=x;
		x->p=tmp2;
		x->left=x->right=NIL;
		++alive;
		return 0;
	}
	return 1;
}
template<class T>
void RBtree<T>::FixDel(RBnode *x)
{
	RBnode *w;
	while ((x!=ROOT)&&(x->color==Black))
	{
		if (x==x->p->left){						// if x is the right son
			w=x->p->right;
			if (w->color==Red){					// case 1
				w->color=Black;
				x->p->color=Red;
				RotateLeft(x->p);
				w=x->p->right;
			}
			if ((w->left->color==Black)&&(w->right->color==Black))
			{
				w->color=Red;					// case 2
				x=x->p;
			}else{
				if (w->right->color==Black)
				{	
					w->left->color=Black;		// case 3
					w->color=Red;
					RotateRight(w);
					w=x->p->right;
				}
				w->color=x->p->color;			// case 4
				x->p->color=Black;
				w->right->color=Black;
				RotateLeft(x->p);
				x=ROOT;
			}
		}
		else
		{									// if x is the left son
			w=x->p->left;
			if (w->color==Red)				// case 5
			{				
				w->color=Black;
				x->p->color=Red;
				RotateRight(x->p);
				w=x->p->left;
			}
			if ((w->right->color==Black)&&(w->left->color==Black))
			{
				w->color=Red;					// case 6
				x=x->p;
			}
			else
			{
				if (w->left->color==Black)		// case 7
				{	
					w->right->color=Black;		
					w->color=Red;
					RotateLeft(w);
					w=x->p->left;
				}
				w->color=x->p->color;			// case 8
				x->p->color=Black;
				w->left->color=Black;
				RotateRight(x->p);
				x=ROOT;
			}
		}
	}
	x->color=Black;
	return;
}

template<class T>
void RBtree<T>::Print()
{
	int depth=-1;
	RBnode *x=ROOT;
	RBPrint(x,depth);
	return;
}
// the printing will be done so that the root will be on the left
// and the tree will expend to the right
template<class T>
void RBtree<T>::RBPrint(RBnode *x,int level)
{
	if (x==NIL) return;
	++level;
	RBPrint(x->right,level);
	x->Print(level);
	cout<<"---|"<<endl;
	RBPrint(x->left,level);
	return;
}
template<class T>
void RBtree<T>::DeleteAll(RBnode *x)
{
	if(x==NIL) return;
	DeleteAll(x->left);
	DeleteAll(x->right);
	delete x;
};
#endif
//Rbtree.h end