avl.h

AVL树的创建与基本操作

template<class type> class AVLTREE{
	public:
		struct AVLNODE{
			struct{type key;int inum;};
			AVLNODE * left, * right;
			int balance;
			AVLNODE():left(NULL),right(NULL),balance(0){}
			AVLNODE(type d,AVLNODE *l=NULL,AVLNODE *r=NULL):data(d),left(l),right(r),balance(0){}
		}data;
		AVLTREE():root(NULL){}
		AVLTREE(type ref):refvalue(ref),root(NULL){}
		int insert(type x){int taller;return(root,x,taller);}
		friend istream&operator>>(istream &in,AVLTREE<type> & tree);
		friend ostream& operator<<(ostream& out,const AVLTREE<type>& tree);
		int height()const;
	private:
		type refvalue;
		AVLNODE *root;
		int insert(AVLNODE * &tree,type x,int &taller);
		void rotateleft(AVLNODE *tree,VALNODE *&newtree);
		void rotateright(AVLNODE *tree,AVLNODE *&newtree);
		void leftbalance(AVLNODE *&tree,AVLNODE *&taller);
		void rightbalance(AVLNODE *&tree,int &taller);
		int height(AVLNODE * t)const;
        void traverse(AVLNODE *ptr,ostream &out)const;

};

template<class type> void AVLTREE<type>::rotateleft(AVLNODE *tree,AVLTREE *&newtree){
	newtree=tree->right;
	tree->right=newtree->left;
	newtree->left=tree;
}

template<class type> void AVLTREE<type>::rotateright(AVLNODE *tree,AVLTREE *&newtree){
	newtree=tree->left;
	tree->left=newtree->right;
	newtree->right=tree;
}

template<class type>void AVLTREE<type>::leftbalance(AVLNODE*& tree,int &taller){
	AVLNODE* leftsub=tree->left,*rightsub;
	switch(leftsub->balance){
	case -1:tree->balance=leftsub->balance=0;
		rotateright(tree,tree);taller=0;break;
	case 0:cout<<"leftbalance error:tree already balanced.\n";break;
	case 1:rightsub=leftsub->right;
		switch(rightsub->balance){
		case -1:tree->balance=0;leftsub->balance=0;break;
		case 0:tree->balance=leftsub->balance=0;break;
		case 1:tree->balance=0;leftsub->balance=-1;break;
		}
		rightsub->balance=0;
		rotateleft(leftsub,tree->left);
		rotateright(tree,tree);taller=0;
	}
}

template<class type>void AVLTREE<type>::rightbalance(AVLNODE*& tree,int &taller){
	AVLNODE * rightsub=tree->right,*leftsub;
	switch(rightsub->balance){
	case 1:tree->balance=rightsub->balance=0;
	case 0:cout<<"rightbalance error:tree already balanced.\n";break;
	case -1:leftsub=rightsub->left;
		switch(leftsub->balance){
		case 1:tree->balance=-1;rightsub->balance=0;break;
		case 0:tree->balance=right->balance=0;break;
		case -1:tree->balance=0;rightsub->balance=1;break;
		}
		left->balance=0;
		r0tateright(rightsub,tree->right);
		rotateleft(tree,tree);taller=0;
	}
}

template<class type>int AVLTREE<type>::insert(AVLTREE * &tree,type x,int &taller){
	int success;
	if(tree==NULL){
		tree=new AVLNODE(x);
		success=tree!=NULL?1:0;
		if(success)taller=1;
	}
	else if(x<tree->data){
		success=insert(tree->left,x,taller);
		if(taller)
			switch(tree->balance){
			case -1:leftbalance(tree,taller);break;
			case 0:tree->balance=-1;break;
			case 1:tree->balance=0;taller=0;break;
		}
	}
	else if(x>tree->data){
		success=insert(tree->right,x,taller);
		if(taller)
			switch(tree->balance){
			case -1:tree->balance=0;taller=0;break;
			case 0:tree->balance=1;break;
			case 1:rightbalance(tree,taller);break;
		}
	}
	return success;
}

//这里还有输入函数没有写

template<class type>ostream &operator<<(ostream &out,const AVLTREE<tree> & tree){
	out<<"inorder traversal of AVL tree.\n";
	tree.traverse(tree.root,out);
	out<<endl;
	return out;
}

template<class type>void AVLTREE<type>::traverse(AVLNODE *ptr,ostream &out)const{
	if(ptr!=NULL){
		traverse(ptr->left,out);
		out<<ptr->data<<"  ";
		traverse(ptr->right,out);
	}
}