avltree.h

清华大学计算机系数据结构课程教材《数据结构 用面向对象方法和C++描述》（殷人昆主编）的类库（书中程序的源代码）

#ifndef AVLTREE_H
#define AVLTREE_H

#include "SeqStack.h"

template <class E, class K>
struct AVLNode  {
	//AVL树结点的类定义  
	E data;
	AVLNode<E, K> * left , *right;
	int bf;
	AVLNode() { left = NULL; right = NULL; bf = 0; }
	AVLNode (E d, AVLNode<E, K> *l = NULL,  
		AVLNode<E, K> *r = NULL) 
	{ data = d;  left = l;  right = r;  bf = 0; }
	bool operator < (AVLNode<E,K> & t){
		return d< t.data;
	}
	bool operator > (AVLNode<E,K> & t){
		return d>t.data;
	}
	bool operator == (AVLNode<E,K> & t){
		return d==t.data;
	}
};

template <class E, class K>
class AVLTree {
	//平衡的二叉搜索树（AVL）类定义
public:
	AVLTree() { root = NULL; }		//构造函数
	AVLTree (K Ref) { RefValue = Ref; root = NULL; }
	//构造函数：构造非空AVL树
	int Height() const{ return Height(root);}				         //高度
	bool Insert (E& e1) { return Insert (root, e1); } //插入
	bool Remove (K x, E& e1)
	{ return Remove (root, x, e1); } 	         //删除
	AVLNode<E,K> *Search(K x)const{return Search(x,root);}
	friend istream& operator >> (istream& in,AVLTree<E, K>& Tree){
		//输入一系列的值, 建立AVL树。约定Tree中的RefValue是终止输入的标记。
		E item;										//输入暂存单元
		cout << "AVL树：";			//提示：构造AVL树
		cout << "输入数据，以" << Tree.RefValue << "结束："<<endl;
		//提示：输入以RefValue结束
		in >> item;									//输入
		while (item.key != Tree.RefValue) {		//当输入不等于RefValue时
			Tree.Insert(item);						//插入到树中
			cout << "输入数据: ";
			//提示：输入以RefValue结束
			in >> item;								//输入
		}
		return in;
	};		       
	friend ostream& operator << (ostream& out, AVLTree<E, K>& Tree){
		out << "AVL树的中序遍历: "<<endl;	//提示：AVL树的中序遍历
		Tree.Traverse(Tree.root, out);				//以中序次序输出各结点的数据
		out << endl;
		return out;									//返回输出元素
	};

protected:
	K RefValue;
	AVLNode<E,K> * root;
	int Height (AVLNode<E, K> *ptr) const; 
	bool Insert (AVLNode<E, K>*& ptr, E& e1);
	bool Remove (AVLNode<E, K>*& ptr, K x, E& e1);
	void RotateL (AVLNode<E, K>*& ptr); 	  //左单旋
	void RotateR (AVLNode<E, K>*& ptr);	  //右单旋
	void RotateLR (AVLNode<E, K>*& ptr);		//先左后右双旋
	void RotateRL (AVLNode<E, K>*& ptr);		//先右后左双旋
	void Traverse(AVLNode<E,K> *ptr, ostream& out);
	AVLNode<E,K> *Search(K x, AVLNode<E,K> *par)const;

};

template <class E, class K>
AVLNode<E,K> *AVLTree<E,K>::Search(K x, AVLNode<E,K> *par)const {
	if (! par)
		return NULL;
	if (x == par->data.key)
		return par;
    AVLNode<E,K> *p;
	if ((p=Search(x,par->left))!=NULL)
		return p;
	else
		return Search(x,par->right);
}

template <class E, class K>
int AVLTree<E,K>::Height (AVLNode<E,K> *ptr) const {
	if (! ptr)
		return 0;
	int n=Height(ptr->left);
	int m=Height(ptr->right);
	return n<m? m+1: n+1;
}

template <class E, class K> 
void AVLTree<E, K>::
RotateL (AVLNode<E, K> *& ptr) {
	//右子树比左子树高: 做左单旋转后新根在ptr
	AVLNode<E, K> *subL = ptr;
	ptr = subL->right;
	subL->right = ptr->left;
	ptr->left = subL; 
	ptr->bf = subL->bf = 0;
};
template <class E, class K>
void AVLTree<E, K>::
RotateR (AVLNode<E, K> *& ptr) { 
	//左子树比右子树高, 旋转后新根在ptr
	AVLNode<E, K> *subR = ptr;   //要右旋转的结点
	ptr = subR->left;
	subR->left = ptr->right;	      //转移ptr右边负载
	ptr->right = subR;		      //ptr成为新根
	ptr->bf = subR->bf = 0;
};

template <class E, class K>
void AVLTree<E, K>:: RotateLR (AVLNode<E, K> *& ptr) {
	AVLNode<E, K> *subR = ptr;
	AVLNode<E, K> *subL = subR->left;
	ptr = subL->right;
	subL->right = ptr->left;
	ptr->left = subL;
	if (ptr->bf <= 0) subL->bf = 0;
	else subL->bf = -1;
	subR->left = ptr->right;
	ptr->right = subR;	
	if (ptr->bf == -1) subR->bf = 1;
	else subR->bf = 0;
	ptr->bf = 0;
};

template <class E, class K>
void AVLTree<E, K>::RotateRL (AVLNode<E, K> *& ptr) {
	AVLNode<E, K> *subL = ptr;
	AVLNode<E, K> *subR = subL->right;
	ptr = subR->left;
	subR->left = ptr->right; 
	ptr->right = subR;
	if (ptr->bf >= 0) subR->bf = 0;
	else subR->bf = 1;
	subL->right = ptr->left;
	ptr->left = subL;
	if (ptr->bf == 1) subL->bf = -1;
	else subL->bf = 0;
	ptr->bf = 0;
}; 


template <class E, class K>
bool AVLTree<E,K>::Insert(AVLNode<E,K> *& ptr, E& e1) {
	//在以ptr为根的AVL树中插入新元素e1,如果插入成功,函数返回true, 否则返回false。 
	AVLNode<E,K> *pr = NULL, *p = ptr, *q;  int d;
	SeqStack<AVLNode<E,K> *> st;
	while (p != NULL) {							//寻找插入位置
		if (e1 == p->data) return false;		//找到等于e1的结点,不插入
		pr = p;  st.Push(pr);					//否则用栈记忆查找路径
		if (e1 < p->data) p = p->left;
		else p = p->right;
	}
	p = new AVLNode<E,K>(e1);					//创建新结点,data=e1,bf=0
	if (p == NULL) {cerr <<"存储空间不足！"<< endl;  exit(1);}
	if (pr == NULL) {ptr = p;	return true;}	//空树,新结点成为根结点 
	if (e1 < pr->data) pr->left = p;			//新结点插入
	else pr->right = p;
	while (st.IsEmpty() == false) {				//重新平衡化
		st.Pop(pr);								//从栈中退出父结点
		if (p == pr->left) pr->bf--;			//调整父结点的平衡因子
		else pr->bf++;
		if (pr->bf == 0) break;					//第1种情况,平衡退出
		if (pr->bf == 1 || pr->bf == -1)		//第2种情况,|bf|=1
			p = pr;
		else {									//第3种情况,|bf|=2
			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.IsEmpty() == true) ptr = pr;		//调整到树的根结点
	else {										//中间重新链接
		st.getTop(q);
		if (q->data > pr->data) q->left = pr;
		else q->right = pr;
	}
	return true;
};



template <class E, class K>
void AVLTree <E,K>::Traverse(AVLNode<E,K> *ptr, ostream& out) {
	if (ptr != NULL) {							//树非空
		Traverse(ptr->left, out);				//中序遍历左子树
		out << ptr->data << ' ';				//输出根的数据
		Traverse(ptr->right, out);				//中序遍历右子树
	}
};

template <class E, class K>
bool AVLTree<E,K>::Remove(AVLNode<E,K> *& ptr, K x, E& e1) {
	//在以ptr为根的AVL树中删除关键码为x的结点。如果删除成功,函数返回true,同时通过参
	//数e1返回被删结点元素,如果删除失败则函数返回false。 
	AVLNode<E,K> *pr = NULL, *p = ptr, *q, *ppr;
	int d, dd = 0;
	SeqStack<AVLNode<E,K> *> st;
	while (p != NULL) {							//寻找删除位置
		if (x == p->data.key) break;			//找到等于x的结点,停止搜索
		pr = p;  st.Push(pr);					//否则用栈记忆查找路径
		if (x < p->data.key) p = p->left;
		else p = p->right;
	}
	if (p == NULL) return false;				//未找到被删结点,删除失败
	if (p->left != NULL && p->right != NULL) {	//被删结点有两个子女
		pr = p;  st.Push(pr);
		q = p->left;							//在p左子树找p的直接前驱
		while (q->right != NULL) 
		{pr = q;  st.Push(pr);  q = q->right;}
		p->data = q->data;						//用q的值填补p
		p = q;									//被删结点转化为q
	}
	if (p->left != NULL) q = p->left;			//被删结点p只有一个子女q
	else q = p->right;
	if (pr == NULL) ptr = q;					//被删结点为根结点
	else  {										//被删结点不是根结点
		if (pr->left == p) pr->left = q;		//链接
		else pr->right = q;					
		while (st.IsEmpty() == false) {			//重新平衡化
			st.Pop(pr);							//从栈中退出父结点
			if (pr->right == q) pr->bf--;		//调整父结点的平衡因子
			else pr->bf++;
			if (st.IsEmpty() == false) {
				st.getTop(ppr);					//从栈中取出祖父结点
				dd = (ppr->left == pr) ?-1 : 1;	//旋转后与上层链接方向
			}
			else dd = 0;						//栈空,旋转后不与上层链接
			if (pr->bf == 1 || pr->bf == -1) break; 	//图7.20,|bf|=1
			if (pr->bf != 0) {					//|bf|=2
				if (pr->bf < 0) {d = -1;  q = pr->left;}
				else {d = 1;  q = pr->right;}	//用q指示较高的子树
				if (q->bf == 0) {				//图7.22
					if (d == -1) 
					{RotateR(pr);  pr->bf = 1;  pr->left->bf = -1;}
					else {RotateL(pr); pr->bf = -1;  pr->right->bf = 1;}
					break;
				}
				if (q->bf == d) {				//两结点平衡因子同号,图7.23
					if (d == -1) RotateR(pr);	//右单旋转
					else RotateL(pr);			//左单旋转
				}
				else {							//两结点平衡因子反号,图7.24
					if (d == -1) RotateLR(pr);	//先左后右双旋转,”<”型 
					else RotateRL(pr);			//先右后左双旋转,”>”型
				}
				if (dd == -1) ppr->left = pr;
				else if (dd == 1) ppr->right = pr;	//旋转后新根与上层链接
			}
			q = pr;								//图7.21,|bf|=0
		}
		if (st.IsEmpty() == true) ptr = pr;	//调整到树的根结点
	}
	delete p;  return true;
};


#endif