DSA AVL 樹

AVL 樹

普通 二叉搜尋樹 與 AVL 樹之間的唯一區別在於，AVL 樹還執行旋轉操作，以保持樹的平衡。

當左右子樹的高度差小於 2 時，二叉搜尋樹處於平衡狀態。

透過保持平衡，AVL 樹確保了最小的樹高，這意味著搜尋、插入和刪除操作可以非常快速地完成。

上面的兩棵樹都是二叉搜尋樹，它們擁有相同的節點和相同的有序遍歷（按字母順序），但高度卻大不相同，因為 AVL 樹已經進行了自平衡。

在下面的動畫中，逐步演示 AVL 樹的構建過程，以瞭解平衡因子是如何更新的，以及何時需要執行旋轉操作來恢復平衡。

繼續閱讀，瞭解更多關於平衡因子是如何計算的，旋轉操作是如何執行的，以及 AVL 樹是如何實現的。

左旋和右旋

為了恢復 AVL 樹中的平衡，需要執行左旋或右旋，或者左右旋的組合。

前面的動畫展示了一個特定的左旋和一個特定的右旋。

但總的來說，左旋和右旋的操作就像下面的動畫所示。

請注意子樹是如何改變其父節點的。在旋轉過程中，子樹透過這種方式改變父節點，以保持正確的有序遍歷，並維持 BST 的屬性，即樹中所有節點，左子節點都小於右子節點。

同時也要記住，並非總是根節點會失去平衡並需要旋轉。

平衡因子

節點的平衡因子是子樹高度的差值。

子樹的高度儲存在 AVL 樹中每個節點的子樹高度中，平衡因子是根據其子樹高度計算的，以檢查樹是否失去平衡。

子樹的高度是子樹根節點與該子樹中最深葉節點之間的邊數。

讓我們仔細看看 AVL 樹可以執行的四種不同型別的旋轉操作，以重新獲得平衡。

四種“失衡”情況

當僅一個節點的平衡因子小於 -1 或大於 1 時，該樹被視為失衡，需要進行旋轉以恢復平衡。

AVL 樹失衡有四種不同的情況，每種情況都需要不同的旋轉操作。

請參閱下面的動畫和解釋。

左-左 (LL) 情況

發現失衡的節點呈左重，並且該節點的左子節點也呈左重。

當發生 LL 情況時，對失衡節點進行單次右旋就足以恢復平衡。

逐步執行下面的動畫，以檢視 LL 情況，以及如何透過單次右旋恢復平衡。

當你逐步執行上面的動畫時，發生了兩次 LL 情況。

1. 當插入 D 時，Q 的平衡因子變為 -2，這意味著樹失衡。這是 LL 情況，因為失衡節點 Q 及其左子節點 P 都呈左重（負平衡因子）。在節點 Q 處進行單次右旋可以恢復樹的平衡。
2. 在插入 L、C 和 B 節點後，P 的平衡因子為 -2，這意味著樹失衡。這也是 LL 情況，因為失衡節點 P 及其左子節點 D 都呈左重。單次右旋可以恢復平衡。

右-右 (RR) 情況

當一個節點失衡且呈右重，而其右子節點也呈右重時，就會發生右-右情況。

在 RR 情況中，對失衡節點進行單次左旋足以恢復平衡。

上面的動畫中發生了兩次 RR 情況。

1. 當插入節點 D 時，A 變得失衡，並且 A 和 B 都呈右重。在節點 A 處進行左旋可以恢復樹的平衡。
2. 在插入 E、C 和 F 節點後，節點 B 變得失衡。這是 RR 情況，因為節點 B 及其右子節點 D 都呈右重。左旋可以恢復樹的平衡。

左-右 (LR) 情況

左-右情況是指失衡節點呈左重，但其左子節點呈右重。

在這種 LR 情況中，首先對左子節點進行左旋，然後對原始失衡節點進行右旋。

逐步執行下面的動畫，以檢視左-右情況可能如何發生，以及如何執行旋轉操作來恢復平衡。

在你構建上面動畫中的 AVL 樹時，左-右情況發生了 2 次，並且需要執行旋轉操作來恢復平衡。

1. 當插入 K 時，節點 Q 因平衡因子為 -2 而失衡，所以它是左重的，而其左子節點 E 是右重的，因此這是左-右情況。
2. 在插入 C、F 和 G 節點後，節點 K 變得失衡且呈左重，其左子節點 E 呈右重，因此這是左-右情況。

右-左 (RL) 情況

右-左情況是指失衡節點呈右重，而其右子節點呈左重。

在這種情況下，我們首先對失衡節點的右子節點進行右旋，然後對失衡節點本身進行左旋。

逐步執行下面的動畫，以檢視右-左情況可能如何發生，以及如何執行旋轉來恢復平衡。

插入節點 B 後，我們得到一個右-左情況，因為節點 A 變得失衡且呈右重，而其右子節點呈左重。為了恢復平衡，首先在節點 F 上執行右旋，然後在節點 A 上執行左旋。

下一個右-左情況發生在插入 G、E 和 D 節點後。這是一個右-左情況，因為 B 失衡且呈右重，而其右子節點 F 呈左重。為了恢復平衡，首先在節點 F 上執行右旋，然後在節點 B 上執行左旋。

在 AVL 樹中回溯

在 AVL 樹中插入或刪除節點後，樹可能會失去平衡。為了確定樹是否失衡，我們需要更新所有祖先節點的高度並重新計算它們的平衡因子。

這個過程稱為回溯，透過遞迴處理。當插入或刪除後遞迴呼叫返回到根節點時，每個祖先節點的高度都會被更新，並重新計算平衡因子。如果發現任何祖先節點的平衡因子超出 -1 到 1 的範圍，則在該節點執行旋轉以恢復樹的平衡。

在下面的模擬中，在插入節點 F 後，節點 C、E 和 H 都失衡，但由於回溯是透過遞迴處理的，因此首先發現並修復節點 H 的失衡，在這種情況下，這也修復了節點 E 和 C 的失衡。

在插入節點 F 後，程式碼將回溯，在向上傳播到根節點的過程中計算平衡因子。當到達節點 H 並計算出平衡因子 -2 時，將執行右旋。僅當完成此旋轉後，程式碼才會繼續回溯，計算祖先節點 E 和 C 上方的平衡因子。

由於進行了旋轉，節點 E 和 C 的平衡因子與插入節點 F 之前的情況保持不變。

AVL 插入節點實現

此程式碼基於前一頁關於插入節點的 BST 實現。

與 BST 相比，AVL 樹的每個節點只有一個新屬性，那就是高度，但由於 AVL 樹的自平衡機制，AVL 樹實現需要許多新函式和額外的程式碼行。

下面的實現根據一個字元列表構建 AVL 樹，以建立上面模擬中的 AVL 樹。插入的最後一個節點“F”也觸發了右旋，就像上面的模擬一樣。

class TreeNode:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
        self.height = 1

def getHeight(node):
    if not node:
        return 0
    return node.height

def getBalance(node):
    if not node:
        return 0
    return getHeight(node.left) - getHeight(node.right)

def rightRotate(y):
    print('Rotate right on node',y.data)
    x = y.left
    T2 = x.right
    x.right = y
    y.left = T2
    y.height = 1 + max(getHeight(y.left), getHeight(y.right))
    x.height = 1 + max(getHeight(x.left), getHeight(x.right))
    return x

def leftRotate(x):
    print('Rotate left on node',x.data)
    y = x.right
    T2 = y.left
    y.left = x
    x.right = T2
    x.height = 1 + max(getHeight(x.left), getHeight(x.right))
    y.height = 1 + max(getHeight(y.left), getHeight(y.right))
    return y

def insert(node, data):
    if not node:
        return TreeNode(data)

    if data < node.data:
        node.left = insert(node.left, data)
    elif data > node.data:
        node.right = insert(node.right, data)

    # Update the balance factor and balance the tree
    node.height = 1 + max(getHeight(node.left), getHeight(node.right))
    balance = getBalance(node)

    # Balancing the tree
    # Left Left
    if balance > 1 and getBalance(node.left) >= 0:
        return rightRotate(node)

    # Left Right
    if balance > 1 and getBalance(node.left) < 0:
        node.left = leftRotate(node.left)
        return rightRotate(node)

    # Right Right
    if balance < -1 and getBalance(node.right) <= 0:
        return leftRotate(node)

    # Right Left
    if balance < -1 and getBalance(node.right) > 0:
        node.right = rightRotate(node.right)
        return leftRotate(node)

    return node

def inOrderTraversal(node):
    if node is None:
        return
    inOrderTraversal(node.left)
    print(node.data, end=", ")
    inOrderTraversal(node.right)

# Inserting nodes
root = None
letters = ['C', 'B', 'E', 'A', 'D', 'H', 'G', 'F']
for letter in letters:
    root = insert(root, letter)

inOrderTraversal(root)

AVL 刪除節點實現

當刪除一個非葉子節點時，AVL 樹需要 minValueNode() 函式來查詢節點的下一個節點（按有序遍歷）。這與在二叉搜尋樹中刪除節點相同，如前一頁所述。

要在 AVL 樹中刪除節點，與插入節點所需的程式碼一樣，也需要相同的程式碼來恢復平衡。

def minValueNode(node):
    current = node
    while current.left is not None:
        current = current.left
    return current

def delete(node, data):
    if not node:
        return node

    if data < node.data:
        node.left = delete(node.left, data)
    elif data > node.data:
        node.right = delete(node.right, data)
    else:
        if node.left is None:
            temp = node.right
            node = None
            return temp
        elif node.right is None:
            temp = node.left
            node = None
            return temp

        temp = minValueNode(node.right)
        node.data = temp.data
        node.right = delete(node.right, temp.data)

    if node is None:
        return node

    # Update the balance factor and balance the tree
    node.height = 1 + max(getHeight(node.left), getHeight(node.right))
    balance = getBalance(node)

    # Balancing the tree
    # Left Left
    if balance > 1 and getBalance(node.left) >= 0:
        return rightRotate(node)

    # Left Right
    if balance > 1 and getBalance(node.left) < 0:
        node.left = leftRotate(node.left)
        return rightRotate(node)

    # Right Right
    if balance < -1 and getBalance(node.right) <= 0:
        return leftRotate(node)

    # Right Left
    if balance < -1 and getBalance(node.right) > 0:
        node.right = rightRotate(node.right)
        return leftRotate(node)

    return node

AVL 樹的時間複雜度

看看下面的不平衡二叉搜尋樹。搜尋“M”意味著必須比較除 1 之外的所有節點。但是，在下面的 AVL 樹中搜索“M”只需要訪問 4 個節點。

因此，在最壞情況下，像搜尋、插入和刪除這樣的演算法必須遍歷整個樹的高度。這意味著使用 AVL 樹保持樹的低高度（\(h\)) 可以帶來更低的執行時。

請參閱下面二叉搜尋樹和 AVL 樹之間時間複雜度的比較，以及時間複雜度如何與樹的高度 (\(h\)) 和樹中的節點數 (\(n\)) 相關。

• BST 不會自動平衡。這意味著 BST 可能非常不平衡，幾乎像一個長鏈，高度幾乎與節點數相同。這使得像搜尋、刪除和插入節點這樣的操作變慢，時間複雜度為 \(O(h) = O(n)\)。
• 然而，AVL 樹是自平衡的。這意味著樹的高度被保持在最低水平，因此搜尋、刪除和插入節點等操作更快，時間複雜度為 \(O(h) = O( \log n)\)。

\(O( \log n)\) 解釋

具有 \(h\) 高度和 \(n\) 個節點的 AVL 樹的搜尋、插入和刪除的時間複雜度為 \(O(h) = O( \log n)\) 這個事實可以這樣解釋：

想象一棵完美的二叉樹，除了最低級別外，所有節點都有兩個子節點，就像下面的 AVL 樹一樣。

這種 AVL 樹中每個級別的節點數是

\[1, 2, 4, 8, 16, 32, ..\]

這與

\[2^0, 2^1, 2^2, 2^3, 2^4, 2^5, ..\]

要獲得高度 \(h=3\) 的完美二叉樹中的節點數 \(n\)，我們可以將每個級別的節點數相加

\[n_3=2^0 + 2^1 + 2^2 + 2^3 = 15\]

這實際上與

\[n_3=2^4 - 1 = 15\]

對於更大的樹也是如此！例如，如果我們想獲得高度 \(h=5\) 的樹中的節點數 \(n\)，我們可以這樣計算節點數

\[n_5=2^6 - 1 = 63\]

所以總的來說，一棵完美二叉樹的高度 \(h\) 與其中的節點數 \(n\) 之間的關係可以表示為

\[n_h = 2^{h+1} - 1\]

我們知道 AVL 樹中搜索、刪除或插入節點的時間複雜度是 \(O(h)\)，但我們想論證的是時間複雜度實際上是 \(O(\log(n))\)，所以我們需要找出由節點數 \(n\) 描述的高度 \(h\)。

\[ \begin{equation} \begin{aligned} n & = 2^{h+1}-1 \\ n+1 & = 2^{h+1} \\ \log_2(n+1) & = \log_2(2^{h+1}) \\ h & = \log_2(n+1) - 1 \\ \\ O(h) & = O(\log{n}) \end{aligned} \end{equation} \]

上面最後一行是如何推匯出來的可能不明顯，但對於具有大量節點（大 \(n\)) 的二叉樹，當我們考慮時間複雜度時，“+1”和“-1”項並不重要。有關如何使用大 O 符號計算時間複雜度的更多詳細資訊，請參閱此頁面。

上面的數學表明，AVL 樹的搜尋、刪除和插入操作的時間複雜度 \(O(h)\) 實際上可以表示為 \(O(\log{n})\)，這很快，比 BST 的時間複雜度 \(O(n)\) 快得多。

DSA 練習

透過練習來測試自己

練習

下面的 AVL 樹中，每個節點都與其平衡因子一起顯示。

什麼是平衡因子？

The balance factor is the 
difference between each node's 
left and right subtree .

提交答案 »

開始練習