紅黑樹是一種特殊的二叉搜索樹，它通過顏色標記和一系列規則來保證樹的平衡，從而讓插入、刪除、查找等操作都能在近似O(log n)的時間複雜度內完成。對於初學者來說，理解紅黑樹的核心規則是關鍵，下面我們一步步拆解它的“平衡密碼”。
爲什麼需要紅黑樹？¶
普通的二叉搜索樹在插入有序數據時會退化成鏈表（比如按1、2、3、4、5順序插入，樹會變成一條向右的鏈），此時查找時間複雜度會從O(log n)退化爲O(n)。爲了解決這個問題，我們需要一種“自平衡”的二叉搜索樹——紅黑樹就是其中的經典代表。它通過給節點塗顏色（紅/黑）和嚴格的規則約束，讓樹始終保持近似平衡狀態。
紅黑樹的5條核心規則¶
紅黑樹的每個節點有一個顏色屬性（紅或黑），加上以下5條規則，共同保證了樹的平衡：
規則1：每個節點要麼是紅色，要麼是黑色¶
最簡單的顏色標記，沒有其他顏色。
規則2：根節點必須是黑色¶
根節點固定爲黑色，避免“根節點是紅色”導致後續路徑的黑高不一致。
規則3：所有空葉子節點（NIL節點）被視爲黑色¶
在畫圖或代碼中，我們通常用NIL表示空的子節點（比如葉子節點的左右子節點），這些NIL節點本身也是黑色的。這是爲了統一規則——所有路徑都從實際節點到NIL節點，無需單獨處理葉子的顏色。
規則4：如果一個節點是紅色的，則它的兩個子節點必須是黑色¶
紅色節點不能有紅色的子節點。
舉個例子：如果父節點是紅色，那麼左孩子和右孩子必須是黑色（如圖1）；如果父節點是黑色，子節點可以是紅色或黑色。
（圖示：紅色節點下掛兩個黑色子節點）
爲什麼？ 避免連續兩個紅色節點，否則會導致“紅色鏈”，破壞平衡。
規則5：從任一節點到其所有後代NIL節點的路徑上，黑色節點的數量必須相同¶
這條規則定義了“黑高”的一致性：從根到葉子的所有路徑中，黑色節點的數量（稱爲“黑高”）必須相等。
舉個例子：假設從根節點到某個葉子的路徑上有3個黑色節點，那麼所有其他路徑的黑高也必須是3。
爲什麼？ 黑高相等意味着樹的最長路徑（由紅黑交替組成）不會比最短路徑長太多，從而保證樹的高度穩定在O(log n)。
規則如何保證平衡？¶
這5條規則共同作用，讓紅黑樹“近似平衡”：
- 規則4 阻止了連續紅色節點，確保紅色節點不會形成“紅色塊”；
- 規則5 強制所有路徑的黑高一致，最長路徑最多是最短路徑的2倍（黑高相等，紅節點可以穿插在黑色節點之間）。
最終，紅黑樹的高度被限制在2倍log n（n爲節點數），因此查找、插入、刪除的時間複雜度都穩定在O(log n)。
插入節點時的調整邏輯¶
插入新節點時，我們先按二叉搜索樹規則找到插入位置，然後將新節點標記爲紅色（規則2允許根是黑色，其他節點默認紅色更安全，因爲紅色節點不能有紅色子節點，初始插入紅色更容易滿足規則4）。但此時可能違反規則4或規則5，需要調整：
情況1：新節點是紅色，但父節點是黑色
此時不違反任何規則，直接插入即可（父節點黑色，子節點紅色，滿足規則4）。
情況2：新節點是紅色，父節點也是紅色
此時違反規則4（父紅子紅），需要調整：
- 步驟1：將父節點設爲黑色（避免父紅）；
- 步驟2：如果祖父節點是黑色，則將祖父節點設爲紅色（因爲祖父節點是黑色，不違反規則4）；
- 步驟3：如果祖父節點是紅色（此時祖父節點的父節點可能是紅色，需要遞歸調整），則可能需要旋轉（左/右旋轉）或重新着色。
（注：具體旋轉操作需根據父節點和叔叔節點的顏色決定，此處不深入細節，但核心是通過調整顏色和旋轉，讓樹重新滿足所有規則。）
紅黑樹的應用場景¶
紅黑樹因爲平衡穩定、插入刪除靈活，被廣泛應用於需要高效有序操作的場景：
- Java的TreeMap/TreeSet：基於紅黑樹實現，保證鍵值對的有序性和快速插入刪除；
- Redis的有序集合（Sorted Set）：用紅黑樹維護有序數據，支持範圍查詢；
- Linux的進程調度：用於維護進程優先級的有序結構。
總結¶
紅黑樹通過5條規則（顏色標記+黑高一致）實現自平衡，它不需要嚴格限制樹的高度（如AVL樹的高度差），而是通過“避免連續紅節點”和“強制黑高一致”來平衡樹的結構。這讓它在插入、刪除、查找操作中都能保持高效，成爲平衡二叉搜索樹的經典方案。理解這些規則，你就能明白紅黑樹“平衡”的本質——用顏色約束和黑高一致性，在效率和穩定性之間找到完美平衡點。