AVL树

前言

AVL树，也叫平衡二叉树，是一种二叉排序树，其中每一个结点的左子树和右子树的高度差至多等于1。同时，将二叉树上结点的左子树深度减去右子树深度的值称为平衡因子BF，还将距离插入结点最近的且平衡因子的绝对值大于1的结点为根的子树，称为最小不平衡子树

如图：一为一个不平衡二叉排序树，显然时间复杂度较大，二为改进后的平衡二叉树，而在改进的过程中，最重要的就是通过平衡因子来判断是进行左旋还是右旋，如右旋，新增一个节点N后，平衡被打破，需要平衡因子2大于0，需要右旋，就是将其左子树作为根结点，左子树的右子树作为原根结点的左子树，这样做的原因就是根据二叉排序树的左右子树特点来的，很容易想明白

模拟平衡二叉树

不妨构造一个a[10]={3,2,1,4,5,6,7,10,9,8};

大概过程如图所示，其中最重要的就是平衡因子的判断，如果是同号，且绝对值大于1的话，就要做相应的旋转操作，如果是不同号的话，就要通过旋转先转换成同号，在做操作

左右旋操作

typedef struct BiTNode
{
	int data;
	int bf;
	struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;

//左旋处理
void R_Rotate(BiTree *p){
	BiTree L;
	L=(*p)->lchild;   //L指向p的左子树根结点
	(*p)->lchild=L->rchild; //L的右子树挂接为p的左子树
	L->rchild=(*p);  
	*p=L;           //p指向新的根结点
}

//右旋处理
void L_Ronate(BiTree *p)
{
	BiTree R;
	R=(*p)->rchild; //R指向p的右子树根结点
	(*p)->rchild=R->lchild;  //R的左子树挂接为P的右子树
	R->lchild=(*p);
	*p=R;            //p指向新的根结点
}

可以通过之前的图来对比看，其实质也就是交互根结点位置和挂接新左右子树

左右平衡旋转

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

/*  对以指针T所指结点为根的二叉树作左平衡旋转处理 */
/*  本算法结束时，指针T指向新的根结点 */
void LeftBalance(BiTree *T)
{ 
	BiTree L,Lr;
	L=(*T)->lchild; /*  L指向T的左子树根结点 */ 
	switch(L->bf)
	{ /*  检查T的左子树的平衡度，并作相应平衡处理 */ 
		 case LH: /*  新结点插入在T的左孩子的左子树上，要作单右旋处理 */ 
			(*T)->bf=L->bf=EH;
			R_Rotate(T);
			break;
		 case RH: /*  新结点插入在T的左孩子的右子树上，要作双旋处理 */ 
			Lr=L->rchild; /*  Lr指向T的左孩子的右子树根 */ 
			switch(Lr->bf)
			{ /*  修改T及其左孩子的平衡因子 */ 
				case LH: (*T)->bf=RH;
						 L->bf=EH;
						 break;
				case EH: (*T)->bf=L->bf=EH;
						 break;
				case RH: (*T)->bf=EH;
						 L->bf=LH;
						 break;
			}
			Lr->bf=EH;
			L_Rotate(&(*T)->lchild); /*  对T的左子树作左旋平衡处理 */ 
			R_Rotate(T); /*  对T作右旋平衡处理 */ 
	}
}

/*  对以指针T所指结点为根的二叉树作右平衡旋转处理， */ 
/*  本算法结束时，指针T指向新的根结点 */ 
void RightBalance(BiTree *T)
{ 
	BiTree R,Rl;
	R=(*T)->rchild; /*  R指向T的右子树根结点 */ 
	switch(R->bf)
	{ /*  检查T的右子树的平衡度，并作相应平衡处理 */ 
	 case RH: /*  新结点插入在T的右孩子的右子树上，要作单左旋处理 */ 
			  (*T)->bf=R->bf=EH;
			  L_Rotate(T);
			  break;
	 case LH: /*  新结点插入在T的右孩子的左子树上，要作双旋处理 */ 
			  Rl=R->lchild; /*  Rl指向T的右孩子的左子树根 */ 
			  switch(Rl->bf)
			  { /*  修改T及其右孩子的平衡因子 */ 
				case RH: (*T)->bf=LH;
						 R->bf=EH;
						 break;
				case EH: (*T)->bf=R->bf=EH;
						 break;
				case LH: (*T)->bf=EH;
						 R->bf=RH;
						 break;
			  }
			  Rl->bf=EH;
			  R_Rotate(&(*T)->rchild); /*  对T的右子树作右旋平衡处理 */ 
			  L_Rotate(T); /*  对T作左旋平衡处理 */ 
	}
}

插入与主函数

/*  若在平衡的二叉排序树T中不存在和e有相同关键字的结点，则插入一个 */ 
/*  数据元素为e的新结点，并返回1，否则返回0。若因插入而使二叉排序树 */ 
/*  失去平衡，则作平衡旋转处理，布尔变量taller反映T长高与否。 */
Status InsertAVL(BiTree *T,int e,Status *taller)
{  
	if(!*T)
	{ /*  插入新结点，树“长高”，置taller为TRUE */ 
		 *T=(BiTree)malloc(sizeof(BiTNode));
		 (*T)->data=e; (*T)->lchild=(*T)->rchild=NULL; (*T)->bf=EH;
		 *taller=TRUE;
	}
	else
	{
		if (e==(*T)->data)
		{ /*  树中已存在和e有相同关键字的结点则不再插入 */ 
			*taller=FALSE; return FALSE;
		}
		if (e<(*T)->data)
		{ /*  应继续在T的左子树中进行搜索 */ 
			if(!InsertAVL(&(*T)->lchild,e,taller)) /*  未插入 */ 
				return FALSE;
			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;
				}
		}
		else
		{ /*  应继续在T的右子树中进行搜索 */ 
			if(!InsertAVL(&(*T)->rchild,e,taller)) /*  未插入 */ 
				return FALSE;
			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;
				}
		}
	}
	return TRUE;
}

int main(void)
{    
	int i;
	int a[10]={3,2,1,4,5,6,7,10,9,8};
	BiTree T=NULL;
	Status taller;
	for(i=0;i<10;i++)
	{
		InsertAVL(&T,a[i],&taller);
	}
	return 0;
}

最后不得不说，AVL树是在是太复杂了，但是其思想是在是太精妙了，它克服了二叉排序树在查找效率上的不足，通过在插入数据时，就将其变成一个平衡二叉树，从而使其时间复杂度为O(logn)