avltree.h

在各种各样的搜索算法中

#ifndef AVLTREE_H
#define AVLTREE_H
#include"xcept.h"
#include<iostream>
#include<vector>
using namespace std;
template<class T> class AVLtree;
template<class T>
class AVLtreeNode
{
	friend AVLtree<T>;
	public:
		AVLtreeNode()
		{
			Left=Right=0;
			bf=0;
		}
		AVLtreeNode(const T x)
		{
			data=x;
			Left=Right=0;
			bf=0;
		}
		AVLtreeNode(const T x,AVLtreeNode<T>* l,AVLtreeNode<T> *r)
		{
			data=x;
			Left=l;
			Right=r;
			bf=0;
		}
	private:
		AVLtreeNode<T>* Left,* Right;
		T data;
		int bf;//平衡因子
};
template<class T>
class AVLtree
{
	public:
		AVLtree(){root=0;}
		~AVLtree(){}
		int V_height(AVLtreeNode<T>* t);//求平衡因子
		int Height(AVLtreeNode<T>* t);
		AVLtree<T>& Insert(const T e);
		AVLtree<T>& Delete(T& x);
		void output();
		AVLtreeNode<T>* Root(){return root;}
	private:
		void ROrotate(AVLtreeNode<T>* A);//删除发生在R子树，B点为的平衡因子为1或0
		void R_1rotate(AVLtreeNode<T>* A);//删除发生在R子树，B点为的平衡因子为-1
    	void LOrotate(AVLtreeNode<T>* A);//删除发生在R子树，B点为的平衡因子为-1或0
		void L1rotate(AVLtreeNode<T>* A);//删除发生在R子树，B点为的平衡因子为1
		void LLrotate(AVLtreeNode<T>* A,AVLtreeNode<T>* pA,int flag);
		void LRrotate(AVLtreeNode<T>* A,AVLtreeNode<T>* pA,int flag);
		void RLrotate(AVLtreeNode<T>* A,AVLtreeNode<T>* pA,int flag);
		void RRrotate(AVLtreeNode<T>* A,AVLtreeNode<T>* pA,int flag);
		void visit(AVLtreeNode<T>* t,T a[],int i);
		void preorder(AVLtreeNode<T>* t,T a[],int i);
		int power(int h);
		void setposition(int m);
		AVLtreeNode<T>* root;
};
template<class T>
void AVLtree<T>::ROrotate(AVLtreeNode<T>* A)
{
	AVLtreeNode<T>* B=A->Left;
	A->Right=new AVLtreeNode<T>(A->data,B->Right,A->Right);
	A->data=B->data;
	A->Left=B->Left;
}
template<class T>
void AVLtree<T>::R_1rotate(AVLtreeNode<T>* A)
{
	AVLtreeNode<T>* C=A->Left->Right;
	AVLtreeNode<T>* B=A->Left;
	A->Right=new AVLtreeNode<T>(A->data,C->Right,A->Right);
	A->data=C->data;
	B->Right=C->Left;
}
template<class T>
void AVLtree<T>::LOrotate(AVLtreeNode<T>* A)
{
	AVLtreeNode<T>* B=A->Right;
	A->Left=new AVLtreeNode<T>(A->data,A->Left,B->Left);
	A->data=B->data;
	A->Right=B->Right;
}
template<class T>
void AVLtree<T>::L1rotate(AVLtreeNode<T>* A)
{
	AVLtreeNode<T>* C=A->Right->Left;
	AVLtreeNode<T>* B=A->Right;
	A->Left=new AVLtreeNode<T>(A->data,A->Left,C->Left);
	A->data=C->data;
	B->Left=C->Right;
}
template<class T>
AVLtree<T>& AVLtree<T>::Delete(T& x)
{
	vector<AVLtreeNode<T>* > v;
	v.clear();
	AVLtreeNode<T> *p=root,*pp=0;//p为删除节点 ，pp为p父节点
	while(p && p->data!=x)
	{
		pp=p;
		v.push_back(pp);
		if(x<p->data)
			p=p->Left;
		else 
			p=p->Right;
	}
	if(!p)
		throw BadInput();
	//所删除的节点有两个孩子的情况
	if(p->Left && p->Right)
	{
		AVLtreeNode<T>* s=p->Left,*ps=p;//s为左子树的最大节点，ps是s父节点
		while(s->Right)
		{
			ps=s;
			v.push_back(ps);
			s=s->Right;
		}
		p->data=s->data;
		p=s;
		pp=ps;
	}
	//只有一个孩子节点或没有孩子的情况
	AVLtreeNode<T>* c;
	if(p->Left)
	{
		c=p->Left;
	}
	else 
	{
		c=p->Right;
	}
	if(p==root)
	{
		c=root;
	}
	else
	{
		int flag;
		if(pp->Left==p)
		{
			pp->Left=c;
			flag=1;
		}
		else
		{
			pp->Right=c;
			flag=2;
		}
	}
	delete p;
	V_height(root);//修改平衡因子
	for (int j=v.size()-1;j>=0;j--)
		if(v[j]->bf==2||v[j]->bf==-2)
		{
			pp=v[j];
			break;
		}
RO:	if(pp->bf==2)
	{
		if(pp->Left->bf==0)//LR0型不平衡
		{
			ROrotate(pp);
			V_height(root);
		}
		else if(pp->Left->bf==1)//LR1型
		{
			ROrotate(pp);
			V_height(root);
			if(v.size()>1)
			{
				v.pop_back();
		    	pp=v[v.size()-1];
		    	if(pp->bf==2 || pp->bf==-2)
					goto RO;
			}
		}
		else if(pp->Left->bf==-1)//LR-1型
		{
			R_1rotate(pp);
			V_height(root);
			if(v.size()>1)
			{
				v.pop_back();
		    	pp=v[v.size()-1];
		    	if(pp->bf==2 || pp->bf==-2)
			    	goto RO;
			}
		}
	}
	else if(pp->bf==-2)
	{
		if(pp->Right->bf==0)
		{
			LOrotate(pp);
			V_height(root);
		}
		else if(pp->Right->bf==-1)
		{
			LOrotate(pp);
			V_height(root);
			if(v.size()>1)
			{
				v.pop_back();
	    		pp=v[v.size()-1];
		    	if(pp->bf==2 || pp->bf==-2)
		    		goto RO;
			}
		}
		else if(pp->Right->bf==1)
		{
			L1rotate(pp);
			V_height(root);
			if(v.size()>1)
			{
				v.pop_back();
		    	pp=v[v.size()-1];
		    	if(pp->bf==2 || pp->bf==-2)
			    	goto RO;
			}
		}

	}
	return *this;
}
template<class T>
int AVLtree<T>::V_height(AVLtreeNode<T>* t)
{
	if(!t)
		return 0;
	int h1=V_height(t->Left);
	int h2=V_height(t->Right);
	t->bf=h1-h2;
	if(h1>h2)
		return ++h1;
	else 
		return ++h2;
}
template<class T>
AVLtree<T>& AVLtree<T>::Insert(const T e)
{
	AVLtreeNode<T>* p=root;
	AVLtreeNode<T>* pp=0;//pp为p的父节点
	AVLtreeNode<T>* p_Anear=0;
	AVLtreeNode<T>* Anear=0;//Anear为插入前离插入点最近的为－1或1的点，p_Anear为Anear的父节点
	V_height(p);
	if(p && (p->bf==1 || p->bf==-1))
		Anear=p;
	while(p)
	{
		pp=p;
		if(e>p->data)
			p=p->Right;
		else if(e<p->data)
			p=p->Left;
		else
			throw BadInput();
		if(p && (p->bf==1 || p->bf==-1))
		{
			p_Anear=pp;
			Anear=p;
		}
	}
	AVLtreeNode<T> *r=new AVLtreeNode<T>(e);
	if(root)
	{
		if(pp->data<e)
			pp->Right=r;
    	else 
	    	pp->Left=r;
	}
	else
		root=r;
	if(!Anear)
	{
		V_height(root);
		return *this;
	}
	int flag;
	if(p_Anear && p_Anear->Left==Anear)
		flag=1;
	else if(p_Anear && p_Anear->Right==Anear)
		flag=2;
	if(Anear)
	{
		V_height(Anear);
		if(!Anear->bf)
			return *this;
		else
		{
			if(Anear->bf==2)
			{
				if(Anear->Left->bf==1)
					LLrotate(Anear,p_Anear,flag);
				else if(Anear->Left->bf==-1)
					LRrotate(Anear,p_Anear,flag);
			}
			else if(Anear->bf==-2)
			{
				if(Anear->Right->bf==1)
					RLrotate(Anear,p_Anear,flag);
				else if(Anear->Right->bf==-1)
					RRrotate(Anear,p_Anear,flag);
			}
			return *this;
		}
	}

}
template<class T>
void AVLtree<T>::LRrotate(AVLtreeNode<T>* A,AVLtreeNode<T>* pA,int flag)//第二种旋转的方法，只需要一个参数即A就可以了
{
	AVLtreeNode<T>* C=A->Left->Right;
	AVLtreeNode<T>* B=A->Left;
	A->Right=new AVLtreeNode<T>(A->data,C->Right,A->Right);
	A->data=C->data;
	B->Right=C->Left;
	V_height(A);
}
template<class T>
void AVLtree<T>::RLrotate(AVLtreeNode<T>* A,AVLtreeNode<T>* pA,int flag)//第二种旋转的方法，只需要一个参数即A就可以了
{
	AVLtreeNode<T>* C=A->Right->Left;
	AVLtreeNode<T>* B=A->Right;
	A->Left=new AVLtreeNode<T>(A->data,A->Left,C->Left);
	A->data=C->data;
	B->Left=C->Right;
	V_height(A);
}
template<class T>
void AVLtree<T>::LLrotate(AVLtreeNode<T>* A,AVLtreeNode<T>* pA,int flag)
{
	AVLtreeNode<T>* CA=A->Left;
	AVLtreeNode<T>* CAR=CA->Right;
	if(A==root)
	{
		root=CA;
	}
	else
	{
		if(flag==1)
		{
			pA->Left=CA;
		}
		else if(flag==2)
		{
			pA->Right=CA;
		}
	}
	CA->Right=A;
	A->Left=CAR;
	V_height(CA);
}
/*template<class T>
void AVLtree<T>::LRrotate(AVLtreeNode<T>* A,AVLtreeNode<T>* pA,int flag)//第一种旋转的方法
{
	AVLtreeNode<T>* CA=A->Left;//A的孩子即课本中的B点
	AVLtreeNode<T>* CAR=CA->Right;//B的右孩子即C点
	RRrotate(CA,A,1);
	LLrotate(A,pA,flag);
	V_height(CAR);
}*/
/*template<class T>
void AVLtree<T>::RLrotate(AVLtreeNode<T>* A,AVLtreeNode<T>* pA,int flag)//第一种旋转的方法
{
	AVLtreeNode<T>* CA=A->Right;
	AVLtreeNode<T>* CAL=CA->Left;
	LLrotate(CA,A,2);
	RRrotate(A,pA,flag);
	V_height(CAL);
}*/
template<class T>
void AVLtree<T>::RRrotate(AVLtreeNode<T>* A,AVLtreeNode<T>* pA,int flag)
{
	AVLtreeNode<T>* CA=A->Right;
	AVLtreeNode<T>* CAL=CA->Left;
	if(A==root)
	{
		root=CA;
	}
	else
	{
		if(flag==1)
		{
			pA->Left=CA;
		}
		else if(flag==2)
		{
			pA->Right=CA;
		}
	}
	CA->Left=A;
   	A->Right=CAL;
    V_height(CA);
}
template<class T>
int AVLtree<T>::power(int h)
{
	int result=1;
	for(int i=0;i<h;i++)
		result*=2;
	return result;
}
template<class T>
void AVLtree<T>::setposition(int m)
{
	for(int i=0;i<m;i++)
		cout<<" ";
}
template<class T>
int AVLtree<T>::Height(AVLtreeNode<T>* t)
{
	if(!t)
		return 0;
	int h1=Height(t->Left);
	int h2=Height(t->Right);
	if(h1>h2)
		return ++h1;
	else 
		return ++h2;
}
template<class T>
void AVLtree<T>::visit(AVLtreeNode<T>* t,T a[],int i)
{
	a[i]=t->data;
}
template<class T>
void AVLtree<T>::preorder(AVLtreeNode<T>* t,T a[],int i)
{
	if(t)
	{
		visit(t,a,i);
    	preorder(t->Left,a,2*i);
	    preorder(t->Right,a,2*i+1);
	}
		
}
template<class T>
void AVLtree<T>::output()
{
	int height=Height(root);
	int n=power(height);
	T* a=new T[n];
	for(int i=1;i<n;i++)
		a[i]=10000;
	preorder(root,a,1);
	int k=0;
	i=1;
	while(i<n)
	{
		if(i==power(k))
		{
			k++;
			int m=power(height-k)-1;
			cout<<endl;
			setposition(m);

		}
		else
		{
			int j=power(height-k+1)-1;
			setposition(j);
		}
		if(a[i]!=10000)
			cout<<a[i];
		else
			cout<<" ";
		i++;
	}
	cout<<endl;
	delete []a;
}
#endif