樹的平衡：AVL樹

4.1 不平衡樹的問題

在普通（不平衡）的樹中，添加元素可能會帶來不愉快的效果。

1. 樹的高度增加：

在不平衡的樹中，樹的高度可能達到 n（n 是節點的數量），這會導致性能下降。

主要操作（搜尋、插入、刪除）的執行時間在最壞情況下變為 O(n)。

2. 節點分佈不均：

在不平衡的樹中，一些子樹可能包含明顯比其他子樹更多的節點，導致記憶體使用效率低下和處理時間增加。

3. 操作時間惡化：

在不平衡的樹中，搜尋、插入和刪除操作需要更長的時間，因為樹的高度增加。

不平衡樹的例子：

在這個例子中，樹實際上變成了一個鏈表，操作時間變為線性。

4.2 AVL樹的定義及其特性

AVL樹（以其發明者Adelson-Velsky和Landis命名）是一種平衡的二元搜尋樹，其中任何節點的左、右子樹的高度差不超過1。

AVL樹的特性：

1. 平衡：

任何節點的左、右子樹的高度差不超過1。

這確保了樹的高度為 O(log n)，其中 n 是節點的數量，保證搜尋、插入和刪除操作的有效執行。

2. 二元搜尋樹：

AVL樹具有所有二元搜尋樹的特性：對於任何節點，左子樹的所有鍵值都小於該節點的鍵值，而右子樹的所有鍵值都大於該節點的鍵值。

3. 自動平衡：

在每次插入或刪除操作後進行樹的平衡，以保持其特性。

4.3 樹的平衡範例

旋轉是用來在插入或刪除節點後恢復AVL樹的平衡的操作。共有四種旋轉：左旋、右旋、左-右旋和右-左旋。

1. 左旋 (Left Rotation)：

在左旋中，節點 x 向上移動，而其右子節點 y 成為其父節點。y 的左子樹成為 x 的右子樹。

2. 右旋 (Right Rotation)：

在右旋中，節點 x 向上移動，而其左子節點 y 成為其父節點。y 的右子樹成為 x 的左子樹。

3. 左-右旋 (Left-Right Rotation)：

先對左子節點進行左旋，然後對節點本身進行右旋。

4. 右-左旋 (Right-Left Rotation)：

先對右子節點進行右旋，然後對節點本身進行左旋。

4.4 AVL樹的基本操作

AVL樹的基本操作包括插入、刪除和搜尋。

插入 (Insertion)

需要將新節點插入AVL樹並在必要時使其平衡。

步驟：

1. 插入節點：
   • 從樹的根節點開始，遞迴找到新節點的合適位置，將其值與當前節點比較。
   • 像在普通二元搜尋樹中一樣，將新節點插入找到的位置。
2. 更新高度：
   • 插入後，更新從新節點到根的所有節點的高度。
3. 平衡樹：
   • 檢查從新節點到根的每個節點的平衡。
   • 如果某個節點的平衡被破壞（左、右子樹的高度差大於1），則執行相應的旋轉以恢復平衡。

範例：

2. 刪除 (Deletion)

需要從AVL樹中刪除節點並在必要時使其平衡。

步驟：

1. 搜尋並刪除節點：

• 從樹的根節點開始，遞迴尋找要刪除的節點。
• 像在普通二元搜尋樹中一樣刪除節點：
• 如果節點是葉子，直接刪除它。
• 如果節點有一個子節點，用其子節點替換節點。
• 如果節點有兩個子節點，在右子樹中找到最小的節點（或在左子樹中找到最大的），將其值複製到要刪除的節點，然後遞迴刪除右子樹中的最小節點。

2. 更新高度：

• 刪除後，更新從刪除的節點到根的所有節點的高度。

3. 平衡樹：

• 檢查從刪除的節點到根的每個節點的平衡。
• 如果某個節點的平衡被破壞，則執行相應的旋轉以恢復平衡。

範例：

3. 搜尋 (Search)

需要在AVL樹中找到具有指定值的節點。

步驟：

1. 遞迴搜尋：

• 從樹的根節點開始，遞迴將搜尋值與當前節點比較。
• 如果值小於當前節點，則移至左子樹。
• 如果值大於當前節點，則移至右子樹。
• 如果值與當前節點相同，則返回該節點。

範例：