avlnode.h.bak

数据结构avltr

//this is avl tree node 



template <class T> class avlNode//平衡二叉树结点类
{
	public:
		avlNode(T val);//构造函数
		avlNode(T val,avlNode<T> *left,avlNode<T> *right,int bf);
		avlNode<T>* copy()const;//复制以当前结点为根的二叉树 ：(写多了，没用上)                           
		void release();//删除以当前结点为根的左右子树									
		void left(avlNode *);//把当前结点的左指针修改为函数的参数
		avlNode<T>* left()const;//左子结点访问，返回左结点的指针
		void right(avlNode *v);//把当前结点的右指针修改为函数的参数
		avlNode<T>* right()const;//右子结点访问，返回右结点的指针
		int add(avlNode<T>* &p,T val);//插入一个值；返回新的avl树的根结点的指针
		void preorderview(avlNode<T> *current,int i=-1);//前序周游
		avlNode<T>* remove(T val,avlNode<T>* &waste);//删除以当前结点的为根的avl树中的val结点
		avlNode<T>* findNodeValue(T val);//查找val结点
		T value;//码值
	private:
		int bf;// balance factor
		avlNode<T>* leftptr;//左右指针
		avlNode<T>* rightptr;
		avlNode<T>* restoreLeftBalance(int oldbf);//删除时左子树失衡的时候调整，返回新的树根的指针
		avlNode<T>* restoreRightBalance(int oldbf);//删除时右子树失衡的时候调整，返回新的树根的指针
		avlNode<T>* removeLeftmostElement(avlNode<T>* &childptr);//找到最左的结点
		avlNode<T>* removeBalanceLeft();//从左子树删除的时候判断层数的改变
		avlNode<T>* removeBalanceRight();//从右子树删除的时候判断层数的改变
		avlNode<T>* LL_singleRotation();//在插入时候左子树LL失衡的时候调整，返回新的树根的指针
		avlNode<T>* RR_singleRotation();//在插入时候右子树RR失衡的时候调整，返回新的树根的指针
		avlNode<T>* LR_doubleRotation();//在插入时候左子树LR失衡的时候调整，返回新的树根的指针
		avlNode<T>* RL_doubleRotation();//在插入时候右子树RL失衡的时候调整，返回新的树根的指针

};


template <class T> avlNode<T>::avlNode(T val)
{
	value=val;
	leftptr=NULL;
	rightptr=NULL;
	bf=0;
}
template <class T> avlNode<T>::avlNode(T val,avlNode<T> *left,avlNode<T> *right,int bf=0)
{
	value=val;
	leftptr=left;
	rightptr=right;
	bf=bf;
}
template <class T> avlNode<T>* avlNode<T>::copy()const
{
	avlNode<T> *nl,*nr;
	nl=(leftptr==NULL?NULL:leftptr->copy());//递归调用复制左子树
	nr=(rightptr==NULL?NULL:rightptr->copy());//递归调用复制右子树
	avlNode<T>* node=new avlNode<T>(value,nl,nr,bf);
	if(node!=NULL)   //?? ==NULL
		cout<<"error"<<endl;
	else
		return node;
}
template <class T> void avlNode<T>::release()
{
	if (leftptr)
	{//删除左子树中的结点
		leftptr->release();//递归调用
		delete leftptr;
		leftptr=0;
	}
	if (rightptr)
	{//删除右子树中的结点
		rightptr->release();//递归调用
		delete rightptr;
		rightptr=0;
	}
}
template <class T> avlNode<T>* avlNode<T>::left()const
{
	return leftptr;
}
template <class T> void avlNode<T>::left(avlNode<T>* v)
{
	leftptr=v;
}
template <class T> avlNode<T>* avlNode<T>::right()const
{
	return rightptr;
}
template <class T> void avlNode<T>::right(avlNode<T>* v)
{
	rightptr=v;
}
template <class T> int avlNode<T>::add(avlNode<T>* &rp,T val)
{//返回值表明以当前结点为根的树是否再插入之后增高，0:非增高，非0:增高
	if (val<value)
	{//左子树插入
		if (rp->left()==NULL)
			rp->left(new avlNode<T>(val));
		else if(rp->left()->add(rp->leftptr,val)==0)//插入后子树没有增高
			return 0;
		if (rp->bf==-1)
		{//原来已经倾斜，左边失衡，需要做平衡处理
	       if (rp->left()->bf<0)  //插入在左侧，单旋转
	             rp = LL_singleRotation();
	       else rp = LR_doubleRotation();	//插入在右侧，双旋转
		   return 0;
		}
		return --bf;   // bf=(0, +1)的情况，不需要调整树，只要修改bf
	}
	else
	{
		if (rp->right()==NULL)
			rp->right(new avlNode<T>(val));
		else if (rp->right()->add(rp->rightptr,val)==0)//插入后子树没有增高 
			return 0;
		if(rp->bf==1)
		{//原来已经倾斜，需要做平衡处理
	       if (rp->right()->bf>0)    //插入在右侧，单旋转
	           rp = RR_singleRotation();
	       else rp = RL_doubleRotation();  //插入点在右侧.双旋转
		   return 0;
		}
		return ++bf; // bf=(0, -1)的情况，不需要调整树，只要修改bf
	}
}


template <class T> avlNode<T>* avlNode<T>::remove(T val,avlNode<T>* &waste)
{
	if (val==value)
	{
		waste=this;
		//当没有右子树的时候返回左子树
		if(right()==NULL)
			return left();
		//删除右子树中的最小结点
		int oldbf=right()->bf;
		avlNode* newroot;
		right(right()->removeLeftmostElement(newroot));//找到后返回已经平衡的avl树的根指针
		newroot->left(left());
		newroot->right(right());
		newroot->bf=bf;
		return newroot->restoreRightBalance(oldbf);//作树的平衡
	}
	else if(val<value)
	{//从左子树中删除
		if(left()==NULL)
			return this;
		//执行删除
		int oldbf=left()->bf;
		left(left()->remove(val,waste));//递归调用
		return restoreLeftBalance(oldbf);//平衡当前的子树
	}
	else
	{//从右子树中删除
		if(right()==NULL)
			return this;
		//执行删除
		int oldbf=right()->bf;
		right(right()->remove(val,waste));//递归调用
		return restoreRightBalance(oldbf);//平衡当前的子树
	}
}
template <class T> avlNode<T>* avlNode<T>::removeLeftmostElement(avlNode<T>* &childptr)
{
	avlNode* leftchild=left();
	//找到最小的值，返回，否则递归调用
	if (leftchild==NULL)
	{
		childptr=this;
		return right();
	}
	int oldbf=leftchild->bf;
	left(leftchild->removeLeftmostElement(childptr));//递归调用
	return restoreLeftBalance(oldbf);//做平衡
}
template <class T> avlNode<T>* avlNode<T>::restoreLeftBalance(int oldbf)
{
	avlNode<T>* leftchild=left();
	//计算删除后的子树对当前的根结点的平衡因子的影响
	if (leftchild==NULL)
		bf++;
	else if((leftchild->bf!=oldbf)&&(leftchild->bf==0))
		bf++;
	if (bf>1)//失衡
		return removeBalanceLeft();//调整
	return this;
}
template <class T> avlNode<T>* avlNode<T>::restoreRightBalance(int oldbf)//和上个函数对称的。一个左边一个右边
{
	avlNode<T>* rightchild=right();
	if (rightchild==NULL) 
		bf--;
	else if((rightchild->bf!=oldbf)&&(rightchild->bf==0))
		bf--;
	if (bf<-1)
		return removeBalanceRight();
	return this;
}
template <class T> avlNode<T>* avlNode<T>::removeBalanceLeft()//删除时左子树失衡的时候调整，返回新的树根的指针
{
	int oldbf=right()->bf;
	if (oldbf<0)//双旋转
	{
	    return RL_doubleRotation();
	}
	else
	{//单旋转
		return RR_singleRotation();
	}
}
template <class T> avlNode<T>* avlNode<T>::removeBalanceRight()//和上个函数对应，一个左边一个右边
{
	int oldbf=left()->bf;
	if (oldbf<0)
	{//双旋转
    	return LR_doubleRotation();
	}
	else
	{//单旋转
		return LL_singleRotation();
	}
}
template <class T> avlNode<T>* avlNode<T>::findNodeValue(T val)
{
	if (val==value)
	{
		return this;
	}
	else if (val>value)
	{//大于的话在右子树中查找
		if (right()!=NULL)
			return right()->findNodeValue(val);//递归调用
		else 
			return NULL;
	}
	else
	{//小于的话在左子树中查找
		if (left()!=NULL)			
			return left()->findNodeValue(val);//递归调用
		else
			return NULL;
	}
}
template <class T> void avlNode<T>::preorderview(avlNode<T> *current,int i)
{
	i++;//层计数器
	if (current)
	{
		cout<<setw(8)<<current->value<<setw(10)<<current->bf<<" "<<setw(6)<<i<<endl;
		preorderview(current->left(),i);//递归调用
		preorderview(current->right(),i);//递归调用
	}
}

template <class T> avlNode<T>* avlNode<T>::LL_singleRotation()
{
	avlNode<T> *p;
	p=left();
	left(p->right());
	bf=0;
	p->right(this);
	p->bf=0;
	return p;
}

template <class T> avlNode<T>* avlNode<T>::LR_doubleRotation()
{
	avlNode<T> *p,*q;
	q=left();
	p=q->right();
	q->right(p->left());
	left(p->right());
	p->left(q);
	bf=q->bf=0;
	if(p->bf==-1) bf=1;
	if(p->bf==1) q->bf=-1;
	p->right(this);
	p->bf=0;
	return p;
}

template <class T> avlNode<T>* avlNode<T>::RR_singleRotation()
{
	avlNode<T> *p;
	p=right();
	right(p->left());
	bf=0;
	p->left(this);
	p->bf=0;
	return p;
}

template <class T> avlNode<T>* avlNode<T>::RL_doubleRotation()
{
	avlNode<T> *p,*q;
	q=right();
	p=q->left();
	q->left(p->right());
	right(p->left());
	p->right(q);
	bf=q->bf=0;
	if(p->bf=-1) q->bf=1;
	if(p->bf=1) bf=-1;
	p->left(this);
	p->bf=0;
	return p;
}