AVL樹詳解

下面講解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放到根節點位置
}