avltree.h

平衡树

//******************************  AVLTree.h  ******************************
//						definition of class AVL Tree
//                                 平衡树
#ifndef AVLTREE_H
#define AVLTREE_H

#include "AVLNode.h"

using namespace std;

template< typename T>
class AVLTree
{
public:
	AVLTree( AVLNode<T>* p = 0 ) { root = p; }
	int height() const { return heightHelper(root); }                       // 平衡树的高度
	void insert( const T& el ) { insertHelper( root, el ); }				// 插入节点
	void displayTree() const { displayTreeHelper( root, 0 ); }				// 打印平衡树
private:
	AVLNode<T>* root;
	void rotateWithLeftChild( AVLNode<T>*& );				// 左单旋
	void doubleWithLeftChild( AVLNode<T>*& );				// 右左双旋
	void rotateWithRightChild( AVLNode<T>*& );				// 右单旋
	void doubleWithRightChild( AVLNode<T>*& );				// 左右双旋
	/*--------------------utility functions--------------------*/     //利用工具函数实现封装
	int heightHelper( AVLNode<T>* ) const;
	void insertHelper( AVLNode<T>* &, const T& );
	void displayTreeHelper( AVLNode<T>*, int ) const;
};
//-------------------------------------------------------------------------
template<typename T>					// 左单旋：k2左节点的左子树高度太大
void AVLTree<T>::rotateWithLeftChild( AVLNode<T>* &k2 )
{
	AVLNode<T>* k1 = k2->lc;
	k2->lc = k1->rc;
	k1->rc = k2;
	k2 = k1;
}
//-------------------------------------------------------------------------
template<typename T>				  // 右左双旋：k3左节点的右子树高度太大
void AVLTree<T>::doubleWithLeftChild( AVLNode<T>* &k3 )
{
	rotateWithRightChild( k3->lc );
	rotateWithLeftChild( k3 );
}
//-------------------------------------------------------------------------
template<typename T>					// 右单旋：k2右节点的右子树高度太大
void AVLTree<T>::rotateWithRightChild( AVLNode<T>* &k2 )
{
	AVLNode<T>* k1 = k2->rc;
	k2->rc = k1->lc;
	k1->lc = k2;
	k2 = k1;
}
//-------------------------------------------------------------------------
template<typename T>				  // 左右双旋：k3右节点的左子树高度太大
void AVLTree<T>::doubleWithRightChild( AVLNode<T>* &k3 )
{
	rotateWithLeftChild( k3->rc );
	rotateWithRightChild( k3 );
}
//******************** definition of utility functions ****************************
//-------------------------------------------------------------------------
template<class T>                                           // 平衡树的高度
int AVLTree<T>::heightHelper( AVLNode<T> *p ) const 
{
	if( !p )
		return 0;
	else {
		int lheight = heightHelper( p->lc );
		int rheight = heightHelper( p->rc );
		if( lheight > rheight )
			return ++lheight;
		else
			return ++rheight;
	}	
}
//-------------------------------------------------------------------------
template<typename T>						// 添加节点，并调节使树保持平衡
void AVLTree<T>::insertHelper( AVLNode<T>*& p, const T& element )
{
	if( p == NULL )
		p = new AVLNode<T>( element );
	else if ( element < p->data )
	{
		insertHelper( p->lc, element );
		if( heightHelper(p->lc) - heightHelper(p->rc) == 2 )
			if( element < p->lc->data )
				rotateWithLeftChild( p );
			else
				doubleWithLeftChild( p );
	}
	else if ( element > p->data )
	{
		insertHelper( p->rc, element );
		if( heightHelper(p->rc) - heightHelper(p->lc) == 2 )
			if( element > p->rc->data )
				rotateWithRightChild( p );
			else
				doubleWithRightChild( p );
	}
}
//-------------------------------------------------------------------------
template<class T>                                   // 按树的形状打印平衡树
void AVLTree<T>::displayTreeHelper( AVLNode<T>* p, int totalSpaces ) const 
{
	while ( p )
	{
		displayTreeHelper( p->rc, totalSpaces+5 );
		for ( int i = 0; i <= totalSpaces; i++ )
			cout << ends;
		cout << p ->data << endl;
		p = p->lc;
		totalSpaces += 5;
	}
}

#endif