平衡二叉樹

平衡二叉樹就是對二叉查找樹的優(yōu)化升級秘车，它要求每個(gè)節(jié)點(diǎn)的左右子樹的高度相差不大于1

1.平衡二叉樹的查找

平衡二叉樹和二叉排序樹的查找是一摸一樣的。

2.平衡二叉樹的順序輸出

平衡二叉樹的中序遍歷和二叉排序樹一樣桅锄，都是可以輸出一個(gè)有序的數(shù)列琉雳。

3.平衡二叉樹的插入

平衡二叉樹在插入數(shù)據(jù)時(shí)，當(dāng)發(fā)生了高度的不平衡時(shí)友瘤，會采取4種旋轉(zhuǎn)操作：LL,RR,LR,RL（左左翠肘，右右，左右辫秧，右左）旋轉(zhuǎn)束倍，我們來一一分析這4種旋轉(zhuǎn)方式。

RR調(diào)整

針對右孩子的右子樹引起的不平衡

tree12.jpg

調(diào)整策略

• 右孩子c左上旋轉(zhuǎn)作為根節(jié)點(diǎn)
• 根節(jié)點(diǎn)a左下旋轉(zhuǎn)作為c的左子樹
• c的左子樹作為a的右子樹

tree8.jpg

LL調(diào)整

針對左孩子的左子樹引起的不平衡

tree13.jpg

調(diào)整策略

• 左孩子b右上旋轉(zhuǎn)作為根節(jié)點(diǎn)
• 根節(jié)點(diǎn)a右下旋轉(zhuǎn)作為b的右子樹
• b的右子樹作為a的左子樹

tree9.jpg

LR調(diào)整

針對左孩子的右子樹引起的不平衡

tree14.jpg

調(diào)整策略

• 根節(jié)點(diǎn)的左孩子進(jìn)行一次RR調(diào)整
• 根節(jié)點(diǎn)進(jìn)行一次LL調(diào)整

tree10.jpg

RL調(diào)整

針對右孩子的左子樹引起的不平衡

tree15.jpg

• 根節(jié)點(diǎn)的右孩子進(jìn)行一次LL調(diào)整
• 根節(jié)點(diǎn)進(jìn)行一次RR調(diào)整

tree11.jpg

平衡調(diào)整的總結(jié)

現(xiàn)在我們將平衡二叉樹的調(diào)整歸納成一種簡單且好理解的記憶方式

• LL失衡，我們稱之為LL調(diào)整绪妹，策略是對產(chǎn)生失衡的節(jié)點(diǎn)進(jìn)行兩次右右旋轉(zhuǎn)甥桂，第一次是對失衡節(jié)點(diǎn)的左孩子進(jìn)行右上旋轉(zhuǎn)，第二次是對失衡節(jié)點(diǎn)進(jìn)行右下旋轉(zhuǎn)邮旷。
• RR失衡格嘁，我們稱之為RR調(diào)整，策略是對產(chǎn)生失衡的節(jié)點(diǎn)進(jìn)行兩次左左旋轉(zhuǎn)廊移，第一次是對失衡節(jié)點(diǎn)的右孩子進(jìn)行左上旋轉(zhuǎn)糕簿，第二次是對失衡節(jié)點(diǎn)進(jìn)行左下旋轉(zhuǎn)。
• LR失衡狡孔，我們稱之為LR調(diào)整懂诗，策略是對產(chǎn)生失衡的節(jié)點(diǎn)進(jìn)行左右旋轉(zhuǎn)，第一次是對失衡節(jié)點(diǎn)的左孩子進(jìn)行LL調(diào)整苗膝，第二次是對失衡節(jié)點(diǎn)進(jìn)行RR調(diào)整殃恒。
• RL失衡，我們稱之為RL調(diào)整辱揭，策略是對產(chǎn)生失衡的節(jié)點(diǎn)進(jìn)行右左旋轉(zhuǎn)离唐，第一次是對失衡節(jié)點(diǎn)的右孩子進(jìn)行RR調(diào)整，第二次是對失衡節(jié)點(diǎn)進(jìn)行LL調(diào)整问窃。

注意點(diǎn)亥鬓，LL失衡和RR失衡直接兩次旋轉(zhuǎn)，而LR失衡和RL失衡域庇，是分別進(jìn)行兩次LL和RR的組合調(diào)整嵌戈。

實(shí)戰(zhàn)演練

現(xiàn)在我們有一關(guān)鍵字序列16,3,7,11,9,26,18,14,15，我們來逐個(gè)插入構(gòu)建一棵平衡二叉樹听皿。

1. 插入數(shù)字16熟呛，直接插入

tree31.jpg

2.插入數(shù)字3，插入后不失衡尉姨，所以不調(diào)整庵朝。

tree32.jpg

3.插入數(shù)字7，插入后如左圖又厉，發(fā)現(xiàn)失衡九府，失衡點(diǎn)是16，此時(shí)的失衡是LR失衡馋没，根據(jù)總結(jié)規(guī)律昔逗，先對失衡點(diǎn)的左孩子進(jìn)行RR調(diào)整降传，然后再對失衡點(diǎn)進(jìn)行一次LL調(diào)整篷朵。

tree33.jpg

4.插入數(shù)字11，插入后，不失衡声旺。

tree34.jpg

5.插入數(shù)字9笔链，插入后如左圖，發(fā)現(xiàn)失衡腮猖，此時(shí)失衡節(jié)點(diǎn)有兩個(gè)節(jié)點(diǎn)16和節(jié)點(diǎn)7鉴扫，因?yàn)榇a設(shè)計(jì)是遞歸的判斷失衡，所以從從下往上的調(diào)整澈缺，所以對失衡點(diǎn)16調(diào)整坪创，此時(shí)16的失衡是LL失衡，先對失衡點(diǎn)16右孩子進(jìn)行一次LL調(diào)整姐赡，發(fā)現(xiàn)竟然平衡了莱预。所以不用繼續(xù)調(diào)整了。

tree35.jpg

6.插入數(shù)字26项滑，插入后依沮，節(jié)點(diǎn)7發(fā)生了失衡，失衡是RR失衡枪狂。所以進(jìn)行RR調(diào)整危喉。

tree36.jpg

7.插入數(shù)字18，此時(shí)節(jié)點(diǎn)16出現(xiàn)了RL失衡州疾，所以進(jìn)行RL的調(diào)整策略辜限。

tree37.jpg

8.插入數(shù)字14，此時(shí)二叉樹平衡严蓖。

tree38.jpg

9.插入數(shù)字15列粪，此時(shí)節(jié)點(diǎn)16發(fā)生了LR失衡，進(jìn)行LR調(diào)整谈飒。

tree39.jpg

好了岂座，上面就是一個(gè)完整的插入過程，可能你會注意到一個(gè)特殊情況杭措，就是再插入一個(gè)節(jié)點(diǎn)時(shí)费什，平衡二叉樹失衡點(diǎn)會不只一個(gè)，這個(gè)時(shí)候選擇哪個(gè)進(jìn)行調(diào)整手素？結(jié)合代碼的思路分析鸳址，因?yàn)槎鏄涫沁f歸創(chuàng)建的，它是由根節(jié)點(diǎn)往葉子節(jié)點(diǎn)向下遞歸創(chuàng)建的泉懦，所以檢測平衡只能是逆向的稿黍，由靠近葉子的向根節(jié)點(diǎn)逐層調(diào)整，當(dāng)發(fā)現(xiàn)平衡時(shí)崩哩，就不用調(diào)整了巡球。

4.平衡二叉樹的刪除

平衡二叉樹的刪除操作分為三大部分言沐，第一大部分是先找打這個(gè)節(jié)點(diǎn)，第二大部分是按照二叉排序樹的刪除規(guī)則進(jìn)行刪除(可看前面二叉排序樹),第三大部分是從該刪除點(diǎn)一直上溯到根節(jié)點(diǎn)逐個(gè)的判斷是否失衡酣栈，根據(jù)失衡條件進(jìn)行調(diào)整平衡二叉樹险胰。下面是步驟

• 按照二叉排序樹的查找規(guī)則，去找待刪除的節(jié)點(diǎn)矿筝，沒找到直接退出起便。
• 根據(jù)二叉排序樹總結(jié)刪除規(guī)則的三條，去選擇對應(yīng)的刪除步驟進(jìn)行刪除操作窖维。
• 從刪除該節(jié)點(diǎn)的位置開始榆综，一直上溯到根節(jié)點(diǎn)，判斷是否失衡铸史，如果失衡根據(jù)對應(yīng)失衡奖年，進(jìn)行相應(yīng)的調(diào)整處理。

刪除演示

1.刪除26沛贪，如下圖所示陋守，元素26無左右孩子，直接刪除利赋，從此處開始水评，上溯到根判斷是否失衡，發(fā)現(xiàn)18節(jié)點(diǎn)失衡媚送，是LL失衡中燥，進(jìn)行LL調(diào)整，后面到根都平衡塘偎，不用調(diào)整疗涉。

tree45.jpg

2.刪除15，如下圖所示吟秩，按照規(guī)則咱扣，15左右孩子都有，所以可以先向左走一步涵防，再一直向右走闹伪，直到此節(jié)點(diǎn)無右孩子，來到了14壮池，將14放在待刪除的15位置上偏瓤，如下圖中間，此時(shí)從該點(diǎn)開始回溯到根進(jìn)行調(diào)整椰憋，發(fā)現(xiàn)14失衡厅克，和RL失衡，進(jìn)行RL調(diào)整策略橙依。此時(shí)發(fā)現(xiàn)調(diào)整完畢結(jié)束证舟。

tree46.jpg

3.刪除18硕旗，如下圖所示，18只有一個(gè)左孩子16褪储，按照刪除規(guī)則卵渴，將該左孩子直接放在待刪除的18位置上慧域。此時(shí)整個(gè)二叉樹上溯到根節(jié)點(diǎn)都是平衡的鲤竹，不用調(diào)整，結(jié)束昔榴。

tree47.jpg

刪除操作也講述完畢辛藻，好累。大家多看看步驟互订，根據(jù)步驟去畫畫圖就可以很好的理解了吱肌。