🧭 學習重點
- 刪除節點的三種情況
- 紅黑樹如何恢復性質
- 四種修復情況
- 完整可運行的 C++ 實現
一、紅黑樹刪除的基礎理解
紅黑樹刪除比插入復雜得多，因為：
- 刪除的是黑節點可能會破壞“從根到葉子黑節點數相等”的性質。
- 刪除紅節點無需修復，直接刪。
- 刪除黑節點，要么借黑色、要么旋轉重構。
二、刪除節點的三種基本情況（和 BST 類似）
- 無子節點（葉子節點）：直接刪。
- 有一個子節點：用子節點替代。
- 有兩個子節點：找到中序后繼，用其值替換被刪節點，然后刪除后繼。
注意：紅黑樹中處理的是“顏色破壞”，不是結構本身。
三、紅黑樹刪除修復目標
- 恢復五大性質（尤其是黑高一致性）
- 使用雙黑節點表示“臨時多了一層黑色”
- 四種修復方式：兄弟紅、兄弟黑侄紅、兄弟黑侄黑、旋轉變色
四、四種刪除修復情況（核心）
設 x 為“被提上來”的節點（可能是 NIL）
? Case 1：x 的兄弟是紅色
P(B) S(B)
/ \ => / \
x(B) S(R) P(R) Sr(B)
/ \ / \
Sl Sr x(B) Sl- 父變紅，兄變黑，左旋父節點，變成 Case 2~4。
? Case 2：x 的兄弟是黑色，且兩個侄子都是黑色
P(?)
/ \
x(B) S(B)
/ \
B B- 把
S變紅，x = p，向上傳遞雙黑
? Case 3：兄弟黑，近侄子紅，遠侄子黑
P(?)
/ \
x(B) S(B)
/
R- 先右旋
S，再變成 Case 4
? Case 4：兄弟黑，遠侄子紅
P(?)
/ \
x(B) S(B)
\
R- 左旋
p，交換p和s顏色，把遠侄子設為黑，修復完畢
五、完整 C++ 實現：紅黑樹刪除
我們先定義紅黑樹結構（含旋轉、插入、刪除等）：
? 樹結構和節點定義
#include <iostream>
using namespace std;enum Color { RED, BLACK };struct Node {
int val;
Color color;
Node *left, *right, *parent;Node(int val): val(val), color(RED), left(nullptr), right(nullptr), parent(nullptr) {}
};? 左旋操作
void leftRotate(Node*& root, Node* x) {Node* y = x->right;x->right = y->left;if (y->left) y->left->parent = x;y->parent = x->parent;if (!x->parent) root = y;else if (x == x->parent->left) x->parent->left = y;else x->parent->right = y;y->left = x;x->parent = y;
}? 右旋操作
void rightRotate(Node*& root, Node* y) {Node* x = y->left;y->left = x->right;if (x->right) x->right->parent = y;x->parent = y->parent;if (!y->parent) root = x;else if (y == y->parent->left) y->parent->left = x;else y->parent->right = x;x->right = y;y->parent = x;
}? 找到最小節點（用于后繼替換）
Node* minimum(Node* node) {while (node->left) node = node->left;return node;
}? 刪除修復函數
void deleteFixUp(Node*& root, Node* x) {while (x != root && (!x || x->color == BLACK)) {if (x == x->parent->left) {Node* w = x->parent->right;if (w->color == RED) {w->color = BLACK;x->parent->color = RED;leftRotate(root, x->parent);w = x->parent->right;}if ((!w->left || w->left->color == BLACK) &&(!w->right || w->right->color == BLACK)) {w->color = RED;x = x->parent;} else {if (!w->right || w->right->color == BLACK) {if (w->left) w->left->color = BLACK;w->color = RED;rightRotate(root, w);w = x->parent->right;}w->color = x->parent->color;x->parent->color = BLACK;if (w->right) w->right->color = BLACK;leftRotate(root, x->parent);x = root;}} else {// 對稱處理Node* w = x->parent->left;if (w->color == RED) {w->color = BLACK;x->parent->color = RED;rightRotate(root, x->parent);w = x->parent->left;}if ((!w->left || w->left->color == BLACK) &&(!w->right || w->right->color == BLACK)) {w->color = RED;x = x->parent;} else {if (!w->left || w->left->color == BLACK) {if (w->right) w->right->color = BLACK;w->color = RED;leftRotate(root, w);w = x->parent->left;}w->color = x->parent->color;x->parent->color = BLACK;if (w->left) w->left->color = BLACK;rightRotate(root, x->parent);x = root;}}}if (x) x->color = BLACK;
}? 刪除操作主函數
void rbDelete(Node*& root, Node* z) {Node* y = z;Node* x;Color yOriginalColor = y->color;if (!z->left) {x = z->right;transplant(root, z, z->right);} else if (!z->right) {x = z->left;transplant(root, z, z->left);} else {y = minimum(z->right);yOriginalColor = y->color;x = y->right;if (y->parent == z) {if (x) x->parent = y;} else {transplant(root, y, y->right);y->right = z->right;y->right->parent = y;}transplant(root, z, y);y->left = z->left;y->left->parent = y;y->color = z->color;}if (yOriginalColor == BLACK)deleteFixUp(root, x);
}? 替換子樹輔助函數
void transplant(Node*& root, Node* u, Node* v) {if (!u->parent) root = v;else if (u == u->parent->left) u->parent->left = v;else u->parent->right = v;if (v) v->parent = u->parent;
}六、總結與練習建議
- 刪除是紅黑樹最復雜操作，邏輯較多但結構穩定
- 建議多畫圖分析每種情況
- 自己實現一棵樹，從插入到刪除，打印中序遍歷驗證
