avltree_delete.cpp

AVL树

/***********************************************************************/
/*                                                      */
/***********************************************************************/


#include<iostream.h>
#include"adjust.h"	
void avl_delete(PAVLTree ptree,KeyType key)
{
	PAVLNode p,s,temp;
	if(ptree==NULL)                              //原树为空的情况
		cout<<"The AVLtree is empty!"<<endl;
	p=*ptree;
    if(key==p->key)                              //原树只有一个结点的情况
	{
		delete p;
		cout<<"This AVLtree has only one node and it has been delete!"<<endl;
	}
	while(p=!NULL)                               //原树有1个以上结点，搜索要删除的结点                                     
	{
		if(key==p->key)
		break;
		if(key<p->key)
			p=p->llink;
		else
			p=p->rlink;
	}                                                
	if(p==NULL)                          
		cout<<"This node not exist!"<<endl;      //找不到要删除的结点
	s=temp=p;                                    //找到要删除的结点，先用temp储存起来
	if(p->llink!=NULL)                           //要删结点*p有左子女的情况，删除其左子树中关键码最大结点
	{
		p=p->llink;
        while(p->rlink!=NULL)
		{
			p=p->rlink;
		}
		if(p->key<p->plink->key)
		{
			p->plink->llink=p->llink;
			p->llink->plink=p->plink;
		}
		else
		{
			p->plink->rlink=p->llink;
			p->llink->plink=p->plink;
		}
		s->key=p->key;
		s->value=p->value;
	}
	else                                        //要删除的结点*p没有左子女的情况，直接删除*p
	{
		if(p->key<p->plink->key)
			p->plink->llink=p->rlink;
		else
			p->plink->rlink=p->rlink;
	}
	//至此已将关键码为key的结点(*p)从树中删除
	//以下调整沿被删结点通向根结点路径上结点的平衡因子，同时调整树的平衡
	while(p!=NULL)
	{
		p=p->plink;
		switch(p->bf)
		{
		case 0:                                 //平衡因子为0，整棵树平衡不会被破坏
			if(p->key<temp->key)                //所删结点在左子树
				p->bf=1;
			else                                //所删结点在右子树
				p->bf=-1;
			return;
		case 1:                                 //*p右子树较高
			if(p->key>temp->key)                //所删结点在右子树，该层平衡未破坏 
			{
				p->bf=0;
			}
			else                                //所删结点在左子树，要进行调整
			{
				if(p->rlink->bf==0)
					p=adjust1(p,p->rlink);
				if(p->rlink->bf==1)
					p=adjust1(p,p->rlink);        //上面两种情况调整方式相似
				if(p->rlink->bf==-1)
					p=adjust2(p,p->rlink);
			}
			break;
		case -1:                                //*p左子树较高
			if(p->key<temp->key)                //所删结点在左子树，该层平衡未破坏 
			{
				p->bf=0;
				return;
			}
			else                                //所删结点在右子树，要进行调整
			{
				if(p->llink->bf==0)
					p=adjust_1(p,p->llink);
				if(p->llink->bf==-1)
					p=adjust_1(p,p->llink);       //上面两种情况调整方式相似
				if(p->llink->bf==1)
					p=adjust_2(p,p->llink);
			}
			break;
		default:
			break;
		}
	}
}
void main()
{

}