紅黑樹原理詳解（一）：定義、性質與平衡機制

紅黑樹是自平衡二叉搜索樹的經典實現，廣泛應用於C++ STL的map/set、Java的TreeMap、Linux內核的rb_root等核心組件。本文從二叉搜索樹的缺陷切入，層層剖析紅黑樹的五大性質與平衡維護邏輯。

一、 為什麼需要紅黑樹？

普通二叉搜索樹（BST）在最壞情況下（如有序插入）會退化為鏈表，查找/插入/刪除時間複雜度惡化至O(N)。根因在於樹缺乏平衡約束。紅黑樹通過引入「顏色」屬性與五條嚴格性質，保證樹高不超過2log₂(N+1)，所有關鍵操作穩定在O(log N)。

二、 紅黑樹節點結構

除BST通用的key、left、right、parent指標外，每個節點新增一個color屬性（紅/黑）。為了統一邊界處理，紅黑樹引入哨兵節點（NIL）：所有葉子節點的left/right、根節點的parent均指向同一個黑色NIL節點，而非NULL。

三、 五大核心性質

1. 二色性：節點非紅即黑。
2. 根黑性：根節點必為黑色。
3. 葉黑性：所有NIL葉節點為黑色。
4. 紅不相鄰：紅色節點的兩個子節點必為黑色（即不存在連續紅節點）。
5. 黑高一致：從任一節點到其所有後代葉節點的路徑上，黑色節點數量相同（稱為黑高）。

性質4與5共同約束了「最長路徑不超過最短路徑的2倍」，這是紅黑樹平衡的數學基石。

四、 平衡維護：旋轉與重新著色

插入/刪除節點後，可能違背上述性質。恢復手段只有兩種：

• 變色：改變節點顏色（紅↔黑）。
• 旋轉：局部調整指標結構，包含左旋與右旋，時間複雜度O(1)。

左旋以x → y邊為軸，使y上升為新子樹根，x成為y左孩子，y原左孩子轉為x右孩子；右旋對稱。旋轉不改變中序遍歷順序，故保持BST有序性。

下篇將詳細拆解插入修復的三種情況與刪除修復的四種情況，配合圖解與偽代碼，帶你徹底掌握紅黑樹核心算法。