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

前置概念

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

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

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

每插入一個結(jié)點，

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

二、一個示例

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

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

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

（1）LL型（順時針 ）

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

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

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

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

舉例

（2）RR型（逆時針）

（3）LR型（先逆時針再順時針）

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

舉例

（4）RL型（先順時針再逆時針）

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

四、例題

解題過程

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

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

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

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

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