這篇文章收錄在我的 Github 上 algorithms-tutorial，另外記錄了些算法題解站欺，感興趣的可以看看迎瞧，轉(zhuǎn)載請注明出處。

(一) AVL 樹概念

AVL 樹(也可以稱為平衡樹)是一類數(shù)據(jù)結(jié)構(gòu)吴旋，是改進(jìn)后的二叉查找樹损肛。一般的二叉樹的查詢復(fù)雜度是跟目標(biāo)結(jié)點(diǎn)到樹根的距離 (即樹深) 有關(guān)，因此如果當(dāng)結(jié)點(diǎn)的深度普遍比較大時(shí)荣瑟，查詢的成本就會(huì)上升治拿，所以 AVL 樹就應(yīng)運(yùn)而生。

AVL 樹可以理解為平衡樹樹的一種具體實(shí)現(xiàn)笆焰，兩者并無二致劫谅。這里介紹的平衡樹跟老師說的AVL 樹不一樣。

一、AVL 樹特性：

1. AVL 樹本身首先得是一棵二叉搜索樹
2. 每個(gè)結(jié)點(diǎn)的左右子樹的高度之差的絕對值 (平衡因子) 不超過 1
3. 每個(gè)結(jié)點(diǎn)的左右子樹也要滿足特性 2捏检，也是平衡二叉樹

平衡因子：某結(jié)點(diǎn)的左子樹與右子樹的高度(深度)差即為該結(jié)點(diǎn)的平衡因子

AVL 樹上所有結(jié)點(diǎn)的平衡因子只可能是 -1荞驴，0 或 1。

比如：

AVL 樹：

1.png

non-AVL 樹：根節(jié)點(diǎn)無左子樹

2.png

二贯城、為什么使用 AVL 樹熊楼？

3.png

我們都知道二叉搜索樹可以具有良好的查詢，插入等操作冤狡，但是如果二叉樹退化成了鏈?zhǔn)綐?上圖右)孙蒙，那么其空間復(fù)雜度也會(huì)從原本 O(logn) 退化成了 O(n)，這樣顯然是不想看到的結(jié)果悲雳。

如果可以讓樹維持矮矮胖胖的好身材, 也就是讓高度維持在 O(log n)左右, 完成上述工作就很省時(shí)間挎峦。能夠一直維持好身材, 不因新增刪除而長歪的搜尋樹, 叫做 AVL 樹。

(二) AVL 樹基本操作

相對于二叉查找樹的節(jié)點(diǎn)來說合瓢，我們需要用一個(gè)屬性二叉樹的高度坦胶，目的是維護(hù)插入和刪除過程中的旋轉(zhuǎn)算法。

JAVA 代碼實(shí)現(xiàn):

public class AVLTree{
    TreeNode leftChild = null;
    TreeNode rightChild = null;
    int height;
    String data;
}

那么我們在對一棵二叉查找樹進(jìn)行插入和刪除操作的時(shí)候晴楔，如何讓其保持 AVL 樹的特性呢顿苇？

一、旋轉(zhuǎn)：

假設(shè)有一個(gè)結(jié)點(diǎn)的平衡因子為 2(在 AVL 樹中税弃，因?yàn)榻Y(jié)點(diǎn)是一個(gè)個(gè)插入到樹中纪岁，一旦出現(xiàn)不平衡的狀態(tài)就會(huì)立即調(diào)整，因此平衡因子最大不可能超過 2)

那么這時(shí)候就要進(jìn)行調(diào)整了则果，由于任意結(jié)點(diǎn)最多只有兩個(gè)兒子幔翰，所以當(dāng)高度不平衡時(shí)候，無非以下情況所造成：

1. 對該結(jié)點(diǎn)的左兒子的左子樹進(jìn)行了一次插入西壮。
2. 對該結(jié)點(diǎn)的左兒子的右子樹進(jìn)行了一次插入遗增。
3. 對該結(jié)點(diǎn)的右兒子的左子樹進(jìn)行了一次插入。
4. 對該結(jié)點(diǎn)的右兒子的右子樹進(jìn)行了一次插入款青。

情況 1 和 4 是關(guān)于該點(diǎn)的鏡像對稱做修，同樣，情況 2 和 3 也是一對鏡像對稱抡草。

當(dāng)那個(gè)結(jié)點(diǎn)高度出現(xiàn)不平衡饰及，我們就要對那個(gè)結(jié)點(diǎn)進(jìn)行操作，這里我們稱這個(gè)不平衡結(jié)點(diǎn)為當(dāng)前節(jié)點(diǎn)康震。

二旋炒、單旋轉(zhuǎn)：

情況 1 和情況 4類似，我們可以理解為發(fā)生在 “外邊” 的情況 (即左-左签杈，右-右的情況) 該情況只需要通過一次旋轉(zhuǎn)來完成調(diào)整

情況 1：對該結(jié)點(diǎn)的左兒子的左子樹進(jìn)行了一次插入

4.png

此時(shí)結(jié)點(diǎn) k2 出現(xiàn)了不平衡瘫镇，所以我們以 k2 為當(dāng)前節(jié)點(diǎn)進(jìn)行右旋鼎兽，并將 Y 移到 k2 左子結(jié)點(diǎn)，從而變成右圖（因?yàn)樽筮吀叨雀呦吵晕覀儗⒆笞訕渖弦蒲枰В瑏砥胶馄涓叨炔睿芎美斫猓?/p>

代碼實(shí)現(xiàn)：

public AVLTree singleRotateWithRight(AVLTree unbalancedNode){
    AVLTree node = unbalancedNode.leftChild;
    unbalancedNode.leftChild = node.rightChild;
    node.rightChild = unbalancedNode;
    node.height = MAX(node.leftChild.height, node.rightChild.height) + 1;
    unbalancedNode.height = MAX(unbalancedNode.leftChild.height, unbalancedNode.rightChild.height) + 1;
    return node;   //返回新的根結(jié)點(diǎn)
}

實(shí)例：插入結(jié)點(diǎn) 6

1.gif

情況 4：對該結(jié)點(diǎn)的右兒子的右子樹進(jìn)行了一次插入

6.png

思路和情況 1 類似尚粘，操作剛好相反過來

代碼實(shí)現(xiàn)：

public AVLTree singleRotateWithLeft(AVLTree unbalancedNode){
    AVLTree node = unbalancedNode.rightChild;
    unbalancedNode.rightChild = node.leftChild;
    node.leftChild = unbalancedNode;
    node.height = MAX(node.leftChild.height, node.rightChild.height) + 1;
    unbalancedNode.height = MAX(unbalancedNode.leftChild.height, unbalancedNode.rightChild.height) + 1;
    return node;   //返回新的根結(jié)點(diǎn)
}

實(shí)例：插入結(jié)點(diǎn) 6

2.gif

三择卦、雙旋轉(zhuǎn)：

情況 2 和情況 3 (由于其形狀可以稱為 dog-leg)是插入發(fā)生在“內(nèi)部”的情況（即左-右的情況或右-左的情況），該情況要通過稍微復(fù)雜些的雙旋轉(zhuǎn)來處理郎嫁。

情況2：對該結(jié)點(diǎn)的左兒子的右子樹進(jìn)行了一次插入秉继。

這種情況是單旋轉(zhuǎn)調(diào)整不回來的，如下圖泽铛，旋轉(zhuǎn)后還是不平衡

8.png

這時(shí)候需要旋轉(zhuǎn)兩次來達(dá)到平衡效果：

9.png

以 k1 為當(dāng)前結(jié)點(diǎn)進(jìn)行左旋尚辑，再以 k3 為當(dāng)前結(jié)點(diǎn)進(jìn)行右旋

代碼實(shí)現(xiàn):

public AVLTree doubleRotateWithRight(PAVLNode unbalancedNode){    //之所以稱為 Right，是因?yàn)樽詈蟛黄胶饨Y(jié)點(diǎn)變?yōu)橛易訕淇唬@樣比較好記
    /* Rotate between K1 and K2 */
    AVLTree node = singleRotateWithLeft(unbalancedNode.leftChild); //返回值為 K2 
    node.parent = unbalancedNode;
    /* Rotate between K3 and K2 */
    return singleRotateWithRight(unbalancedNode);  //最后返回的是 k2 結(jié)點(diǎn)杠茬，即根結(jié)點(diǎn)
}

例如：往該樹中插入結(jié)點(diǎn) 9

4.gif

情況3：對該結(jié)點(diǎn)的右兒子的左子樹進(jìn)行了一次插入。

類似需要旋轉(zhuǎn)兩次來達(dá)到平衡效果：

10.png

以 k3 為當(dāng)前結(jié)點(diǎn)進(jìn)行右旋弛随，再以 k2 為當(dāng)前結(jié)點(diǎn)進(jìn)行左旋

代碼實(shí)現(xiàn):

public AVLTree doubleRotateWithLeft(PAVLNode unbalancedNode){   
    /* Rotate between K3 and K2 */
    AVLTree node = singleRotateWithRight(unbalancedNode.rightChild); //返回值為 K2 
    node.parent = unbalancedNode;
    /* Rotate between K1 and K2 */
    return singleRotateWithLeft(unbalancedNode);  //最后返回的是 k2 結(jié)點(diǎn)瓢喉，即根結(jié)點(diǎn)
}

例如：往該樹中插入結(jié)點(diǎn) 11

3.gif

插入操作：

插入的核心思路是通過遞歸找到合適的位置，插入新結(jié)點(diǎn)舀透，然后看新結(jié)點(diǎn)是否平衡（平衡因子是否為2)栓票，如果不平衡的話，就對其進(jìn)行旋轉(zhuǎn)操作：

1. 在結(jié)點(diǎn)的左兒子(X < T->item):
   在左兒子的左子樹(X < T->l-> item): “外邊”愕够，要做單旋轉(zhuǎn)逗载。
   在左兒子的右子樹(X > T->l-> item): “內(nèi)部”，要做雙旋轉(zhuǎn)链烈。
2. 在結(jié)點(diǎn)的右兒子(X > T->item):
   在右兒子的左子樹(X < T->r-> item)，“內(nèi)部”挚躯，要做雙旋轉(zhuǎn)强衡。
   在右兒子的右子樹(X > T->r-> item)，“外邊”码荔，要做單旋轉(zhuǎn)漩勤。
3. (X == T->item) ，對該節(jié)點(diǎn)的計(jì)數(shù)進(jìn)行更新缩搅。

課上的兩個(gè)例題：構(gòu)建一棵 AVL 樹

往樹中按順序插入 342, 206, 444, 523, 607, 301, 142, 183, 102, 157, 149

5.gif

往樹中按順序插入 47, 23, 52, 14, 59, 29, 36, 38, 26

6.gif

參考鏈接：

• 數(shù)據(jù)結(jié)構(gòu)之AVL樹
• AVL樹 - 維基百科越败，自由的百科全書