avltree.cpp

这些程序是本人学习数据结构时编的

// AVLTree.cpp: implementation of the AVLTree class.
//
//////////////////////////////////////////////////////////////////////

#include "AVLTree.h"

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////


template<class Type>
AVLTree<Type>::~AVLTree()
{

}


template<class Type>
void AVLTree<Type>::RightBalance(AVLNode<Type> *&Tree, int &taller)
{
	AVLNode<Type> * rightsub = Tree ->right ,* leftsub;
	switch (rightsub -> balance)
	{
	case 1:
		Tree ->balance  = rightsub ->balance  = 0;
		RotateLeft(Tree,Tree);
		taller = 0;
		break;
	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 = rightsub->balance  =0;
			break;
		case -1:
			Tree->balance = 0;
			rightsub ->balance = 1;
			break;
		}
		leftsub->balance  =0 ;
		RotateRight(rightsub,Tree ->right );
		RotateLeft(Tree,Tree);
		taller = 0;
	}
}

template<class Type>
void AVLTree<Type>::LeftBalance(AVLNode<Type> *&Tree, int &taller)
{
	AVLNode<Type> *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 alrrady balanced. =n ";
		break;
	case 1: 
		rightsub =  leftsub->right ;
		switch(rightsub->balance )
		{
		case -1:
			Tree ->balance  = 1;
			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>::RotateRight(AVLNode<Type> *Tree, AVLNode<Type> *&NewTree)
{
	NewTree = Tree->left ;
	Tree->left = NewTree->right;
	NewTree->right = Tree;	
}

template<class Type>
void AVLTree<Type>::RotateLeft(AVLNode<Type> *Tree, AVLNode<Type> *&NewTree)
{
	NewTree = Tree->right;
	Tree->right = NewTree->left;
	NewTree->left = Tree;
}

template<class Type>
int AVLTree<Type>::Insert(AVLNode<Type> *&tree, Type x, int &taller)
{
	int success;
	if (tree == NULL)
	{
		tree = new AVLNode<Type>(x);
		success = true != 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>
int AVLTree<Type>::Insert(Type x)
{
	int taller;
	return Insert(root , x, taller);
}

template<class Type>
int AVLTree<Type>::Height() const
{
	if (root == NULL)
		return 0;
	if (root->balance == 1)
		return height(root ->right) +1;
	return height(root ->left) +1;
}

template<class Type>
int AVLTree<Type>::height(AVLNode<Type> * ptr) const
{
	if (ptr == NULL)
		return 0;
	if (ptr->balance == 1)
		return height(ptr->right) +1;
	return height(ptr->left) + 1;
}

template<class Type>
Type AVLTree<Type>::RefValue()
{
	return refvalue;
};

template<class Type>
istream& operator >>(istream& in,AVLTree<Type> & tree)
{
	Type item;
	cout<<"Construct AVL tree: \n";
	cout<<"Input Data(end with "<<tree.RefValue()<<"):";
	in>>item;
	while(item != tree.RefValue() )
	{
		tree.Insert(item);
		cout<<"Input Data (end with "<<tree.RefValue()<<"):";
		in>>item;
	}
	return in;
}

template<class Type>
ostream& operator <<(ostream& out, AVLTree<Type>& tree)
{
	out<<"Inorder traversal of AVL tree.\n";
	tree.Traverse(tree.Root(),out, 0);
	return out;
}

template<class Type>
void AVLTree<Type>::Traverse(AVLNode<Type> *ptr, ostream &out,int i)
{
	if(ptr != NULL)
	{
		for (int j = 0;j< i;j++)
			out<<' ';
		cout<<setiosflags(ios::left);
		out<<setw(3)<<ptr->data.key;
		out<<'('<<setw(2)<<ptr->balance<<')';
		for (j = 0; j < 14 - i; j++)
			out<<'-';
		out<<ptr->data.data<<endl;
		Traverse(ptr->left , out, i + 1);
		Traverse(ptr->right , out, i + 1);
	}
};

template<class Type>
int AVLTree<Type>::Find(int x)
{
	AVLNode<Type> * result = find(root,x);
	if (result != NULL)
		return result ->data.data;
	return -1;
};

template<class Type>
AVLNode<Type>*  AVLTree<Type>::find(AVLNode<Type> * current,int x)
{
	AVLNode<Type>* result;
	if (current != NULL)
	{
		if (current ->data.key == x)
			return current;
		result = find(current->left,x);
		if (result != NULL)
			return result;		
		else find(current ->right,x);
	}else
		return NULL;
}


template<class Type>
AVLNode<Type>* AVLTree<Type>::GetPre(AVLNode<Type> * ptr)
{
	AVLNode<Type> * temp = ptr->left;
	while(temp->right != NULL)
		temp = temp->right;
	return temp;
}

template<class Type>
int AVLTree<Type>::Remove(int x)
{
	//find the node is in
	AVLNode<Type>* ptr, * pre,*temp = NULL;
	int data;
	ptr = find( root ,x);
	//not in
	if (!ptr) return -1;
	//if the code have two child
	if (ptr->left && ptr->right)
	{
		//find inorder node
		pre = GetPre(ptr);
		//cover it
//		ptr ->data = pre ->data;
		x = pre->data.key;
		data = pre->data.data;
		temp = ptr;
		ptr = pre;
	}

	if (ptr == root)
	{
		if (root ->left== NULL && root->right == NULL)
		{
			delete root;
			root = NULL;
			return x;
		}

		if (root ->left)
		{
			root = root->left;
			root ->right = ptr ->right;
			if (root)
				root ->balance = 1;
			else root ->balance = 0;
			delete ptr;
			return x;
		}else{
			root = root->right;
			root ->balance = 0;
			delete ptr;
			return x;
		}
	}

	//balance the tree
	balanceTree(root ,x);
	if (temp)
	{
		temp ->data.key = x;
		temp ->data.data = data;
	};

	return 1;
}


template<class Type>
bool AVLTree<Type>::balanceTree(AVLNode<Type> * ptr ,int &x)
{
	bool shorter;
	int taller = 1 ,leaf;
	AVLNode<Type> * temp;
	if (!ptr->left)
		leaf = ptr ->right ->data.key == x ? 1 : 0;
	else if (!ptr->right)
		leaf = ptr ->left ->data.key == x ? -1 : 0;
	else if (ptr->left->data.key == x )
		leaf = -1;
	else if (ptr->right ->data.key == x )
		leaf = 1;
	else leaf = 0;
	if (leaf)
	{
		//remove the node
		if (leaf == -1 )
		{
			temp = ptr ->left;
			if (temp ->left)
				ptr->left = temp ->left;
			else ptr ->left = temp ->right;
			delete temp;
			if ( ptr ->balance == -1)
			{
				ptr ->balance = 0;
				return true;
			}else if (ptr ->balance == 0 )
			{
				ptr -> balance = 1;
				return false;
			}else{
				if (ptr ->right ->right != NULL)
				{
					if (root == ptr)
					{
						RotateLeft(ptr,root);
						ptr = root;
					}else{
						temp = ptr ->left;			
						RotateLeft(ptr,ptr);
						ptr = temp;
					}
					if (ptr ->left ->right == NULL)
					{
						ptr ->balance = 0;
						ptr ->left ->balance = 0;
						return true;
					}else{
						ptr ->balance = -1;
						ptr ->left ->balance = 1;
						return false;
					}
				}else{
					if (ptr == root)
					{
						RightBalance(root,taller);
						ptr = root;
					}else RightBalance(ptr,taller);
					ptr ->balance = 0;
					ptr ->left ->balance = 0;
					return true;
				}
			}
		}else{
			temp = ptr ->right;
			if (temp ->right)
				ptr->right = temp ->right;
			else ptr ->right = temp ->left;
			delete temp;
			if ( ptr ->balance == 1)
			{
				ptr ->balance = 0;
				return true;
			}else if (ptr ->balance == 0 )
			{
				ptr -> balance = -1;
				return false;
			}else{
				if (ptr ->left ->left != NULL)
				{
					if (root == ptr)
					{
						RotateRight(ptr,root);
						ptr = root;
					}else{
						temp = ptr->right;
						RotateRight(ptr,ptr);
						ptr = temp;
					}
					if (ptr ->right ->left == NULL)
					{
						ptr ->balance = 0;
						ptr ->right ->balance = 0;
						return true;
					}else{
						ptr ->balance = 1;
						ptr ->right ->balance = -1;
						return false;
					}
				}else{
					if (ptr == root)
					{
						LeftBalance(root,taller);
						ptr = root;
					}else LeftBalance(root,taller);
					ptr ->balance = 0;
					ptr ->right ->balance = 0;
					return true;
				}
			}
		} 
	}

	if (ptr ->data.key >= x )
	{
		shorter = balanceTree(ptr -> left , x);
		if (shorter)
		{
			if (ptr ->balance == -1)
			{
				ptr ->balance = 0;
				return false;
			}else if (ptr ->balance  == 0)
			{
				ptr ->balance = 1;
				return false;
			}else{
				if (ptr ->right ->balance == 1)
				{
					RotateLeft(ptr,ptr);
					ptr->left->left->balance = 0;
					ptr->left ->balance = 0;
					ptr ->balance = 0;
					return true;
				}else{
					RightBalance(ptr,taller);
					return true;
				}
			}
		}
	}else if (ptr->data.key < x)
	{
		shorter = balanceTree(ptr -> right, x);
		if (shorter)
		{
			if (ptr ->balance == 1)
			{
				ptr ->balance = 0;
				return false;
			}else if (ptr ->balance  == 0)
			{
				ptr ->balance = -1;
				return false;
			}else{
				if (ptr ->left ->balance == -1)
				{
					RotateRight(ptr,ptr);
					ptr->right->right->balance = 0;
					ptr->right ->balance = 0;
					ptr ->balance = 0;
					return true;
				}else{
					LeftBalance(ptr,taller);
					return true;
				}
			}
		}
	}
}