2-3樹與紅黑樹筆記

概述

2-3樹和紅黑樹都是常見的平衡搜索樹，用於在插入、刪除和查找操作中保持時間複雜度為 O(log n)，這兩種樹結構的主要目標都是確保樹的高度平衡，避免極端情況（如偏斜樹）影響操作效率，然而它們的實現方式、結構特性以及操作流程各有不同。
學習影片：https://www.youtube.com/watch?v=pXpPXsTOADI

• 2-3樹：一種多路平衡搜索樹（Multi-way Balanced Search Tree），每個節點可以有 2 個或 3 個子節點。它透過節點的合併與分裂來保持平衡性。
• 紅黑樹（Red-Black Tree）：一種特殊的二元搜索樹（Binary Search Tree），透過給每個節點標記紅色或黑色來表示平衡狀態，紅黑樹是 2-3樹的變體，保留了類似的平衡性特性。

節點結構與性質

2-3樹的結構：

• 2-3樹的每個節點可以是 2 節點或 3 節點。
  • 2 節點：包含 1 個鍵和 2 個子節點。
  • 3 節點：包含 2 個鍵和 3 個子節點。
• 所有葉節點的深度相同，即所有的路徑長度相等。
• 插入或刪除時，如果節點超過了 3 節點，則分裂成 2 個節點，並將中間鍵值提升到父節點。

紅黑樹的結構：

• 紅黑樹是一種二元樹，每個節點都有一個顏色屬性（紅色或黑色），以保持樹的平衡性。
• 紅黑樹必須滿足以下 5 個特性：
  1. 每個節點不是紅色就是黑色。
  2. 根節點必須是黑色。
  3. 任何紅色節點的子節點必須是黑色（即不能出現連續的紅色節點）。
  4. 從根節點到每個葉節點的路徑中，必須包含相同數量的黑色節點（稱為黑色高度）。
  5. 每個葉節點都是黑色（可以視為包含 None 的虛擬葉節點）。

插入與刪除操作的差異

2-3樹的插入與刪除：

• 插入時，若插入點所在節點為 3 節點，則節點會分裂成兩個 2 節點，並將中間鍵值上升到父節點中。這個過程可能會反覆進行，直到根節點（導致樹的高度增加）或操作結束。
• 刪除時，如果刪除某節點後子節點數量不平衡，則會合併或旋轉子節點來恢復平衡。這通常會涉及到與兄弟節點的合併或向父節點借用鍵值。

紅黑樹的插入與刪除：

• 插入時，新節點總是以紅色節點的方式插入，然後透過「變色」或「旋轉」操作來維持紅黑樹的 5 個特性。如果插入後違反了紅黑樹的規則（例如紅色節點的子節點也是紅色），則需要透過變色或旋轉來修正。
• 刪除時，如果刪除的節點為黑色，則可能會打破紅黑樹的平衡性。這時需要進行「變色」、「雙黑」補償及「旋轉」來重新平衡樹的結構。

操作效率與特性比較

兩者的轉換關係

紅黑樹實際上是一種 2-3 樹的變體，這意味著紅黑樹可以通過「變色」和「旋轉」來模擬 2-3 樹的分裂與合併操作。具體而言：

• 紅黑樹的紅色節點可以視為 2-3 樹的 3 節點內的一部分，通過紅色節點的移動（旋轉）和變色，紅黑樹能模擬 2-3 樹的節點分裂和合併，從而達到類似的平衡性。
• 2-3 樹的分裂操作對應於紅黑樹的右旋轉和顏色變換；而 2-3 樹的合併則對應於紅黑樹的左旋轉與重新分配顏色。

使用場景與選擇建議

• 2-3 樹：
  • 適合於需要多路平衡結構的場景，如資料庫索引或文件系統的管理。
  • 當你需要更高效地處理多鍵值節點或在節點間進行快速切換時，2-3 樹是更佳的選擇。
• 紅黑樹：
  • 適合用於一般編程中，如 STL 的 map 和 set 容器（C++ 中的紅黑樹實現）。
  • 當你的應用場景不需要處理多路節點（如 3 節點）時，紅黑樹更為簡單易用。
  • 由於紅黑樹的操作主要是基於變色和旋轉，相比 2-3 樹的分裂與合併，維護起來相對簡單。

總結

2-3 樹和紅黑樹都是平衡搜索樹，但由於結構與維護方式的不同，它們在實際應用中各有優劣。2-3 樹提供了更直觀的平衡操作，但維護成本較高；紅黑樹則透過顏色和旋轉來簡化平衡過程，適合於常見的二元樹應用。理解這兩者的關係與轉換，有助於選擇最合適的樹結構來應對不同的需求場景。