当前位置：首页 > news >正文

红黑树删除的实现与四种情况的证明

news 2025/5/11 7:58:56

🧭 学习重点

删除节点的三种情况
红黑树如何恢复性质
四种修复情况
完整可运行的 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;
}