理解進階資料結構（二）：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 資料庫適合用於需要快速存取資料的情況。

• 圖像跟遊戲開發