平衡二叉樹（Balanced Binary Tree）是二叉查找樹的一個進化體，也是第一個引入平衡概念的二叉樹。1962年，G.M. Adelson-Velsky 和 E.M. Landis發明了這棵樹，所以它又叫AVL樹。平衡二叉樹要求對于每一個節點來說，它的左右子樹的高度之差不能超過1，如果插入或者刪除一個節點使得高度之差大于1，就要進行節點之間的旋轉，將二叉樹重新維持在一個平衡狀態。這個方案很好的解決了二叉查找樹退化成鏈表的問題，把插入，查找，刪除的時間復雜度最好情況和最壞情況都維持在O(logN)。但是頻繁旋轉會使插入和刪除犧牲掉O(logN)左右的時間，不過相對二叉查找樹來說，時間上穩定了很多。

平衡二叉樹實現的大部分過程和二叉查找樹是一樣的（學平衡二叉樹之前一定要會二叉查找樹），區別就在于插入和刪除之后要寫一個旋轉算法去維持平衡，維持平衡需要借助一個節點高度的屬性。

一、定義及原理

現在又a[10] = {3, 2, 1, 4, 5, 6, 7, 10, 9, 8}需要構建二叉排序樹。在沒有學習平衡二叉樹之前，根據二叉排序樹的特性，通常會將它構建成如下左圖。雖然完全符合二叉排序樹的定義，但是對這樣高度達到8的二叉樹來說，查找是非常不利的。因此，更加期望構建出如下右圖的樣子，高度為4的二叉排序樹，這樣才可以提供高效的查找效率。

平衡二叉樹是一種二叉排序樹，是一種高度平衡的二叉樹，其中每個結點的左子樹和右子樹的高度至多等于1.意味著：要么是一棵空樹，要么左右都是平衡二叉樹，且左子樹和右子樹深度之絕對值不超過1. 將二叉樹上結點的左子樹深度減去右子樹深度的值稱為平衡因子BF，那么平衡二叉樹上的所有結點的平衡因子只可能是-1、0和1。只要二叉樹上有一個結點的平衡因子的絕對值大于1，則該二叉樹就是不平衡的。

平衡二叉樹的前提是它是一棵二叉排序樹。

??? 距離插入結點最近的，且平衡因子的絕對值大于1的結點為根的子樹，稱為最小不平衡子樹。如下圖所示，當插入結點37時，距離它最近的平衡因子的絕對值超過1的結點是58。

?

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

二、結點插入

1、插入原理

根據二叉平衡樹的定義，一定保持左右子樹深度絕對值小于1.在平衡二叉樹插入工作一定考慮深度差，在AVL樹進行插入工作時候，困難在于可能破壞AVL樹的平衡屬性。例如在下圖

?

上圖中插入一個節點6，那么如果不進行后續處理就會破壞樹的平衡性。因為8的左子樹深度為1，而右子樹深度為-1.

針對此類問題，需要根據樹的實際結構進行幾種簡單的旋轉（rotation）操作就可以讓樹恢復AVL樹的平衡性質

2.旋轉問題

對于一個平衡的節點，由于任意節點最多有兩個兒子，因此高度不平衡時，此節點的兩顆子樹的高度差2.容易看出，這種不平衡出現在下面四種情況：

1、6節點的左子樹3節點高度比右子樹7節點大2，左子樹3節點的左子樹1節點高度大于右子樹4節點，這種情況成為左左。

2、6節點的左子樹2節點高度比右子樹7節點大2，左子樹2節點的左子樹1節點高度小于右子樹4節點，這種情況成為左右。

3、2節點的左子樹1節點高度比右子樹5節點小2，右子樹5節點的左子樹3節點高度大于右子樹6節點，這種情況成為右左。

4、2節點的左子樹1節點高度比右子樹4節點小2，右子樹4節點的左子樹3節點高度小于右子樹6節點，這種情況成為右右。

從圖2中可以可以看出，1和4兩種情況是對稱的，這兩種情況的旋轉算法是一致的，只需要經過一次旋轉就可以達到目標，我們稱之為單旋轉。2和3兩種情況也是對稱的，這兩種情況的旋轉算法也是一致的，需要進行兩次旋轉，我們稱之為雙旋轉。

3、旋轉操作

單旋轉是針對于左左和右右這兩種情況的解決方案，這兩種情況是對稱的，只要解決了左左這種情況，右右就很好辦了。圖3是左左情況的解決方案，節點k2不滿足平衡特性，因為它的左子樹k1比右子樹Z深2層，而且k1子樹中，更深的一層的是k1的左子樹X子樹，所以屬于左左情況。

為使樹恢復平衡，我們把k2變成這棵樹的根節點，因為k2大于k1，把k2置于k1的右子樹上，而原本在k1右子樹的Y大于k1，小于k2，就把Y置于k2的左子樹上，這樣既滿足了二叉查找樹的性質，又滿足了平衡二叉樹的性質。

這樣的操作只需要一部分指針改變，結果我們得到另外一顆二叉查找樹，它是一棵AVL樹，因為X向上一移動了一層，Y還停留在原來的層面上，Z向下移動了一層。整棵樹的新高度和之前沒有在左子樹上插入的高度相同，插入操作使得X高度長高了。因此，由于這顆子樹高度沒有變化，所以通往根節點的路徑就不需要繼續旋轉了。

右旋轉代碼

void R_rotate(BiTree *t) {BiTree s;s = (*t)->lchild; //s指向t的左子樹根結點(*t)->lchild = s->rchild; //s的右子樹掛接為t的左子樹s->rchild = (*t);*t = s; //t指向新的根結點 }

右旋轉原理：獲取失去平衡結點以及左結點，為了讓lchild作為根節點，將lchild的rchild掛接到之前左結點上，然后在掛接到s->rchild.

左旋轉代碼

void L_rotate(BiTree *t) {BiTree s;s = (*t)->rchild; //s指向t的右子樹根結點(*t)->rchild = s->lchild; //s的左子樹掛接為t的右子樹s->lchild = (*t);*t = s; //t指向新的根結點 }

左旋轉原理正好相反，讓其右結點作為根節點

第六步：雙旋轉

對于左右和右左這兩種情況，單旋轉不能使它達到一個平衡狀態，要經過兩次旋轉。雙旋轉是針對于這兩種情況的解決方案，同樣的，這樣兩種情況也是對稱的，只要解決了左右這種情況，右左就很好辦了。圖4是左右情況的解決方案，節點k3不滿足平衡特性，因為它的左子樹k1比右子樹Z深2層，而且k1子樹中，更深的一層的是k1的右子樹k2子樹，所以屬于左右情況。

? 為使樹恢復平衡，我們需要進行兩步，第一步，把k1作為根，進行一次z左旋轉，旋轉之后就變成了左左情況，所以第二步再進行一次右旋轉，最后得到了一棵以k2為根的平衡二叉樹樹。

3、旋轉代碼分析

#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作右旋平衡處理 */} }

首先，定義三個常數變量，分別代碼1、0、-1。

??? （1）函數被調用，傳入一個需調整平衡型的子樹T，根節點為k3,由于LeftBalance函數被調用時，其實是已經確認當前子樹是不平衡的狀態，且左子樹的高度大于右子樹的高度。換句話說，此時T的根結點應該是平衡因子BF的值大于1的數。k3的BF為2

??? （2）將T的左孩子賦值給L。L指向K1.

??? （3）然后是分支判斷。

??? （4）當L（k1)的平衡因子為LH，即為1時，表明它與根結點的BF值符號相同，因此，將它們的BF值都改為0，并進行右旋（順時針）操作，是左左情況

??? （5）當L的平衡因子為RH時，即為-1時，表明它與根結點的BF值符號相反，此時需要做雙旋操作。針對L的右孩子k2的BF作判斷，修改結點T(k3)和L(k1)的BF值。將當前的Lr的BF改為0。從圖中看到K2的左結點是連接到K1的右子樹上，右結點連接到K3的左子樹

其中當k2結點為RH，說明K2有右結點有，左結點無，k3為0（(*T)->bf=EH; ），k1就沒有右結點為LH。當為Lh看程序。

??? （6）對根結點的左子樹進行左旋，以K1為根節點進行左旋轉，形成左左情況。

??? （7）對根結點K3進行右旋，完成平衡操作。

?

三、總體代碼

<strong>#include <stdio.h> #include <stdlib.h> #define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0 #define MAXSIZE 100 /* 存儲空間初始分配量 */typedef int Status; /* Status是函數的類型,其值是函數結果狀態代碼，如OK等 *//* 二叉樹的二叉鏈表結點結構定義 */ typedef struct BitNode /* 結點結構 */ {int data; /* 結點數據 */int bf; /* 結點的平衡因子 */struct BitNode *lchild, *rchild; /* 左右孩子指針 */ } BitNode, *BiTree;/* 對以p為根的二叉排序樹作右旋處理 */ /* 處理之后p指向新的樹根結點，即旋轉處理之前的左子樹的根結點 */ //右旋-順時針旋轉(如LL型就得對根結點做該旋轉) void R_Rotate(BiTree *P) { BiTree L;L=(*P)->lchild; /* L指向P的左子樹根結點 */(*P)->lchild=L->rchild; /* L的右子樹掛接為P的左子樹 */L->rchild=(*P);*P=L; /* P指向新的根結點 */ }/* 對以P為根的二叉排序樹作左旋處理， */ /* 處理之后P指向新的樹根結點，即旋轉處理之前的右子樹的根結點0 */ //左旋-逆時針旋轉(如RR型就得對根結點做該旋轉) void L_Rotate(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; }/* 若在平衡的二叉排序樹t中存在和e有相同關鍵字的結點，則刪除之 并返回TRUE，否則返回FALSE。若因刪除而使二叉排序樹 失去平衡，則作平衡旋轉處理，布爾變量shorter反映t變矮與否 */ int deleteAVL(BiTree *t, int key, int *shorter) {if(*t == NULL) //不存在該元素 {return FALSE; //刪除失敗 }else if(key == (*t)->data) //找到元素結點 {BitNode *q = NULL;if((*t)->lchild == NULL) //左子樹為空 {q = (*t);(*t) = (*t)->rchild;free(q);*shorter = TRUE;}else if((*t)->rchild == NULL) //右子樹為空 {q = (*t);(*t) = (*t)->lchild;free(q);*shorter = TRUE;}else //左右子樹都存在, {q = (*t)->lchild;while(q->rchild){q = q->rchild;}(*t)->data = q->data;deleteAVL(&(*t)->lchild, q->data, shorter); //在左子樹中遞歸刪除前驅結點 }}else if(key < (*t)->data) //左子樹中繼續查找 {if(!deleteAVL(&(*t)->lchild, key, shorter)){return FALSE;}if(*shorter){switch((*t)->bf){case LH:(*t)->bf = EH;*shorter = TRUE;break;case EH:(*t)->bf = RH;*shorter = FALSE;break;case RH:RightBalance(&(*t)); //右平衡處理if((*t)->rchild->bf == EH) //注意這里，畫圖思考一下 *shorter = FALSE;else*shorter = TRUE;break;}}}else //右子樹中繼續查找 {if(!deleteAVL(&(*t)->rchild, key, shorter)){return FALSE;}if(shorter){switch((*t)->bf){case LH:LeftBalance(&(*t)); //左平衡處理 if((*t)->lchild->bf == EH) //注意這里，畫圖思考一下 *shorter = FALSE;else*shorter = TRUE;break;case EH:(*t)->bf = LH;*shorter = FALSE;break;case RH:(*t)->bf = EH;*shorter = TRUE;break;}}}return TRUE; }void InOrderTraverse(BiTree t) {if(t){InOrderTraverse(t->lchild);printf("%d ", t->data);InOrderTraverse(t->rchild);} }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);}printf("中序遍歷二叉平衡樹:\n");InOrderTraverse(T);printf("\n");printf("刪除結點元素5后中序遍歷:\n");int shorter;deleteAVL(&T, 5, &shorter);InOrderTraverse(T);printf("\n");return 0; }

轉載于:https://www.cnblogs.com/polly333/p/4798944.html

總結

以上是生活随笔為你收集整理的浅谈数据结构-平衡二叉树的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。