AVL树详解

红太狼 2022-06-13 11:21 201阅读 0赞

下面讲解AVL树的C语言代码实现：

1.首先是定义：

#define LH 1
    #define EH 0
    #define LH -1
    #define TRUE 1
    #define FALSE 0

第一个LH是左子树比右子树高1，EH是两棵子树高度相同，RH代表右子树比左子树高一个节点。

2.二叉树节点声明：

typedef struct BiTNode	//二叉树生命
    	int data;	//节点值
    	int bf;		//平衡因子balance factor
    	struct BiTNode *left,*right;	//声明左孩子跟右孩子
    }BiTNode,*BiTree;

3.插入节点的操作：

BiTree InsertAVL(BiTNode *T, int e, int *taller)//二叉树插入操作
    {
    	if(*T == NULL)//如果是一只空树
    	{
    		T = (*BiTree)malloc(sizeof(BiTree));//申请空间
    		T->data = e;
    		T->bf = EH;
    		T->left = T->right = NULL;
    		*taller = TRUE;//taller用来标识树是否增加高度
    	}
    	else
    	{
    		if(e == (*T)->data )//如果树中本来有这个数
    		{
    			T->bf = EH; 
    			*taller = FALSE;
    			return FALSE;//返回插入失败
    		}
    		else if( e < (*T)->data )//如果小于节点值，则向左子树进行检查
    		{
    			if(!InsertAVL( &(*T)->lchild, e, taller))//检测是否插入失败
    			{
    				reutrn FALSE;
    			}
    			if(*taller)//如果树的高度加一，检测是否还是平衡，如果不平衡，就进行调整
    			{
    				switch((*T)->bf)//对节点T的平衡因子进行检测
    				{
    					case LH://左子树高
    						LeftBalance(T);//进行旋转调整
    						*taller = FASLE;//左子树高，原本应该变高，但旋转调整之后高度未增加
    						break;
    					case EH://两边一样高
    						*taller = TRUE;//高度加一个节点
    						(*T)->bf = LH;
    						break;
    					case RH://右子树高
    						(*T)->bf = EH;
    						*taller = FALSE;
    						break;				
    				}
    			}
    		}
    		else//原理同上
    		{
    			if(!InsertAVL( &(*T)->rchild, e, taller))
    			{
    				reutrn FALSE;
    			}
    			if(*taller)
    			{
    				switch((*T)->data)
    				{
    					case LH:
    						(*T)->bf = EH;
    						*taller = FASLE;
    						break;
    					case EH:
    						*taller = TRUE;
    						(*T)->bf = RH;
    						break;
    					case RH:
    						RightBalance(T);
    						*taller = FALSE;
    						break;
    				}
    			}
    		}
    	}
    }

4.左子树高，进行平衡操作：

void LeftBalance(BiTree *T)	//左子数过长
    {
    	BiTree L,Lr;
    	L = (*T)->left;	//令L等于T的左孩子
    	
    	switch(L->bf)	//检查左孩子的平衡因子
    	{
    		case LH:	//LL型
    			(*T)->bf = L->bf = EH;
    			R_Rotate(&(*T));
    			break;
    		case RH:	//LR型
    			Lr = L->left;	//检查T的左孩子的右孩子的平衡因子
    			switch(Lr->bf)
    			{
    				case LH:	//如果平衡因子为1，而不是0或者-1，即左子树比右子树高一个节点
    					(*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)->left);				//先左旋
    			R_Rotate(T);						//后右旋
    			break;
    	}
    }

5.右子树过高，进行平衡操作，原理同上：

void RightBalance(BiTree *T)//同上
    {
    	BiTree R,Rl;
    	R = (*T)->right;				
    
    	switch(R->bf)					
    	{
    		case RH:			//RR型
    			(*T)->bf = L->bf = EH;
    			L_Rotate(&(*T));
    			break;
    		case LH:			//RL型
    			Rl = R->left;
    			switch(Rl->bf)
    			{
    				case LH:
    					(*T)->bf = EH;
    					L->bf = RH;
    					break;
    				case EH:
    					(*T)->bf = L->bf = EH;
    					break;
    				case RH:
    					(*T)->bf = LH;
    					L->right = EH;
    					break;
    			}
    			Rl->bf = EH;
    			R_Rotate(&(*T)->right);
    			L_Rotate(T);
    			break;
    	}
    }

6.左旋操作：

void L_Rotate(BiTree *p)	//左旋
    {
    	BiTree R;
    	R = (*p)->right;
    	(*p)->right = R->left;
    	(*p)->right = (*p);
    	*p =R;
    }

7.右旋操作：

void R_Rotate(BiTree *p)	//右旋
    {
    	BiTree L;	//声明一个BiTree变量来储存p的左孩子
    	L = (*p)->left;	
    	(*p)->left = L->right;	//令p的左孩子L的右孩子等于p的左孩子
    	L->right = (*p);	//将p作为其右孩子
    	*p = L;	//将L放到根节点位置
    }