理解進階資料結構（二）：AVL樹 ｜紅黑樹

前一篇提到B樹和B+樹，這篇介紹AVL 樹和經典的紅黑樹。

在開始之前，可以看個輕鬆的影片，對於紅黑樹在真實商業案例的應用更有印象

學習資料結構、演算法在工作上真的有用嗎? 實際工作經歷不藏私! | 二元樹 | 雜湊 | 計算機概論 | 工程師 Nic

AVL Tree 資料結構

AVL tree 也是一種二元搜尋自平衡樹 Binary Search Tree (BST) ，他的名字由來是由Georgy Adelson-Velsky 和 Evgenii Landis 兩位共同發表，故稱 AVL 樹。

• 特性：當樹失去平衡（左右子節點的高度差超過 1），AVL 樹會自動透過旋轉操作進行調整，維持樹的平衡性。
• 限制與規則：在每個插入或刪除操作後，必須檢查並維持樹的平衡，透過「左旋」、「右旋」、「左右旋」和「右左旋」來重新調整高度。每個節點的左右子樹高度差不能超過 1。
• 應用：例如通訊錄管理、遊戲排行榜等，因為高度平衡的結構可以確保查找效率。

AVL 的操作

• 新增：Insertion
• 刪除：Deletion
• 搜尋：Searching （跟二元搜尋樹很像）

子樹們的旋轉方式：

1. 左旋 Left Rotation:

如果在右邊新增資料，使整個樹不平衡，樹就會啟動左旋模式。

2. 右旋 Right Rotation:

如果新增的資料是向左偏移，已違反節點左右正負 1 的原則，就必須向右旋轉。

3. 左右旋 Left-Right Rotation:

在沒有偏向任何一邊的情況下，但是左右子節點的高度差超過 1 先將最下面偏右的節點往右，再把往左旋轉。

4. 右左旋 Right-Left Rotation:

AVL 樹的優點：

1. 不管是搜尋、刪除、新增的時間複雜度都是 O(Log n) 。
2. 自平衡的條件限制比紅黑樹更嚴苛，AVL 樹通常高度較低，搜尋速度也較快。
3. AVL 樹比紅黑樹更容易理解跟應用。

AVL 樹的缺點：

1. 比一般的二元搜尋樹難應用（但比紅黑樹簡單）。
2. 在業界實務的頻率比紅黑樹少。
3. 因為限制條件嚴苛，所以新增跟刪除資料要大規模變化樹的形狀。

AVL 樹的應用：

1. 教學用XD 因為 AVL 樹相較紅黑樹較容易讓學生理解，所以是資料庫的入門課程
2. 需要頻繁查找數據以及執行其他二元搜尋樹（BST）的操作，例如有序遍歷( Sorted Traversal) 最小值和最大值）時，可以考慮使用這些結構。Sorted Traversal（有序遍歷）指的是按照數據從小到大（或從大到小）的順序來遍歷二元搜尋樹（BST, Binary Search Tree）中的所有節點。
3. 紅黑樹較常用於程式語言的標準函式庫中，例如 C++ 中的 map 和 set，以及 Java 中的 TreeMap 和 TreeSet。
4. AVL 樹則適合應用在對即時性有要求的場景，這些場景需要預測性和穩定的性能表現。

紅黑樹 Red-Black Tree

前面一直拿紅黑樹跟 AVL 樹比較，到底什麼是紅黑樹呢？

Red-black trees in 4 minutes — Intro

• 特性：紅黑樹是一種二元搜尋樹，透過標記每個節點為紅或黑色，並維持特定規則以保持樹的平衡。
• 限制與規則：紅黑樹遵守五個紅黑規則：
• 1. 每個節點（node）是紅色或黑色。
  2. Root 和 Leaves（NIL 或 NULL節點）必為黑色。
  3. 若節點為紅色，其子節點必為黑色（不允許兩個紅色節點相連）。
  4. 從任何節點到葉節點（NIL 或 NULL節點）的每條路徑，必須包含相同數目的黑色節點。
• 應用：由於其快速調整和查找性能，紅黑樹被應用於需要頻繁查找與插入的場景，例如 Java 的 TreeMap、操作系統排程和網路應用中的快速數據存取。

注意：在紅黑樹中，leaf (葉) 是指 NULL 而非 樹字1、3、5、7、8哦。

限制和規格的範例

下圖就是符合規則的紅黑樹

我們來用 Red-black trees in 5 minutes — Insertions (strategy)

這部影片來解釋紅黑樹是如何插入資料的 （刪除太難了QQ 我這篇先暫時不提）

插入資料 Z （假定是紅色）

Z 的父母節點是 A 叔叔是 D （請先記住這個關係）

咦~~ Z 跟 A都是紅色，這樣違反規則。會有四種情況讓我們重新塗色跟調整

Z 是 Root (根)

• 直接把 Z 塗黑就好

Z 的 uncle 是紅色

• 把所有人都改變顏色

Z 的 uncle 是黑色 (三角形)

Z的 uncle 是黑色 (一條線)

要旋轉祖父母節點，再用父母節點取代。

最後，需要再重新塗原父母和祖父母節點的顏色。

紅黑樹的優點：

• 自平衡: 插入、刪除、搜尋的時間複雜度皆是 O(log n) 。
• 容易應用: 規則限制簡單，所以在實務上廣泛被應用。
• 應用廣泛: 許多的資料結構、地圖使用紅黑樹的概念。

紅黑樹的缺點：

• 較難被初學者理解: 相較於 AVL 樹, 紅黑樹的刪除規則較難理解。
• 額外的負擔Constant overhead: 維持紅黑樹需要額外的操作（例如變更節點顏色、旋轉子樹等）
• 並非所有情況都是最佳解：雖然紅黑樹在大多數操作中效率高，但對於需要頻繁插入和刪除的應用場景來說，紅黑樹可能不是最佳選擇，因為這些額外負擔在頻繁操作下會變得明顯。

紅黑樹的應用:

• 應用在集合（Set）、Map （key-value pair）的結構
• • Map 是一種鍵值對（key-value pair）的結構，例如 { "apple": 1, "banana": 2 }
  • Set 只儲存唯一元素，像 {1, 2, 3}
• Priority Queues（優先佇列）: 造優先程度處理，並非誰先到誰先處理。
• 檔案管理系統
• In-memory Databases（記憶體資料庫）

　資料存在RAM（隨機存取記憶體）中，而不是儲存在硬碟上。這樣做的好處是讀寫速度非常快，因為 RAM 的速度遠高於硬碟。然而，由於 RAM 的容量有限且斷電後資料會消失，in-memory 資料庫適合用於需要快速存取資料的情況。

• 圖像跟遊戲開發