搜尋樹靠鍵值次序來尋找數據,但次序本身容許整棵樹退化成長鏈。AVL 樹直接限制相鄰子樹的高度;紅黑樹則為每個節點加上一個顏色位元,約束路徑上黑節點的分佈。左右子樹的普通高度未必相同。不過,每條路徑的黑節點數相同,而且紅節點不能連續出現。這兩個條件合起來,便能防止某條路徑無限制地變長。
顏色不屬於集合所儲存的數據:改變顏色不會改變鍵值。它的作用,是提供一個可以在更新附近修復的不變量。本節先證明高度界,再逐步推導插入修復,說明為何一次插入可能沿路重新着色多個祖先,卻最多只需兩次旋轉。刪除需要另一套修復論證,不在本節範圍內。
把空子連結也納入定義
假設鍵值互不相同,並具有一致的全序。每個節點左子樹的鍵都比它小,右子樹的鍵都比它大。插入已存在的鍵不改變集合。普通搜尋只按這些大小關係選擇方向,不需要查看顏色。
定義 15.2.1
(內部節點、外部 NIL 葉與黑高度)
每個儲存鍵值的節點都是內部節點,顏色為紅或黑。每條空子連結在數學上通向一個黑色的外部葉 NIL。程式可以共用一個哨兵物件,但數學樹中每條空連結仍代表一個獨立的外部葉位置。
紅黑搜尋樹須同時滿足以下條件:
- 所有外部
NIL葉都是黑色。 - 非空樹的根是黑色。
- 每個紅色內部節點的子節點都是黑色。
- 對每個內部節點,從它向下到各外部葉的路徑,在離開該節點之後所遇到的黑節點數相同,並計入末端的
NIL。
這個共同數目稱為節點的黑高度 。約定 。因此,內部葉本身不論紅黑,黑高度都是 1。對內部節點 及其任一子節點 ,
指示函數在子節點為黑色時等於 1,包括 NIL;子節點為紅色時等於 0。它補計的是 沒有計入的子節點本身。
兩個內部子節點的黑高度可以不同:黑色子節點還要計入自己的顏色,紅色子節點則不用。必須相等的是沿兩條子連結向下的黑節點總貢獻。黑節點數相等,也不表示兩邊儲存的鍵數相等。
插入修復期間,我們暫時容許根是紅色,或有一個紅節點的父節點也是紅色。這些是中間狀態,並非完成後的合法形式。搜尋次序及路徑黑節點數相等的條件,則會一直保留。
為甚麼顏色能限制搜尋深度
以 表示某子樹的內部節點數;外部葉不計入。設 為根到外部葉的路徑中,最多的邊數;空樹另設 。成功搜尋最多遍歷 個內部節點。失敗搜尋最多比較 個鍵,然後抵達外部葉。
定理 15.2.2
(紅黑樹的高度界)
一棵儲存 個鍵的合法紅黑樹滿足
所以最壞情況的搜尋比較次數為 。
證明
(把黑層數與邊數分開計算)
先對子樹大小作歸納,證明 。在 NIL 處,兩邊都是零。若 是內部節點,兩個子節點的黑高度都至少是 。由歸納假設,
現在考慮非空樹的一條最長根至 NIL 路徑。不計根後,路徑上有 個節點位置,最後一個是黑色 NIL。每個紅節點後面必有黑節點;由於紅節點不能連續,不同紅節點所配對的下一個黑節點也不同。因此至少有 個位置是黑色。它們的數目正是 ,故 。
再結合 ,便得所需高度界。空樹的情況另外直接成立。
這是最壞情況的上界,不是說每次搜尋都要比較同樣多次。紅黑樹的形狀限制可以比 AVL 樹寬鬆,但仍然排除了線性高度的長鏈。
新節點先用紅色,保住黑節點數
先按普通搜尋樹的比較規則找插入位置。如果鍵不存在,就把相應外部葉換成新的紅色節點 ,並讓它有兩個黑色 NIL 子節點。原來經過這條連結的路徑計入一個黑色外部葉;新路徑計入一個紅節點,再計入一個黑色外部葉,所以黑節點數不變。
若 的父節點是黑色,各條件已經成立,唯一例外是 自己可能就是根。最後把根塗黑即可。若父節點 是紅色,便出現紅紅相鄰。插入前根是黑色,而修復迴圈只在父節點為紅色時繼續,所以此時父節點一定有內部祖父節點 。在下面的不變量下, 必為黑色。
父節點的兄弟稱為叔節點 。不存在的叔節點就是黑色 NIL,判斷情況時不能略去它。先分析 在 左邊的情況;另一邊只需把左右完全對調。
常見錯誤
(不存在的叔節點是黑色)
在 10B(5R,-) 中,把 7 插入 5 之下,叔節點是 10 的空右子指標。它是黑色 NIL,因此須先左旋 5,再把 7 染黑、10 染紅,並右旋 10。
證明透視
修復迴圈只保留一個移動中的缺陷
每次迭代開始時, 是紅色。搜尋次序和各路徑黑節點數相等的條件都成立。唯一可能的紅紅相鄰,是 與父節點之間;根也暫時容許是紅色。其他紅節點的子節點都是黑色。
若迴圈執行,父節點便是紅色,因此 不是根。祖父存在而且是黑色:否則父與祖父之間還會有另一條紅紅邊。下面每種修復都會保留這些性質、把唯一可能的缺陷向上移,或把它完全消除。這比「小圖看起來平衡」是一個更具體的正確性保證。
叔節點是紅色:把缺陷移到上面
若 是紅色,把 和 改成黑色,把 改成紅色,然後令 繼續。原來經過這個子樹的每條路徑,計入黑色 和一個紅色子節點;現在則計入紅色 和一個黑色子節點。總黑貢獻不變。
因為 和 原來是紅色,它們的子節點原來都應為黑色,只有涉及 的那條紅紅邊是容許的暫時例外。當 改成黑色,這條邊便不再違規。新改紅的 有黑色子節點,它唯一可能的衝突是與自己的父節點相鄰,剛好成為下一輪所處理的缺陷。如果 是根,迴圈停止,最後把根塗黑即可。
所以,把這個子樹的根 改紅是必要步驟。若只把兩個子節點改黑,卻讓 保持黑色,整個子樹的黑貢獻會增加一。當 不是全樹的根時,祖先另一邊的路徑便可能不再與它相等。
叔節點是黑色:先把三角形變成直線
若叔節點為黑色,而 是左父節點的右子節點,兩條紅連結構成內側三角形。先在 左旋,不改顏色。紅色子節點升為紅色父節點,原來的紅色父節點成為它的左子節點,三角形便轉成外側直線。被旋轉的兩個節點都是紅色,所以各路徑的黑貢獻不變。
現在考慮直線:紅色 在黑色 的左邊,而紅色 在 的左邊。把 改黑、 改紅,再在 右旋。新子樹根是 :
g(B) p(B)
/ \ / \
p(R) U becomes z(R) g(R)
/ \ / \ / \
z(R) C A B C U
/ \
A B
代表整個子樹,不一定只有一個葉。它們的根都是黑色,也可能是 NIL。
證明透視
分別檢查次序、顏色與黑節點數
旋轉前後的中序次序都是 。旋轉把 從 的右邊移到 的左邊,原有大小關係正好保證這個位置合法。沒有鍵被遺失或重複。
為了檢查黑節點數,從每個圖示附掛子樹的根開始,數到最後的外部葉,並且計入該附掛根本身。這些數目相同: 內的等式使 與 相同;紅色 的等式又使它們與 相同;黑色 的等式再使它們與 相同。設共同數目為 。
修復前,整個圖示子樹的每條路徑都計入黑色 ,再加上 。修復後,則計入黑色 ,再加上 。新改紅的 和新的子樹根 本身也滿足路徑等黑數。兩個紅節點 與 的子節點都是黑色。
最後,原子樹根 是黑色,取代它的 也是黑色。祖先所見的黑貢獻不變,也不會多出紅紅相鄰。修復已完成。三角形情況先做一次紅紅節點間的旋轉後,便適用這個直線論證。
父節點在右側時,用完全對稱的操作:左內側三角形先在父節點右旋,再在祖父左旋完成直線修復。大小關係及左右方向對調後,證明不變。
精確追蹤移動中的節點與父連結
以下偽代碼以 RED、BLACK 表示顏色常數。root.parent 是黑色哨兵。每個內部節點有 left、right、parent 及 color 欄位。NIL 永遠是黑色,不會被重新着色。rotate_left(x) 與 rotate_right(x) 會在需要時更新全樹根、受影響的父連結及被移動的中間子樹。旋轉本身不改顏色,但會保留搜尋次序。
insert(key):
search for key from root
if key exists: return false
attach a new RED node z at the missing child link
set z.left = NIL and z.right = NIL
while z.parent.color == RED:
if z.parent == z.parent.parent.left:
u = z.parent.parent.right
if u.color == RED:
z.parent.color = BLACK
u.color = BLACK
z.parent.parent.color = RED
z = z.parent.parent
else:
if z == z.parent.right:
z = z.parent
rotate_left(z)
z.parent.color = BLACK
z.parent.parent.color = RED
rotate_right(z.parent.parent)
else:
u = z.parent.parent.left
if u.color == RED:
z.parent.color = BLACK
u.color = BLACK
z.parent.parent.color = RED
z = z.parent.parent
else:
if z == z.parent.left:
z = z.parent
rotate_right(z)
z.parent.color = BLACK
z.parent.parent.color = RED
rotate_left(z.parent.parent)
root.color = BLACK
return true
三角形情況中,必須在旋轉之前令 z = z.parent。旋轉之後,原父節點成為較低的紅節點;隨後的 z.parent 才會指向中間鍵,亦即直線修復中應塗黑的節點。若一直沿用已快取而沒有更新的父或祖父指標,便可能塗錯節點或在錯誤位置旋轉。
每次紅叔節點修復都把 向上移兩層。黑叔節點修復最多使用兩次旋轉,並消除缺陷;其後 的父節點是黑色,迴圈條件不再成立。因此迴圈必定終止。最後如有需要,把根改黑,會令全樹每條路徑都多計同一個黑節點,保持所有等式,並消除根的暫時例外。
尋找插入位置及向上修復的總時間是 。一次成功插入最多做兩次旋轉,但可能在 個祖先重新着色。兩者是不同的操作計數,不能由旋轉次數是常數便斷言整次插入是常數時間。
定理 15.2.3
(插入保持紅黑樹不變量)
依上述程序在有效的紅黑樹中插入新鍵,必在有限步內結束,至多做兩次旋轉,並得到一棵有效的紅黑樹,其鍵為原有的鍵加上新鍵。所需時間為 。
證明
(把各種情況合成一次歸納)
第一次迭代之前,新的紅節點不改變任何黑計數,唯一可能的紅紅邊連接 與其父節點。每次迭代都由上文證明過的紅叔節點或黑叔節點情況保持這項不變量,而迴圈至多做兩次旋轉便結束。結束時只可能剩下紅色的根,把它染黑,令每條路徑多一個黑節點。迴圈只走過新節點至多 個祖先。
先重新着色,再遇到三角形
例題 15.2.4
(在空樹依次插入 10、5、15、1、2)
用 鍵顏色(左,右) 記錄樹,- 表示黑色外部葉;只有一個內部葉時,簡寫它的鍵與顏色。B 表示黑色,R 表示紅色。
| 插入鍵 | 修復 | 完整結果 |
|---|---|---|
| 10 | 新根改黑 | 10B |
| 5 | 父節點 10 為黑色 | 10B(5R,-) |
| 15 | 父節點 10 為黑色 | 10B(5R,15R) |
| 1 | 父節點 5 與叔節點 15 都是紅色:兩者改黑,再恢復根的黑色 | 10B(5B(1R,-),15B) |
| 2 | 父節點 1 為紅色,叔節點為 NIL,2 是內側子節點:先在 1 左旋,再重新着色並在 5 右旋 | 10B(2B(1R,5R),15B) |
最後一次插入的局部次序是 。第一次旋轉使 2 升到 1 上面;第二次再使它升到 5 上面。這次修復不改動以 15 為根的右子樹。
最後從根 10 出發、不計根本身,每條路徑都有兩個黑節點位置。例如經過 2 和 1 的路徑計入黑色 2 及外部 NIL;經過 15 的路徑則計入黑色 15 及外部 NIL。根的黑高度因此是 2,但最長根至 NIL 路徑有三條邊。相等黑高度並不強迫普通路徑長度相等。
例題 15.2.5
(依遞增次序插入 1、2、3、4)
依次插入 1、2 得 1B(-,2R)。插入 3 時,父節點 2 為紅色,叔節點是 1 的空左指標,即黑色 NIL;3 是外側子節點,所以把 2 染黑、1 染紅並左旋 1,得 2B(1R,3R)。插入 4 時,父節點 3 與叔節點 1 都是紅色:兩者染黑、2 染紅,再把根 2 染回黑色,得 2B(1B,3B(-,4R))。第四次插入時,重新着色傳到根,整棵樹的黑高度由 1 升至 2。
例題 15.2.6
(先重新着色,再在較高處旋轉)
由有效的樹 20B(10R(5B(2R,7R),15B),30B) 出發,把 1 插入為 2 的左子節點。父節點 2 與叔節點 7 都是紅色:把它們染黑、5 染紅,以 繼續。它的父節點 10 為紅色、叔節點 30 為黑色,而 5、10、20 排成左側直線:把 10 染黑、20 染紅並右旋 20。結果是 10B(5R(2B(1R,-),7B),20R(15B,30B))。
反例模式
新鍵一律塗黑,仍不能省去修復
先有一個黑鍵 10 及其兩個外部葉。把 5 當作黑色左子節點插入。離開 10 後,左路徑計入黑色 5 和黑色 NIL,右路徑卻只計入黑色 NIL:兩邊是 2 與 1。
雖然沒有紅紅相鄰,黑節點數相等的不變量已被破壞。插入時先選紅色,是為了保住黑節點數,再修復可能出現的局部紅紅衝突。
清楚界定這個實作的保證
這是一個有序集合的插入算法。它不保留插入次序,不會自動提供按任意排名的常數時間存取,也不表示儲存陣列或節點配置次序已排序。中序遍歷才提供鍵的排序次序。如果用作映射,更新已存在鍵的值不必改變形狀或顏色。
若另外儲存子樹大小來支援排名查詢,旋轉時也要更新這些大小。若加入刪除,移走黑節點可能改變路徑黑數,不能直接使用上面的插入迴圈修復。NIL 是外部葉標記,不是供鍵比較遍歷的一般鍵。共用哨兵可以節省空間,卻不改變數學樹中的外部葉位置數。
練習與解答
快速檢查
(1. 根 8 是黑色,左子節點 4 是紅色並有黑色 NIL 子節點,右子節點是 NIL。這是紅黑樹嗎?n、H 和根的黑高度各是多少?)
解答
是。經過 4 的各路徑及直接向右的路徑,離開 8 後都只計入一個黑節點:末端的 NIL。樹中沒有紅紅相鄰。此時 、、。左子樹有一個鍵,右子樹沒有鍵;相等黑數不等於相等子樹大小。
快速檢查
(2. 黑色根 10 有紅色左葉 5。插入 7,指出叔節點、兩次旋轉及最後的顏色。為甚麼只在 10 右旋一次不足夠?)
解答
新節點 7 是紅色,父節點 5 是紅色,叔節點是黑色 NIL。這是左右三角形。先在 5 左旋,把 7 改黑、10 改紅,再在 10 右旋。結果是黑根 7,左右子節點分別為紅葉 5、10。
只在 10 右旋,會使 5 升到 10 上面,而 7 變成 10 的左子節點。即使只把新根改黑,仍有紅色 10 接著紅色子節點 7。因此須先把內側紅節點轉成外側直線。這裏檢查的是指定的旋轉與着色修復;單靠旋轉保留次序,從來不能保證顏色條件成立。
快速檢查
(3. 合法樹的根 20 為黑色,子節點 10、30 都是黑色;10 有紅葉 5、15。插入 1。說明只把 5、15 改黑、卻讓 10 保持黑色為何失敗,再寫出正確結果。)
解答
插入後,紅色 1 在紅色 5 下面,叔節點 15 也是紅色。若把 5、15 改黑而讓 10 保持黑色,離開 20 後經 10、5 的路徑會計入 10、5、NIL 共三個黑位置;經 30 的右路徑卻只計入 30 和 NIL 共兩個。
正確修復還須把 10 改紅。它的父節點 20 是黑色,所以迴圈停止。結果是 20B(10R(5B(1R,-),15B),30B)。每條根路徑的黑數都是 2;紅節點 10 和 1 的子節點都是黑色。這次不用旋轉。
快速檢查
(4. 為甚麼最多兩次旋轉不能推出常數時間插入?這個旋轉界適用於刪除嗎?)
解答
插入前的搜尋可能走一條對數長度的根至葉路徑,紅叔節點修復也可能沿這條路徑多次重新着色。常數界只是在數旋轉:重新着色可以重複,但第一次黑叔節點修復會在一或兩次旋轉後結束。總插入時間仍是 。本證明不對刪除作任何結論;移走黑節點需要另一套不變量及修復分析。