數(shù)據(jù)結(jié)構(gòu)之AVL解析

現(xiàn)有一串序列1234567，用序列數(shù)作為節(jié)點(diǎn)值構(gòu)造二叉搜索樹(shù)，對(duì)于同樣的節(jié)點(diǎn)，插入的順序不同，最后得到的二叉搜索樹(shù)的結(jié)構(gòu)也不一樣
當(dāng)節(jié)點(diǎn)固定時(shí)，左右子樹(shù)高度越接近，這顆二叉樹(shù)就越平衡（高度越低）



理想的平衡是像完全二叉樹(shù)，滿二叉樹(shù)那樣，高度是最小的


在計(jì)算機(jī)科學(xué)中，AVL樹(shù)是最先發(fā)明的自平衡二叉查找樹(shù)，AVL樹(shù)得名于它的發(fā)明者G. M. Adelson-Velsky和E. M. Landis，他們?cè)?962年的論文《An algorithm for the organization of information》中發(fā)表了它
相比于"二叉搜索樹(shù)"，AVL樹(shù)的特點(diǎn)是：AVL樹(shù)中任何節(jié)點(diǎn)的兩個(gè)子樹(shù)的高度最大差別為1

  • 添加導(dǎo)致的失衡

新增節(jié)點(diǎn)為12



祖先節(jié)點(diǎn)10、15失衡

試著分析其他可能出現(xiàn)的情況，得出以下結(jié)論：
可能的最壞情況是所有祖先節(jié)點(diǎn)都失衡
父節(jié)點(diǎn)、非祖先節(jié)點(diǎn)，都不可能失衡
因?yàn)槿绻歉腹?jié)點(diǎn)那么它下面還有一個(gè)子節(jié)點(diǎn)，總共就兩個(gè)節(jié)點(diǎn)，兩個(gè)節(jié)點(diǎn)的高度差一定是在≤1的范圍

  • 平衡因子

概念：某節(jié)點(diǎn)左右子樹(shù)的高度差
普通二叉搜索樹(shù)的平衡因子：



AVL樹(shù)經(jīng)過(guò)一系列變換可以減少樹(shù)的高度，讓平衡因子的絕對(duì)值<=1，每個(gè)節(jié)點(diǎn)的平衡因子只可能是1，0，-1，超過(guò)1稱(chēng)之為失衡
AVL樹(shù)的搜索、添加、刪除的時(shí)間復(fù)雜度為O(logn)

  • 變換

旋轉(zhuǎn)變換可以幫助二叉樹(shù)恢復(fù)平衡，按可能出現(xiàn)的情況分為四種：

  1. RR（右右旋轉(zhuǎn)）：當(dāng)在AVL樹(shù)中的一個(gè)節(jié)點(diǎn)的右子樹(shù)的右子樹(shù)上插入了節(jié)點(diǎn)，導(dǎo)致右子樹(shù)高度過(guò)高，就會(huì)觸發(fā)右右旋轉(zhuǎn)。通過(guò)右右旋轉(zhuǎn)，我們可以將當(dāng)前節(jié)點(diǎn)旋轉(zhuǎn)到其父節(jié)點(diǎn)的位置，而原先的父節(jié)點(diǎn)則變?yōu)楫?dāng)前節(jié)點(diǎn)的左子節(jié)點(diǎn)。

  2. RL（右左旋轉(zhuǎn)）：當(dāng)在AVL樹(shù)中的一個(gè)節(jié)點(diǎn)的右子樹(shù)的左子樹(shù)上插入了節(jié)點(diǎn)，導(dǎo)致右子樹(shù)的左子樹(shù)高度過(guò)高，就會(huì)觸發(fā)右左旋轉(zhuǎn)。通過(guò)右左旋轉(zhuǎn)，我們先對(duì)右子節(jié)點(diǎn)進(jìn)行右旋轉(zhuǎn)，再對(duì)當(dāng)前節(jié)點(diǎn)進(jìn)行左旋轉(zhuǎn)，以保持樹(shù)的平衡。

  3. LR（左右旋轉(zhuǎn)）：當(dāng)在AVL樹(shù)中的一個(gè)節(jié)點(diǎn)的左子樹(shù)的右子樹(shù)上插入了節(jié)點(diǎn)，導(dǎo)致左子樹(shù)的右子樹(shù)高度過(guò)高，就會(huì)觸發(fā)左右旋轉(zhuǎn)。通過(guò)左右旋轉(zhuǎn)，我們先對(duì)左子節(jié)點(diǎn)進(jìn)行左旋轉(zhuǎn)，再對(duì)當(dāng)前節(jié)點(diǎn)進(jìn)行右旋轉(zhuǎn)，也是為了保持樹(shù)的平衡。

  4. LL（左左旋轉(zhuǎn)）：當(dāng)在AVL樹(shù)中的一個(gè)節(jié)點(diǎn)的左子樹(shù)的左子樹(shù)上插入了節(jié)點(diǎn)，導(dǎo)致左子樹(shù)高度過(guò)高，就會(huì)觸發(fā)左左旋轉(zhuǎn)。通過(guò)左左旋轉(zhuǎn)，我們可以將當(dāng)前節(jié)點(diǎn)旋轉(zhuǎn)到其父節(jié)點(diǎn)的位置，而原先的父節(jié)點(diǎn)則變?yōu)楫?dāng)前節(jié)點(diǎn)的右子節(jié)點(diǎn)。

說(shuō)明：為了便于觀察分析，將左右子樹(shù)畫(huà)為長(zhǎng)條狀，T1 T2 T3 T4可以想象成是節(jié)點(diǎn)高度未知的左右子樹(shù)，在新節(jié)點(diǎn)添加之前處于平衡

1、RR-左單旋

2、LL-右單旋

3、LR-RR左單旋，LL右單旋

4、RL-LL右單旋，RR左單旋

  • 刪除導(dǎo)致的失衡

刪除值為11的節(jié)點(diǎn)，值為15的節(jié)點(diǎn)失衡

試著分析其他可能出現(xiàn)的情況，得出以下結(jié)論：
刪除只可能導(dǎo)致父節(jié)點(diǎn)失衡，除父節(jié)點(diǎn)以外的其他節(jié)點(diǎn)都不可能失衡

源碼解析：

AVLNode：
首先需要了解AVLnode
BST的Node在下面 BST參考 的鏈接中

private static class AVLNode<E> extends Node<E> {
    int height = 1;
    
    public AVLNode(E element, Node<E> parent) {
        super(element, parent);
    }
    public int balanceFactor() {
        int leftHeight = left == null ? 0 : ((AVLNode<E>)left).height;
        int rightHeight = right == null ? 0 : ((AVLNode<E>)right).height;
        return leftHeight - rightHeight;
    }
    public void updateHeight() {
        int leftHeight = left == null ? 0 : ((AVLNode<E>)left).height;
        int rightHeight = right == null ? 0 : ((AVLNode<E>)right).height;
        height = 1 + Math.max(leftHeight, rightHeight);
    }
    public Node<E> tallerChild() {
        int leftHeight = left == null ? 0 : ((AVLNode<E>)left).height;
        int rightHeight = right == null ? 0 : ((AVLNode<E>)right).height;
        if (leftHeight > rightHeight) return left;
        if (leftHeight < rightHeight) return right;
        return isLeftChild() ? left : right;
    }
}

balanceFactor( )此方法用于獲取節(jié)點(diǎn)的平衡因子，需要先獲得左（leftNode）右(rightNode)節(jié)點(diǎn)的高度，然后根據(jù)定義：平衡因子=左節(jié)點(diǎn)高度 - 右節(jié)點(diǎn)高度
updateHeight( )此方法用于更新節(jié)點(diǎn)高度，這個(gè)方法的就已經(jīng)存在說(shuō)明了在特定位置會(huì)進(jìn)行使用那么什么時(shí)候需要更新高度呢？結(jié)合下面的add方法進(jìn)行分析

add( )方法：
添加節(jié)點(diǎn)因?yàn)樯婕暗牟僮鬏^多，所以相對(duì)比較復(fù)雜
它是在BST的add基礎(chǔ)之上進(jìn)行的添加
BST參考：

http://m.itdecent.cn/p/d6f2921b0e66

BST節(jié)點(diǎn)的添加只是按照 二叉樹(shù)的特征（任意節(jié)點(diǎn)的值大于左子樹(shù)所有節(jié)點(diǎn)的值，任意節(jié)點(diǎn)的值小于右子樹(shù)所有節(jié)點(diǎn)的值）進(jìn)行的添加，并不涉及添加后的節(jié)點(diǎn)旋轉(zhuǎn)，所以在此基礎(chǔ)上需要增加旋轉(zhuǎn)操作（ afterAdd( )方法 ）
下面代碼是BST的add操作源碼，注意afterAdd( )的位置

public void add(E element) {
    elementNotNullCheck(element);
    
    // 添加第一個(gè)節(jié)點(diǎn)
    if (root == null) {
        root = createNode(element, null);
        size++;
        // 新添加節(jié)點(diǎn)之后的處理
        afterAdd(root);
        return;
    }
    
    // 添加的不是第一個(gè)節(jié)點(diǎn)
    // 找到父節(jié)點(diǎn)
    Node<E> parent = root;
    Node<E> node = root;
    int cmp = 0;
    do {
        cmp = compare(element, node.element);
        parent = node;
        if (cmp > 0) {
            node = node.right;
        } else if (cmp < 0) {
            node = node.left;
        } else { // 相等
            node.element = element;
            return;
        }
    } while (node != null);

    // 看看插入到父節(jié)點(diǎn)的哪個(gè)位置    
    Node<E> newNode = createNode(element, parent);
    if (cmp > 0) {
        parent.right = newNode;
    } else {
        parent.left = newNode;
    }
    size++;
    
    // 新添加節(jié)點(diǎn)之后的處理
    afterAdd(newNode);
}

分析：
代碼的核心思想是 創(chuàng)建新節(jié)點(diǎn) ,因?yàn)椴迦胄鹿?jié)點(diǎn)需要element和parent，而parent需要分情況討論
parent可能出現(xiàn)的情況：parent為null，parent為node.left，parent為node.right
此外在每一種添加操作的最后應(yīng)該有旋轉(zhuǎn)操作( afterAdd( ) )

  • afterAdd( )

afterAdd( )涉及的操作較多，需要判斷平衡因子……

private void afterAdd(Node<E> node) {
    while ((node = node.parent) != null) {
        if (isBalanced(node)) {
            // 更新高度
            updateHeight(node);
        } else {
            // 恢復(fù)平衡
            rebalance(node);
            // 整棵樹(shù)恢復(fù)平衡
            break;
        }
    }
}

循環(huán)內(nèi)：
首先判斷是否平衡 isBalanced(node)

private boolean isBalanced(Node<E> node) {
    return Math.abs(((AVLNode<E>)node).balanceFactor()) <= 1;
}

public int balanceFactor() {
    int leftHeight = left == null ? 0 : ((AVLNode<E>)left).height;
    int rightHeight = right == null ? 0 : ((AVLNode<E>)right).height;
    return leftHeight - rightHeight;
}

平衡則更新高度

public void updateHeight() {
    int leftHeight = left == null ? 0 : ((AVLNode<E>)left).height;
    int rightHeight = right == null ? 0 : ((AVLNode<E>)right).height;
    height = 1 + Math.max(leftHeight, rightHeight);
}

不管是獲取平衡因子還是更新高度都需要當(dāng)前節(jié)點(diǎn)的高度來(lái)完成，關(guān)系圖如下：

因?yàn)槊刻砑右粋€(gè)節(jié)點(diǎn)就會(huì)更新高度，所以每一個(gè)AVLNode的height屬性就是當(dāng)前節(jié)點(diǎn)的高度

  • remove( )

刪除只可能導(dǎo)致父節(jié)點(diǎn)失衡
除父節(jié)點(diǎn)以外的其他節(jié)點(diǎn)都不可能失衡
刪除不會(huì)影響父節(jié)點(diǎn)的高度，自然祖父節(jié)點(diǎn)的平衡因子不會(huì)改變（刪除了短邊，長(zhǎng)邊高度不變）

刪除與添加一樣也是LL RR LR RL四種情況，可以自行畫(huà)圖模擬
remove也是在BST的刪除方法基礎(chǔ)上增加了afterRemove
afterRemove里的邏輯與afterAdd大概一樣，只是少了break,因?yàn)閯h除節(jié)點(diǎn)后恢復(fù)平衡會(huì)進(jìn)行旋轉(zhuǎn)操作，在旋轉(zhuǎn)恢復(fù)了平衡后的這個(gè)過(guò)程里會(huì)造成更高一級(jí)的祖先節(jié)點(diǎn)一直持續(xù)到根節(jié)點(diǎn)都是不平衡的，那么就需要不斷的rebalance恢復(fù)平衡

public void remove(E element) {
    remove(node(element));
}

private void remove(Node<E> node) {
    if (node == null) return;
    
    size--;
    
    if (node.hasTwoChildren()) { // 度為2的節(jié)點(diǎn)
        // 找到后繼節(jié)點(diǎn)
        Node<E> s = successor(node);
        // 用后繼節(jié)點(diǎn)的值覆蓋度為2的節(jié)點(diǎn)的值
        node.element = s.element;
        // 刪除后繼節(jié)點(diǎn)
        node = s;
    }
    // 刪除node節(jié)點(diǎn)（node的度必然是1或者0）
    Node<E> replacement = node.left != null ? node.left : node.right;

    if (replacement != null) { // node是度為1的節(jié)點(diǎn)
        // 更改parent
        replacement.parent = node.parent;
        // 更改parent的left、right的指向
        if (node.parent == null) { // node是度為1的節(jié)點(diǎn)并且是根節(jié)點(diǎn)
            root = replacement;
        } else if (node == node.parent.left) {
            node.parent.left = replacement;
        } else { // node == node.parent.right
            node.parent.right = replacement;
        }
        // 刪除節(jié)點(diǎn)之后的處理
        afterRemove(node);
    } else if (node.parent == null) { // node是葉子節(jié)點(diǎn)并且是根節(jié)點(diǎn)
        root = null;
        // 刪除節(jié)點(diǎn)之后的處理
        afterRemove(node);
    } else { // node是葉子節(jié)點(diǎn)，但不是根節(jié)點(diǎn)
        if (node == node.parent.left) {
            node.parent.left = null;
        } else { // node == node.parent.right
            node.parent.right = null;
        }
        // 刪除節(jié)點(diǎn)之后的處理
        afterRemove(node);
    }
}

protected void afterRemove(Node<E> node) {
        while ((node = node.parent) != null) {
        if (isBalanced(node)) {
            // 更新高度
            updateHeight(node);
        } else {
            // 恢復(fù)平衡
            rebalance(node);
        }
    }
}

AVL搜索、刪除、添加的時(shí)間復(fù)雜度是Olog(n)

(10條消息) 算法復(fù)雜度O(logn)詳解一月的博客-CSDN博客_時(shí)間復(fù)雜度o(logn)的算法

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書(shū)系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容