c语言求平衡因子,平衡二叉树（AVL树）的基本操作
0x00、平衡二叉樹的定義
平衡二叉樹(AVL樹)是一種特殊的二叉搜索樹，只是在二叉搜索樹上增加了對"平衡"的需求。
假如一棵二叉搜索樹，按照“1,2,3,4,5”的順序插入數(shù)據(jù)，會發(fā)現(xiàn)二叉樹甚至變成了一個線性的鏈表狀結(jié)構(gòu)，這樣查找數(shù)據(jù)的時間復(fù)雜度就會達到O(n)，為了優(yōu)化這一點，使二叉查找樹時間復(fù)雜度保持O(log n)的級別，我們就需要調(diào)整樹的插入方式，使之保持住樹的結(jié)構(gòu)。
這里引入一個定義：
平衡因子：二叉樹的某個節(jié)點的左子樹與右子樹高度之差稱為結(jié)點的平衡因子。
而平衡二叉樹就是要保證平衡因子絕對值不能超過1。也就是左子樹高度比右子樹高度最多大1。
0x01、平衡二叉樹的C語言實現(xiàn)
首先定義平衡二叉樹，這和定義二叉搜索樹有些不同，定義的結(jié)構(gòu)體必須加上當前子樹的高度。也就是這樣：
struct?node{
int?data;????//數(shù)據(jù)域
int?height;??//當前子樹高度
node*?lchild,?*rchild;????????//左右孩子
};
這樣定義的好處是方便上一節(jié)點計算平衡因子。
計算平衡因子之前我們先定義計算高度的函數(shù)，直接返回root->height即可。如果root為NULL，說明是葉子節(jié)點，返回0即可
int?getHeight(node*?root){
return?root?==?NULL???0?:?root->height;
}
接著我們計算平衡因子，即左子樹比右子樹高了多少：
int?getBalanceFactor(node*?root){
return?getHeight(root->lchild)?-?getHeight(root->rchild);
}
當我們執(zhí)行了插入操作，二叉樹發(fā)生改變的時候，我們需要重新計算高度。
某節(jié)點的高度值等于左右子樹高度值最大的，加上1。(這是高度值的定義)
更新高度值：
void?updateHeight(node*?root){
root->height?=?max(getHeight(root->lchild),?getHeight(root->rchild))?+?1;
}
0x02、平衡二叉樹的查找
AVL樹的查找與一般二叉搜索樹的查找方法一樣。代碼如下：
void?search(node*?root,?int?data){
if(!root)?return;????//查找失敗
if(root->data?==?data)//找到了
printf("%d",?root->data);
if(root->data?>?data)?//大了，訪問左節(jié)點
search(root->lchild,?data);
else?search(root->rchild,?data);
}
0x03、平衡二叉樹的插入操作
平衡二叉樹的插入操作較為復(fù)雜，我們?yōu)榱吮３侄鏄涞钠胶鉅顟B(tài)，就要在二叉樹失衡的時候?qū)Χ鏄溥M行旋轉(zhuǎn)。
常見的旋轉(zhuǎn)方式有LL型(單次右旋)、RR型(單次左旋)、LR型(先左旋，再右旋)、RL型(先右旋，再左旋)
下面我們進行詳細介紹：
1、LL型(單次右旋)
假設(shè)一棵平衡二叉樹再插入數(shù)據(jù)后，成了這個樣子：
圖中的 4 和 12 的高度分別是 3 和 1 ，高度差為 2 ，此時，二叉樹不平衡了。對于這種由根節(jié)點的左子樹的左子樹造成平衡因子為2的失衡，我們要使用LL型旋轉(zhuǎn)，即單次右旋，使其平衡。
正確的旋轉(zhuǎn)方式是：使原二叉樹的 根節(jié)點(K2) 的 左孩子(k1) 做為 新根節(jié)點，新根節(jié)點(k1) 原來的 右子樹(Y) ，做為 原來的根節(jié)點(K2) 的左子樹
如果記不住的話可以按照這個思路來記憶：
既然左邊高度比右邊高，就讓左子樹的根節(jié)點稱為新根，這樣高度就減小了1，我們把左子樹K1"揪起來"，讓原根節(jié)點k2"掉下去"，這樣K1就多了一個孩子，而X小于K1，K2大于K1，Y大于K1且Y小于K2，這樣把Y"拽下來"插到K2的左邊，仍然符合二叉搜索樹的規(guī)則，而且還處理好了K1的關(guān)系，多么完美！
轉(zhuǎn)轉(zhuǎn)后，K1和K2(新根與原來的根)的高度發(fā)生了變化，而XYZ(三個子樹)沒有發(fā)生變化，所以我們只需要更新K1和K2的高度值即可。
用C語言實現(xiàn)，就是：
void?LLrotation(node*?&root){
node*?temp?=?root->lchild;????//讓temp=K1
root->lchild?=?temp->rchild;????//讓root的左節(jié)點變?yōu)閅
temp->rchild?=?root;????//讓新根K1的右節(jié)點指向K2
//以上，旋轉(zhuǎn)完畢
updateHeight(temp);????//更新新根的節(jié)點高度
updateHeight(root);????//更新老根的節(jié)點高度
root?=?temp;????//把樹的根換成我們定義的新根
}
2、RR型(單次左旋)
假設(shè)一棵二叉樹插入數(shù)據(jù)后的狀態(tài)：
很顯然，失衡了。平衡因子為-2。對于這種根節(jié)點的右子樹的右子樹造成平衡因子為-2的失衡，我們采用RR旋轉(zhuǎn)，即單次左旋。
單次左旋的思路就是單次右旋倒過來想，我們先將原根節(jié)點的右節(jié)點K2當做新根，將K2的左子樹當做原根K1的右子樹。
同樣的，只有K1和K2的高度發(fā)生了變化，所以我們只需要更新K1和K2的高度即可。
C語言實現(xiàn)：
void?RRrotation(node*?&root){
node*?temp?=?root->rchild;????//另temp=K2
root->rchild?=?temp->lchild;????//舊根的右節(jié)點為新根的左節(jié)點
temp->lchild?=?root;????//新根的右節(jié)點等于舊根
//以上，旋轉(zhuǎn)完畢
updateHeight(temp);????//更新節(jié)點高度
updateHeight(root);
root?=?temp;????//重賦值
}
3、LR型(先單次左旋，后單次右旋)
一棵二叉樹，插入數(shù)據(jù)后形成了這個鬼樣子
4的高度為3； 而12的高度為1，平衡因子即高度差為2，這是由于根節(jié)點的左子樹的右子樹造成了平衡因子為2的失衡，通常采用LR型旋轉(zhuǎn)，即先左旋，后右旋。
先左旋，也就是讓K3的左孩子單次左旋，以K1為根節(jié)點，進行單次左旋，使得K2成為根節(jié)點，K1成為K2的左節(jié)點，K2原來的左節(jié)點B成為K1的右節(jié)點。這樣就完成了單次左旋
接著對左旋后的二叉樹，以K3為根節(jié)點，進行單次右旋，讓K3的左節(jié)點K2成為新根，K2的右孩子C成為K3的左孩子，讓K3做K2的右孩子。
這里K1、K2、K3的高度均發(fā)生了變化，ABCD的高度沒有發(fā)生變化。
說起來很麻煩，其實實現(xiàn)起來很簡單。因為我們有了前面LL旋轉(zhuǎn)和RR旋轉(zhuǎn)的基礎(chǔ)，直接對子樹操作即可。
C語言實現(xiàn)：
void?LRrotation(node*?&root){
RRrotation(root->lchild);????//先對根節(jié)點的左孩子單次左旋
LLrotation(root);
}
4、RL型(先單次右旋，后單次左旋)
二叉樹數(shù)據(jù)插入后：
此時的狀態(tài)是：由于根節(jié)點的右節(jié)點的左子樹造成了平衡因子為-2的失衡，我們通常采用RL型旋轉(zhuǎn)，即先單次右旋，后單次左旋。
其實就是把LR倒過來啦，不做詳細解釋了。(敲鍵盤敲的手指好痛，嗚嗚嗚~~~~(>_
C語言實現(xiàn)：
void?RLrotation(node*?&root){
LLrotation(root->rchild);????//先對根節(jié)點的左孩子單次左旋
RRrotation(root);
}
寫了這么多，總結(jié)一下吧。根據(jù)這個表格進行判斷AVL樹以何種旋轉(zhuǎn)類型保持平衡：
樹型
判定條件
調(diào)整方法
LL(單次右旋)
BF(root) = 2；BF(root->lchild) = 1
對root單次右旋
RR(單次左旋)
BF(root) =-2；BF(root->rchild) =-1
對root單次左旋
LR(先左后右)
BF(root) = 2；BF(root->lchild) =-1
對root->lchild進行左旋，再對root進行右旋
RL(先右后左)
BF(root) =-2；BF(root->rchild) = 1
對root->rchild進行右旋，再對root進行左旋
*BF代表平衡因子
0x04、二叉平衡樹的插入
還記得二叉搜索樹是怎樣插入數(shù)據(jù)的嗎？
void?insert(node*?&root,?int?data){
if(root?==?NULL){
root?=?new?node;
root->data?=?data;
root->lchild?=?root->rchild?=?NULL;
}
if(root->data?<=?data)
insert(root->rchild,?data);
else?insert(root->lchild,?data);
}
這段代碼是不考慮平衡關(guān)系的插入代碼。我們要做的是在這串代碼上稍加修改，使之能及時通過旋轉(zhuǎn)，保證平衡關(guān)系。
我們的思路是：沿用上面代碼進行插入，插入后更新樹的高度，接著判斷平衡因子，根據(jù)平衡因子判斷四種類型的旋轉(zhuǎn)，最后執(zhí)行旋轉(zhuǎn)。
C語言實現(xiàn)：
void?insert(node*?&root,?int?data){
if(root?==?NULL){????//插入位置
root?=?new?node;
root->data?=?data;
root->lchild?=?root->rchild?=?NULL;
root->height?=?1;????//由于插入的時候是葉子節(jié)點，所以初始高度為1
return;
}
if(root->data?>?data){????//節(jié)點數(shù)據(jù)大，往左插入
insert(root->lchild,?data);????//繼續(xù)遞歸尋找插入位置
updataHeight(root);????????//因為插入了一個節(jié)點，所以樹根的高度會發(fā)生變化
if(getBalanceFactor(root)?==?2)????//根節(jié)點平衡因子為2
if(getBalanceFactor(root->lchild)?==?1)?//根節(jié)點左孩子平衡因子為1，根據(jù)表格，采用LL型
LLrotation(root);
else?if(getBalanceFactor(root->lchild)?==?-1)???//根節(jié)點左孩子平衡因子為-1，LR型
LRrotation(root);
}
else{????//節(jié)點數(shù)據(jù)小，往右插入
insert(root->rchild,?data);
updataHeight(root);
if(getBalanceFactor(root)?==?-2){
if(getBalanceFactor(root->rchild)?==?-1)?//RR型
RRrotation(root)
else?if(getBalanceFactor(root->rchild)?==?1)//RL型
RLrotation(root);
}
}
}
這里往左插入后，只需要判斷平衡因子是否為2，是因為如果樹之前是平衡的，往左插入的時候，不可能造成平衡因子為-2，只有往右插入的時候才會是-2，所以判斷平衡因子 是否為-2就多余了。
總結(jié)
以上是生活随笔為你收集整理的c语言求平衡因子,平衡二叉树（AVL树）的基本操作的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 世卫称疫情有望在2022年结束 张文宏
- 下一篇： 美汽车机构：希望尽快结束特斯拉安全性调查