Red-Black Tree
紅黑樹是另一種 balanced tree. 定義如下:
它基本上是一棵 binary search tree, 但每個 node 還漆上了顏色 -- 可以是紅色或黑色.
所有的 leaves 都是空的 (不存資料), 且都是黑色的.
紅色的 node 必定有兩個 children, 且兩個 children 都是黑色的.
從一個 node X 往下走, 每一條通往 leaf 的路徑上遇到的黑色 nodes 都一樣多. 這個固定的數目叫做 X 的 black-height.
直覺解釋: 希望定義出一棵 (黑色的) full binary tree (每個 leaf 所在的深度都一樣), 但這個條件顯然太嚴格, 無法達成 (nodes 數目只能是 2^k - 1). 所以允許有紅色的 nodes 穿插其間. 又, 紅色的 nodes 不可以太多, 以免讓樹太不平衡.
n 個 internal nodes 的紅黑樹 (可以存放 n 筆資料), 它的高度為 Theta(lg n), 所以它是一棵 balanced tree.
查詢資料很簡單; 刪除資料比較麻煩, 但原則與新增相同.
新增或刪除資料時需要用到的一個基本動作: rotation.
y x
/ \ / \
x C <==> A y
/ \ / \
A B B C


圖中 x 與 y 為 nodes; A, B, C 為一整串的 subtrees 注意: 這個動作很小心地保持 binary search tree 的特性 -- 旋轉前後都滿足: (A 內的所有元素) <= x <= (B 內的所有元素) <= y <= (C 內的所有元素). 姑且將這個動作稱為 "以 x-y 為軸, 向左/右旋轉".
新增資料時如何保持 red-black tree 的特性? 先當做一般的 BST, 一路往下找到新資料 x 的落點, 並把 x 塗上紅色, 然後一路往上整修樹:
如果 x 的父親是黑色的, 就太完美了, 完全不需要整修. 結束.
不然的話, x 的父親既是紅色, x 的祖父一定是黑色的. 令 y 表 x 的叔叔. 有以下三種狀況要考慮:
y 也是紅色的: 讓祖/父兩輩「紅黑變色」. 現在 x 是沒有問題了, 但祖父可能變成紅色, 因而產生問題. 所以讓祖父扮演 x 的角色, 繼續往上整修.
y 是黑色的, x 到祖父的路上沒有轉彎: 以「祖父-父親」為軸旋轉, 並調整顏色.
y 是黑色的, x 到祖父的路上有轉彎: 先以「父親-x」為軸旋轉, 變成上個狀況, 再依上個狀況處理.
注意: 第二/三種狀況表示祖父以下還可以容納新的 red node, 所以不需要再往上整修.
結論: 不論是增刪查改, 所需時間皆為 O(lg (n)).