上一篇文章二叉搜索樹 Binary Search Tree介紹了其性能為O(log n)判耕，但不平衡的二叉樹可能導(dǎo)致其性能下降狐血，最差變?yōu)?code>O(n)步清。

1962年，G. M. Adelson-Velsky 和 Evgenii Landis 在他們的論文An algorithm for the organization of information中首次公開 AVL 樹這一數(shù)據(jù)結(jié)構(gòu)妙同。AVL 樹是最早被發(fā)明的自平衡二叉搜索樹。在 AVL 樹中，任一節(jié)點(diǎn)對應(yīng)的兩顆子樹最大高度差為1尿庐，因此，AVL 樹也稱為高度平衡樹。查找旨剥、刪除咧欣、插入平均、最壞復(fù)雜度都是O(log n)轨帜，增加和刪除元素的操作可能觸發(fā)一次或多次樹旋轉(zhuǎn)魄咕。

這篇文章將介紹二叉搜索樹的平衡如何影響性能，以及實(shí)現(xiàn)一個(gè) AVL 樹蚌父。

1. 平衡

優(yōu)化二叉搜索樹的關(guān)鍵是平衡哮兰，下面介紹三種平衡狀態(tài)。

1.1 完美平衡

二叉搜索樹最理想的狀態(tài)就是完美平衡苟弛，即所有非葉子節(jié)點(diǎn)的度都是2喝滞，同時(shí)所有葉子節(jié)點(diǎn)都在最后一層，被稱為完美二叉樹（Perfect Binary Tree）膏秫，也就是國內(nèi)教材中的滿二叉樹右遭。

AVLPerfectBinaryTree.png

1.2 非完美平衡

雖然完美平衡是最理想的，但其很難實(shí)現(xiàn)缤削。滿二叉樹必須包含指定數(shù)量的節(jié)點(diǎn)窘哈，以便填滿每一層。例如亭敢，節(jié)點(diǎn)數(shù)量為1滚婉、3、7時(shí)是滿二叉樹帅刀；節(jié)點(diǎn)數(shù)量為2让腹、4、5劝篷、6時(shí)哨鸭，由于不能填滿最后一層，不能成為滿二叉樹娇妓。

AVLCompleteBinaryTree.png

左子樹高度減去右子樹高度是該節(jié)點(diǎn)的平衡因子像鸡。通常，認(rèn)為平衡因子1哈恰、0只估、-1的節(jié)點(diǎn)是平衡的。

1.3 不平衡

不平衡二叉搜索樹會有性能損失着绷，并且隨不平衡程度而異蛔钙。

AVLUnbalance.png

保持樹平衡可以確保插入、移除荠医、查找操作保持O(log n)復(fù)雜度吁脱。AVL 樹通過調(diào)整自身結(jié)構(gòu)確保樹保持平衡狀態(tài)桑涎。

2. 實(shí)現(xiàn) AVL 樹

AVL 樹和二叉搜索樹有很多共同點(diǎn)，只是 AVL 樹增加了自平衡的部分兼贡。因此攻冷，這里使用上一篇文章二叉搜索樹 Binary Search Tree的源碼，在其基礎(chǔ)上增加平衡部分即可遍希。此外等曼，為方便理解將demo中BinaryNode重命名為AVLNode，將BinarySearchTree重命名為AVLTree凿蒜。

2.1 平衡因子

AVL 樹使用節(jié)點(diǎn)中的高度（height）屬性測量節(jié)點(diǎn)是否平衡禁谦。高度是節(jié)點(diǎn)到最遠(yuǎn)葉子節(jié)點(diǎn)的距離。

AVLMeasuringBalance.png

在AVLNode.swift中增加以下屬性：

    public var height = 0

指定節(jié)點(diǎn) children 的相對高度決定該節(jié)點(diǎn)是否平衡废封，左右子樹高度相差最大為1州泊，高度差被稱為平衡因子。

在上述height屬性下添加以下代碼：

    public var balanceFactor: Int {
        leftHeight - rightHeight
    }
    
    public var leftHeight: Int {
        leftChild?.height ?? -1
    }
    
    public var rightHeight: Int {
        rightChild?.height ?? -1
    }

balanceFactor計(jì)算左右子樹的高度虱饿，如果子樹為nil拥诡，則其高度為-1。

下面是一顆 AVL 樹：

AVLBalanceHeight.png

藍(lán)色表示高度氮发，綠色表示平衡因子渴肉。

插入40后如下所示：

AVLInsert40.png

插入40后，平衡因子出現(xiàn)了大于等于2爽冕，或小于等于-2仇祭，即樹失去平衡。雖然多個(gè)節(jié)點(diǎn)會失去平衡颈畸，但只需平衡最底部失去平衡的節(jié)點(diǎn)乌奇，樹就會恢復(fù)平衡。

2.2 旋轉(zhuǎn)

讓二叉搜索樹恢復(fù)平衡的過程眯娱，稱為旋轉(zhuǎn)（Rorations）礁苗。旋轉(zhuǎn)有兩大基礎(chǔ)操作：左旋和右旋。共有四種失去平衡類型：LL型徙缴、RR型试伙、LR型、RL型于样。

2.2.1 RR型 左旋轉(zhuǎn) 單旋

所謂的RR型就是節(jié)點(diǎn)的右子樹的右子樹導(dǎo)致其失去平衡疏叨，即下圖中的 Z 導(dǎo)致其失去平衡。

插入40導(dǎo)致失去平衡可以通過左旋解決穿剖，對 x 節(jié)點(diǎn)左旋操作如下：

AVLLeftRotation.png

旋轉(zhuǎn)前后有以下兩個(gè)要點(diǎn)：

• 中序遍歷結(jié)果保持不變蚤蔓。
• 旋轉(zhuǎn)后樹的深度減一。

在AVLTree.swift文件insert(from:value:)方法下添加以下代碼：

    /// 左旋
    private func leftRotate(_ node: AVLNode<Element>) -> AVLNode<Element> {
        // 節(jié)點(diǎn)右子樹作為樞紐
        let pivot = node.rightChild!
        
        // 要旋轉(zhuǎn)的節(jié)點(diǎn)會被設(shè)置為樞紐的左子樹糊余，pivot現(xiàn)在的左子樹被設(shè)置為node的右子樹秀又。
        node.rightChild = pivot.leftChild
        pivot.leftChild = node
        
        // 更新pivot和node的高度
        node.height = max(node.leftHeight, node.rightHeight) + 1
        pivot.height = max(pivot.leftHeight, pivot.rightHeight) + 1
        
        // 返回 pivot单寂，用以替換旋轉(zhuǎn)的節(jié)點(diǎn)。
        return pivot
    }

對25左旋前后對比如下：

AVLLeftLeft.png

2.2.2 LL型 右旋 單旋

所謂的LL型就是節(jié)點(diǎn)的左子樹的左子樹導(dǎo)致其失去平衡涮坐，即下圖中的 Z 導(dǎo)致其失去平衡凄贩。

LL型與RR型相反，當(dāng)一系列左子樹導(dǎo)致失衡袱讹，需進(jìn)行右旋。

對 X 進(jìn)行右旋操作如下：

AVLRightRight.png

具體算法如下：

    /// 右旋
    private func rightRotate(_ node: AVLNode<Element>) -> AVLNode<Element> {
        let pivot = node.leftChild!
        node.leftChild = pivot.rightChild
        pivot.rightChild = node
        
        node.height = max(node.leftHeight, node.rightHeight) + 1
        pivot.height = max(pivot.leftHeight, pivot.rightHeight) + 1
        
        return pivot
    }

與RR型類似昵时，只是左右子樹進(jìn)行了互換捷雕。

2.2.3 RL 型 右旋+左旋 雙旋

RL 就是將節(jié)點(diǎn)插入到了右子樹的左子樹上，導(dǎo)致失去平衡壹甥。

前面遇到的都是子樹在同一側(cè)（左側(cè)或右側(cè)）救巷，當(dāng)向其插入36時(shí)，將出現(xiàn)以下情況：

AVLRightLeft.png

此時(shí)句柠，左旋無法恢復(fù)平衡浦译。需先對右子樹右旋，再進(jìn)行左旋溯职。如下所示：

AVLRightLeftRotation.png

1. 先對37右旋精盅。
2. 目前，25谜酒、36叹俏、37都是右子樹，執(zhí)行左旋可以恢復(fù)平衡僻族。

算法如下：

    /// 先右旋粘驰，在左旋
    private func rightLeftRotate(_ node: AVLNode<Element>) -> AVLNode<Element> {
        guard let rightChild = node.rightChild else { return node }
        
        node.rightChild = rightRotate(rightChild)
        return leftRotate(node)
    }

稍后會介紹何時(shí)調(diào)用上述算法。

2.2.4 LR 型 左旋+右旋 雙旋

LR 型和RL型剛好相反述么，如下所示：

AVLLeftRight.png

1. 對10左旋蝌数。
2. 節(jié)點(diǎn)25、15度秘、10都是左子樹顶伞，執(zhí)行右旋恢復(fù)平衡。

算法如下：

    /// Left-Right
    private func leftRightRotate(_ node: AVLNode<Element>) -> AVLNode<Element> {
        guard let leftChild = node.leftChild else { return node }
        
        node.leftChild = leftRotate(leftChild)
        return rightRotate(node)
    }

上面是可進(jìn)行的旋轉(zhuǎn)類型敷钾，下一步將分析何時(shí)使用何種旋轉(zhuǎn)方式枝哄。

2.3 平衡因子

根據(jù)balanceFactor決定節(jié)點(diǎn)是否平衡，具體方法如下：

    /// 平衡
    private func balanced(_ node: AVLNode<Element>) -> AVLNode<Element> {
        switch node.balanceFactor {
        case 2: // 2表示左子樹高度大于右子樹高度
            // ...
        case -2:    // -2表示右子樹高度大于左子樹高度
            // ...
        default:    // 節(jié)點(diǎn)已經(jīng)平衡阻荒，無序調(diào)節(jié)挠锥。
            return node
        }
    }

balanceFactor的符號用于判斷子樹需要進(jìn)行一次旋轉(zhuǎn)，還是兩次旋轉(zhuǎn)侨赡。

AVLSignOfBalanceFactor.png

更新update(node:)方法如下：

    /// 平衡
    private func balanced(_ node: AVLNode<Element>) -> AVLNode<Element> {
        switch node.balanceFactor {
        case 2: // 2表示左子樹高度大于右子樹高度
            if let leftChild = node.leftChild, leftChild.balanceFactor == -1 {
                return leftRightRotate(node)
            } else {
                return rightRotate(node)
            }
        case -2:    // -2表示右子樹高度大于左子樹高度
            if let rightChild = node.rightChild, rightChild.balanceFactor == 1 {
                return rightLeftRotate(node)
            } else {
                return leftRotate(node)
            }
        default:    // 節(jié)點(diǎn)已經(jīng)平衡蓖租，無序調(diào)節(jié)粱侣。
            return node
        }
    }

上述方法根據(jù)balanceFactor決定要執(zhí)行的平衡類型。目前蓖宦，只需在合適時(shí)機(jī)調(diào)用balance(:node)即可齐婴。

2.4 插入后恢復(fù)平衡

二叉搜索樹中已經(jīng)處理了插入的邏輯，這里只需在插入后查看高度稠茂，恢復(fù)平衡即可柠偶。

insert(from:value:)方法更新后如下：

    private func insert(from node: AVLNode<Element>?, value: Element) -> AVLNode<Element> {
        // 如果節(jié)點(diǎn)為nil，則找到了插入點(diǎn)睬关，返回節(jié)點(diǎn)诱担，結(jié)束遞歸。
        guard let node = node else { return AVLNode(value: value) }
        
        // Element 遵守 Comparable电爹，比較值大小蔫仙。
        if value < node.value { // 值小于當(dāng)前節(jié)點(diǎn)，繼續(xù)與左子樹比較丐箩。
            node.leftChild = insert(from: node.leftChild, value: value)
        } else {    // 大于等于當(dāng)前節(jié)點(diǎn)值摇邦，繼續(xù)與右子樹比較。
            node.rightChild = insert(from: node.rightChild, value: value)
        }
        
        // 恢復(fù)平衡
        let balancedNode = balanced(node)
        balancedNode.height = max(balancedNode.leftHeight, balancedNode.rightHeight) + 1
        
        return balancedNode
    }

插入后屎勘、返回節(jié)點(diǎn)前旋轉(zhuǎn)節(jié)點(diǎn)施籍，使其恢復(fù)平衡。同時(shí)挑秉，更新節(jié)點(diǎn)的高度法梯。

在 playground page 中增加以下方法，查看樹是否保持了平衡：

example(of: "repeated insertions in sequence") {
    var tree = AVLTree<Int>()
    for i in 0..<15 {
        tree.insert(i)
    }
    print(tree)
}

控制臺輸出如下：

--- Example of repeated insertions in sequence ---
  ┌──14
 ┌──13
 │ └──12
┌──11
│ │ ┌──10
│ └──9
│  └──8
7
│  ┌──6
│ ┌──5
│ │ └──4
└──3
 │ ┌──2
 └──1
  └──0

如果沒有執(zhí)行平衡措施犀概，該二叉樹會退化成鏈表立哑。

2.5 移除后恢復(fù)平衡

移除后恢復(fù)平衡與插入后恢復(fù)平衡類似，只需在移除操作的return前恢復(fù)平衡即可姻灶。

將remove(node:value:)的return語句使用以下代碼替換：

        // 刪除后恢復(fù)平衡
        let balancedNode = balanced(node)
        balancedNode.height = max(balancedNode.leftHeight, balancedNode.rightHeight) + 1
        return balancedNode

在 playground page 中使用以下代碼驗(yàn)證移除后是否恢復(fù)了平衡：

example(of: "removing a value") {
    var tree = AVLTree<Int>()
    tree.insert(15)
    tree.insert(10)
    tree.insert(16)
    tree.insert(18)
    print(tree)
    tree.remove(10)
    print(tree)
}

執(zhí)行后控制臺輸出如下：

--- Example of removing a value ---
 ┌──18
┌──16
│ └──nil
15
└──10

┌──18
16
└──15

移除10后铛绰，15的高度變?yōu)?2，觸發(fā)左旋产喉。

AVL 樹的自平衡屬性確保了插入捂掰、刪除、查找復(fù)雜度永遠(yuǎn)保持在O(log n)曾沈。

3. AVL 樹算法題

3.1 樹遍歷協(xié)議

由于樹有多種不同類型这嚣，把通用功能放入單獨(dú)協(xié)議會更簡潔，例如遍歷功能塞俱。

創(chuàng)建TraversableBinaryNode協(xié)議姐帚，在協(xié)議內(nèi)提供遍歷方法的默認(rèn)實(shí)現(xiàn)。二叉樹遵守該協(xié)議就自動獲得了遍歷功能障涯。

首先罐旗，創(chuàng)建協(xié)議：

protocol TraversableBinaryNode {
    associatedtype Element
    var value: Element { get }
    var leftChild: Self? { get }
    var rightChild: Self? { get }
    
    func traverseInOrder(visit: (Element) -> Void)
    func traversePreOrder(visit: (Element) -> Void)
    func traversePostOrder(visit: (Element) -> Void)
}

AVLNode遵守TraversableBinaryNodeprotocol：

extension AVLNode: TraversableBinaryNode {
    func traverseInOrder(visit: (Element) -> Void) {
        leftChild?.traverseInOrder(visit: visit)
        visit(value)
        rightChild?.traverseInOrder(visit: visit)
    }
    
    func traversePreOrder(visit: (Element) -> Void) {
        visit(value)
        leftChild?.traversePreOrder(visit: visit)
        rightChild?.traversePreOrder(visit: visit)
    }
    
    func traversePostOrder(visit: (Element) -> Void) {
        leftChild?.traversePreOrder(visit: visit)
        rightChild?.traversePreOrder(visit: visit)
        visit(value)
    }
}

由于協(xié)議使用了Self膳汪，AVLNode應(yīng)禁止繼承、重寫九秀。更新AVLNode類的聲明遗嗽，增加final關(guān)鍵字：

public final class AVLNode<Element> {

最后，嘗試調(diào)用遍歷方法：

example(of: "using TraversableBinaryNode") {
    var tree = AVLTree<Int>()
    for i in 0..<15 {
        tree.insert(i)
    }
    tree.root?.traverseInOrder(visit: {
        print($0)
    })
}

可以看到中序遍歷 AVL 樹鼓蜒，其按照升序進(jìn)行了輸出痹换，如下所示：

--- Example of using TraversableBinaryNode ---
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14

總結(jié)

插入、刪除后友酱，自平衡的樹會通過四種不同類型旋轉(zhuǎn)恢復(fù)平衡晴音，這樣可以避免性能下降。

Demo名稱：AVLTree
源碼地址：https://github.com/pro648/BasicDemos-iOS/tree/master/AVLTree

歡迎更多指正：https://github.com/pro648/tips

本文地址：https://github.com/pro648/tips/blob/master/sources/AVL樹.md