Swift 數(shù)據(jù)結(jié)構(gòu) - AVL樹(AVL Tree)

AVL樹

平衡二叉搜索樹（Self-balancing binary search tree）又被稱為AVL樹（有別于AVL算法）建蹄，且具有以下性質(zhì)：它是一棵空樹或它的左右兩個(gè)子樹的高度差的絕對值不超過1碌更，并且左右兩個(gè)子樹都是一棵平衡二叉樹裕偿。

image.png

平衡因子

某結(jié)點(diǎn)的左子樹與右子樹的 高度(深度)差 即為該結(jié)點(diǎn)的 平衡因子（BF,Balance Factor）。平衡二叉樹上所有結(jié)點(diǎn)的平衡因子只可能是 -1针贬，0 或 1击费。如果某一結(jié)點(diǎn)的平衡因子絕對值大于1則說明此樹不是平衡二叉樹。為了方便計(jì)算每一結(jié)點(diǎn)的平衡因子我們可以為每個(gè)節(jié)點(diǎn)賦予 height 這一屬性桦他，表示此節(jié)點(diǎn)的高度。

節(jié)點(diǎn)的 height 是獲取該節(jié)點(diǎn)最低葉子所需的步數(shù)谆棱。例如快压，在下面的樹中，從A到E需要三個(gè)步垃瞧，因此A的高度為3蔫劣。B的高度為2，C的高度為1个从，其他的高度為0脉幢，因?yàn)樗鼈兪侨~節(jié)點(diǎn)。

image.png

高度和深度是相反的表示嗦锐，深度是 從上到下 數(shù)的嫌松，而高度是 從下往上 數(shù)。
我們先來看看高度和深度的定義奕污，某節(jié)點(diǎn)的深度是指從根節(jié)點(diǎn)到該節(jié)點(diǎn)的最長簡單路徑邊的條數(shù)萎羔，而高度是指從該節(jié)點(diǎn)到葉子節(jié)點(diǎn)的最長簡單路徑邊的條數(shù)。

基礎(chǔ)設(shè)計(jì)

首先我們可以設(shè)計(jì)出 AVL 樹節(jié)點(diǎn)碳默，并且實(shí)現(xiàn)一些簡單通用的方法供后續(xù)操作贾陷。

/**
 * AVLTree是BST，所以節(jié)點(diǎn)值必須是可比較的
 */
public class AvlTree<E: Comparable>{
    private class Node {
        public var e: E
        public var left: Node? = nil
        public var right: Node? = nil
        public var height: Int = 1

        public init(e: E){
            self.e = e
        }
    }
    private var root: Node?
    private var size: Int

    public init() {
        root = nil
        size = 0
    }
    
    //獲取某一結(jié)點(diǎn)的高度
    private func getHeight(node: Node?) -> Int {
        guard let node = node else {
            return 0
        }
        return node.height
    }
    
    public func getSize() -> Int {
        return size
    }
    
    public func isEmpty() -> Bool {
        return size == 0
    }
    
    /**
     * 獲取節(jié)點(diǎn)的平衡因子
     * @param node
     * @return
     */
    private func getBalanceFactor(node: Node?) -> Int {
        guard let node = node else {
            return 0
        }
        return abs(getHeight(node: node.left) - getHeight(node: node.right))
    }
    
    //判斷樹是否為平衡二叉樹
    public func isBalanced() -> Bool {
        return isBalanced(node: root)
    }
    
    private func isBalanced(node: Node?) -> Bool {
        guard let node = node else {
            return true
        }
        
        let balanceFactory = getBalanceFactor(node: node)
        if balanceFactory > 1 {
            return false
        }
        return isBalanced(node: node.left) && isBalanced(node: node.right)
    }
}

添加節(jié)點(diǎn)

往平衡二叉樹中添加節(jié)點(diǎn)很可能會(huì)導(dǎo)致二叉樹失去平衡嘱根，所以我們需要在每次插入節(jié)點(diǎn)后進(jìn)行平衡的維護(hù)操作髓废。插入節(jié)點(diǎn)破壞平衡性有如下四種情況：

LL（需要右旋平衡）

LL的意思是向左子樹（L）的左孩子（L）中插入新節(jié)點(diǎn)后導(dǎo)致不平衡，這種情況下需要 右旋操作该抒，而不是說LL的意思是右旋慌洪，后面的也是一樣。

image.png

我們將這種情況抽象出來柔逼，得到下圖：

image.png

我們需要對節(jié)點(diǎn)y進(jìn)行平衡的維護(hù)蒋譬。步驟如下圖所示：

image.png

    /**
     * 右旋轉(zhuǎn),返回根節(jié)點(diǎn)
     */
    private func rightRotate(y: Node?) -> Node? {
        guard let y = y else {
            return nil
        }
        let x = y.left
        let t3 = x?.right
        x?.right = y
        y.left = t3
        //更新height
        y.height = max(getHeight(node: y.left),getHeight(node: y.right))+1
        x?.height = max(getHeight(node: x?.left),getHeight(node: x?.right))+1
        return x
    }

RR（需要左旋平衡）

image.png

我們將這種情況抽象出來，得到下圖：

image.png

我們需要對節(jié)點(diǎn)y進(jìn)行平衡的維護(hù)。步驟如下圖所示：

image.png

    /**
     * 左旋轉(zhuǎn)
     */
    private func leftRotate(y: Node?) -> Node? {
        guard let y = y else {
            return nil
        }
        let x = y.right
        let t3 = x?.left
        x?.left = y
        y.right = t3
        //更新height
        y.height = max(getHeight(node: y.left),getHeight(node: y.right)) + 1
        x?.height = max(getHeight(node: x?.left),getHeight(node: x?.right)) + 1
        return x
    }

LR（先左旋后右旋）

image.png

我們將這種情況抽象出來舶衬，得到下圖：

image.png

我們需要對節(jié)點(diǎn)y進(jìn)行平衡的維護(hù)猫胁。步驟如下圖所示：

image.png

RL（先右旋后左旋）

image.png

我們將這種情況抽象出來，得到下圖：

image.png

我們需要對節(jié)點(diǎn)y進(jìn)行平衡的維護(hù)剂买。步驟如下圖所示：

image.png

添加節(jié)點(diǎn)代碼

extension AvlTree {
    // 向二分搜索樹中添加新的元素(key, value)
    public func add(e: E) {
        root = add(node: root, e: e)
    }
    
    // 向以node為根的二分搜索樹中插入元素(key, value)惠爽，遞歸算法
    // 返回插入新節(jié)點(diǎn)后二分搜索樹的根
    private func add(node: Node?, e: E) -> Node? {
        guard let node = node else {
             size += 1
            return Node(e: e)
        }

        //判斷是插入根節(jié)點(diǎn)的左子樹還是右子樹
        if e < node.e {
            node.left = add(node: node.left, e: e)
        } else if e > node.e {
            node.right = add(node: node.right, e: e)
        }
        
        //更新height
        node.height = 1 + max(getHeight(node: node.left),getHeight(node: node.right))
        
        //計(jì)算平衡因子
        let balanceFactor = getBalanceFactor(node: node)
        if balanceFactor > 1 && getBalanceFactor(node: node.left) > 0 {
            //右旋LL
            return rightRotate(y: node)
        }
        if balanceFactor < -1 && getBalanceFactor(node: node.right) < 0  {
            //左旋RR
            return leftRotate(y: node)
        }
        
        //LR
        if balanceFactor > 1 && getBalanceFactor(node: node.left) < 0 {
            node.left = leftRotate(y: node.left)
            return rightRotate(y: node)
        }
        
        //RL
        if balanceFactor < -1 && getBalanceFactor(node: node.right) > 0 {
            node.right = rightRotate(y: node.right)
            return leftRotate(y: node)
        }
        return node
    }
}

刪除節(jié)點(diǎn)

在刪除AVL樹節(jié)點(diǎn)前需要知道二分搜索樹的節(jié)點(diǎn)刪除操作【點(diǎn)此學(xué)習(xí)吧！】瞬哼，和二分搜索樹刪除節(jié)點(diǎn)不同的是我們刪除AVL樹的節(jié)點(diǎn)后需要進(jìn)行平衡的維護(hù)操作婚肆。

extension AvlTree {
    //查找二叉搜索樹的節(jié)點(diǎn)
    private func getNode(root: Node?, e: E) -> Node? {
        guard let root = root else {
            return nil
        }
        
        if(root.e == e) {
            return root
        } else if e > root.e {
            return getNode(root: root.right, e: e)
        } else {
            return getNode(root: root.left, e: e)
        }
        return nil
    }
    //移出節(jié)點(diǎn)
    public func remove(e: E) -> E? {
        guard let node = getNode(root: root, e: e) else {
            return nil
        }
        root = remove(node: root, e: e)
        return node.e
    }
    
    //二叉搜索樹的最小值一直找左孩子就行了
    private func minNode(node: Node?) -> Node? {
        guard let node = node else {
            return nil
        }
        
        if let node = node.left {
            return minNode(node: node.left)
        } else {
            return node
        }
    }

    private func remove(node: Node?, e: E) -> Node? {
        guard let node = node else {
            return nil
        }
        var retNode: Node?
        if e < node.e {
            node.left = remove(node: node.left , e: e)
            retNode = node
        } else if e > node.e {
            node.right = remove(node: node.right, e: e)
            retNode = node
        } else {
            // 待刪除節(jié)點(diǎn)左子樹為空的情況
            if node.left == nil {
                let rightNode = node.right
                node.right = nil
                size -= 1
                retNode = rightNode
            } else if node.right == nil {
                // 待刪除節(jié)點(diǎn)右子樹為空的情況
                let leftNode = node.left
                node.left = nil
                size -= 1
                retNode = leftNode
            } else {
                // 待刪除節(jié)點(diǎn)左右子樹均不為空的情況
                // 找到比待刪除節(jié)點(diǎn)大的最小節(jié)點(diǎn), 即待刪除節(jié)點(diǎn)右子樹的最小節(jié)點(diǎn)
                // 用這個(gè)節(jié)點(diǎn)頂替待刪除節(jié)點(diǎn)的位置
                let successor = minNode(node: node.right)!
                successor.right = remove(node: node.right, e: successor.e)
                successor.left = node.left

                node.left = nil
                node.right = nil
                retNode = successor
            }
        }
        
        guard let retNodeTmp = retNode else {
            return nil
        }
        //維護(hù)平衡
        //更新height
        retNodeTmp.height = 1 + max(getHeight(node: retNodeTmp.left),getHeight(node: retNodeTmp.right))
        
        //計(jì)算平衡因子
        let balanceFactor = getBalanceFactor(node: retNodeTmp)
        if balanceFactor > 1 && getBalanceFactor(node: retNodeTmp.left) >= 0 {
            //右旋LL
            return rightRotate(y: retNodeTmp)
        }
        
        if balanceFactor < -1 && getBalanceFactor(node: retNodeTmp.right) <= 0 {
            //左旋RR
            return leftRotate(y: retNodeTmp)
        }
        
        //LR
        if balanceFactor > 1 && getBalanceFactor(node: retNodeTmp.left) < 0 {
            node.left = leftRotate(y: retNodeTmp.left)
            return rightRotate(y: retNodeTmp)
        }
        
        //RL
        if balanceFactor < -1 && getBalanceFactor(node: retNodeTmp.right) > 0 {
            node.right = rightRotate(y: retNodeTmp.right)
            return leftRotate(y: retNodeTmp)
        }
        return retNodeTmp
    }
}

參考文章

詳細(xì)圖文——AVL樹