圖解紅黑樹原理與 Java 實現遍歷終止技巧

紅黑樹核心概念

紅黑樹是資料結構與演算法課程中常被提及、面試必考的平衡二叉搜尋樹，但教科書與網路資料往往枯燥難懂。本文將以圖解方式深入淺出地說明紅黑樹的插入、刪除操作，並探討 Java 中如何優雅地終止樹的遍歷。

從二叉樹到紅黑樹的演進

二叉樹中每個非葉節點最多擁有左右兩個孩子。二叉搜尋樹（BST）在此基礎上要求：左子樹所有節點值小於根節點，右子樹值大於根節點。為避免退化成鏈表，引入平衡機制，如 AVL 樹、Treap、伸展樹與紅黑樹。紅黑樹在 BST 基礎上為每個節點增加顏色屬性（紅/黑），透過五大性質約束路徑長度，確保最長路徑不超過最短路徑的兩倍，達到「近似平衡」。

紅黑樹五大性質

• 節點非紅即黑
• 根節點為黑
• 所有葉節點（NIL）為黑
• 紅節點的孩子必為黑（不允許連續紅節點）
• 任一節點到其所有子孫葉節點的路徑包含相同數量的黑節點

注意：紅黑樹將傳統二叉樹葉節點的空指針替換為 NIL 節點，NIL 含指向父節點的指針，便於操作。

插入操作詳解

新節點初始著紅，按 BST 方式插入葉子位置，再透過重新著色與旋轉修復性質，分三種情況：

情況 1：新節點為根節點

直接改為黑色。

情況 2：父節點為黑

無需調整，性質自動滿足。

情況 3：父節點為紅（違反性質 4）

需根據叔父節點顏色處理（以父節點為左孩子為例，右孩子對稱）：

3.1 叔父節點為紅

父、叔改黑，祖父改紅。此舉保持祖父到葉子的黑節點數不變，但祖父變紅可能導致其父也是紅，需遞向上檢查修復。

3.2 叔父節點為黑

• 新節點為左孩子：父改黑、祖父改紅、對祖父右旋。
• 新節點為右孩子：先對父左旋轉化為左孩子情況，再按上述處理。

刪除操作詳解

刪除黑節點會導致路徑黑高度減少，需透過「額外黑色」上移修復。本文採用直觀分類法：

1. 被刪節點 D 兩孩子皆為 NIL

• D 為紅：直接用 NIL 替換。
• D 為黑：視兄弟節點 B 孩子情況分三種子情況，透過重新著色與旋轉修復黑高度平衡。

2. 被刪節點 D 兩孩子皆非 NIL

找後繼節點 S 交換內容（顏色不變），轉化為刪除 S，遞歸處理至孩子為 NIL 情況。

3. 被刪節點 D 有一孩子非 NIL

該孩子必為紅（否則違反性質 5），交換內容後轉化為情況 1。

二叉樹遍歷與 Java 實現

二叉樹遍歷分前序（根左右）、中序（左根右）、後序（左根右）。每種均有遞歸與迭代兩種實現。

節點定義

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    public TreeNode(int x) { val = x; }
}

前序遍歷

遞歸：訪問根 → 遞歸左 → 遞歸右。
迭代：借助棧，先壓右再壓左，彈出即訪問順序。

中序遍歷

遞歸：遞歸左 → 訪問根 → 遞歸右。
迭代：用 curr 指針沿左邊緣入棧，彈出訪問後轉向右子樹；curr==null 表示左子樹已遍歷完。

後序遍歷

遞歸：遞歸左 → 遞歸右 → 訪問根。
迭代（標記法）：用 pre 記錄上一訪問節點，判斷當前節點孩子是否已訪問。
迭代（反轉法）：修改前序為「根右左」，最後反轉結果即得「左右根」。

總結

遞歸實現最簡潔；前序迭代最易寫；中序迭代需雙重循環條件；後序迭代轉化為前序反轉最優雅。掌握這些模板，面試與工程實踐皆得心應手。