认识红黑树
上篇文章我们主要认识了二叉树搜索树，这篇文章正式介绍红黑树。
红黑树在二叉搜索树的基础上，加了些性质，包含color、key、left、right、p，颜色取值为红色或者黑色，此外，我们把NIL节点视为特殊的节点，具体而言，视为外部节点，也叫叶子节点，把带有关键字的节点视为内部节点。
红黑树是具有下面性质的二叉搜索树：
- 每个节点，要么是红色的，要么是黑色的。
- 根节点是黑色的。
- 每个叶子节点（
NIL）是黑色的。 - 如果一个节点是红色的，那么它的两个子节点都是黑色的（如果子节点是
NIL，则子节点也是黑色的） - 对于每个节点，从该节点到其所有后代叶节点的简单路径（即只会从该节点往叶子节点向往下）上，均包含相同数目的黑色节点。
我们把bh(x)定义为从节点x开始（不包括该节点）到叶子节点的任意一条简单路径上的黑色节点个数成为黑高（black-height）。
例如：
节点旁边的表示是对应的黑高。
红黑树通俗点，就是节点的左右子树高度差异不会很大，而上文提到的二叉搜索树的插入和删除，这两个会影响左右子树的高度差，因此我们要在插入或者删除后，调整红黑树的某些节点的左右子树，才能使得这两个操作满足红黑树的性质。
我们可以将红黑树中所有的NIL节点（包括根节点的双亲）都指向同一个，即：
为了方便，我们可以对NIL节点进行缺省，即：
左旋右旋
在开始前，我们先来认识左旋右旋，这两个操作会辅助我们对红黑树调整：
上述的左旋右旋是以最上层的结点角度来说的
左旋x节点：假设x节点的右孩子节点y不是NIL节点，则y成为该子树的新的根节点，x成为y的左孩子，y的左孩子成为x的右孩子。
左旋时，我们假定x.right!=NIL且根节点的父节点为T.NIL，则左旋的伪代码如下：
rb_tree_left_rotation(T, x){
y = x.right;
x.right = y.left;
if y.left != T.NIL
y.left.p = x;
y.p = x.p;
// 如果x是红黑树的根节点
if x.p == T.NIL
T.root = y;
T.root.p = T.NIL;
// 如果x是双亲节点的左孩子
else if x == x.p.left
x.p.left = y;
// 如果x是双亲节点的右孩子
else
x.p.right = y;
y.left = x;
x.p = y;
}
右旋时，我们假定y.left!=NIL，且根节点的父节点为T.NIL，则右旋的伪代码如下：
rb_tree_right_rotation(T, y){
x = y.left;
y.left = x.right;
if x.right != T.NIL
x.right.p = y;
x.p = y.p;
// 如果y是红黑树的根节点
if y.p == T.NIL
T.root = x;
T.root.p = T.NIL;
// 如果y是双亲节点的左孩子
else if y == y.p.left
y.p.left = x;
// 如果y是双亲节点的右孩子
else
y.p.right = x;
x.right = y;
y.p = x;
}
插入
插入步骤主要包括以下步骤：
- 找到合适位置，插入节点
- 将新节点染成红色
- （可选的）调整红黑树，直至符合红黑树定义
与往二叉搜索树中插入节点类似：
rb_tree_insert(T, z){
y = T.NIL;
x = T.root;
while x != T.NIL
y = x;
// 插到左子树
if z.key < x.key
x = x.left;
// 插到右子树
else
x = x.right;
z.p = y;
// 空树
if y == T.NIL
T.root = z;
else if z.key < y.key
y.left = z;
else
y.right = z;
z.left = T.NIL;
z.right = T.NIL;
z.color = RED;
rb_tree_insert_fixup(T, z);
}
如果节点z插入的位置中，其双亲节点是黑色的，则无需进行调整，这是因为插入这个红色节点后并不会违反上文所提的5个性质，相反，如果其双亲节点是红色的，那么就有连续两个红色的节点，违反了性质4，这时候我们要对红黑树进行调整，我们可以证明，仅当新插入的节点的双亲是红色时，需要对红黑树调整，我们可以将需要进行调整的情况分为3种：
- z的叔节点y是红色的。
- z的叔节点y是黑色的且z是其双亲的右孩子。
- z的叔节点y是黑色的且z是其双亲的左孩子。
在情况1中，由于y是红色的，我们可以同时将z的双亲和y染成黑色，将y的双亲染成红色，则以y的双亲为根的子树满足红黑树定义（当然如果y的双亲是整棵红黑树的根，则y的双亲要再次染成黑色的）。
由于y的双亲被染成了红色，有可能会对y的祖先造成影响（即此时y的双亲的双亲是红色的，此时存在连续的红色的节点），使得一些祖先不能满足红黑树定义，此时，我们要把y的双亲当成z，递归重新判断。
在情况2中，由于z是其双亲的右孩子，我们可以对z的双亲进行一次左旋，此时可以转为情况3.
在情况3中，由于z和z的双亲是红色的，则y的双亲必然是黑色的（因为插入z之前，树是满足红黑树定义的，而z的双亲是红色的，则z的双亲的双亲必然是黑色的），因此我们可以对z的双亲染成黑色，而y的双亲是红色，再对y的双亲做一个右旋，则以z的双亲为根的子树满足红黑树定义。
我们可以以算法导论中的例子为例：
因此调整的伪代码为：
rb_tree_insert_fixup(T, z){
while z.p.color == RED
// 如果z的双亲是左孩子
if z.p == z.p.p.left
y = z.p.p.right;
if y.color == RED
z.p.color = BLACK; // case 1
y.color = BLACK; // case 1
z.p.p.color = RED; // case 1
z = z.p.p; // case 1
else if z == z.p.right
z = z.p; // case 2
rb_tree_left_rotation(T, z) // case 2
else
z.p.color = BLACK; // case 3
z.p.p.color = RED; // case 3
rb_tree_right_rotation(T, z.p.p); // case 3
// 如果z的双亲是右孩子
else
// 与上面分支对称，将left和right互换即可
...
// 不管怎样，红黑树的性质2一定要满足
T.root.color = BLACK;
}
删除
删除过程有亿点点复杂，不过我们可以先分成几个大类（假设被删除的结点是z）：
A.：z是红色的，且没有子结点：由于其没有孩子，因此删除这个红色结点对其子树（实际子树为空）以及其他的子树都不影响，我们简单地将其删除即可。
B.：z是黑色的，且没有子结点：由于z是黑色的，那么删除z后，对于之前简单路径中包含z的路径长度都减少了1，我们破坏了红黑树性质，这个分类是最复杂的，因此我们后面再展开这类。
C.：z只有一个非T.NIL子结点y：这种情况下，z必然是黑色的且y是红色的，为什么呢？假如z和y都是黑色的，那么根到y的子树的叶子节点的简单路径中黑色结点个数会比根到z的另一个空子树的叶子节点的简单路径中黑色结点个数多1，同理也不可能出现“z是红色的且y是黑色的”，这种情况下我们可以用y替换z（然后删除z），同时将y染成黑色即可。
D.：z有两个子结点：根据之前二叉搜索树的删除，我们可以知道，将来替换z的结点是z的后继x（实际上前驱也可以，不过我们延续二叉搜索树的做法），替换过程我们把z的关键字设置为x的关键字，然后我们删除x按照步骤A、B、C进行（因为x是z的后继，根据前面知识我们知道，当z存在右孩子时，其后继x是z的右子树中最左边的结点，因此其不可能有两个孩子结点）
我们重点展开B类情况：
开始之前，我们先思考一下，如果z是根节点，我们直接删除z即可，然后将红黑树根节点设置为T.NIL即可，如果z不是根节点，参照上文C类的分析，当z没有子结点且z是黑色的情况下，z必然存在一个兄弟节点，我们记该结点为y。
B.a：z的兄弟y是黑色的，且y有一个红色的子结点x，我们对y进行一次旋转，然后再重新染色，再删除z即可，这里又可以分为两种情况：
- B.a.a：x和z不同向，即一个为左节点，一个为右节点，当z是右节点时，我们对y的双亲进行右旋，如果z是左节点，我们则对y的双亲进行左旋，如下图所示：
注意，变化后新的2号结点颜色要与原先的3号节点颜色相同，否则不满足性质5；此外我们可以证明x没有非NIL子结点
- B.a.b：x和z同向，即同为其双亲的右孩子或者左孩子，此时我们可以旋转y，并交换x和y的颜色，即可转至上面
B.a.a的情况:
B.b：z的兄弟y是黑色的，且y没有子结点，这里可以分z的双亲是红色和黑色情况
- B.b.a：如果z的双亲是红色：这里比较简单，我们直接删除z，然后将y的双亲染为黑色同时将y染为红色
- B.b.b：如果z的双亲是黑色的，这种情况就比较复杂了，我们需要先删除z的同时将y染成红色，然后将z指向y的双亲，由于新的z只有一个红色的子结点y，红色结点的存在与否不影响包含该节点的简单路径中黑色结点个数，因此我们可以当成是B情况的特例，然后使用
B.a~B.c的情况进一步调整（虽然B.c的情况在下面才说明），只不过有些时候我们把黑色的非NIL结点当成了NIL结点，但是不影响最终的调整，注意这种情况下我们不再对新的z进行删除操作。当然这个过程中，z有可能一直往上，直至遇到根节点，届时我们不再需要往上进行，这几种情况如下图所示：
B.c：z的兄弟y是红色的，由于z是黑色的且没有子结点，y是红色的，因此z的双亲必然是黑色的且y有两个黑色的子结点（但是y有没有红色的孙子结点不确定）：
我们可以先对z的双亲做一个旋转（上图的情况是左旋，当z是右孩子时对称地对双亲右旋即可），并将y和其新的左孩子对调颜色，外面可以发现，此时如果不删除结点1，那么这棵树是满足红黑树的，但是外面删除了结点1，言外之意，我们把左边的删除过程和右边做了一个等价交换，而这种情况，我们可以转成B.a和B.b情况。
new y 和 旧的y同向
还有一点值得注意，B情况包含涵盖了所有情况了吗？？其实没有，我们还缺少一种情况，即“z是黑色的没有孩子结点，且z的兄弟结点y也是黑色的且y有两个红孩子”，但是我们这种情况可以规约成B.a.a情况，例如：
完成上面的分析后，我们就可以写出这部分的伪代码了，不过在开始之前，我们也要先定义一个子过程，用于使用以v为根的子树来替换以u为根的子树
rb_tree_transplant(T, u, v){
if u.p == T.NIL
T.root = v;
else if u == u.p.left
u.p.left = v;
else
u.p.right = v;
v.p = u.p;
}
ok，下面是删除功能的伪代码了：
rb_tree_delete_case_B_a_a_fix(T, x){
y = x.p;
y_is_left = (y == y.p.left);
y_p_color = y.p.color
if y_is_left
rb_tree_right_rotation(T, y.p)
y.right.color = BLACK;
else
rb_tree_left_rotation(T, y.p);
y.left.color = BLACK;
x.color = BLACK;
y.color = y_p_color;
}
rb_tree_delete_case_B_a_b_fix(T, x){
y = x.p;
y_is_left = (y == y.p.left);
y.color = RED;
x.color = BLACK
if y_is_left
rb_tree_left_rotation(T, y);
else
rb_tree_right_rotation(T, y);
// 交换 x 和 y 指针
swap_ptr(y, x);
// 化为 B.a.a
rb_tree_delete_case_B_a_a_fix(T, x);
}
yrb_tree_delete_case_B_b_a_fix(T, y){
y.color = RED;
y.p.color = BLACK;
}
rb_tree_delete_case_B_b_b_fix(T, y){
y.color = RED;
new_z = y.p;
if new_z == T.root
return;
new_z_is_left = (new_z == new_z.p.left);
new_y = (new_z_is_left ? new_z.p.right : new_z.p.left)
if new_y.color == BLACK and (
(new_z_is_left and new_y.right != T.NIL and new_y.right.color == RED) or
(!new_z_is_left and new_y.left != T.NIL and new_y.left.color == RED)
)
// 转 B.a.a后结束
rb_tree_delete_case_B_a_a_fix(T, new_z_is_left ? new_y.right : new_y.left);
else if new_y.color == BLACK and (
(new_z_is_left and new_y.left != T.NIL and new_y.left.color == RED) or
(!new_z_is_left and new_y.right != T.NIL and new_y.right.color == RED)
)
// 转 B.a.b后结束
rb_tree_delete_case_B_a_a_fix(T, new_z_is_left ? new_y.left : new_y.right);
// 注意，这里使用“y是不是有俩个黑色的子结点”而不是使用“y是不是有两个NIL子结点”
else if new_y.color == BLACK and new_y.left.color == BALCK and new_y.right.color == BALCKL and new_z.p.color == RED
// 转 B.b.a后结束
rb_tree_delete_case_B_b_a_fix(T, new_y);
else if new_y.color == BLACK and new_y.left.color == BALCK and new_y.right.color == BALCKL and new_z.p.color == BLACK
// 继续递归 B.b.b
rb_tree_delete_case_B_b_b_fix(T, new_y);
else if new_y.color == RED
// 转 B.c后结束
rb_tree_delete_case_B_c_fix(T, new_y);
}
rb_tree_delete_case_B_c_fix(T, y){
y.color = BLACK;
y_is_left = (y == y.p.left);
if y_is_left
rb_tree_right_rotation(T, y.p);
y.right.left.color = RED;
new_y = y.right.left;
else
rb_tree_left_rotation(T, y.p);
y.left.right.color = RED;
new_y = y.left.right;
// 如果 new_y 有红色子结点，跳转 B.a.a 或者 B.a.b
if (y_is_left and new_y.left.color == RED) or
(!y_is_left and new_y.right.color == RED)
rb_tree_delete_case_B_a_a_fix(T, y_is_left ? new_y.left : new_y.right);
else if (y_is_left and new_y.right.color == RED) or
(!y_is_left and new_y.left.color == RED)
rb_tree_delete_case_B_a_b_fix(T, y_is_left ? new_y.right : new_y.left);
// 如果 new_y 有没有子结点，由于 new y 的双亲是红色的，跳转B.b.a
else if new_y.left.color == BLACK and new_y.right.color == BLACK
rb_tree_delete_case_B_b_a_fix(T, new_y);
}
rb_tree_delete_case_A(T, z){
// 直接删除
if z == z.p.left
z.p.left = T.NIL;
else
z.p.right = T.NIL;
}
rb_tree_delete_case_B(T, z){
// 先删除z
if z == z.p.left
z.p.left = T.NIL;
y = z.p.right;
z_is_left = true;
else
z.p.right = T.NIL;
y = z.p.left;
z_is_left = false;
// 如果z是根节点，则删除后是空树，不需要考虑z的兄弟节点了，因为根本不存在
if z == T.root
T.root = T.NIL;
return;
// 再根据不同的情况进行调整
// b.a.a
if y.color == BLACK and (
(z_is_left and y.right != T.NIL and y.right.color == RED) or
(!z_is_left and y.left != T.NIL and y.left.color == RED)
)
rb_tree_delete_case_B_a_a_fix(T, z_is_left ? y.right : y.left);
// b.a.b
else if y.color == BLACK and (
(z_is_left and y.left != T.NIL and y.left.color == RED) or
(!z_is_left and y.right != T.NIL and y.right.color == RED)
)
rb_tree_delete_case_B_a_b_fix(T, z_is_left ? y.left : y.right);
// b.b.a
else if y.color == BLACK and y.left == T.NIL and y.right == T.NIL and z.p.color == RED
rb_tree_delete_case_B_b_a_fix(T, y);
// b.b.b
else if y.color == BLACK and y.left == T.NIL and y.right == T.NIL and z.p.color == BLACK
rb_tree_delete_case_B_b_b_fix(T, y);
// b.c
else if y.color == RED
rb_tree_delete_case_B_c_fix(T, y);
}
rb_tree_delete_case_C(T, z){
if z.left == T.NIL
y = z.right;
else
y = z.left;
rb_tree_transplant(T, z, y);
y.color = BLACK;
}
rb_tree_delete_case_D(T, z){
x = rb_tree_search_suc(z);
z.key = x.key;
rb_tree_delete(T, x);
}
rb_tree_delete(T, z){
// A情况
else if z.color == RED and z.left == T.NIL and z.right == z.left
rb_tree_delete_case_A(T, z);
// B情况
else if z.color == BLACK and z.left == T.NIL and z.right == T.NIL
rb_tree_delete_case_B(T, z);
// C情况
else if (z.left == T.NIL and z.right != T.NIL) or (z.right == T.NIL and z.left != T.NIL)
rb_tree_delete_case_C(T, z);
// D情况
else if z.left != T.NIL and z.right != T.NIL
rb_tree_delete_case_D(T, z);
}
C语言实现
先定义红黑树以及树的结点：
typedef struct Node {
int key;
int color;
struct Node* p, * left, * right;
}TreeNode;
typedef struct Tree {
TreeNode* root;
TreeNode* NIL;
}RedBlackTree;
然后是初始化红黑树的代码：
// 初始化一个NIL结点，红黑树整个生命周期只会生成一个NIL结点
void initRedBlackTree(RedBlackTree* tree) {
TreeNode* nil = (TreeNode*)malloc(sizeof(TreeNode));
nil->color = BLACK;
tree->NIL = nil;
tree->root = nil;
tree->root->p = tree->NIL;
tree->root->left = tree->NIL;
tree->root->right = tree->NIL;
}
我们还要写一个用于验证红黑树的函数：
int valid;
int dfsValid(RedBlackTree* T, TreeNode* root, TreeNode* p) {
if (root->color != RED && root->color != BLACK) {
// 性质1
valid = -1;
}
if (root == T->NIL && root->color != BLACK) {
// 性质3
valid = -1;
}
if (root->color == RED && (root->left->color == RED || root->right->color == RED)) {
// 性质4
valid = -1;
}
if (root != T->NIL && root->p != p) {
valid = -1;
}
// 性质5
if (root != T->NIL) {
int leftBlackNodeCnt = dfsValid(T, root->left, root);
int rightBlackNodeCnt = dfsValid(T, root->right, root);
if (leftBlackNodeCnt != rightBlackNodeCnt) {
valid = -1;
}
return leftBlackNodeCnt + (root->color == BLACK ? 1 : 0);
}
// 搜索树性质
if (root->left != T->NIL && root->left->key > root->key) {
valid = -1;
}
if (root->right != T->NIL && root->right->key < root->key) {
valid = -1;
}
return (root->color == BLACK ? 1 : 0);
}
int redBlackTreeValid(RedBlackTree* T) {
// 根节点是黑色的（性质2），空节点是黑色的（性质3）
if (T->root->color != BLACK || T->NIL->color != BLACK) {
return -1;
}
if (T->root->p != T->NIL) {
return -1;
}
valid = 1;
dfsValid(T, T->root, T->NIL);
if (valid == -1) {
printf("*********Not valid red black tree!*********\n");
return -1;
}
return 1;
}
我们可以编写一个测试代码，测试10次，每次产生指定长度10000的随机数据插入，插入完毕后随机删除结点：
int final_test(int len, int debug) {
if (len > 10000) {
}
RedBlackTree* T = (RedBlackTree*)malloc(sizeof(RedBlackTree));
initRedBlackTree(T);
redBlackTreeValid(T);
int nums[10000];
// 测试插入
printf("----- start insert -----\n");
for (int i = 0; i < len;i++) {
nums[i] = generateRandomNumber(0, len);
if (debug) {
printf("insert %d\n", nums[i]);
}
TreeNode* z = (TreeNode*)malloc(sizeof(TreeNode));
z->color = RED;
z->p = T->NIL;
z->left = T->NIL;
z->right = T->NIL;
z->key = nums[i];
rb_tree_insert(T, z);
redBlackTreeValid(T);
}
// 测试删除
printf("----- start delete -----\n");
int remain = len;
int deleteIdx, deleteKey;
for (int i = 1; i <= len;i++) {
deleteIdx = generateRandomNumber(0, remain);
// 避免下次再被选到
deleteKey = nums[deleteIdx];
// printf("delete %d\n", deleteKey);
nums[deleteIdx] = nums[remain - 1];
nums[remain - 1] = deleteKey;
TreeNode* z = rb_tree_search(T, T->root, deleteKey);
if (z == T->NIL) {
printf("No found!");
}
else {
if (debug) {
printf("delete %d\n", deleteKey);
}
rb_tree_delete(T, z);
if (redBlackTreeValid(T) == -1) {
printf("delete error just now on %d\n", deleteKey);
}
}
remain--;
}
}
int main() {
// 重新设置随机数种子
srand(time(NULL));
for (int i = 1; i <= 10; i++) {
final_test(10000, 0);
}
return 0;
}
测试结果如下（如果有出现删除或者插入后不符合红黑树性质，则会打印*********Not valid red black tree!*********）
完整实现：
#include<stdio.h>
#include<malloc.h>
#include <stdlib.h>
#include <time.h>
#define RED 0
#define BLACK 1
typedef struct Node {
int key;
int color;
struct Node* p, * left, * right;
}TreeNode;
typedef struct Tree {
TreeNode* root;
TreeNode* NIL;
}RedBlackTree;
// 初始化一个NIL结点，红黑树整个生命周期只会生成一个NIL结点
void initRedBlackTree(RedBlackTree* tree) {
TreeNode* nil = (TreeNode*)malloc(sizeof(TreeNode));
nil->color = BLACK;
tree->NIL = nil;
tree->root = nil;
tree->root->p = tree->NIL;
tree->root->left = tree->NIL;
tree->root->right = tree->NIL;
}
void rb_tree_left_rotation(RedBlackTree* T, TreeNode* x) {
TreeNode* y = x->right;
x->right = y->left;
if (y->left != T->NIL) {
y->left->p = x;
}
y->p = x->p;
// 如果x是红黑树的根节点
if (x->p == T->NIL) {
T->root = y;
T->root->p = T->NIL;
}
// 如果x是双亲节点的左孩子
else if (x == x->p->left) {
x->p->left = y;
}
// 如果x是双亲节点的右孩子
else {
x->p->right = y;
}
y->left = x;
x->p = y;
}
void rb_tree_right_rotation(RedBlackTree* T, TreeNode* y) {
TreeNode* x = y->left;
y->left = x->right;
if (x->right != T->NIL) {
x->right->p = y;
}
x->p = y->p;
// 如果y是红黑树的根节点
if (y->p == T->NIL) {
T->root = x;
T->root->p = T->NIL;
}
// 如果y是双亲节点的左孩子
else if (y == y->p->left) {
y->p->left = x;
}
// 如果y是双亲节点的右孩子
else {
y->p->right = x;
}
x->right = y;
y->p = x;
}
TreeNode* rb_tree_search(RedBlackTree* T, TreeNode* root, int key) {
if (root == T->NIL || root->key == key) {
return root;
}
// 在左子树中
if (key < root->key) {
return rb_tree_search(T, root->left, key);
}
// 在右子树中
else {
return rb_tree_search(T, root->right, key);
}
}
// ======= 插入开始部分 ==========
void rb_tree_insert_fixup(RedBlackTree* T, TreeNode* z) {
TreeNode* y;
while (z->p->color == RED) {
// 如果z的双亲是左孩子
if (z->p == z->p->p->left) {
y = z->p->p->right;
if (y->color == RED) {
z->p->color = BLACK; // case 1
y->color = BLACK; // case 1
z->p->p->color = RED; // case 1
z = z->p->p; // case 1
}
else if (z == z->p->right) {
z = z->p; // case 2
rb_tree_left_rotation(T, z); // case 2
}
else {
z->p->color = BLACK; // case 3
z->p->p->color = RED; // case 3
rb_tree_right_rotation(T, z->p->p); // case 3
}
}
else {
y = z->p->p->left;
if (y->color == RED) {
z->p->color = BLACK; // case 1
y->color = BLACK; // case 1
z->p->p->color = RED; // case 1
z = z->p->p; // case 1
}
else if (z == z->p->left) {
z = z->p; // case 2
rb_tree_right_rotation(T, z); // case 2
}
else {
z->p->color = BLACK; // case 3
z->p->p->color = RED; // case 3
rb_tree_left_rotation(T, z->p->p); // case 3
}
}
}
// 不管怎样，红黑树的性质2一定要满足
T->root->color = BLACK;
}
void rb_tree_insert(RedBlackTree* T, TreeNode* z) {
TreeNode* y = T->NIL;
TreeNode* x = T->root;
while (x != T->NIL) {
y = x;
// 插到左子树
if (z->key < x->key) {
x = x->left;
}
// 插到右子树
else {
x = x->right;
}
}
z->p = y;
// 空树
if (y == T->NIL) {
T->root = z;
}
else if (z->key < y->key) {
y->left = z;
}
else {
y->right = z;
}
z->left = T->NIL;
z->right = T->NIL;
z->color = RED;
rb_tree_insert_fixup(T, z);
}
// ======= 插入结束部分 ==========
// ======= 删除开始部分 ==========
rb_tree_delete_case_B_a_a_fix(RedBlackTree* T, TreeNode* x) {
TreeNode* y = x->p;
int y_is_left = (y == y->p->left);
int y_p_color = y->p->color;
if (y_is_left) {
rb_tree_right_rotation(T, y->p);
y->right->color = BLACK;
}
else {
rb_tree_left_rotation(T, y->p);
y->left->color = BLACK;
}
x->color = BLACK;
y->color = y_p_color;
}
rb_tree_delete_case_B_a_b_fix(RedBlackTree* T, TreeNode* x) {
TreeNode* y = x->p;
int y_is_left = (y == y->p->left);
y->color = RED;
x->color = BLACK;
if (y_is_left) {
rb_tree_left_rotation(T, y);
}
else {
rb_tree_right_rotation(T, y);
}
// 交换 x 和 y 指针
TreeNode* t = x;
x = y;
y = t;
// 化为 B->a->a
rb_tree_delete_case_B_a_a_fix(T, x);
}
rb_tree_delete_case_B_b_a_fix(RedBlackTree* T, TreeNode* y) {
y->color = RED;
y->p->color = BLACK;
}
rb_tree_delete_case_B_c_fix(RedBlackTree* T, TreeNode* y) {
y->color = BLACK;
int y_is_left = (y == y->p->left);
TreeNode* new_y;
if (y_is_left) {
rb_tree_right_rotation(T, y->p);
y->right->color = RED;
new_y = y->right->left;
}
else {
rb_tree_left_rotation(T, y->p);
y->left->color = RED;
new_y = y->left->right;
}
// new_y 和旧的 y 是同向的
// 如果 new_y 有红色子结点，跳转B.a.a 或者 B.a.b
if ((y_is_left && new_y->left->color == RED) || (!y_is_left && new_y->right->color == RED)) {
rb_tree_delete_case_B_a_a_fix(T, y_is_left ? new_y->left : new_y->right);
}
else if ((y_is_left && new_y->right->color == RED) || (!y_is_left && new_y->left->color == RED)) {
rb_tree_delete_case_B_a_b_fix(T, y_is_left ? new_y->right : new_y->left);
}
// 如果 new_y 有没有子结点，由于 new y 的双亲是红色的，跳转B.b.a
else if (new_y->left->color == BLACK && new_y->right->color == BLACK) {
rb_tree_delete_case_B_b_a_fix(T, new_y);
}
}
rb_tree_delete_case_B_b_b_fix(RedBlackTree* T, TreeNode* y) {
y->color = RED;
TreeNode* new_z = y->p;
if (new_z == T->root) {
return;
}
int new_z_is_left = (new_z == new_z->p->left);
TreeNode* new_y = (new_z_is_left ? new_z->p->right : new_z->p->left);
if (new_y->color == BLACK && (
(new_z_is_left && new_y->right != T->NIL && new_y->right->color == RED) ||
(!new_z_is_left && new_y->left != T->NIL && new_y->left->color == RED)
)) {
// 转 B.a.a后结束
rb_tree_delete_case_B_a_a_fix(T, new_z_is_left ? new_y->right : new_y->left);
}
else if (new_y->color == BLACK && (
(new_z_is_left && new_y->left != T->NIL && new_y->left->color == RED) ||
(!new_z_is_left && new_y->right != T->NIL && new_y->right->color == RED)
)) {
// 转 B.a.b后结束
rb_tree_delete_case_B_a_b_fix(T, new_z_is_left ? new_y->left : new_y->right);
}
// 注意，这里使用“y是不是有俩个黑色的子结点”而不是使用“y是不是有两个NIL子结点”
else if (new_y->color == BLACK && new_y->left->color == BLACK && new_y->right->color == BLACK && new_z->p->color == RED) {
// 转 B.b.a后结束
rb_tree_delete_case_B_b_a_fix(T, new_y);
}
else if (new_y->color == BLACK && new_y->left->color == BLACK && new_y->right->color == BLACK && new_z->p->color == BLACK) {
// 继续递归 B.b.b
rb_tree_delete_case_B_b_b_fix(T, new_y);
}
else if (new_y->color == RED) {
// 转 B.c后结束
rb_tree_delete_case_B_c_fix(T, new_y);
}
}
rb_tree_delete_case_A(RedBlackTree* T, TreeNode* z) {
// 直接删除
if (z == z->p->left) {
z->p->left = T->NIL;
}
else {
z->p->right = T->NIL;
}
free(z);
}
rb_tree_delete_case_B(RedBlackTree* T, TreeNode* z) {
int z_is_left;
TreeNode* y;
// 先删除z
if (z == z->p->left) {
z->p->left = T->NIL;
y = z->p->right;
z_is_left = 1;
}
else {
z->p->right = T->NIL;
y = z->p->left;
z_is_left = 0;
}
// 如果z是根节点，则删除后是空树，不需要考虑z的兄弟节点了，因为根本不存在
if (z == T->root) {
T->root = T->NIL;
return;
}
TreeNode* z_p = z->p;
free(z);
// 其他再根据不同的情况进行调整
// b.a.a
if (y->color == BLACK && (
(z_is_left && y->right != T->NIL && y->right->color == RED) ||
(!z_is_left && y->left != T->NIL && y->left->color == RED)
)) {
rb_tree_delete_case_B_a_a_fix(T, z_is_left ? y->right : y->left);
}
// b.a.b
else if (y->color == BLACK && (
(z_is_left && y->left != T->NIL && y->left->color == RED) ||
(!z_is_left && y->right != T->NIL && y->right->color == RED)
)) {
rb_tree_delete_case_B_a_b_fix(T, z_is_left ? y->left : y->right);
}
// b.b.a
else if (y->color == BLACK && y->left == T->NIL && y->right == T->NIL && z_p->color == RED) {
rb_tree_delete_case_B_b_a_fix(T, y);
}
// b.b.b
else if (y->color == BLACK && y->left == T->NIL && y->right == T->NIL && z_p->color == BLACK) {
rb_tree_delete_case_B_b_b_fix(T, y);
}
// b.c
else if (y->color == RED) {
rb_tree_delete_case_B_c_fix(T, y);
}
}
rb_tree_transplant(RedBlackTree* T, TreeNode* u, TreeNode* v) {
if (u->p == T->NIL) {
T->root = v;
}
else if (u == u->p->left) {
u->p->left = v;
}
else {
u->p->right = v;
}
v->p = u->p;
}
rb_tree_delete_case_C(RedBlackTree* T, TreeNode* z) {
TreeNode* y;
if (z->left == T->NIL) {
y = z->right;
}
else {
y = z->left;
}
rb_tree_transplant(T, z, y);
y->color = BLACK;
free(z);
}
TreeNode* b_tree_search_min(RedBlackTree* T, TreeNode* root) {
if (root == T->NIL) {
return T->NIL;
}
TreeNode* ans = root;
while (ans->left != T->NIL) {
ans = ans->left;
}
return ans;
}
TreeNode* rb_tree_search_suc(RedBlackTree* T, TreeNode* x) {
if (x->right != T->NIL) {
return b_tree_search_min(T, x->right);
}
TreeNode* y = x->p;
while (y != T->NIL && x == y->right) {
x = y;
y = y->p;
}
return y;
}
rb_tree_delete_case_D(RedBlackTree* T, TreeNode* z) {
TreeNode* x = rb_tree_search_suc(T, z);
z->key = x->key;
rb_tree_delete(T, x);
}
rb_tree_delete(RedBlackTree* T, TreeNode* z) {
// A情况
if (z->color == RED && z->left == T->NIL && z->right == z->left) {
rb_tree_delete_case_A(T, z);
}
// B情况
else if (z->color == BLACK && z->left == T->NIL && z->right == T->NIL) {
rb_tree_delete_case_B(T, z);
}
// C情况
else if ((z->left == T->NIL && z->right != T->NIL) || (z->right == T->NIL && z->left != T->NIL)) {
rb_tree_delete_case_C(T, z);
}
// D情况
else if (z->left != T->NIL && z->right != T->NIL) {
rb_tree_delete_case_D(T, z);
}
}
// ======= 删除结束部分 ==========
int valid;
int dfsValid(RedBlackTree* T, TreeNode* root, TreeNode* p) {
if (root->color != RED && root->color != BLACK) {
// 性质1
valid = -1;
}
if (root == T->NIL && root->color != BLACK) {
// 性质3
valid = -1;
}
if (root->color == RED && (root->left->color == RED || root->right->color == RED)) {
// 性质4
valid = -1;
}
if (root != T->NIL && root->p != p) {
valid = -1;
}
// 性质5
if (root != T->NIL) {
int leftBlackNodeCnt = dfsValid(T, root->left, root);
int rightBlackNodeCnt = dfsValid(T, root->right, root);
if (leftBlackNodeCnt != rightBlackNodeCnt) {
valid = -1;
}
return leftBlackNodeCnt + (root->color == BLACK ? 1 : 0);
}
// 搜索树性质
if (root->left != T->NIL && root->left->key > root->key) {
valid = -1;
}
if (root->right != T->NIL && root->right->key < root->key) {
valid = -1;
}
return (root->color == BLACK ? 1 : 0);
}
int redBlackTreeValid(RedBlackTree* T) {
// 根节点是黑色的（性质2），空节点是黑色的（性质3）
if (T->root->color != BLACK || T->NIL->color != BLACK) {
return -1;
}
if (T->root->p != T->NIL) {
return -1;
}
valid = 1;
dfsValid(T, T->root, T->NIL);
if (valid == -1) {
printf("*********Not valid red black tree!*********\n");
return -1;
}
return 1;
}
// 生成[a, b)范围内的随机整数
int generateRandomNumber(int a, int b) {
return a + rand() % (b - a);
}
void printdfs(RedBlackTree* T, TreeNode* root) {
if (root == T->NIL) {
return;
}
printf("%d:%c left = %d, right = %d\n", root->key, root->color == RED ? 'R' : 'B', root->left->key, root->right->key);
printdfs(T, root->left);
printdfs(T, root->right);
}
int final_test(int len, int debug) {
if (len > 10000) {
}
RedBlackTree* T = (RedBlackTree*)malloc(sizeof(RedBlackTree));
initRedBlackTree(T);
redBlackTreeValid(T);
int nums[10000];
// 测试插入
printf("----- start insert -----\n");
for (int i = 0; i < len;i++) {
nums[i] = generateRandomNumber(0, len);
if (debug) {
printf("insert %d\n", nums[i]);
}
TreeNode* z = (TreeNode*)malloc(sizeof(TreeNode));
z->color = RED;
z->p = T->NIL;
z->left = T->NIL;
z->right = T->NIL;
z->key = nums[i];
rb_tree_insert(T, z);
redBlackTreeValid(T);
}
// 测试删除
printf("----- start delete -----\n");
int remain = len;
int deleteIdx, deleteKey;
for (int i = 1; i <= len;i++) {
deleteIdx = generateRandomNumber(0, remain);
// 避免下次再被选到
deleteKey = nums[deleteIdx];
// printf("delete %d\n", deleteKey);
nums[deleteIdx] = nums[remain - 1];
nums[remain - 1] = deleteKey;
TreeNode* z = rb_tree_search(T, T->root, deleteKey);
if (z == T->NIL) {
printf("No found!");
}
else {
if (debug) {
printf("delete %d\n", deleteKey);
}
rb_tree_delete(T, z);
if (redBlackTreeValid(T) == -1) {
printf("delete error just now on %d\n", deleteKey);
}
}
remain--;
}
}
int main() {
// 重新设置随机数种子
srand(time(NULL));
for (int i = 1; i <= 10; i++) {
final_test(9999, 0);
}
return 0;
}
后记
红黑树应用十分广，因为它能够做到插入、删除和检索都接近O(\log n)，没有平衡二叉树调整那么频繁，却能够接近平衡二叉树的查询时间，当然由于其树型结构，当面临大量顺序读写时，比不上数组，因为数组能够借助硬件缓存，使得CPU直接从高速缓存中拿到数据，而红黑树难以做到高命中率。在随机读写方面，除了哈希表，红黑树和平衡二叉树天下无敌！
参考文献
算法导论第三版