平衡二叉樹是一種二叉排序樹，其中每一個(gè)節(jié)點(diǎn)的左子樹和右子樹的高度至多等于1，平衡二叉樹又稱為AVL樹。

將二叉樹節(jié)點(diǎn)的左子樹深度減去右子樹深度的值稱為平衡因子BF，平衡二叉樹上所有節(jié)點(diǎn)的平衡因子只可能是-1,0或者1。

距離插入點(diǎn)最近的，且平衡因子的絕對值大于1的結(jié)點(diǎn)為根的子樹，我們稱為最小不平衡子樹。

平衡二叉樹實(shí)現(xiàn)原理

先來看一個(gè)例子：

對于數(shù)組a[10]={3,2,1,4,5,6,7,10,9,8}構(gòu)建平衡二叉樹。

按照二叉排序樹的方式插入新的元素，當(dāng)插入1的時(shí)候，使得當(dāng)前二叉樹失去平衡：

當(dāng)插入5的時(shí)候，使得平衡二叉樹再次失去平衡：

插入6的時(shí)候，同樣產(chǎn)生不平衡：

注意：上面的這些不平衡都有一個(gè)共同的特點(diǎn)，那就是最小不平衡子樹的根的BF同它的孩子（左孩子或者右孩子）的BF是同號的。所以這是僅需要一次旋轉(zhuǎn)就可以了。

當(dāng)插入到數(shù)字9的時(shí)候，同樣的發(fā)生了不平衡：

從上面的圖可以看到一次的旋轉(zhuǎn)是不能做到再次的平衡的。所以要兩次旋轉(zhuǎn)。

在插入8的時(shí)候，同樣的發(fā)生了不平衡，同樣的需要兩次調(diào)整：

所以總結(jié)上面的過程：

當(dāng)最小不平衡子樹根節(jié)點(diǎn)的平衡因子BF是大于1的時(shí)候，就右旋，小于-1時(shí)就左旋。

插入節(jié)點(diǎn)后，最小不平衡子樹的BF與它的子樹的BF符號相反時(shí)，就需要對子樹節(jié)點(diǎn)先進(jìn)行一次旋轉(zhuǎn)，以使得符號相同后，在反向旋轉(zhuǎn)一次才能夠完成平衡操作。

平衡二叉樹算法實(shí)現(xiàn)

加入了平衡因子，所以在每一個(gè)結(jié)點(diǎn)中增加一個(gè)數(shù)據(jù)域，這個(gè)數(shù)據(jù)域表示以這個(gè)結(jié)點(diǎn)為根的二叉樹的平衡因子。所以樹結(jié)點(diǎn)的定義為：

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

其實(shí)對于二叉平衡樹的每一次的調(diào)整都可以分成兩個(gè)步驟：

• 調(diào)整各個(gè)結(jié)點(diǎn)的BF值
• 旋轉(zhuǎn)子樹結(jié)構(gòu)

先寫旋轉(zhuǎn)子樹結(jié)構(gòu)代碼：

void R_Rotate(BiTree *T) {BiTree tmp;tmp = (*T)->lchild;(*T)->lchild = tmp->rchild;tmp->rchild = (*T);*T = tmp; }void L_Rotate(BiTree *T) {BiTree tmp;tmp = (*T)->rchild;(*T)->rchild = tmp->lchild;tmp->lchild = (*T);*T = tmp; }

所以當(dāng)插入一個(gè)新的結(jié)點(diǎn)，導(dǎo)致樹結(jié)構(gòu)不平衡的時(shí)候，當(dāng)樹右邊超重的時(shí)候，要右平衡：（樹主體左旋轉(zhuǎn)）

//右平衡，右子樹超重 void RightBalance(BiTree *T) {BiTree tmp, tmpr;tmp = (*T)->rchild;switch (tmp->bf){case -1:(*T)->bf = 0;tmp->bf = 0;L_Rotate(T);break;case 1:tmpr = tmp->lchild;switch (tmpr->bf){case 1:tmp->bf = -1;(*T)->bf = 0;break;case -1:tmp->bf = 0;(*T)->bf = 1;break;case 0:tmp->bf = (*T)->bf = 0;}tmpr->bf = 0;//R_Rotate(&tmp);是錯(cuò)誤的，因?yàn)椴荒苄薷纳弦患壍闹羔楻_Rotate(&(*T)->rchild);L_Rotate(T);} }

當(dāng)插入一個(gè)結(jié)點(diǎn)導(dǎo)致樹結(jié)構(gòu)不平衡的時(shí)候，左子樹超重，要左平衡：（樹主體右旋轉(zhuǎn)）

//左平衡，左子樹超重 void LeftBlance(BiTree *T) {BiTree tmp,tmpr;tmp = (*T)->lchild;switch (tmp->bf){case 1:(*T)->bf = 0;tmp->bf = 0;R_Rotate(T);break;case -1:tmpr = tmp->rchild;switch (tmpr->bf){case 1:tmp->bf = 0;(*T)->bf = -1;break;case -1:tmp->bf = 1;(*T)->bf = 0;break;case 0:(*T)->bf = 0;tmp->bf = 0;break;}//switchtmpr->bf = 0;//L_Rotate(&tmp);是錯(cuò)誤的，因?yàn)椴荒苄薷纳弦患壍闹羔楲_Rotate(&(*T)->lchild);R_Rotate(T);} }

注意：上面兩處的雙旋轉(zhuǎn)的時(shí)候，不能旋轉(zhuǎn)tmp，因?yàn)檫@樣不能把父結(jié)點(diǎn)的指針修改，所以要旋轉(zhuǎn)父結(jié)點(diǎn)指下來得指針。

?最后插入操作的主函數(shù)：

bool InsertAVL(BiTree *T, int key, bool *taller) {if (*T ==NULL){*T = (BiTree)malloc(sizeof(BiTNode));(*T)->data = key;(*T)->lchild = (*T)->rchild = NULL;(*T)->bf = 0;*taller = true;return true;}if((*T)->data == key){*taller = false;return false;}else if((*T)->data > key){if(!InsertAVL(&(*T)->lchild, key, taller))return false;if(*taller){switch ((*T)->bf){case 1:LeftBlance(T);*taller = false;break;case 0:(*T)->bf = 1;*taller = true;break;case -1:(*T)->bf = 0;*taller = false;break;}//switch}//if}//else ifelse //(*T)->data < key{if (!InsertAVL(&(*T)->rchild, key, taller))return false;if(*taller){switch ((*T)->bf){case 1:(*T)->bf = 0;*taller = false;break;case 0:(*T)->bf = -1;*taller = true;break;case -1:RightBalance(T);*taller = false;}//switch}//if}//elsereturn true; }

　　

　　

轉(zhuǎn)載于:https://www.cnblogs.com/stemon/p/4839019.html

總結(jié)

以上是生活随笔為你收集整理的[树结构]平衡二叉树AVL的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。