紅黑樹的刪除詳解與思路分析——不同於教科書上的演算法（dart語言實現）
摘要：
對於紅黑樹的刪除，看了資料結構的書，也看了很多網上的講解和實現，但都不滿意。很多講解都是囫圇吞棗，知其然，不知其所以然，講的晦澀難懂。
紅黑樹是平衡二叉樹的一種，其刪除演算法是比較複雜的，因為刪除後還要保持紅黑樹的特性。紅黑樹的特性如下：
節點是紅色或黑色...
對於紅黑樹的刪除，看了資料結構的書，也看了很多網上的講解和實現，但都不滿意。很多講解都是囫圇吞棗，知其然，不知其所以然，講的晦澀難懂。
紅黑樹是平衡二叉樹的一種，其刪除演算法是比較複雜的，因為刪除後還要保持紅黑樹的特性。紅黑樹的特性如下：
-
- 節點是紅色或黑色。
- 根是黑色。
- 所有葉子都是黑色（葉子是NIL節點）。
- 每個紅色節點必須有兩個黑色的子節點。（從每個葉子到根的所有路徑上不能有兩個連續的紅色節點。）
- 從任一節點到其每個葉子的所有簡單路徑都包含相同數目的黑色節點（簡稱黑高）。
因此，從紅黑樹最基礎的特性出發，拋開教科書和網上的演算法，畫了無數張圖，分析了多種可能的情況以後，經過歸納提煉，實現了不同於教科書上的刪除演算法。
經過多次畫圖證明以後，筆者發現，紅黑樹的刪除演算法不是唯一的，不管如何調整，只要保證刪除後還是一顆紅黑樹即可。
因此，筆者實現的 刪除思路和演算法如下：
1. 刪除轉移：（這部分是大路貨，不是自己實現的）
- 如果被刪除節點有兩個非空子節點，則用後繼節點的值代替該節點的值，這樣演變成了刪除後繼節點；否則轉下一條；
- 如果被刪除節點一個或兩個孩子都為空：若有非空孩子，則用非空孩子節點替代之；若無，直接刪除；
- 刪除後繼節點：後繼節點的左孩子節點一定為空，右孩子可能為空；處理如上一條；
刪除轉移的目的是為了簡化刪除操作，更是為了簡化修復操作。因為刪除轉移後，最終待刪除的節點最多隻會有一個非空孩子。
2. 刪除後修復：
2.1 簡單的情況：
-
- 若被刪除節點為紅色節點，不需修復；此時該節點一定為紅色的葉子節點（可根據紅黑樹的特性證明）；
- 若被刪除的節點為黑色節點，且有一個非空子節點，則將其非空子節點顏色塗黑即可；
對於以上兩種簡單的情況，做個說明：根據紅黑樹特性，非空子節點一定為紅色節點，否則將違反特性；根據紅黑樹特性，在刪除前，一顆紅黑樹 不可能 出現以下幾種情況：
（圖片來自網路，感謝原作者。）
2.2 複雜的情況：刪除後需要修復的。
只有當被刪除的節點為黑色葉子節點時，導致該節點所在的分支，少了一個黑色節點，樹不再平衡，因此需要修復。
修復的整體思路是：
-
- 如果該節點的父節點、或兄弟節點、或兄弟節點的特定方向的子節點 中，有紅色節點，則將此紅色節點旋轉過來，通過旋轉、塗黑操作，保持自父節點以來的樹的平衡；
- 如果不滿足上述條件，則通過旋轉和變色操作，使其兄弟分支上也減少一個黑色節點，這樣自父節點以來的分支保持了平衡，滿足了條件，但對於父節點來說，其整個分支減少了一個黑色節點，需要遞歸向上處理，直至重新平衡，或者到達根節點；
掌握了整體思路以後，就可編碼實現了，編碼中用了一些小技巧，合併了一些情況，程式碼比較簡單易懂，閱讀者可以根據程式碼的情況自己畫圖證明：
說明：程式碼為dart語言實現，dart語法基本與Java一致，不清楚的地方可以參考：
https://www.dartlang.org/guides/language/language-tour
1// 刪除
2bool delete(E value) {
3var node = find(value);
4if (node == null) return false;
5_delete(node);
6_nodeNumbers--;
7return true;
8}
9
10// 刪除轉移 並修復
11void _delete(RBTNode<E> d) {
12if (d.left != null && d.right != null) {
13var s = _successor(d);
14d.value = s.value;
15d = s;
16}
17
18var rp = d.left ?? d.right;
19rp?.parent = d.parent;
20if (d.parent == null)
21_root = rp;
22else if (d == d.parent.left)
23d.parent.left = rp;
24else
25d.parent.right = rp;
26
27if (rp != null)
28rp.paintBlack();
29else if (d.isBlack && d.parent != null)
30_fixAfterDelete(d.parent, d.parent.left == null);
31}
32
33RBTNode<E> _successor(RBTNode<E> d) =>
34d.right != null ? _minNode(d.right) : d.left;
35
36RBTNode<E> _minNode(RBTNode<E> r) => r.left == null ? r : _minNode(r.left);
37
38// fix up after delete
39void _fixAfterDelete(RBTNode<E> p, bool isLeft) {
40var ch = isLeft ? p.right : p.left;
41if (isLeft) { // 如果被刪除節點是父節點p的左分支;
42if (p.isRed) { // 如果父節點為紅，則兄弟節點ch一定為黑;
43if (ch.left != null && ch.left.isRed) {
44p.paintBlack();
45_rotateRight(ch);
46}
47_rotateLeft(p);
48} else if (ch.isRed) { // 兄弟節點為紅，此時兄弟節點一定有兩個非空黑色子節點;
49p.paintRed();
50ch.paintBlack();
51_rotateLeft(p);
52_fixAfterDelete(p, true); // 變換為父節點為紅的情況，遞迴處理;
53} else if (ch.left != null && ch.left.isRed) { // 父、兄均為黑，兄有紅色左孩子;
54ch.left.paintBlack();
55_rotateRight(ch);
56_rotateLeft(p);
57} else { // 父兄均為黑，將父分支左右均減少一個黑節點，然後遞歸向上處理;
58p.paintRed();
59_rotateLeft(p);
60if (ch.parent != null) _fixAfterDelete(ch.parent, ch == ch.parent.left);
61}
62} else { // symmetric
63if (p.isRed) {
64if (ch.right != null && ch.right.isRed) {
65p.paintBlack();
66_rotateLeft(ch);
67}
68_rotateRight(p);
69} else if (ch.isRed) {
70p.paintRed();
71ch.paintBlack();
72_rotateRight(p);
73_fixAfterDelete(p, false);
74} else if (ch.right != null && ch.right.isRed) {
75ch.right.paintBlack();
76_rotateLeft(ch);
77_rotateRight(p);
78} else {
79p.paintRed();
80_rotateRight(p);
81if (ch.parent != null) _fixAfterDelete(ch.parent, ch == ch.parent.left);
82}
83}
84}
旋轉操作的程式碼：
1void _rotateLeft(RBTNode<E> node) {
2var r = node.right, p = node.parent;
3r.parent = p;
4if (p == null)
5_root = r;
6else if (p.left == node)
7p.left = r;
8else
9p.right = r;
10
11node.right = r.left;
12r.left?.parent = node;
13r.left = node;
14node.parent = r;
15}
16
17void _rotateRight(RBTNode<E> node) {
18var l = node.left, p = node.parent;
19l.parent = p;
20if (p == null)
21_root = l;
22else if (p.left == node)
23p.left = l;
24else
25p.right = l;
26
27node.left = l.right;
28l.right?.parent = node;
29l.right = node;
30node.parent = l;
31}