AVL樹

為什么要學(xué)習(xí)AVL樹：

為什么要學(xué)習(xí)AVL樹，因?yàn)槲覀儾迦胍活w呈直線的樹。

因?yàn)檫@棵樹是線性結(jié)構(gòu)的，所以這棵樹的時(shí)間復(fù)雜度為 O(m)，而一顆平衡二叉樹的時(shí)間復(fù)雜度為 O(log(m))，則一顆不平衡的樹的時(shí)間復(fù)雜度在兩者之間。

AVL樹是什么：

AVL樹是一種自平衡二叉搜索樹，在AVL樹中每個(gè)節(jié)點(diǎn)中存有一個(gè)量為平衡因子。

平衡因子的定義與計(jì)算方法：

平衡因子的值(定義) 就是左子樹的高度的值減去右子樹的高度的值，舉個(gè)例子。

因?yàn)闃涞淖笞訕涞母叨葹槿?，右子樹為二，所以平衡因子的值?3-2 = 1。

同理，如果把當(dāng)前這棵樹的左子樹 (也就是左邊黃色框內(nèi)的部分) 看成新的樹 (更新前面的值) 再進(jìn)行操作，因?yàn)楫?dāng)前這棵樹的左子樹的高度為二 (更新前面的值) ，則右子樹的高度為一，則平衡因子的值為 2-1 = 1。那繼續(xù)我們就可以得到所有結(jié)點(diǎn)的平衡因子 (友情提示：沒(méi)看懂的話請(qǐng)?jiān)倏匆槐閯偛盼覍懙脑?。

因?yàn)锳VL樹規(guī)定每個(gè)節(jié)點(diǎn)的平衡因子的絕對(duì)值不大于一，也就是每個(gè)結(jié)點(diǎn)的左右子樹高度差不大于一，所以二叉搜索樹才可以保持高度的平衡，哪么同理如果結(jié)點(diǎn)的平衡因子的絕對(duì)值大于一，就說(shuō)明該節(jié)點(diǎn)得子樹不平衡。

AVL樹的插入操作：

比如說(shuō)我們要將0插入到這個(gè)AVL樹中。

首先，我們按照常規(guī)二叉搜索樹的插入操作，也就是不斷比較直到葉子節(jié)點(diǎn)為止

注意，這個(gè)比較的路徑需要記錄，因?yàn)楹罄m(xù)調(diào)整需要沿著路經(jīng)從下往上進(jìn)行。

當(dāng)插入一個(gè)元素時(shí)，可能會(huì)打破AVL樹的平衡，所以我們要沿著路徑依次檢查結(jié)點(diǎn)的平衡因子，如果該平衡因子的絕對(duì)值不大于1，則不需要操作。

看到這時(shí)檢測(cè)到4結(jié)點(diǎn)平衡因子為2，平衡被打破，那么4結(jié)點(diǎn)就要執(zhí)行調(diào)整方法，按照插入元素的落點(diǎn)分為4種情況。

• 右旋：就是提拔B結(jié)點(diǎn)B連A，A連2子樹，其他不變
• 左旋：提拔C結(jié)點(diǎn)，C連A，A連3子樹，其他不變。

插入元素落入以上4個(gè)子樹的情況分別對(duì)應(yīng)著4種情況。

LL型狀態(tài)：

當(dāng)插入元素落在1號(hào)子樹上為L(zhǎng)L型，也就是右旋操作。

• 右旋：就是提拔B結(jié)點(diǎn)B連A，A連2子樹，其他不變。

這樣就平衡了兩邊的高度差，當(dāng)然還有RR型（左旋）操作。

RR型狀態(tài)：

• 左旋：提拔C結(jié)點(diǎn)，C連A，A連3子樹，其他不變。

這樣就平衡了兩邊的高度差，當(dāng)然左旋和右旋時(shí)最基本的調(diào)整方式。如果要學(xué)習(xí)更深的東西就要學(xué)習(xí)雙旋。

左旋&右旋：

那么接下來(lái)我們就要學(xué)習(xí)雙旋了，先舉個(gè)例子：

我們回到之前的例子中，我們檢測(cè)到4號(hào)結(jié)點(diǎn)不平衡，所以要進(jìn)行調(diào)整。

將4號(hào)結(jié)點(diǎn)和其子樹放入之前的模板里比較。

0號(hào)結(jié)點(diǎn)又在模板對(duì)應(yīng)的1號(hào)子樹中，而0號(hào)結(jié)點(diǎn)又在模板對(duì)應(yīng)的1號(hào)子樹中，所以對(duì)4號(hào)結(jié)點(diǎn)進(jìn)行的是右旋操作。

我們回到檢查路徑中，最后檢查到根節(jié)點(diǎn)，結(jié)點(diǎn)平衡，操作完成。

因?yàn)闃涞膶訑?shù)比較少，所以路徑上只有一個(gè)結(jié)點(diǎn)不平衡，那么如果路徑中出現(xiàn)了多個(gè)不平衡的點(diǎn)，只要進(jìn)行多次調(diào)整方法即可。

雙旋操作：

當(dāng)插入元素在2號(hào)子樹中，這種情況被稱為LR型狀態(tài)。

LR型狀態(tài)：

這種情況稍微復(fù)雜一點(diǎn)，如圖所示，其節(jié)點(diǎn)為D，其左右子樹標(biāo)為5和6。

插入操作還是同樣的處理，因?yàn)?strong>處理后5和6號(hào)子樹都會(huì)向上移動(dòng)，這時(shí)我們對(duì)根節(jié)點(diǎn)A使用雙旋操作來(lái)調(diào)整

• LR雙旋：提拔D結(jié)點(diǎn)D鏈接A、B，A連6子樹，B連5子樹。

這時(shí)樹就可以恢復(fù)平衡，再仔細(xì)觀察這個(gè)結(jié)果，可以發(fā)現(xiàn)這個(gè)操作等效于先對(duì)B結(jié)點(diǎn)作左旋操作

• LR雙旋：先左旋B結(jié)點(diǎn)，在右旋A結(jié)點(diǎn)。

結(jié)果如下：

RL型狀態(tài)：

既然有LR就有RL嗎，同樣拆開3號(hào)子樹。

• RL雙旋：提拔D結(jié)點(diǎn)，D連A、C，A連5子樹，C連6子樹。

這個(gè)操作等效于先對(duì)C結(jié)點(diǎn)作右旋操作，在對(duì)A結(jié)點(diǎn)作左旋操作。

• RL雙旋：先對(duì)C右旋，在對(duì)A左旋。

舉個(gè)例子：

如圖所示，我們將3號(hào)元素插入到AVL樹中。

標(biāo)出插入的比較路徑，然后依次檢查：

發(fā)現(xiàn)2號(hào)結(jié)點(diǎn)不平衡，則要進(jìn)行修改。

按照模板的位置，3號(hào)元素是在3號(hào)子樹中，所以是RL型狀態(tài)：

可以看到樹恢復(fù)了平衡，同時(shí)2號(hào)元素是原來(lái)的根節(jié)點(diǎn)，所以插入調(diào)整結(jié)束。

總結(jié)：

首先我們按照常規(guī)二叉搜索樹的方法插入，然后按照比較路徑回溯檢查，如果結(jié)點(diǎn)平衡，則無(wú)需操作，當(dāng)遇到平衡因子絕對(duì)值大于一的結(jié)點(diǎn)，就進(jìn)入判斷方法，按照插入元素的位置，來(lái)判斷是4種狀態(tài)中的哪一種，再用對(duì)應(yīng)的方法進(jìn)行操作，繼續(xù)直到根節(jié)點(diǎn)結(jié)束。

流程圖：

• 右旋：就是提拔B結(jié)點(diǎn)B連A，A連2子樹，其他不變。
• 左旋：提拔C結(jié)點(diǎn)，C連A，A連3子樹，其他不變。
• LR雙旋：先左旋B結(jié)點(diǎn)，在右旋A結(jié)點(diǎn)。
• RL雙旋：先對(duì)C右旋，在對(duì)A左旋。

最后祝大家rp++（催更），考試加油??????，拜拜ヾ(?ω?`)o