C# 資料結構 - 紅黑樹基本性質與動畫示範 (上)(1)

介紹

紅黑樹由 Rudolf Bayer 1972 年發明，原稱對稱二元 B 樹，1978 年改現名。同 AVL 為平衡二元搜尋樹，透過插入/刪除時的特定操作維持平衡，獲得高效查找。紅黑樹追求局部平衡而非 AVL 的嚴格平衡，複雜度遠高於 AVL。

Silverlight 動畫示範

需安裝 Silverlight 2.0 RTW。支援整數輸入、拖曳控制動畫速度、非法輸入隨機操作。

紅黑樹五大性質

1. 節點顏色僅紅或黑
2. 根節點為黑
3. 葉節點帶兩個空黑節點 (黑哨兵) — 單一子節點時另一側為哨兵
4. 紅節點的兩個子節點必為黑 (路徑無相鄰紅)
5. 任一節點到其子孫葉節點所有路徑包含相同數目黑節點 (黑高度一致)

黑哨兵必要性

左圖無哨兵滿足性質，加入哨兵後葉節點變 8 個，根到各葉黑高度不一，違反性質 5。真正紅黑樹必須包含黑哨兵。