avl树

#include<time.h>

#include<iostream>

#include<stack>

using namespace std;



template<class E>

struct AVLNode

{

	int bf;   //ÆœºâÒò×Ó balance factor

	AVLNode *leftchild;  //leftchild

	AVLNode *rightchild; //rightchild

	E data;

	AVLNode(E el){ data=el;bf=0;leftchild=NULL;rightchild=NULL;};

};

template<class E>

class AVLTree

{

public:

	AVLTree():root(NULL){};          //construtor

	bool Insert(E el);              //insert new node

	bool Remove(E el);              //remove the node



	void output(ostream &out);       //output the AVLTree by inorder

private:

	AVLNode<E> *root;                //root of avl Tree

	void RotateL(AVLNode<E> *&ptr);  //rotation left

	void RotateR(AVLNode<E> *&ptr);  //rotation right

	void RotateLR(AVLNode<E> *&ptr); //rotation left right

	void RotateRL(AVLNode<E> *&ptr); //rotation right left

	void Traverse(AVLNode<E> *ptr,ostream &out); //traverse the tree inorder

};

//remove a node

//@param

//el  the key of the node to be removed

//if the node is removed successfully ,return true,else return false

template<class E>

bool AVLTree<E>::Remove(E el)

{

	AVLNode<E> *pr=NULL,*p=root,*q,*ppr;

	int d,dd=0;

	stack<AVLNode<E> *>st;

	while(p!=NULL)        //Ñ°ÕÒÉŸ³ýλÖÃ

	{

		if(el==p->data)break;  //ÕÒµœµÈÓÚkµÄœáµã Í£Ö¹ËÑË÷

		pr=p;

		st.push(pr);     //ÓÃÕ»ŒÇÒä²éÕÒ·Ÿ¶

		if(el<p->data)p=p->leftchild;

		else p=p->rightchild;

	}

	if(p==NULL) return false;     //ÎŽÕÒµœ±»ÉŸœáµã£¬ÉŸ³ýʧ°Ü

	if(p->leftchild!=NULL&&p->rightchild!=NULL)  //±»ÉŸœáµãÓÐÁœžö×ÓÅ®

	{

		pr=p;

		st.push(pr);

		q=p->leftchild;                    //ÔÚp×ö×ÖÊýÕÒpµÄÖ±œÓÇ°Çý

		while(q->rightchild!=NULL)

		{

			pr=q;

			st.push(pr);

			q=q->rightchild;

		}

		p->data=q->data;                 

		p=q;

	}

	if(p->leftchild!=NULL)q=p->leftchild;

	else q=p->rightchild;

	if(pr==NULL)root=q;

	else

	{

		if(pr->leftchild==p)pr->leftchild=q;

		else pr->rightchild=q;

		while(st.empty()==false)   //ÖØÐÂÆœºâ»¯

		{

			pr=st.top();

			st.pop();

			if(pr->rightchild==q)pr->bf--;

			else pr->bf++;

			if(st.empty()==false)

			{

				ppr=st.top();

				dd=(ppr->leftchild==pr)?-1:1;

			}

			else dd=0;            //Õ»¿Õ Ðýתºó²»ÓÃÓëÉϲãÁŽœÓ



			if(pr->bf==1||pr->bf==-1)break;

			if(pr->bf!=0)           //|bf|=2

			{

				if(pr->bf<0)

				{

					d=-1;

					q=pr->leftchild;

				}

				else

				{

					d=1;

					q=pr->rightchild;

				}

				if(q->bf==0)

				{

					if(d==-1)

					{

						RotateR(pr);

						pr->bf=1;

						pr->leftchild->bf=-1;

					}

					else

					{

						RotateL(pr);

						pr->bf=-1;

						pr->rightchild->bf=1;

					}

					break;

				}

				if(q->bf==d)        //ÁœœÚµãÆœºâÒò×ÓͬºÅ

				{

					if(d==-1) RotateR(pr);

					else RotateL(pr);

				}

				else                  //ÁœÆœºâÒò×Ó·ŽºÅ

				{

					if(d==-1)RotateLR(pr);

					else RotateRL(pr);

				}

				if(dd==-1)ppr->leftchild=pr;

				else if(dd==1)ppr->rightchild=pr;

			}

			q=pr;

		}

		if(st.empty()==true)root=pr;

	}

	delete p;

	return true;

}

//output the AVLTree inorder

//@param

//out  the ostream 

template<class E>

void AVLTree<E>::output(ostream &out)

{

	out<<"Inorder traversal of AVL Tree.\n";

	Traverse(root,out);

	out<<endl;

}

//Traverse the AVLTree inorder

//@param

//ptr the root of tree  

//out the ostream

template<class E>

void AVLTree<E>::Traverse(AVLNode<E> *ptr,ostream &out)

{

	if(ptr==NULL)return;

	Traverse(ptr->leftchild,out);

	out<<ptr->data<<"  ";

	Traverse(ptr->rightchild,out);

}

//insert new node into the AVLTree

//@param el new element to insert

//if insert successfully ,return true,else return false

template<class E>

bool AVLTree<E>::Insert(E el)

{

	AVLNode<E> *pr=NULL,*p=root,*q;

	 

	stack<AVLNode<E> *> st;

	while(p!=NULL)

	{                 //Ñ°ÕÒ²åÈëλÖÃ

		if(el==p->data) return false;  //ÕÒµœµÈÓÚelµÄœáµã£¬²»²åÈë

		pr=p;

		st.push(pr);

		if(el<p->data)p=p->leftchild;

		else  p=p->rightchild;

	}

	p=new AVLNode<E>(el);              //ŽŽœšÒ»žöÐÂœáµã£¬data=el,bf=0;

	if(p==NULL)

	{

		cerr<<"ŽæŽ¢¿ÕŒä²»×ã!"<<endl;

		exit(1);

	}

	if(pr==NULL)

	{

		root=p;     //¿ÕÊ÷£¬ÐÂœáµã³ÉΪžùœáµã

		return true;

	}

	if(el<pr->data) pr->leftchild=p; //²åÈëÐÂœáµã

	else pr->rightchild=p;



	while(st.empty()==false)

	{ //ÖØÐÂÆœºâ»¯

		pr=st.top();

		st.pop();



		if(p==pr->leftchild) pr->bf--;

		else pr->bf++;



		if(pr->bf==0)break;  //²åÈëÖ®ºóÆœºâ  Í˳ö



		if(pr->bf==1||pr->bf==-1)  //|bf|=1  ÔòŒÌÐøÏòÉÏÕÒ²»ÆœºâµÄœáµã

			p=pr;

		else                       //|bf|=2,Ôòµ÷Õû

		{

			int d=(pr->bf<0)?-1:1; //ÉÏÃæœáµãµÄ·ûºÅ

			if(p->bf==d)           //ÁœžöœáµãÆœºâÒò×ÓͬºÅ£¬µ¥Ðý

			{

				if(d==-1) RotateR(pr);

				else RotateL(pr);

			}

			else

			{

				if(d==-1) RotateLR(pr);

				else RotateRL(pr);

			}

			break;  //²»ÔÙÏòÉϵ÷Õû

		}

	}

	if(st.empty()) root=pr;  //µ÷ÕûµœÊ÷µÄžùœÚµã

	else

	{

		q=st.top();

		if(q->data>pr->data)q->leftchild=pr;

		else q->rightchild=pr;

	}

	return true;

}

//rotation left right

//@param

//ptr the root of the tree to be rotated

template<class E>

void AVLTree<E>::RotateLR(AVLNode<E> *&ptr)

{

	AVLNode<E> *subR=ptr,*subL=subR->leftchild;

	ptr=subL->rightchild;

	subL->rightchild=ptr->leftchild;

	subR->leftchild=ptr->rightchild;

	ptr->leftchild=subL;

	ptr->rightchild=subR;

	if(ptr->bf<=0)subL->bf=0;

	else subL->bf=-1;

	if(ptr->bf==-1)subR->bf=1;

	else subR->bf=0;

	ptr->bf=0;

}

//rotation right left

//@param

//ptr the root of the tree to be rotated

template <class E>

void AVLTree<E>::RotateRL(AVLNode<E> *&ptr)

{

	AVLNode<E> *subL=ptr,*subR=subL->rightchild;

	ptr=subR->leftchild;

	subL->rightchild=ptr->leftchild;

	subR->leftchild=ptr->rightchild;

	ptr->leftchild=subL;

	ptr->rightchild=subR;

	if(ptr->bf>=0)subR->bf=0;

	else subR->bf=1;

	if(ptr->bf==1)subL->bf=-1;

	else subL->bf=0;

	ptr->bf=0;

}

//rotation left

//@param

//ptr the root of the tree to be rotated

template<class E>

void AVLTree<E>::RotateL(AVLNode<E> *&ptr)

{

	AVLNode<E> *subL=ptr;

	ptr=subL->rightchild;

	subL->rightchild=ptr->leftchild;

	ptr->leftchild=subL;

	ptr->bf=subL->bf=0;

}

//rotation right

//@param

//ptr  the root of the tree to be rotated

template<class E>

void AVLTree<E>::RotateR(AVLNode<E> *&ptr)

{

	AVLNode<E> *subR=ptr;

	ptr=subR->leftchild;

	subR->leftchild=ptr->rightchild;

	ptr->rightchild=subR;

	subR->bf=0;

	ptr->bf=0;

}

int _tmain(int argc, _TCHAR* argv[])

{

	int n;

	srand(unsigned int(time(0)));

	n=rand()%5+5;

	int *arr=new int [n];

	for(int i=0;i<n;i++)

	{

		arr[i]=rand()%100;

		cout<<arr[i]<<"  ";

	}

	cout<<endl;



	AVLTree<int> myAVLTree;

	for(int i=0;i<n;i++)

	{

		myAVLTree.Insert(arr[i]);

	}

	myAVLTree.output(cout);

	myAVLTree.Remove(arr[0]);

	myAVLTree.output(cout);

	myAVLTree.Remove(arr[n-1]);

	myAVLTree.output(cout);

	myAVLTree.Remove(arr[n/2]);

	myAVLTree.output(cout);

	return 0;

}