AVL是(Adelson-Velskii 和 Landis) 在1962年的論文中提出的解決二叉樹不平衡的一種數(shù)據(jù)結(jié)構(gòu).

為什么需要AVL
在BST中, 如果我們按照順序插入元素, 那么BST會形成最壞的情況: 退化為鏈表, 那么就失去了原本的O(logN)的時間復(fù)雜度, 轉(zhuǎn)而變?yōu)镺(N)的時間復(fù)雜度. 如下圖所示:

造成這個問題的原因是因為: 我們的BST發(fā)生了不平衡的情況. AVL數(shù)據(jù)結(jié)構(gòu)就是為了解決這個問題.

如何保證樹的平衡
很簡單的一種情況, 我們讓每個節(jié)點的左右子樹都具有相同的高度, 這種想法不要求樹的深度. 因此設(shè)想一下, 某個節(jié)點的左右子樹都很深, 這樣該節(jié)點的左右子樹實際上都是一個鏈表.

另一種平衡條件要求每個節(jié)點都左右子樹都必須有相同的高度, 但該方式太嚴(yán)格, 難以使用.

AVL的平衡要求
AVL要求每個節(jié)點都左子樹和右子樹的高度最多相差為1. (如果沒有左右子樹, 高度為1).

AVL平衡基礎(chǔ)

節(jié)點高度
前面提到AVL的平衡要求, 因此需要對每個節(jié)點進(jìn)行高度的標(biāo)注 (編程上每個節(jié)點的結(jié)構(gòu)都需要附帶一個高度值). 如下圖所示

根據(jù)AVL的性質(zhì), 左邊的二叉樹是AVL樹, 右邊的則不是AVL樹, 因為不滿足AVL平衡要求.
根據(jù)圖就可以看出來, 節(jié)點的高度計算為: s(h) = max(s.left.h, s.right.h) + 1

平衡因子
前面提到了AVL樹存在節(jié)點高度, 有了節(jié)點高度, 就可以據(jù)此 計算出來平衡因子.
平衡因子的計算為 s(f) = abs(s.left.h - s.right.h), 有了平衡因子, 就可以判斷當(dāng)前節(jié)點是否滿足AVL的性質(zhì), 如果 s(f) > 1 則不平衡, 此時需要進(jìn)行處理. 處理的方式也成為 AVL旋轉(zhuǎn)

AVL旋轉(zhuǎn)

在進(jìn)行AVL旋轉(zhuǎn)之前, 先要搞清楚什么情況會導(dǎo)致二叉樹不平衡.
對二叉樹的添加和刪除會破壞樹的平衡性, 此時就需要進(jìn)行旋轉(zhuǎn)了. 不過AVL的旋轉(zhuǎn)添加和刪除都會導(dǎo)致, 因此我們將從添加操作開始引出AVL樹的旋轉(zhuǎn)算法, 在刪除操作的時候可以復(fù)用這些旋轉(zhuǎn)算法.

以前面圖中展示的平衡二分搜索樹為例, 此時往該樹中添加元6, 就得到了一棵新的二分搜索樹, 不過它是不平衡的 (8這個節(jié)點平衡因子大于1), 如圖所示:

對于二叉樹來說, 任意節(jié)點最多有兩個字節(jié)點, 因此高度不平衡時, 該節(jié)點的兩棵子樹高度差為2 (添加和刪除每次都是一個節(jié)點, 同時本次不平衡的時候就會執(zhí)行旋轉(zhuǎn)操作).
這樣不平衡的情況就分為以下4種情形

LL (左兒子的左子樹)

如圖所示, 插入節(jié)點6造成了8所在的節(jié)點不平衡, 這種情況叫做LL

對于LL, 需要進(jìn)行一次旋轉(zhuǎn)來保證AVL的性質(zhì).

那么怎么進(jìn)行旋轉(zhuǎn)呢?

對于插入節(jié)點6來說, 插入路徑是 6 <- 7 <- 8 <-5 , 因此不平衡的情況也只會發(fā)生在這條路徑上, 只要沿著該路徑向上回溯, 通過計算平衡因子看是否滿足AVL性質(zhì), 如果出現(xiàn)不滿足的節(jié)點, 就進(jìn)行一次旋轉(zhuǎn),旋轉(zhuǎn)過程如圖:

未命名文件-3.png

從圖上可以看出旋轉(zhuǎn)過程涉及8和7兩個節(jié)點, 發(fā)生不平衡的節(jié)點是8, 通過旋轉(zhuǎn)操作后對于同樣在路徑上的5來說平衡因子是滿足AVL要求的, 因此并不需要旋轉(zhuǎn).

我們把上面描述的旋轉(zhuǎn)過程成為 右旋轉(zhuǎn)

旋轉(zhuǎn)可以描述為:

8->Left = 7->Right
7->Right = 8

RR (右兒子的右子樹)

和LL相對應(yīng)的一種情況是RR, 對于RR情況的修復(fù)操作稱為左旋轉(zhuǎn), 具體方式和LL的右旋轉(zhuǎn)相差不大, 如圖:

旋轉(zhuǎn)可以描述為:

Y->Right = X->Left
X->Left = Y 

單旋轉(zhuǎn)總結(jié)

前面提到的LL和RR兩種單旋轉(zhuǎn)，屬于對稱的旋轉(zhuǎn)，有時候也叫它們?yōu)閱涡D(zhuǎn)，這一小節(jié)通過一個完整的插入示例來對單旋轉(zhuǎn)整體來做一個總結(jié)。

插入節(jié)點4的時候依舊保持BST以及AVL的性質(zhì)，插入節(jié)點5后以2為節(jié)點的右子樹高度為3，左子樹高度為1，因此引發(fā)了一次左旋轉(zhuǎn)，旋轉(zhuǎn)之后滿足AVL的性質(zhì)，同時也滿足BST的性質(zhì)。

下圖描述了另一種情況，插入節(jié)點11后，根節(jié)點3和節(jié)點4都不平衡了，但由于向上回溯，因此首先會對節(jié)點4進(jìn)行旋轉(zhuǎn)，而旋轉(zhuǎn)后節(jié)點3和4都滿足了AVL性質(zhì)，此時3就不需要處理了。

LR

前面描述的LL和RR情況都是插入的元素在不平衡節(jié)點的左側(cè)的左側(cè)以及右側(cè)的右側(cè)。
但由于每個節(jié)點都有兩個子節(jié)點，因此插入的元素有可能在不平衡節(jié)點的左側(cè)的右側(cè)以及右側(cè)的左側(cè)，這兩種情況的旋轉(zhuǎn)稱為LR和RL，也叫做雙旋轉(zhuǎn)。

來看一種LR的情況，如下圖所示，三個節(jié)點的大小關(guān)系為 k1 < k2 < k3，從圖中可以看出，使用前面描述的LL和RR情況旋轉(zhuǎn)后都不能滿足大小關(guān)系。因此對于LR的情況，單純的左旋轉(zhuǎn)和右旋轉(zhuǎn)都不能滿足。

對于LR情形，為了解決這個問題，就需要使用左-右雙旋轉(zhuǎn)。來看對于上圖，通過左-右雙旋轉(zhuǎn)旋轉(zhuǎn)后得到的樣子：

未命名文件.png

首先對k3的左節(jié)點k1進(jìn)行左旋轉(zhuǎn)，得到一個旋轉(zhuǎn)結(jié)果后在對k3進(jìn)行右旋轉(zhuǎn)，經(jīng)過兩次旋轉(zhuǎn)后，得到一棵新樹，這棵樹是滿足AVL性質(zhì)的，同時也滿足BST的性質(zhì)。

LR的旋轉(zhuǎn)過程可以描述為：

// 左旋轉(zhuǎn) 
k1.right= k2.left
k2.left = k1
// 右旋轉(zhuǎn)
k3.left = k2.right
k2.right = k3

RL

RL和LR的左-右雙旋轉(zhuǎn)差不多，通過右-左雙旋轉(zhuǎn)調(diào)整插入元素在節(jié)點的右子樹的左子樹，如下圖所示：

首先對k3節(jié)點進(jìn)行右旋轉(zhuǎn)，得到一個新的旋轉(zhuǎn)結(jié)果后，在對k1進(jìn)行左旋轉(zhuǎn)，經(jīng)過兩次旋轉(zhuǎn)后，新的樹滿足AVL以及BST的性質(zhì)。

RL的旋轉(zhuǎn)過程可以描述為：

//右旋轉(zhuǎn)
k3.left =k2.right
k2.right = k3
//左旋轉(zhuǎn)
k1.right = k2.left
k2.left = k1

雙旋轉(zhuǎn)總結(jié)

AVL刪除

AVL相關(guān)優(yōu)化

AVL的局限性