在紅黑樹中刪除

Question

我正在嘗試引入算法第3版中的RB-DELETE-FIXUP。他們有這樣的代碼：

RB-DELETE-FIXUP(T, x) 
1 while x != root[T] and color[x] == BLACK 
2  do if x == left[p[x]] 
3   then w = right[p[x]] 
4    if color[w] == RED 
5     then color[w] = BLACK      ? Case 1 
6      color[p[x]] = RED      ? Case 1 
7      LEFT-ROTATE(T, p[x])     ? Case 1 
8      w = right[p[x]]       ? Case 1 
9    if color[left[w]] == BLACK and color[right[w]] == BLACK 
10     then color[w] = RED       ? Case 2 
11      x = p[x]         ? Case 2 
12     else if color[right[w]] == BLACK 
13       then color[left[w]] = BLACK   ? Case 3 
14        color[w] = RED     ? Case 3 
15        RIGHT-ROTATE(T, w)    ? Case 3 
16        w = right[p[x]]     ? Case 3 
17       color[w] = color[p[x]]     ? Case 4 
18       color[p[x]] = BLACK     ? Case 4 
19       color[right[w]] = BLACK    ? Case 4 
20       LEFT-ROTATE(T, p[x])     ? Case 4 
21       x = root[T]       ? Case 4 
22  else (same as then clause with "right" and "left" exchanged) 
23 color[x] = BLACK 

我無法理解如何將樹的情況下，4所平衡望着這一形象：（從here）

的情況下，結果4不平衡。從D到A，黑色高度是2.而D到E，黑色高度是1.我在這裏錯過了什麼？

Answer 1

你缺少的是左手邊不平衡。這個例程在x的父親被拼接出樹之後調用，並且只有父類是黑色的。由於樹在移除父代之前已經達到平衡，那麼我們知道以A爲根的子樹必須具有黑色的高度，這比根植於D的子樹小一個。由於E最初是紅色的而D是黑色的，那麼以E爲根的子樹就必須具有與A相同的黑色高度。變換之後，E的顏色現在變成黑色，所以它的黑色高度現在比A高一個，所以樹的兩側確實是平衡的。