avl树实现

//=================avl 的异常处理类=======================
//============== avl_tree_exception.h=====================
#ifndef AVL_TREE_EXCEPTION_H_
#define AVL_TREE_EXCEPTION_H_
#include<stdexcept>
#include<string>
class ATException: public std::logic_error
{
	public:
		ATException(const std::string &message="")
			:std::logic_error(message.c_str())
		{}
};
#endif

//====================avl_tree_item.h=====================
//===========存放节点中数据，包含两项关键字和值=========
#ifndef AVL_TREE_ITEM_H_
#define AVL_TREE_ITEM_H_
template<class ValT,class KeyT>
class Item
{
	private:
		ValT val;
		KeyT key;
	public:
		Item()
		{}
		Item(ValT &_val,KeyT &_key)
			:val(_val),key(_key)
		{
		}
		void set(ValT _val,KeyT _key)
		{
			val=_val;
			key=_key;
		}
		KeyT getKey()const
		{
			return key;
		}
		ValT getVal()const
		{
			return val;
		}
};
#endif

//========================avl_tree_node.h========================
//===================avl 树的节点，包含有========================
//===========左右孩子的指针 leftPtr and rightPtr=================
//=======bal 标识 该节点左右子树的相对高度LH  , EH or RH=========
#ifndef AVL_TREE_NODE_H_
#define AVL_TREE_NODE_H_
//mark the state of the current node
//LH----left subtree is higher than right subtree 1 node;		
//EH----left subtree is equal to right subtree;
//RH----left subtree is shorter than right subtree 1 node;
#define LH +1
#define EH 0
#define RH -1
template<class ItemT,class KeyT> class AvlTree;
template<class ItemT,class KeyT>
class Node
{
	private:
		
		ItemT item;
		Node *leftPtr,*rightPtr;
		int bal;
		Node(ItemT &_item,Node *_leftPtr,Node *_rightPtr)
			:item(_item),leftPtr(_leftPtr),rightPtr(_rightPtr)
		{
			bal=EH;
		}
		friend class AvlTree<ItemT,KeyT>;
};
#endif

//=======================avl_tree.h======================
//======================定义avl的类======================
#ifndef AVL_TREE_H_
#define AVL_TREE_H_
#include"avl_tree_exception.h"
#include"avl_tree_node.h"
template<class ItemT,class KeyT>
class AvlTree
{
	public:
		AvlTree();
		AvlTree(AvlTree &_tree);
		~AvlTree();

		void insert(ItemT &_item)throw(ATException);
		void remove(KeyT &_key)throw(ATException);
		void retrieve(KeyT &_key,ItemT &_item)throw(ATException);
		void traverse(void (*visit)(ItemT _item));
		bool empty()const;
	protected:
		void insertNode(Node<ItemT,KeyT> *&treePtr,ItemT & newitem,bool &taller)throw(ATException);

		void removeNode(Node<ItemT,KeyT> *&treePtr,KeyT &_key,bool &shorter)throw(ATException);

		//当平衡的avl树经过处理（insert or delete）后，失去原有的平衡，则调用
		//leftBalance 或者 rightBalance 函数处理，重新得到平衡
		void leftBalance(Node<ItemT,KeyT> *&treePtr,bool &state);
		void rightBalance(Node<ItemT,KeyT> *&treePtr,bool &state);

	
		void rotateLeft(Node<ItemT,KeyT> *&treePtr);
		void rotateRight(Node<ItemT,KeyT> *&treePtr);

		void retrieveNode(Node<ItemT,KeyT> *&treePtr,KeyT &_key,ItemT &_item)throw(ATException);
		
		void traverseNode(Node<ItemT,KeyT> *&treePtr,void (*visit)(ItemT _item));

		void copy(Node<ItemT,KeyT> *&treePtr,Node<ItemT,KeyT> *&oldPtr)throw(ATException);

		void destroy(Node<ItemT,KeyT> *&treePtr);

	private:
		Node<ItemT,KeyT> *root;
};
#endif

//=====================avl_tree.cpp======================
//===============avl_tree.h 的实现文件===================
#include<cstddef>
#include"avl_tree.h"
template<class ItemT,class KeyT>
AvlTree<ItemT,KeyT>::AvlTree()
{
	root=NULL;
}

template<class ItemT,class KeyT>
AvlTree<ItemT,KeyT>::AvlTree(AvlTree<ItemT,KeyT>& _tree)
{
	copy(root,_tree.root);
}

template<class ItemT,class KeyT>
AvlTree<ItemT,KeyT>::~AvlTree()
{
	destroy(root);
}
template<class ItemT,class KeyT>
void AvlTree<ItemT,KeyT>::insert(ItemT &_item)
	throw(ATException)
{
	bool taller=true;
	try{
		insertNode(root,_item,taller);
	}catch(ATException & e)
	{
		throw;
	}
}

template<class ItemT,class KeyT>
void AvlTree<ItemT,KeyT>::remove(KeyT &_key)
	throw(ATException)
{
	bool shorter=true;
	try{
		removeNode(root,_key,shorter);
	}catch(ATException &e)
	{
		throw;
	}
}

template<class ItemT,class KeyT>
void AvlTree<ItemT,KeyT>::retrieve(KeyT &_key,ItemT &_item)
	throw(ATException)
{
	try{
		retrieveNode(root,_key,_item);
	}catch(ATException &e)
	{
		throw;
	}
}

template<class ItemT,class KeyT>
void AvlTree<ItemT,KeyT>::traverse(void (*visit)(ItemT _item))
{
	traverseNode(root,visit);
}

template<class ItemT,class KeyT>
bool AvlTree<ItemT,KeyT>::empty()const
{
	return root==NULL;
}

template<class ItemT,class KeyT>
void AvlTree<ItemT,KeyT>::insertNode(Node<ItemT,KeyT> *&treePtr,ItemT &newitem,bool &taller)
	throw(ATException)
{
	if(treePtr==NULL)
	{
		treePtr=new Node<ItemT,KeyT>(newitem,NULL,NULL);
		if(treePtr==NULL)
			throw ATException("allocate memory faild !");
		taller=true;
	}
	else if(newitem.getKey()<treePtr->item.getKey())
	{
		insertNode(treePtr->leftPtr,newitem,taller);
		if(taller)
		{
			switch(treePtr->bal)
			{
				case LH:leftBalance(treePtr,taller);
			            taller=false;
						break;
				case EH:treePtr->bal=LH;
						break;
				case RH:treePtr->bal=EH;
					    taller=false;
						break;
			}
		}
	}
	else
	{
		insertNode(treePtr->rightPtr,newitem,taller);
		if(taller)
		{
			switch(treePtr->bal)
			{
				case LH:treePtr->bal=EH;
						taller=false;
						break;
				case EH:treePtr->bal=RH;
						break;
				case RH:rightBalance(treePtr,taller);
						taller=false;
						break;
			}
		}
	} 
}

template<class ItemT ,class KeyT>
void AvlTree<ItemT,KeyT>::removeNode(Node<ItemT,KeyT>*&treePtr,KeyT &_key,bool &shorter)
	throw(ATException)
{
	if(treePtr==NULL)
		throw ATException("the key item not exist !");
	else if(_key<treePtr->item.getKey())
	{
		removeNode(treePtr->leftPtr,_key,shorter);
		if(shorter)
		{
			switch(treePtr->bal)
			{
				case LH:treePtr->bal=EH;
						break;
				case EH:treePtr->bal=RH;
						shorter=false;
						break;
				case RH:rightBalance(treePtr,shorter);
						break;
			}
		}
	}
	else if(_key>treePtr->item.getKey())
	{
		removeNode(treePtr->rightPtr,_key,shorter);
		if(shorter)
		{
			switch(treePtr->bal)
			{
				case LH:leftBalance(treePtr,shorter);
						break;
				case EH:treePtr->bal=LH;
						shorter=false;
						break;
				case RH:treePtr->bal=EH;
						break;
			}
		}
	}
	else
		//the item who's key word equal to _key exist
	{
		Node<ItemT,KeyT> *temp;
		if(treePtr->leftPtr==NULL)
			//the node pointer treePtr only has a right subtree 
			//  or is a leaf
		{
			temp=treePtr->rightPtr;
			treePtr->rightPtr=NULL;
			delete treePtr;
			treePtr=temp;
			shorter=true;
		}
		else if(treePtr->rightPtr==NULL)
			//the node pointer treePtr only has a left subtree
			//   or is a leaf
		{
			temp=treePtr->leftPtr;
			treePtr->leftPtr=NULL;
			delete treePtr;
			treePtr=temp;
			shorter=true;
		}
		else
			// the node pointer treePtr has both left subtree and
			//    right subtree 
		{
			temp=treePtr->rightPtr;
			while(temp->leftPtr!=NULL)
				temp=temp->leftPtr;
			treePtr->item=temp->item;
			removeNode(treePtr->rightPtr,temp->item.getKey(),shorter);
			if(shorter)
			{
				switch(treePtr->bal)
				{
					case LH:leftBalance(treePtr,shorter);
							break;
					case EH:treePtr->bal=LH;
							shorter=false;
							break;
					case RH:treePtr->bal=EH;
							break;
				}
			}
		}
	}
}

template<class ItemT,class KeyT>
void AvlTree<ItemT,KeyT>::leftBalance(Node<ItemT,KeyT> *&treePtr,bool &shorter)
{
	Node<ItemT,KeyT> *leftTree=treePtr->leftPtr;
	Node<ItemT,KeyT> *rightTree=leftTree->rightPtr;
	switch(leftTree->bal)
	{
		case LH:treePtr->bal=EH;
				leftTree->bal=EH;
				rotateRight(treePtr);
				break;
		case EH:treePtr->bal=LH;
				leftTree->bal=RH;
				rotateRight(treePtr);
				shorter=false;
				break;
		case RH:
			{
				switch(rightTree->bal)
				{
			    	case LH:treePtr->bal=RH;
							leftTree->bal=EH;
							break;
					case EH:treePtr->bal=EH;
							leftTree->bal=EH;
							break;
					case RH:treePtr->bal=EH;
							leftTree->bal=LH;
							break;
				}
			    rightTree->bal=EH;
				rotateLeft(leftTree);
				rotateRight(treePtr);
				break;
			}
	}
}

template<class ItemT,class KeyT>
void AvlTree<ItemT,KeyT>::rightBalance(Node<ItemT,KeyT>*&treePtr,bool &shorter)
{
	Node<ItemT,KeyT> *rightTree=treePtr->rightPtr;
	Node<ItemT,KeyT> *leftTree=rightTree->leftPtr;
	switch(rightTree->bal)
	{
		case LH:
			{
				switch(leftTree->bal)
				{
					case LH:treePtr->bal=EH;
							rightTree->bal=RH;
							break;
					case EH:treePtr->bal=EH;
							rightTree->bal=EH;
							break;
					case RH:treePtr->bal=LH;
							rightTree->bal=EH;
				}
				leftTree->bal=EH;
				rotateRight(rightTree);
				rotateLeft(treePtr);
				break;
			}
		case EH:treePtr->bal=RH;
				rightTree->bal=LH;
				rotateLeft(treePtr);
				shorter=false;
				break;
		case RH:treePtr->bal=EH;
				rightTree->bal=EH;
				rotateLeft(treePtr);
				break;
	}
}

template<class ItemT,class KeyT>
void AvlTree<ItemT,KeyT>::retrieveNode(Node<ItemT,KeyT>*&treePtr,KeyT &_key,ItemT &_item)
	throw(ATException)
{
	if(treePtr==NULL)
		throw ATException("found key item failed !");
	else if(_key<treePtr->item.getKey())
	{
		retrieveNode(treePtr->leftPtr,_key,_item);
	}
	else if(_key>treePtr->item.getKey())
	{
		retrieveNode(treePtr->rightPtr,_key,_item);
	}
	else
		_item=treePtr->item;
}

template<class ItemT,class KeyT>
void AvlTree<ItemT,KeyT>::traverseNode(Node<ItemT,KeyT>*&treePtr,void (*visit)(ItemT _item))
{
	if(treePtr!=NULL)
	{
		traverseNode(treePtr->leftPtr,visit);
		visit(treePtr->item);
		traverseNode(treePtr->rightPtr,visit);
	}
}

template<class ItemT,class KeyT>
void AvlTree<ItemT,KeyT>::copy(Node<ItemT,KeyT> *&treePtr,Node<ItemT,KeyT>*&oldPtr)
	throw(ATException)
{
	if(oldPtr!=NULL)
	{
		treePtr=new Node<ItemT,KeyT>(oldPtr->item,NULL,NULL);
		if(treePtr==NULL)
			throw ATException("allocate memory failed !");
		treePtr->bal=oldPtr->bal;
		copy(treePtr->leftPtr,oldPtr->leftPtr);
		copy(treePtr->rightPtr,oldPtr->rightPtr);
	}
}

template<class ItemT,class KeyT>
void AvlTree<ItemT,KeyT>::destroy(Node<ItemT,KeyT>*& treePtr)
{
	if(treePtr!=NULL)
	{
		destroy(treePtr->leftPtr);
	    destroy(treePtr->rightPtr);
		delete treePtr;
		treePtr=NULL;	
	}
}

template<class ItemT,class KeyT>
void AvlTree<ItemT,KeyT>::rotateLeft(Node<ItemT,KeyT> *&treePtr)
{
	Node<ItemT,KeyT>*temp=treePtr->rightPtr;
	treePtr->rightPtr=temp->leftPtr;
	temp->leftPtr=treePtr;
	treePtr=temp;
}

template<class ItemT,class KeyT>
void AvlTree<ItemT,KeyT>::rotateRight(Node<ItemT,KeyT>*&treePtr)
{
	Node<ItemT,KeyT> *temp=treePtr->leftPtr;
	treePtr->leftPtr=temp->rightPtr;
	temp->rightPtr=treePtr;
	treePtr=temp;
}

//=====================测试程序========================
#include<iostream>
#include<string>
#include<ctime>
#include<cstdlib>
#include"avl_tree_item.h"
#include"avl_tree.h"
#include"avl_tree.cpp"
using namespace std;
void display(Item<string,string> _item);
int main()
{
	//srand(time(0));
	AvlTree<Item<string,string>,string> atree;
	Item<string,string> newitem;
	string thekey,theval;
	cout<<"creating avl tree atree with 100 datas !"<<endl;
	for(int i=0;i<100;i++)
	{
		for(int j=0;j<10;j++)
		{
			thekey=thekey+char(rand()%26+'a');
			theval=theval+char(rand()%10+'0');
		}
		newitem.set(theval,thekey);
		try{
		atree.insert(newitem);
		thekey.clear();
		theval.clear();
		}catch(ATException &e)
		{
			cout<<e.what()<<endl;
		}
	}
	cout<<"the data in atree are :"<<endl;
	atree.traverse(display);
	cout<<"traverse the tree atree over !"<<endl;
	cout<<"enter the key word of the item (q to quit ):"<<endl;
	string keyword;
	cin>>keyword;
	while(keyword!="q")
	{
		try{
			atree.retrieve(keyword,newitem);
			display(newitem);
		}catch(ATException &e)
		{
			cout<<e.what()<<endl;
		}
		cout<<"enter other one key (q to quit): "<<endl;
		cin>>keyword;
	}
	cout<<"enter the key word of the item you want to delete (s to stop):"<<endl;
	cin>>keyword;
	while(keyword!="q")
	{
		try{
			atree.remove(keyword);
		}catch(ATException &e)
		{
			cout<<e.what()<<endl;
		}
		cout<<"enter other one key (s to stop):"<<endl;
		cin>>keyword;
	}
	cout<<"create a tree same as atree !"<<endl;
	AvlTree<Item<string,string>,string> btree(atree);
	cout<<"the date in btree :"<<endl;
	btree.traverse(display);
	cout<<"over !"<<endl;
	return 0;

}
void display(Item<string,string> _item)
{
	cout<< _item.getKey()<<'\t'<<_item.getVal()<<endl;
}