上一節介紹如何使用二叉排序樹實現動態查找表，本節介紹另外一種實現方式——平衡二叉樹。平衡二叉樹，又稱為?AVL 樹。實際上就是遵循以下兩個特點的二叉樹：

• 每棵子樹中的左子樹和右子樹的深度差不能超過 1；
• 二叉樹中每棵子樹都要求是平衡二叉樹；

其實就是在二叉樹的基礎上，若樹中每棵子樹都滿足其左子樹和右子樹的深度差都不超過 1，則這棵二叉樹就是平衡二叉樹。圖 1 平衡與不平衡的二叉樹及結點的平衡因子平衡因子：每個結點都有其各自的平衡因子，表示的就是其左子樹深度同右子樹深度的差。平衡二叉樹中各結點平衡因子的取值只可能是：0、1 和 -1。如圖 1 所示，其中 (a) 的兩棵二叉樹中由于各個結點的平衡因子數的絕對值都不超過 1，所以 (a) 中兩棵二叉樹都是平衡二叉樹；而 (b) 的兩棵二叉樹中有結點的平衡因子數的絕對值超過 1，所以都不是平衡二叉樹。

二叉排序樹轉化為平衡二叉樹

為了排除動態查找表中不同的數據排列方式對算法性能的影響，需要考慮在不會破壞二叉排序樹本身結構的前提下，將二叉排序樹轉化為平衡二叉樹。例如，使用上一節的算法在對查找表{13，24，37，90，53}構建二叉排序樹時，當插入 13 和 24 時，二叉排序樹此時還是平衡二叉樹：圖 2 平衡二叉樹當繼續插入 37 時，生成的二叉排序樹如圖 3(a)，平衡二叉樹的結構被破壞，此時只需要對二叉排序樹做“旋轉”操作(如圖 3(b))，即整棵樹以結點 24 為根結點，二叉排序樹的結構沒有破壞，同時將該樹轉化為了平衡二叉樹：圖 3 二叉排序樹變為平衡二叉樹的過程當二叉排序樹的平衡性被打破時，就如同扁擔的兩頭出現了一頭重一頭輕的現象，如圖3(a)所示，此時只需要改變扁擔的支撐點(樹的樹根)，就能使其重新歸為平衡。實際上圖 3 中的 (b) 是對(a) 的二叉樹做了一個向左逆時針旋轉的操作。繼續插入 90 和 53 后，二叉排序樹如圖 4(a)所示，導致二叉樹中結點 24 和 37 的平衡因子的絕對值大于 1 ，整棵樹的平衡被打破。此時，需要做兩步操作：

如圖 4(b) 所示，將結點 53 和 90 整體向右順時針旋轉，使本該以 90 為根結點的子樹改為以結點 53 為根結點；

如圖 4(c) 所示，將以結點 37 為根結點的子樹向左逆時針旋轉，使本該以 37 為根結點的子樹，改為以結點 53 為根結點；

圖 4 二叉排序樹轉化為平衡二叉樹做完以上操作，即完成了由不平衡的二叉排序樹轉變為平衡二叉樹。當平衡二叉樹由于新增數據元素導致整棵樹的平衡遭到破壞時，就需要根據實際情況做出適當的調整，假設距離插入結點最近的“不平衡因子”為 a。則調整的規律可歸納為以下 4 種情況：

• 單向右旋平衡處理：若由于結點 a 的左子樹為根結點的左子樹上插入結點，導致結點 a 的平衡因子由 1 增至 2，致使以 a 為根結點的子樹失去平衡，則只需進行一次向右的順時針旋轉，如下圖這種情況：圖 5 單向右旋
• 單向左旋平衡處理：如果由于結點 a 的右子樹為根結點的右子樹上插入結點，導致結點 a 的平衡因子由 -1變為 -2，則以 a 為根結點的子樹需要進行一次向左的逆時針旋轉，如下圖這種情況：圖 6 單向左旋
• ?雙向旋轉(先左后右)平衡處理：如果由于結點 a 的左子樹為根結點的右子樹上插入結點，導致結點 a 平衡因子由 1 增至 2，致使以 a 為根結點的子樹失去平衡，則需要進行兩次旋轉操作，如下圖這種情況：圖 7 雙向旋轉(先左后右)注意：圖 7 中插入結點也可以為結點 C 的右孩子，則(b)中插入結點的位置還是結點 C 右孩子，(c)中插入結點的位置為結點 A 的左孩子。
• 雙向旋轉(先右后左)平衡處理：如果由于結點 a 的右子樹為根結點的左子樹上插入結點，導致結點 a 平衡因子由 -1 變為 -2，致使以 a 為根結點的子樹失去平衡，則需要進行兩次旋轉(先右旋后左旋)操作，如下圖這種情況：圖 8 雙向旋轉(先右后左)注意：圖 8 中插入結點也可以為結點 C 的右孩子，則(b)中插入結點的位置改為結點 B 的左孩子，(c)中插入結點的位置為結點 B 的左孩子。

在對查找表{13，24，37，90，53}構建平衡二叉樹時，由于符合第 4 條的規律，所以進行先右旋后左旋的處理，最終由不平衡的二叉排序樹轉變為平衡二叉樹。

構建平衡二叉樹的代碼實現

#include #include //分別定義平衡因子數#define LH +1#define EH 0#define RH -1typedef int ElemType;typedef enum {false,true} bool;//定義二叉排序樹typedef struct BSTNode{ ElemType data; int bf;//balance flag struct BSTNode *lchild,*rchild;}*BSTree,BSTNode;//對以 p 為根結點的二叉樹做右旋處理，令 p 指針指向新的樹根結點void R_Rotate(BSTree* p){ //借助文章中的圖 5 所示加以理解，其中結點 A 為 p 指針指向的根結點 BSTree lc = (*p)->lchild; (*p)->lchild = lc->rchild; lc->rchild = *p; *p = lc;}對以 p 為根結點的二叉樹做左旋處理，令 p 指針指向新的樹根結點void L_Rotate(BSTree* p){ //借助文章中的圖 6 所示加以理解，其中結點 A 為 p 指針指向的根結點 BSTree rc = (*p)->rchild; (*p)->rchild = rc->lchild; rc->lchild = *p; *p = rc;}//對以指針 T 所指向結點為根結點的二叉樹作左子樹的平衡處理，令指針 T 指向新的根結點void LeftBalance(BSTree* T){ BSTree lc,rd; lc = (*T)->lchild; //查看以 T 的左子樹為根結點的子樹，失去平衡的原因，如果 bf 值為 1 ，則說明添加在左子樹為根結點的左子樹中，需要對其進行右旋處理；反之，如果 bf 值為 -1，說明添加在以左子樹為根結點的右子樹中，需要進行雙向先左旋后右旋的處理 switch (lc->bf) { case LH: (*T)->bf = lc->bf = EH; R_Rotate(T); break; case RH: rd = lc->rchild; switch(rd->bf) { case LH: (*T)->bf = RH; lc->bf = EH; break; case EH: (*T)->bf = lc->bf = EH; break; case RH: (*T)->bf = EH; lc->bf = LH; break; } rd->bf = EH; L_Rotate(&(*T)->lchild); R_Rotate(T); break; }}//右子樹的平衡處理同左子樹的平衡處理完全類似void RightBalance(BSTree* T){ BSTree lc,rd; lc= (*T)->rchild; switch (lc->bf) { case RH: (*T)->bf = lc->bf = EH; L_Rotate(T); break; case LH: rd = lc->lchild; switch(rd->bf) { case LH: (*T)->bf = EH; lc->bf = RH; break; case EH: (*T)->bf = lc->bf = EH; break; case RH: (*T)->bf = EH; lc->bf = LH; break; } rd->bf = EH; R_Rotate(&(*T)->rchild); L_Rotate(T); break; }}int InsertAVL(BSTree* T,ElemType e,bool* taller){ //如果本身為空樹，則直接添加 e 為根結點 if ((*T)==NULL) { (*T)=(BSTree)malloc(sizeof(BSTNode)); (*T)->bf = EH; (*T)->data = e; (*T)->lchild = NULL; (*T)->rchild = NULL; *taller=true; } //如果二叉排序樹中已經存在 e ，則不做任何處理 else if (e == (*T)->data) { *taller = false; return 0; } //如果 e 小于結點 T 的數據域，則插入到 T 的左子樹中 else if (e < (*T)->data) { //如果插入過程，不會影響樹本身的平衡，則直接結束 if(!InsertAVL(&(*T)->lchild,e,taller)) return 0; //判斷插入過程是否會導致整棵樹的深度 +1 if(*taller) { //判斷根結點 T 的平衡因子是多少，由于是在其左子樹添加新結點的過程中導致失去平衡，所以當 T 結點的平衡因子本身為 1 時，需要進行左子樹的平衡處理，否則更新樹中各結點的平衡因子數 switch ((*T)->bf) { case LH: LeftBalance(T); *taller = false; break; case EH: (*T)->bf = LH; *taller = true; break; case RH: (*T)->bf = EH; *taller = false; break; } } } //同樣，當 e>T->data 時，需要插入到以 T 為根結點的樹的右子樹中，同樣需要做和以上同樣的操作 else { if(!InsertAVL(&(*T)->rchild,e,taller)) return 0; if (*taller) { switch ((*T)->bf) { case LH: (*T)->bf = EH; *taller = false; break; case EH: (*T)->bf = RH; *taller = true; break; case RH: RightBalance(T); *taller = false; break; } } } return 1;}//判斷現有平衡二叉樹中是否已經具有數據域為 e 的結點bool FindNode(BSTree root,ElemType e,BSTree* pos){ BSTree pt = root; (*pos) = NULL; while(pt) { if (pt->data == e) { //找到節點，pos指向該節點并返回true (*pos) = pt; return true; } else if (pt->data>e) { pt = pt->lchild; } else pt = pt->rchild; } return false;}//中序遍歷平衡二叉樹void InorderTra(BSTree root){ if(root->lchild) InorderTra(root->lchild); printf("%d ",root->data); if(root->rchild) InorderTra(root->rchild);}int main(){ int i,nArr[] = {1,23,45,34,98,9,4,35,23}; BSTree root=NULL,pos; bool taller; //用 nArr查找表構建平衡二叉樹(不斷插入數據的過程) for (i=0;i<9;i++) { InsertAVL(&root,nArr[i],&taller); } //中序遍歷輸出 InorderTra(root); //判斷平衡二叉樹中是否含有數據域為 103 的數據 if(FindNode(root,103,&pos)) printf("\n%d\n",pos->data); else printf("\nNot find this Node\n"); return 0;}

運行結果

1 4 9 23 34 35 45 98
Not find this Node??

總結

使用平衡二叉樹進行查找操作的時間復雜度為?O(logn)。在學習本節內容時，緊貼本節圖示比較容易理解。

總結

以上是生活随笔為你收集整理的平衡二叉树及其操作实现_平衡二叉树（AVL树）及C语言实现的全部內容，希望文章能夠幫你解決所遇到的問題。

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