紅黑樹的特性與優點

紅黑樹是一種自平衡的二叉搜索樹，通過額外的顏色標記和平衡性約束，確保樹的高度始終保持在 O(log n)。其核心特性如下：

1. 每個節點要么是紅色，要么是黑色。
2. 根節點和葉子節點（NIL節點）是黑色。
3. 紅色節點的子節點必須是黑色（不能有兩個連續的紅色節點）。
4. 從任一節點到其每個葉子的路徑都包含相同數目的黑色節點（黑高平衡）。

這些特性使得紅黑樹在插入、刪除時通過顏色調整和旋轉操作維持平衡，避免了BST的退化問題。

順序插入12345

       2(B)/   \1(B)  4(B)/ \3(R)5(R)

步驟解釋：

1. 插入1：根節點，設為黑色。

   • 1(B)

2. 插入2：作為1的右子節點，設為紅色。無沖突。

     1(B)\2(R)
   

3. 插入3：作為2的右子節點，設為紅色。此時父節點2（紅）與子節點3（紅）沖突。

   • 調整：左旋祖父節點1，將2提升為根并設為黑色，1和3設為紅色。

       2(B)/   \1(R)  3(R)
   

4. 插入4：作為3的右子節點，設為紅色。父節點3（紅）與子節點4（紅）沖突。

   • 調整：顏色翻轉（父節點3和叔叔節點1變黑，祖父節點2變紅），最后根保持黑色。

       2(B)/   \1(B)  3(B)\4(R)
   

5. 插入5：作為4的右子節點，設為紅色。父節點4（紅）與子節點5（紅）沖突。

   • 調整：左旋祖父節點3，將4設為黑色，3設為紅色。

       2(B)/   \1(B)  4(B)/ \3(R)5(R)
   

驗證規則：

• 根為黑色：滿足。
• 紅色節點無紅色子節點：3?和5?的子節點均為NIL（黑）。
• 所有路徑黑色節點數相同：每條路徑均為2個黑色節點（例如：2→1→NIL 或 2→4→3→NIL）。

該結構嚴格遵循紅黑樹的五條性質，是一棵有效的紅黑樹。