參考視頻：
懶貓老師-數(shù)據(jù)結(jié)構(gòu)-(59)平衡二叉樹【互動(dòng)視頻】

前置概念

最小不平衡子樹：在平衡二叉樹的構(gòu)造過程中，以距離插入結(jié)點(diǎn)最近的、且平衡因子的絕對值大于1的結(jié)點(diǎn)為根的子樹。

例如上圖，此處4就是最小不平衡子樹的根節(jié)點(diǎn)。

一、構(gòu)造平衡二叉樹的基本思想

每插入一個(gè)結(jié)點(diǎn)，

• 從插入結(jié)點(diǎn)向上計(jì)算各結(jié)點(diǎn)的平衡因子，如果某結(jié)點(diǎn)的平衡因子的絕對值大于1，則說明插入操作破壞了二叉排序樹的平衡性，需要進(jìn)行平衡調(diào)整；否則繼續(xù)執(zhí)行插入操作。
• 如果二叉排序樹不平衡，則找出最小不平衡子樹的根節(jié)點(diǎn)，根據(jù)新插入結(jié)點(diǎn)與最小不平衡子樹根節(jié)點(diǎn)的關(guān)系判斷調(diào)整類型。
• 根據(jù)調(diào)整類型進(jìn)行相應(yīng)的調(diào)整，使之成為新的平衡子樹。

二、一個(gè)示例

三、平衡二叉樹的調(diào)整細(xì)節(jié)

設(shè)結(jié)點(diǎn)A為最小不平衡子樹的根結(jié)點(diǎn)，對該子樹平衡調(diào)整有以下四種情況：

1. LL型
2. RR型
3. LR型
4. RL型

（1）LL型（順時(shí)針 ）

插入結(jié)點(diǎn)X之后，這棵二叉樹不平衡了。B結(jié)點(diǎn)的平衡因子變成1（h+1-h），A結(jié)點(diǎn)的平衡因子變成2（h+2-h）。這里我們稱X結(jié)點(diǎn)為問題的發(fā)生者；A結(jié)點(diǎn)為問題的發(fā)現(xiàn)者。從問題的發(fā)現(xiàn)者A結(jié)點(diǎn)到問題的發(fā)生者要經(jīng)過左子樹的左子樹（即LL）。

現(xiàn)在A發(fā)現(xiàn)二叉樹不平衡了，就需要對二叉樹進(jìn)行調(diào)整。

旋轉(zhuǎn)：扁擔(dān)原理； 沖突：旋轉(zhuǎn)優(yōu)先

利用扁擔(dān)原理，A結(jié)點(diǎn)的左右子樹不平衡了：左子樹“重”，右子樹“輕”。那么我們把B結(jié)點(diǎn)往上抬，A結(jié)點(diǎn)往下壓（進(jìn)行了一個(gè)順時(shí)針旋轉(zhuǎn)），A結(jié)點(diǎn)變成了B結(jié)點(diǎn)的右子樹，B結(jié)點(diǎn)原來的右子樹調(diào)整為A結(jié)點(diǎn)的左子樹（B結(jié)點(diǎn)的右子樹上的所有結(jié)點(diǎn)一定小于A結(jié)點(diǎn)，所以將B原來的右子樹調(diào)整為A結(jié)點(diǎn)的左子樹是最合適的）。

舉例

（2）RR型（逆時(shí)針）

（3）LR型（先逆時(shí)針再順時(shí)針）

理解記憶：想象我們正在背一個(gè)扁擔(dān)，發(fā)現(xiàn)左邊重，但對于左邊來說，左邊的右邊又比較重，所以這個(gè)LR型調(diào)整成平衡二叉樹更為復(fù)雜。我們先需要對左邊好好調(diào)整一番，規(guī)整一下（逆時(shí)針旋轉(zhuǎn)），調(diào)整成LL型，讓所有重量完全徹底地壓到左邊。接著對得到的LL型一次性向右調(diào)整（順時(shí)針旋轉(zhuǎn)）。

舉例

（4）RL型（先順時(shí)針再逆時(shí)針）

（5）四種調(diào)整類型總結(jié)

四、例題

解題過程

• 找到最小不平衡子樹的根結(jié)點(diǎn)：5

• 判斷類型：從問題的發(fā)現(xiàn)者開始到問題的發(fā)生者，先左后右，畫圈的為RL型不平衡樹。注意：下面對畫圈的部分獨(dú)立操作。

• 將RL型的不平衡樹進(jìn)行順時(shí)針旋轉(zhuǎn)變成RR型
  

• 插入結(jié)點(diǎn)9，發(fā)現(xiàn)二叉樹又不平衡了，找到最小不平衡子樹的根結(jié)點(diǎn)：4

• 判斷類型：RR型不平衡樹
• 對RR型不平衡樹進(jìn)行逆時(shí)針旋轉(zhuǎn)