算法9.7.txt

数据结构课件

【算法9.7】

typedef  struct  NODE{
	ElemType   elem;  /*数据元素*/
	int        bf;    /*平衡因子*/
        struct   NODE   *lc,*rc;   /*左右子女指针*/
	}NodeType;     /*结点类型*/

void  R_Rotate(NodeType **p)
{	/*对以*p指向的结点为根的子树，作右单旋转处理，处理之后，*p指向的结点为子树的新根*/
	lp=(*p)->lc;        /*lp指向*p左子树根结点*/
    (*p)->lc=lp->rc;    /*lp的右子树挂接*p的左子树*/
    lp->rc=*p; *p=lp;   /*  *p指向新的根结点*/
}

void  L_Rotate(NodeType **p)
{	/*对以*p指向的结点为根的子树，作左单旋转处理，处理之后，*p指向的结点为子树的新根*/
	lp=(*p)->rc;        /*lp指向*p右子树根结点*/
    (*p)->rc=lp->lc;    /*lp的左子树挂接*p的右子树*/
    lp->lc=*p; *p=lp;  /* *p指向新的根结点*/
}

#define  LH  1  /* 左高 */
#define  EH  0  /* 等高 */
#define  RH  1  /* 右高 */

void	LeftBalance((NodeType **p)
{	/*对以*p指向的结点为根的子树，作左平衡旋转处理，处理之后，*p指向的结点为子树的新根*/
	lp=(*p)->lc;        /*lp指向*p左子树根结点*/
	switch((*p)->bf) 	  /*检查*p平衡度，并作相应处理*/
	{case  LH: 	/*新结点插在*p左子女的左子树上，需作单右旋转处理*/
		(*p)->bf=lp->bf=EH;R_Rotate(p);break;
	case  EH: 	/*原本左、右子树等高，因左子树增高使树增高*/
		(*p)->bf=LH;	*paller=TRUE;break;
	case  RH: 	/*新结点插在*p左子女的右子树上，需作先左后右双旋处理*/
		rd=lp->rc;     /*rd指向*p左子女的右子树根结点*/
		switch(rd->bf) 		/*修正*p及其左子女的平衡因子*/
		{ case	LH:(*p)->bf=RH;lp->bf=EH;break;
		  case	EH:(*p)->bf=lp->bf=EH;break;
		  case	RH:(*p)->bf=EH;lp->bf=LH;break;
		}/*switch(rd->bf)*/
		rd->bf=EH;		L_Rotate(&((*p)->lc)); 		/*对*p的左子树作左旋转处理*/
		R_Rotate(p);		/*对*t作右旋转处理*/
	}/*switch((*p)->bf)*/
}/*LeftBalance*/

int  InsertAVL(NodeType **t,ElemType e,Boolean *taller)
{	/*若在平衡的二叉排序树t中不存在和e有相同关键码的结点，则插入一个数据元素为e的*/
/*新结点，并反回1，否则反回0。若因插入而使二叉排序树失去平衡，则作平衡旋转处理，*/
/*布尔型变量taller反映t长高与否*/
	if(!(*t))   /*插入新结点，树“长高”，置taller为TURE*/
	{	*t=(NodeType *)malloc(sizeof(NodeType)); (*T)->elem=e;
		(*t)->lc=(*t)->rc=NULL;(*t)->bf=EH;*taller=TRUE;
	}/*if*/
	else
	{	if(e.key==(*t)->elem.key)     /*树中存在和e有相同关键码的结点，不插入*/
		{	taller=FALSE; return 0;}
		if(e.key<(*t)->elem.key)
		{	/*应继续在*t的左子树上进行*/
			if(!InsertAVL(&((*t)->lc)),e,&taller))	return 0;  /*未插入*/
			if(*taller)  	/*已插入到(*t)的左子树中，且左子树增高*/
				switch((*t)->bf) 	/*检查*t平衡度*/
				{case  LH: 	/*原本左子树高，需作左平衡处理*/
					LeftBalance(t);	*taller=FALSE;break;
				 case  EH: 	/*原本左、右子树等高，因左子树增高使树增高*/
					(*t)->bf=LH;	*taller=TRUE;break;
				 case  RH: 	/*原本右子树高，使左、右子树等高*/
					(*t)->bf=EH;	*taller=FALSE;break;
				}
		}/*if*/
		else 		/*应继续在*t的右子树上进行*/
		{	if(!InsertAVL(&((*t)->rc)),e,&taller))	return 0;  /*未插入*/
			if(*taller)		  /*已插入到(*t)的左子树中，且左子树增高*/
				switch((*t)->bf) 	/*检查*t平衡度*/
				{case  LH:	 /*原本左子树高，使左、右子树等高*/
					(*t)->bf=EH;	*taller=FALSE;break;
				 case  EH: 	/*原本左、右子树等高，因右子树增高使树增高*/
					(*t)->bf=RH;	*taller=TRUE;break;
				 case  RH: /*原本右子树高，需作右平衡处理*/
					RightBalance(t);	*taller=FALSE;break;
				}
		}/*else*/
	}/*else*/
	return 1;
}/*InsertAVL*/