몇 년 전에 자기가 쓴 AVL을 붙여서 실현을 했어요.

#ifndef __AVL_TREE_H__
#define __AVL_TREE_H__

template
class AVLNode
{
public:
	AVLNode( const T &objData, 
		     AVLNode *pParent = NULL, 
			 AVLNode *pLeft = NULL,
			 AVLNode *pRight = NULL,
			 int  iBF = 0 )
			 :m_data(objData),
			 m_pParent(pParent),
			 m_pLeft(pLeft),
			 m_pRight(pRight),
			 m_iBF(iBF)
	{

	}
public:
	bool	IsRoot() const {  return NULL==m_pParent; }
	bool	IsLeftChild() const { return !IsRoot()&&(this == m_pParent->m_pLeft); }
	bool	IsRightChild() const { return !IsRoot()&&(this == m_pParent->m_pRight); }

public:
	AVLNode* maximum() const
	{
		AVLNode *pNode = this;
		while ( NULL != pNode->m_pRight )
			pNode = pNode->m_pRight;
		return pNode;
	}

	AVLNode* minimum() const
	{
		AVLNode *pNode = this;
		while ( NULL != pNode->m_pLeft )
			pNode = pNode->m_pLeft;
		return pNode;
	}

public:
	AVLNode* Successor() const
	{
		AVLNode *pNode = this;
		if ( NULL != pNode->m_pRight )
			return pNode->m_pRight->minimum();

		while (pNode->IsRightChild())
			pNode = pNode->m_pParent;
		return pNode->m_pParent;
	}

	AVLNode* Predecessor() const
	{
		AVLNode *pNode = this;
		if ( NULL != pNode->m_pLeft )
			return pNode->m_pLeft->maximum();
		
		while ( pNode->IsLeftChild() )
			pNode = pNode->m_pParent;
		return pNode->m_pParent;
	}


private:
	AVLNode *m_pParent;
	AVLNode	*m_pLeft;
	AVLNode *m_pRight;
	T		m_data;
	int		m_iBF;
};

template
class AVLIterator
{
public:
	AVLIterator( const AVLNode *pNode  = NULL)
		:m_pCur( pNode )
	{

	}
public:
	AVLNode& operator*() { return *m_pCur; }
	AVLNode* operator->() { return m_pCur; }

	bool operator==(const AVLIterator &iter ) const
	{
		return iter.m_pCur == m_pCur;
	}

	bool operator!=(const AVLIterator &iter ) const
	{
		return iter.m_pCur != m_pCur;
	}
	
	AVLIterator& operator++()
	{
		if ( NULL != m_pCur )
			m_pCur = m_pCur->Successor();
		return *this;
	}

	AVLIterator operator++(int)
	{
		AVLIterator iter = *this;
		++(*this);
		return iter;
	}

private:
	AVLNode		*m_pCur;
};

template
class AVLTree
{
public:
	AVLTree( AVLNode *pNode = NULL,
		     UINT uCount = 0)
			 :m_pRoot(pNode),
			 m_uCount(uCount)
	{

	}
public:
	void	insert( const T &objData )
	{
		AVLNode *pNode		= GetInsertPos( objData );
		AVLNode *pNewNode	= new AVLNode(objData);
		if ( NULL == m_pRoot )
		{
			m_pRoot = pNewNode;
			++m_uCount;
			return;
		}

		if ( NULL == pNode )
			return;

		if ( pNode->m_data > objData )
			pNode->m_pLeft = pNewNode;
		else
			pNode->m_pRight = pNewNode;
		pNewNode->m_pParent = pNode;
		++m_uCount;

		T *pData = &objData;
		while ( NULL != pNode )
		{
			pNode->m_iBF += pNode->m_data>*pData?1:-1;
			if ( 2 == pNode->m_iBF )
				R_ReBalance( pNode );
			else if ( -2 == pNode->m_iBF )
				L_ReBalance( pNode );
			else if ( 0 == pNode->m_iBF )
				break;

			pData = pNode->m_data;
			pNode = pNode->m_pParent;
		}

		
	}	

	void	remove( T &objData)
	{
		AVLNode *pNode = Search( objData );
		if ( NULL == pNode )
			return;

		AVLNode *pRemoved = pNode;
		if ( pNode->m_pRight && pNode->m_pLeft )
			pRemoved = pNode->Successor();

		AVLNode *pChild = pRemoved->m_pLeft;
		if ( pRemoved->m_pRight )
			pChild = pRemoved->m_pRight;
		if ( NULL != pChild )
			pChild->m_pParent = pRemoved->m_pParent;

		if (pRemoved->IsRoot())
			m_pRoot	 = pChild;
		else if ( pRemoved->IsLeftChild())
			pRemoved->m_pParent->m_pLeft = pChild;
		else
			pRemoved->m_pParent->m_pRight = pChild;

		if ( pRemoved != pNode )
			pNode->m_data = pRemoved->m_data;

		AVLNode *pCurrent = pRemoved->m_pParent;
		delete pRemoved;
		--m_uCount;

		T *pData = &objData;
		while ( NULL != pCurrent )
		{
			pCurrent->m_iBF -= pCurrent->m_data>*pData?1:-1;
			if ( 2 == pCurrent->m_iBF )
				R_ReBalance( pCurrent );
			else if ( -2 == pCurrent->m_iBF )
				L_ReBalance( pCurrent );
			else if ( 0 == pCurrent->m_iBF )
				break;
			
			pData = pCurrent->m_data;
			pCurrent = pCurrent->m_pParent;
		}

	}

	AVLNode *Search( const T &objData )
	{
		AVLNode *pNode = m_pRoot;
		while ( NULL != pNode )
		{
			if ( objData > pNode->m_data )
				pNode = pNode->m_pRight;
			else if ( objData < pNode->m_data )
				pNode = pNode->m_pLeft;
			else
				return pNode;
		}
		return NULL;
	}

private:
	AVLNode *GetInsertPos(const T &objData ) const
	{
		AVLNode *pNode = m_pRoot;
		while ( NULL != pNode )
		{
			if ( objData > pNode->m_data )
			{
				if ( NULL == pNode->m_pRight )
					return pNode;
				pNode = pNode->m_pRight;
			}
			else if ( objData < pNode->m_data )
			{
				if ( NULL == pNode->m_pLeft )
					return pNode;
				pNode = pNode->m_pLeft;
			}
			else
				return NULL;
		}
		return NULL;
	}


	void R_Rotation( AVLNode *&pNode )
	{
		if ( NULL == pNode )
			return;
		AVLNode *pT = pNode->m_pLeft;
		pT->m_pParent = pNode->m_pParent;    //        

		if ( pNode->IsRoot() )				 
			m_pRoot = pT;
		else if ( pNode->IsLeftChild() )
			pNode->m_pParent->m_pLeft = pT; 
		else
			pNode->m_pParent->m_pRight = pT;

		
		if ( NULL != pT->m_pRight )			 //Beta       
			pT->m_pRight->m_pParent = pNode;
		pNode->m_pLeft = pT->m_pRight;


		pT->m_pRight = pNode;				 //       
		pNode->m_pParent = pT;


		//reset the balance factor
		--(pNode->m_iBF) -= pT->m_iBF>0?pT->m_iBF:0;
		--(pT->m_iBF) += pNode->m_iBF<0?pNode->m_iBF:0;

		pNode = pT;
	}

	void L_Rotation( AVLNode *&pNode )
	{
		if ( NULL == pNode )
			return;
		AVLNode *pT = pNode->m_pRight;
		pT->m_pParent = pNode->m_pParent;

		
		if ( pNode->IsRoot() )
			m_pRoot = pT;
		else if ( pNode->IsLeftChild() )
			pNode->m_pParent->m_pLeft = pT;
		else
			pNode->m_pParent->m_pRight = pT;

		if ( NULL != pT->m_pLeft )
			pT->m_pLeft->m_pParent = pNode;
		pNode->m_pRight = pT->m_pLeft;

		pT->m_pLeft = pNode;
		pNode->m_pParent = pT;
		
		//reset the balance factor
		++(pNode->m_iBF) -= pT->m_iBF<0?pT->m_iBF:0;
		++(pT->m_iBF) += pNode->m_iBF>0?pNode->m_iBF:0;
		
		pNode = pT;

	}

	void L_ReBalance( AVLNode *&pNode )
	{
		if ( NULL != pNode->m_pRight && 1 == pNode->m_pLeft->m_iBF )
			R_ReBalance( pNode->m_pRight );
		L_Rotation( pNode );
	}

	void R_ReBalance( AVLNode *&pNode )
	{
		if ( NULL != pNode->m_pLeft && -1 == pNode->m_pLeft->m_iBF )
			L_ReBalance( pNode->m_pLeft );
		R_Rotation( pNode );
	}

public:
	AVLIterator	begin() 
	{
		if ( NULL != m_pRoot )
			return AVLIterator(m_pRoot->minimum());
		return AVLIterator();

	};

	AVLIterator end(){
		return AVLIterator();
	}
	
private:
	AVLNode	*m_pRoot;
	UINT		 m_uCount;
};
#endif //__AVL_TREE_H__