avltree.h

平衡二叉树的原代码,欢迎使用和下载. 请查收

/****************************************
File:				AVLTree.h
Author:			Channon Quillen
Date Created:	10/24/2000
Date Modified:	11/5/2000
*****************************************/

/* 
	This class will construct an AVL Tree.
	Note: This class does not support value semantics.  However,
		  a default constructor and destructor are provided.
*/

#ifndef AVL_TREE
#define AVL_TREE

#include <iostream>
#include <iomanip>	// setw
#include <cstddef>	// NULL
#include <cassert>	// assert

using namespace std;

template <typename T>
class AVLTree
{
	// the node structure of the tree
	struct Node
	{
		T val;					// value stored in this node
		int height;				// height of the subtree rooted at this node
		Node *left, *right;	// pointers to the left and right of subtrees
	};
	
	private:
		// used to point to the nodes
		typedef Node *nodePtr;
		
		// pointer to the root of the tree
		nodePtr root;
		
		// to keep track of the number of nodes in the tree
		int count;
		
		/******************************************/
		//	Pre:	tree is initialized
		//	Post:	item is inserted, balances are checked, heights are fixed
		//	Pur:	to insert a new value recursively
		void recInsert( T val, nodePtr &node)
		{
			if( !node)
			{
				// make a new node containing the new val
				node = new Node;
				node->val = val;
				node->left = NULL;
				node->right = NULL;
				node->height = 1;
				
				return;	// fault check
			}
						
			// made it here, node points to something
			// 	figure out which subtree to insert into
			// insert into left subtree
			if( val < node->val)
			{
				// follow the path to insert the new value
				recInsert( val, node->left);
				
				// fix the heights and rotate if needed
				rebalance( node);
			}			
			
			// insert into right subtree
			if( val > node->val)
			{
				// follow the path to insert the new value
				recInsert( val, node->right);
				
				// fix the heights and rotate if needed
				rebalance( node);
			}
		}
		
		/*********************************************/
		//	Pre:	tree is initialized
		//	Post:	nodes rebalanced and heights fixed
		//	Pur:	to rebalance (rotate) the nodes if needed
		void rebalance( nodePtr &node)
		{
			// get the heights of left and right children
			int left = height( node->left);
			int right = height( node->right);
			
			// check for balance of sub-roots
			if((( left - right) <= 1) && (( right - left) <= 1))
			{
				renum( node);	// fix the heights
				return;
			}
			
			// check to see if left subtree is taller than right by one
			else if(( left - right) > 1)
			{
				// if the left child's left subtree is taller or the same
				//		as the right subtree, use Right rotation
				if( height( node->left->left) >= height( node->left->right))
				{
					nodePtr A = node->left;	// create temp pointer
					
					// set the current node's left equal to A's right
					node->left = A->right;
					A->right = node;		// set A's right equal to node
					node = A;				// current node points to same node as A
					
					// update the heights of the nodes that were changed
					renum( node->right);
					renum( node);
				}
				
				// do a LR Rotation
				else
				{
					// create temp pointers
					nodePtr A = node->left;
					nodePtr B = A->right;
					
					node->left = B->right;	// set current node's left to same as B's right
					A->right = B->left;		// set A's right equal to B's left
					B->left = A;			// set B's left equal to A
					B->right = node;		// set B's right equal to current node
					node = B;
					
					// update the heights of the nodes
					renum( A);
					renum( node->right);
					renum( node);
				}
			}
			
			else
			{
				// if the left child's left subtree is taller or the same
				//		as the right subtree, use Left rotation
				if( height( node->right->right) >= height( node->right->left))
				{
					nodePtr A = node->right;	// create temp pointer
					node->right = A->left;
					A->left = node;	// set temp pointer's left equal to node
					node = A;
					
					// update the heights of the nodes
					renum( node->left);
					renum( node);
				}
				
				// do a RL Rotation
				else
				{
					// create temp pointers
					nodePtr A = node->right;
					nodePtr B = A->left;
					
					node->right = B->left;
					A->left = B->right;
					B->left = node;
					B->right = A;
					node = B;
					
					// update the heights of the nodes
					renum( node->right);
					renum( node->left);
					renum( node);
				}
			}
		}
		
		/******************************************/
		//	Pre:	tree is initialized
		//	Post:	nodes are renumbered
		//	Pur:	to renumber the heights of the nodes
		void renum( nodePtr &node)
		{
			int leftHgt = 0;	// height of the left subtree
			int rightHgt = 0;	// height of the right subtree
			
			// what is the height of the left subtree
			if( node->left)
				leftHgt = node->left->height;
			
			// what is the height of the right subtree
			if( node->right)
				rightHgt = node->right->height;
			
			// if the left subtree is taller than the right subtree,
			//		node's height is plus one than the height of the
			//		right subtree
			if( leftHgt > rightHgt)
				node->height = leftHgt + 1;
				
			// node's height is plus one taller than the height
			//		of the left subtree
			else
				node->height = rightHgt + 1;
		}
		
		/******************************************/
		//	Pre:	tree is initialized, item is in the tree
		//	Post:	item removed, rotations performed, and heights fixed
		//	Pur:	to remove an item from the tree recursively
		void recRemove( T val, nodePtr &node)
		{
			// if the item is less than the val at current node
			if( val < node->val)
			{
				// walk the left subtree for the node with val
				recRemove( val, node->left);
				
				// fix the heights and rotate if needed
				rebalance( node);
			}
			
			// if the item is greater than the val at current node
			else if( val > node->val)
			{
				// walk the right subtree for the node with val
				recRemove( val, node->right);
				
				// fix the heights and rotate if needed
				rebalance( node);
			}
			
			// item is found, this is where it is removed
			else
			{
				nodePtr tempPtr;	// temp pointer
				
				if( !node->left)	// the node has no left child
				{
					tempPtr = node->right;
					delete node;
					node = tempPtr;
					return;	// fault check
				}
				
				if( !root->right)	// the node has left child, but no right
				{
					tempPtr = root->left;
					delete node;
					node = tempPtr;
					return;	// fault check
				}
				
				else	// the node has left and right child
				{
					// find node's parent
					tempPtr = node->left;
					
					while( tempPtr->right)	// while tempPtr has a right child
						tempPtr = tempPtr->right;	// take the tempPtr all the way right
					
					// let the parent's height replace the value to be
					//		deleted, and delete the parent node
					node->val = tempPtr->val;
					recRemove( tempPtr->val, node->left);
					rebalance( node);		// fix the heights and rotate if needed
				}
			}
		}
		
		/******************************************/
		//	Pre:	tree is initialized
		//	Post:	tree printed out to the screen
		//	Pur:	to print out the nodes sideways to the screen recursively
		void recDump( int indent, nodePtr node)
		{
			if( node)
			{
				recDump( indent + 5, node->right);
				cout << setw( indent) << ' ' << node->val << endl;
				recDump( indent + 5, node->left);
			}
		}
		
		/******************************************/
		//	Pre:	tree is initialized
		//	Post:	height of current node is returned
		//	Pur:	to get the height of the subtree rooted at this node
		int height( nodePtr node)
		{
			if( node)
			{
				renum( node);
				return node->height;
			}
			
			else
				return 0;
		}
		
		/******************************************/
		//	Pre:	tree is initialized
		//	Post:	all nodes are removed from the tree
		//	Pur:	to deallocate the tree
		void recRelease( nodePtr &node)
		{
			if( node) // if node points to something
			{
				recRelease( node->left);
				delete node;
				recRelease( node->right);
				node = NULL;
			}
			
			else
				return;
		}
		
		/******************************************/
		//	Pre:	tree contains values
		//	Post:	checks all the balances of the children of a node
		//	Pur:	to recursively check the constraints of the tree,
		//			the balances of the children
		void recSanityCheck( nodePtr node)
		{
			if( node)	// making sure node points to something
			{
				int leftchild, rightchild;	// initialize comparision variables
				
				recSanityCheck( node->left);	// go all the way left first
				
				// get values to compare
				if( !node->left)
					leftchild = 0;
				else
					leftchild = node->left->height;
				
				if( !node->right)
					rightchild = 0;
				else
					rightchild = node->right->height;
				
				// make sure the difference is not greater than 1
				assert( !( leftchild - rightchild > 1));
				
				recSanityCheck( node->right);	// go right
			}
			
			else
				return;	// tree is empty
		}
	
	public:
		/******************************************/
		//	Pre:	Nothing
		//	Post:	count initialized to 0
		//	Pur:	to create an AVL Tree
		AVLTree():count(0)
		{
			root = NULL;
		}
		
		/******************************************/
		//	Pre:	tree is initialized
		//	Post:	item inserted and count incremented
		//	Pur:	to call recInsert to insert a new value into the tree
		bool insert( T val)
		{
			if( contains( val))
				return false;
			else
			{
				count++;
				recInsert( val, root);
				return true;
			}
		}
		
		/******************************************/
		//	Pre:	tree is initialized, item is in the tree
		//	Post:	item removed from tree and count decremented
		//	Pur:	to call recRemove to remove a value from the tree
		bool remove( T val)
		{
			// check if the item is in the tree
			if( contains( val))
				{
					count--;
					recRemove( val, root);	// remove the item
					return true;
				}
			else
				return false;
		}
		
		/******************************************/
		//	Pre:	tree is initialized
		//	Post:	tree is deallocated
		//	Pur:	to deallocate the tree
		~AVLTree()
		{
			if( root)
				recRelease( root);
		}
		
		/******************************************/
		//	Pre:	tree is initialized
		//	Post:	returns true or false
		//	Pur:	to see if the given value is in the tree
		bool contains( T val)
		{
			bool inThere = false;	// false unless while loop changes state
			nodePtr tempPtr = root;	// make a temp pointer to root
			
			// while tempPtr != NULL and val is not there
			while( tempPtr && !inThere)
			{
				if( val < tempPtr->val)			// look left
					tempPtr = tempPtr->left;	// reset tempPtr to left
				else if( val > tempPtr->val)	// look right
					tempPtr = tempPtr->right;	// reset tempPtr to right
				else
					inThere = true;				// found the item
			}
			
			// the value of inThere is set
			//		this is used to check the state of inThere
			//		and return that state
			if( inThere)
				return true;
			else
				return false;
		}
		
		/******************************************/
		//	Pre:	tree is initialized, count initialized
		//	Post:	number of nodes in tree is returned
		//	Pur:	to return the number of nodes in the tree
		int size()
		{
			return count;
		}
		
		/******************************************/
		//	Pre:	tree is initialized
		//	Post:	height of the given node is returned
		//	Pur:	to return the height of the tree
		int height()
		{
			if( root == NULL)	// tree is empty
				return 0;
			else
				return root->height;	// tree has nodes
		}
		
		/******************************************/
		//	Pre:	tree is initialized
		//	Post:	the tree is printed to the screen
		//	Pur:	to print the tree sideways to the screen
		void dump()
		{
			recDump( 0, root);
		}
		
		/******************************************/
		//	Pre:	tree is initialized
		//	Post:	the entire tree is deleted, count = 0
		//	Pur:	to delete the entire tree
		void deleteTree()
		{
			if( root)
			{
				recRelease( root);
				count = 0;
			}
			
			else
				return;
		}
		
		/******************************************/
		//	Pre:	tree is initialized
		//	Post:	returns true if tree is empty
		//	Pur:	to check to see if the tree is empty
		bool isEmpty()
		{
			if( !root)
				return true;
			
			else
				return false;
		}
		
		/******************************************/
		//	Pre:	tree is initialized
		//	Post:	nothing
		//	Pur:	to call the recursive fcn recSanityCheck
		void sanityCheck()
		{
			recSanityCheck( root);
		}
};

#endif