avltree.h

c++ 实现的AVL搜索树。希望站长采纳。

#include<cassert>
#include<stack>
#include<iostream>
template<class Type, class Key> class AVLTree;
template<class Type, class Key>
class AVLNode
{
friend class AVLTree<Type,Key>;
public:
  //  AVLNode():key(0),balance(0),leftChild(NULL),rightChild(NULL){};
	AVLNode(Key k):key(k),balance(b),leftChild(NULL),rightChild(NULL){};
	AVLNode(Key k, AVLNode<Type,Key> *l, AVLNode<Type,Key> *r):key(k),leftChild(l),rightChild(r){};
	AVLNode(Key k, Type d,int b,AVLNode<Type,Key> *l, AVLNode<Type,Key> *r):key(k),data(d),balance(b),leftChild(l),rightChild(r){};
	AVLNode(Key k, Type d, int b):key(k),data(d),balance(b),leftChild(NULL),rightChild(NULL){};
	Type GetData(){return data;};
	void SetData(Type d){data=d;};
	Key GetKey(){return key;};
private:
	int balance;
	Type data;
	Key key;
	AVLNode<Type,Key> *leftChild;
	AVLNode<Type,Key> *rightChild;
};

template<class Type, class Key>
class AVLTree
{
public:
	AVLTree(Type d):root(NULL),refValue(d){};
	bool Search(Key k, Type &d);
	bool Insert(Key k, Type d);
	bool Delete(Key k, Type &d);
	bool CheckAVL();
friend istream &operator >>(istream &is,AVLTree<Type,Key> &avl);
friend ostream &operator <<(ostream &os,AVLTree<Type,Key> &avl);
private:
	AVLNode<Type, Key> *root;
	Key refValue;
	void RotateLeft(AVLNode<Type,Key> * &p);
	void RotateRight(AVLNode<Type,Key> * &p);
	void RotateLR(AVLNode<Type,Key> * &p);
	void RotateRL(AVLNode<Type,Key> * &p);
	bool CheckAVL(AVLNode<Type,Key> *p, int &high);
	void Traverse(ostream &os, AVLNode<Type,Key> *p);
};

template<class Type, class Key>
bool AVLTree<Type, Key>::Search(Key k, Type &d)
{
	AVLNode<Type,Key> *p ;
	p = root;
	while( p!=NULL )
	{
		q = p;
		if(p->key > k)
			p = p->leftChild;
		else if(p->key < k)
			p = p ->rightChild;
		else
		{
			d = p ->data;
			return true;
		}
	}
	return false;
}


template<class Type, class Key>
void AVLTree<Type,Key>::RotateLeft(AVLNode<Type,Key> * &p)
{
	AVLNode<Type,Key> *newTree = p->rightChild;
	p->rightChild = newTree->leftChild;
	newTree->leftChild = p;
	p = newTree;
}
template<class Type, class Key>
void AVLTree<Type,Key>::RotateRight(AVLNode<Type,Key> * &p)
{
	AVLNode<Type,Key> *newTree = p ->leftChild;
	p->leftChild = newTree->rightChild;
	newTree->rightChild = p;
	p = newTree;
}
template<class Type, class Key>
void AVLTree<Type,Key>::RotateRL(AVLNode<Type,Key> * &p)
{
	AVLNode<Type,Key> *newTree = p->rightChild->leftChild;
	AVLNode<Type,Key> *newLeft = p;
	AVLNode<Type,Key> *newRight = p->rightChild;
	newLeft->rightChild = newTree->leftChild;
	newRight->leftChild = newTree->rightChild;
	newTree->leftChild = newLeft;
	newTree->rightChild = newRight;
	p = newTree;
}
template<class Type, class Key>
void AVLTree<Type,Key>::RotateLR(AVLNode<Type,Key> * &p)
{
	AVLNode<Type,Key> *newTree = p->leftChild->rightChild;
	AVLNode<Type,Key> *newLeft = p->leftChild;
	AVLNode<Type,Key> *newRight =p;
	newLeft->rightChild = newTree->leftChild;
	newRight->leftChild = newTree->rightChild;
	newTree->leftChild = newLeft;
	newTree->rightChild = newRight;
	p = newTree;
}

template<class Type, class Key>
bool AVLTree<Type, Key>::Insert(Key k, Type d)
{
	if(root == NULL)
	{
		root = new AVLNode<Type,Key>(k,d,0);
		assert(root != NULL);
		return true;
	}
	stack<AVLNode<Type,Key>*> st;
	AVLNode<Type,Key> *q, *p = root;
	q = NULL;
	while(p != NULL)
	{
		st.push(p);
		q = p;
		if(p->key < k)
			p = p->rightChild;
		else if(p->key > k)
			p = p->leftChild;
		else
			return false;
	}
	if(q ->key < k)
		q->rightChild = new AVLNode<Type,Key>(k, d, 0);
	else
		q->leftChild = new AVLNode<Type,Key>(k,d,0);
	AVLNode<Type,Key> *r = NULL;
	while(!st.empty())
	{
		p = st.top();
		st.pop();
		if(p->leftChild == q)
			p->balance--;
		else
			p->balance++;
		if(p->balance == 2)
		{
				if(q->leftChild == r)
					RotateRL(p);
				else
					RotateLeft(p);
				break;
		}
		else if(p->balance == -2)
		{
			if(q->rightChild == r)
				RotateLR(p);
			else
				RotateRight(p);
			break;
		}
		else if(p->balance == 0)
			break;
		r = q;
		q = p;

	}
	return true;
}

template<class Type, class Key>
bool AVLTree<Type,Key>::Delete(Key k, Type &d)
{
	AVLNode<Type,Key>  *p;
	p = root;
	bool found = false;
	stack<AVLNode<Type,Key>*> st;
	while(p!=NULL)
	{
		st.push(p);
		if(k < p->key)
			p = p->leftChild;
		else if(k > p->key)
			p = p->rightChild;
		else
		{
			found = true;
			break;
		}
	}
	if(!found)
		return false;
	d = p->data;
	if(p->leftChild!=NULL && p->rightChild!=NULL)
	{
		AVLNode<Type,Key> *r = p;  //把p记录下来
		p = p ->leftChild;
		while(p->rightChild != NULL)
		{
			st.push(p);
			p = p->rightChild;
		}
		r->data = p->data;
	}
	if(st.empty())
	{
		root = p ->leftChild;
		delete p;
		return found;
	}
	AVLNode<Type,Key> *q = st.top();
	
	AVLNode<Type,Key> *r = NULL;  //r记录最下面的结点q,p,r分别为结点，子结点，孙节点
	while(!st.empty())
	{
		q = st.top();
		st.pop();
		if(q->leftChild == p)
		{
			q->balance++;
			if(q->balance == 2)
			{
			if(p->leftChild == r)
				RotateRL(q);
			else
				RotateLeft(q);
			break;
			}
		}
		else
		{
			q->balance--;
			if(q->balance == -2)
			{
				if(p->rightChild == r)
					RotateLR(q);
				else
					RotateRight(q);
				break;
			}
		}
		if(q->balance == 0)
			break;
		r = p;
		p = q;
	}
}

template<class Type, class Key>
bool AVLTree<Type,Key>::CheckAVL(AVLNode<Type,Key> *p, int &high)
{
	if(p == NULL)
	{
		high = 0;
		return true;
	}
	int leftHigh = 0;
	int rightHigh = 0;
	if(CheckAVL(p->leftChild, leftHigh) && CheckAVL(p->rightChild, rightChild))
	{
		high = leftHigh>rightHigh ? leftHigh+1 : rightHigh+1;
		return true;
	}
	else
		return false;
}
template<class Type, class Key>
bool AVLTree<Type,Key>::CheckAVL()
{
	int high = 0;
	return CheckAVL(root, high);
}
template<class Type, class Key>
istream &operator >>(istream &is,AVLTree<Type,Key> &avl)
{
	AVLNode<Type,Key> item;
	is>item;
	while(item.key != avl.refValue)
	{
		avl.Insert(item.key, item.data);
		is>>item;
	}
	return is;
}
template<class Type, class Key>
ostream &operator <<(ostream &os,AVLTree<Type,Key> &avl)
{
	avl.Traverse(os, avl.root);
	return os;
}
template<class Type, class Key>
void AVLTree<Type,Key>::Traverse(ostream &os, AVLNode<Type,Key> *p)
{
	if(p != NULL)
	{
		out<<p->data<<" ";
		Traverse(os, p->leftChild);
		Traverse(os, p->rightChild);
	}
	
}