avlnode.h

这是一个非常经典的二叉平衡树

#ifndef _cavlnode_
#define _cavlnode_

#include<iostream.h>
#include"avlite~1.h"

template<class T>
class CAVLNode
{
	private:
		CAVLNode<T>* GetBiggest() {return !m_right?this:m_right->GetBiggest();}
		CAVLNode<T>* GetSmallest(){return !m_left?this:m_left->GetSmallest();}
		CAVLNode<T>* LL();
		CAVLNode<T>* RR();
		CAVLNode<T>* LR();
		CAVLNode<T>* RL();
		CAVLNode<T>* Del();
		void SetSigns(short s);
		void FindWay(short his[]);
		 
		short m_avl;
		short m_sign;
		CAVLNode<T>* m_prev;
		CAVLNode<T>* m_left;
		CAVLNode<T>* m_right;
		T m_content;
		
	public:
		friend class CAVLTree<T>;
		friend class CAVLIterator<T,IN_ORDER>;
		friend class CAVLIterator<T,PRE_ORDER>;
		friend class CAVLIterator<T,POST_ORDER>;
		CAVLNode(T content);
		CAVLNode<T>* GetSymetricSon();
		CAVLNode<T>** GetPrevPtr();
		int GetHeight();
		CAVLNode<T>* GetRoot();
		void CalcAVL();
		CAVLNode<T>* Find(T content);
		CAVLNode<T>* AVL(short his[]=NULL);
		T GetContent();
};

template<class T>
CAVLNode<T>::CAVLNode(T content)
{
	m_prev=m_left=m_right=NULL;
	m_content=content;
}

template<class T>
int CAVLNode<T>::GetHeight()	//liefert Hoehe des Baumes
{
	int l = m_left  ? m_left  -> GetHeight() : -1;
	int r = m_right ? m_right -> GetHeight() : -1;

	return l > r ? l+1 : r+1;
}


template<class T>
CAVLNode<T>* CAVLNode<T>::Find(T content)
{
	if(content == m_content)
		return this;
	if(content <  m_content)
		return m_left?m_left->Find(content):this;

	return m_right?m_right->Find(content):this;
}


template<class T>
CAVLNode<T> *CAVLNode<T>::LL()
{
	CAVLNode<T> *help=m_left->m_right,*ret=GetRoot();
	m_left->m_right=this;
	if(m_prev)
		*GetPrevPtr()=m_left;
	else
		ret=m_left;
	m_left->m_prev=m_prev;
	m_prev=m_left;
	m_left=help;
	if(m_left) m_left->m_prev=this;
	return ret;
}

template<class T>
CAVLNode<T> *CAVLNode<T>::RR()
{
	CAVLNode<T> *help=m_right?m_right->m_left:NULL,*ret=GetRoot();
	m_right->m_left=this;
	if(m_prev)
		*GetPrevPtr()=m_right;
	else
		ret=m_right;
	m_right->m_prev=m_prev;
	m_prev=m_right;
	m_right=help;
	if(m_right) m_right->m_prev=this;
	return ret;
}

template<class T>
CAVLNode<T> *CAVLNode<T>::RL()
{
	CAVLNode<T> *ret=GetRoot();
	m_right->m_left->m_prev=m_prev;
	if(m_prev)
		*GetPrevPtr()=m_right->m_left;
	else
		ret=m_right->m_left;         
	m_prev=m_right->m_left;			
	m_right->m_left=m_prev->m_right;
	if(m_right->m_left) m_right->m_left->m_prev=m_right;
	m_prev->m_right=m_right;		
	m_right=m_prev->m_left;			
	m_prev->m_left=this;			
	m_prev->m_right->m_prev=m_prev;
	if(m_right) m_right->m_prev=this;
	return ret;
}

template<class T>
CAVLNode<T> *CAVLNode<T>::LR()
{
	CAVLNode<T> *ret=GetRoot();
	m_left->m_right->m_prev=m_prev;
	if(m_prev)
		*GetPrevPtr()=m_left->m_right;
	else
		ret=m_left->m_right;        
	m_prev=m_left->m_right;			
	m_left->m_right=m_prev->m_left;	
	if(m_left->m_right) m_left->m_right->m_prev=m_left;
	m_prev->m_left=m_left;		
	m_left=m_prev->m_right;		
	m_prev->m_right=this;		
	m_prev->m_left->m_prev=m_prev;
	if(m_left) m_left->m_prev=this;
	return ret;
}

template<class T>
void CAVLNode<T>::CalcAVL()
{
	m_avl = (m_right ? m_right -> GetHeight() + 1: 0) - (m_left  ? m_left  -> GetHeight() + 1: 0);
}

template<class T>
CAVLNode<T>* CAVLNode<T>::GetRoot()
{
	if(m_prev)
		return m_prev->GetRoot();
	else
		return this;
}

template<class T>
CAVLNode<T> ** CAVLNode<T>::GetPrevPtr()
{
	if(m_prev==NULL)
		return NULL;
	if(m_prev->m_left==this)
		return &(m_prev->m_left);
	else
		return &(m_prev->m_right);
}

template<class T>
CAVLNode<T>* CAVLNode<T>::GetSymetricSon()
{
	if(m_left)
		return m_left->GetBiggest();
	if(m_right)
		return m_right->GetSmallest();
	return NULL;
}

template<class T>
CAVLNode<T>* CAVLNode<T>::AVL(short his[]/*=NULL*/)
{
	if(!his)
	{
		his=new short[2];
		his[0]=his[1]=-1;
	}
	CalcAVL();
	if(m_avl<-1||m_avl>1)
	{
		if(his[0]==-1||his[1]==-1)
			FindWay(his);

		if(his[0])
			if(his[1])
				return RR();
			else
				return RL();
		else
			if(his[1])
				return LR();
			else
				return LL();
	}
	if(!m_prev)
			return this;
	his[1]=his[0];
	his[0]=m_prev->m_left==this?0:1;
	return m_prev->AVL(his);
}

template<class T>
CAVLNode<T>* CAVLNode<T>::Del()
{
	CAVLNode<T> *ret=m_prev;
	if(m_left)
		if(m_right)
		{
			CAVLNode<T>*help=GetSymetricSon();
			m_content=help->m_content;
			ret=help->Del();
			delete help;
		}
		else
		{
			if(m_prev) *GetPrevPtr()=m_left;
			ret=m_left;
			m_left->m_prev=m_prev;
		}
	else
		if(m_right)
		{
			if(m_prev) *GetPrevPtr()=m_right;
			ret=m_right;
			m_right->m_prev=m_prev;
		}
		else
			if(m_prev) *GetPrevPtr()=NULL;
	return ret;
}

template<class T>
void CAVLNode<T>::FindWay(short his[])
{
	his[0]=m_avl<0?0:1;
	if(his[0])
	{
		if(m_right) m_right->CalcAVL();
		his[1]=m_right->m_avl<0?0:1;
	}
	else
	{
		if(m_left) m_left->CalcAVL();
		his[1]=m_left->m_avl<0?0:1;
	}
}

template<class T>
void CAVLNode<T>::SetSigns(short s)
{
	m_sign=s;
	if(m_left)
		m_left->SetSigns(s);
	if(m_right)
		m_right->SetSigns(s);
}

template<class T>
T CAVLNode<T>::GetContent()
{
	return m_content;
}

#endif