01数据结构-红黑树
前言
我们来回顾一下搜索树的“进化过程”
二叉搜索树的特性，二叉树，左子树的值小于根节点的值，右子树的值大于根节点的值，中序遍历的情况下是有序的序列，缺点是在特殊情况下，树可能会退化成单链表
平衡二叉树的特性：二叉树，左子树的值小于根节点的值，右子树的值大于根节点的值，中序遍历的情况下是有序的序列，树的高度可控，优点是静态特性最优，树一旦构建完成，查找时，效率最高，缺点是动态特性稍差，插入，删除节点时平衡因子容易失衡，需要频繁进行旋转操作。
实际工程中，我们大量的数据都是动态性的，不可能有个现成的平衡二叉树让你查找，我们就想能不能再优化一下平衡二叉树，这就是我们今天要讲的红黑树
1.红黑树概述
红黑树(Red-Black Tree，简称R-B Tree)，它一种特殊的二叉查找树。
红黑树特性：
(1) 每个节点或者是黑色，或者是红色。
(2) 根节点是黑色。
(3) 每个叶子节点是黑色。 [注意：这里叶子节点，是指为空的叶子节点！] 红黑树不认为6，11，15，22，27是叶子节点，反而认为所有的我们平时认为的叶子节点最后一定会指向一个NULL，而这个空节点才是红黑树认为的叶子节点。
(4) 如果一个节点是红色的，则它的子节点必须是黑色的。[不存在两个相邻的红色节点] 红色节点没有提供黑高，红色节点一旦多了的话，树的高度变高，查找效率变低。
(5) 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。[黑高相同]
红黑树(二叉树，左小右大，颜色约束，中序遍历是有序序列，树高度可控)的删除，插入平衡因子没有那么苛刻，调整二叉树频率降低，查找效率居中
在C++的STL中：
map，set 底层都是红黑树，容器得到的数据是有序数据。
unorder_map，unorder_set底层都是哈希表，无序。
1.1红黑树的黑高
在一颗红黑树中，从某个结点 x 出发（不包含该结点）到达一个叶结点的任意一条简单路径上包含的黑色结点的数目称为黑高 ，记为 bh(x) 。
例如下图的节点6的黑高和红色节点15的黑高是一样的，都是2
1.2如何保持红黑树平衡
假设有3个节点的序列，那么在红黑树当中，不可能出现3个节点的单链表，如图：
我们发现当有3个节点的序列时，如果我们按单链表的方式排列，无论如何着色，都不可能使其满足红黑树的要求，唯一的办法就是调整树的高度和染色。
1.3红黑树的应用
大多数自平衡BST(self-balancing BST) 库函数都是用红黑树实现的，比如C++中的map 和 set（或者 Java 中的 TreeSet 和 TreeMap）。
红黑树也用于实现 Linux 操作系统的 CPU 调度。完全公平调度（Completely Fair Scheduler）使用的就是红黑树。
红黑树也用于Linux提供的epoll多路复用的底层结构，便于快速增加、删除和查找网络连接的节点。
2.红黑树插入操作思路
2.1 将红黑树当作一颗二叉查找树，将节点插入
红黑树本身就是一颗二叉查找树，将节点插入后，该树仍然是一颗二叉查找树。也就意味着，树的键值仍然是有序的。此外，无论是左旋还是右旋，若旋转之前这棵树是二叉查找树，旋转之后它一定还是二叉查找树。这也就意味着，任何的旋转和重新着色操作，都不会改变它仍然是一颗二叉查找树的事实。
那接下来，我们就来想方设法的旋转以及重新着色，使这颗树重新成为红黑树！
2.2 将插入的节点着色为红色
为什么着色成红色，而不是黑色呢？为什么呢？再看红黑树的性质：
将插入的节点着色为红色，不会违背"特性(5)"！少违背一条特性，就意味着我们需要处理的情况越少。接下来，就要努力的让这棵树满足其它性质即可；满足了的话，它就又是一颗红黑树了。如果插入节点是根节点，将该节点转换为黑色。
第二步中，将插入节点着色为"红色"之后，不会违背"特性(5)“。那它到底会违背哪些特性呢？
对于"特性(1)”，显然不会违背了。因为我们已经将它涂成红色了。
对于"特性(2)“，显然也不会违背。在第一步中，我们是将红黑树当作二叉查找树，然后执行的插入操作。而根据二叉查找数的特点，插入操作不会改变根节点。所以，根节点仍然是黑色。
对于"特性(3)”，显然不会违背了。这里的叶子节点是指的空叶子节点，插入非空节点并不会对它们
造成影响。
对于"特性(4)"，是有可能违背的！
那接下来，想办法使之"满足特性(4)"，就可以将树重新构造成红黑树了。
3.红黑树红红节点的处理
插入操作需要调整的情况，变为了性质4的违背后的调整了，那么，如何进行调整那？
红红节点一定有叔叔节点，调整的核心就是看叔叔节点的颜色，分情况讨论。
一个是叔叔节点是红色，一个是叔叔节点是黑色。当叔叔节点是黑色时，从LL,LR,RR,RL中进行考虑。
3.1叔叔节点是黑色
- LL：
当为LL类型的时候，如果我们按照之前平衡二叉树的方法直接旋转如图，发现满足不了红黑树的性质
所以当叔叔节点为黑色节点的时候我们有三个步骤：
(01) 将“父节点”设为“黑色”。
(02) 将“祖父节点”设为“红色”。
(03) 以“祖父节点”为支点进行左旋。
LR:
当为LR类型的时候，我们类比之前平衡二叉树的LR类型的时候，先右旋一次转成LL类型，如图：
再调用LL类型的旋转方法即可。
同理RR和RL我就不列举了，只展示一下，相信大家应该懂其中的道理
-RR:
RL:
3.2叔叔节点是红色
当叔叔节点为红色的时候，我们将矛盾向上转移：
(01) 将“父节点”设为黑色。
(02) 将“叔叔节点”设为黑色。
(03) 将“祖父节点”设为“红色”。
(04) 将“祖父节点”设为“当前节点”；
这样红色冲突就向上传播了，在传播途中遇到叔叔节点是黑色的时候就用3.1中叔叔节点是黑色中的插入逻辑来操作。如图
4.红黑树插入代码实现
数据结构的设计
typedef int KeyType;
// 红黑树的节点结构
typedef struct _rb_node {
char color;
KeyType key;
struct _rb_node *left;
struct _rb_node *right;
struct _rb_node *parent;
} RBNode;
// 红黑树的树头
typedef struct {
RBNode *root;
int count;
} RBTree;
由于我们不仅要颜色还要表示叔叔节点，所以我们在原来二叉树的数据结构基础上增加了颜色和parent两个变量，找叔叔节点的时候只需要找该节点的parent节点的parent节点的左孩子或者右孩子，方便了我们表示。
创建红黑树：RBTree * createRBTree();
RBTree * createRBTree() {
RBTree *tree =malloc(sizeof(RBTree));
if (tree==NULL) {
fprintf(stderr,"tree malloc failure!!!");
return NULL;
}
tree->count=0;
tree->root=NULL;
return tree;
}
释放红黑树:
static void destroyRBNode(RBTree *tree, RBNode *node) {
if (node) {
destroyRBNode(tree,node->left);
destroyRBNode(tree,node->right);
free(node);
tree->count--;
}
}
void releaseRBTree(RBTree *tree) {
destroyRBNode(tree, tree->root);
printf("released tree count = %d\n", tree->count);
free(tree);
}
这些基本都是之前写过的代码，我就不过多描述。
左旋：static void leftRotate(RBTree *tree, RBNode *x);
/* 将x进行左旋，将左，右，父节点都进行更新
* px px
* | |
* x y
* / \ -------》 / \
* lx y x ry
* / \ / \
* ly ry lx ly
*/
static void leftRotate(RBTree *tree, RBNode *x) {
RBNode *y=x->right;
//维护ly的两边关系
x->right=y->left;
//需要判断，防止段错误
if (y->left!=NULL) {
y->left->parent=x;
}
//维护px下面那个节点的两边关系
y->parent=x->parent;
if (x->parent) {
if (x==x->parent->left) {
x->parent->left=y;
}
else {
x->parent->right=y;
}
}else {
tree->root = y;
}
//维护x y两个节点之间那条边的关系
x->parent=y;
y->left=x;
}
由于我们在结构体中加入了parent变量的关系，我们旋转维护关系的时候需要从两边维护，不能只单独维护一边，区别于我在《01数据结构-平衡二叉树》写的维持平衡旋转时的代码。
右旋：void rightRotate(RBTree* tree, RBNode *y) ;
/* 将y进行左旋，将左、右、父节点进行更新
* py py
* | |
* y x
* / \ --(右旋)--> / \
* x ry lx y
* / \ / \
* lx rx rx ry
* */
void rightRotate(RBTree* tree, RBNode *y) {
RBNode *x=y->left;
//维护rx的两边关系
y->left=x->right;
if (x->right) {
x->right->parent=y;
}
//维护py下面那个节点的两边关系
x->parent=y->parent;
if (y->parent) {
if (y==y->parent->left) {
y->parent->left=x;
}
else{
y->parent->right=x;
}
}
else {
tree->root=x;
}
//维护x y两个节点之间那条边的关系
y->parent=x;
x->right=y;
}
插入逻辑:void insertRBTree(RBTree *tree, KeyType key);
/* 1. 插入节点，如果父节点是黑色，那么不需要调整
* 2. 如果父节点是红色，此时有了两个红红节点，进行调整
* 2.1 叔叔节点是红色
* 重新着色，叔叔节点变为黑色（g->红色，p->黑，u->黑），转入到2.2的大逻辑判断
* 2.2 叔叔节点是黑色
* 2.2.1 cur左孩子，par是左孩子
* g右旋，g->红色，p->黑
* 2.2.2 cur右孩子，par是左孩子
* p左旋，cur和par交换，然后重复2.2.1
* 2.2.3 cur右孩子，par是右孩子
* g左旋，g->红色，p->黑
* 2.2.4 cur左孩子，par是右孩子
* p右旋，cur和par交换，然后重复2.2.3
*/
static void insertFixup(RBTree *tree, RBNode *node) {
RBNode *parent, *grandParent;
RBNode *uncle;
RBNode *tmp;
parent = node->parent;
//处理可能向上传播的红色冲突
while (parent != NULL && parent->color == RED) {
// 违反红红节点
grandParent = parent->parent;
if (parent == grandParent->left) {
uncle = grandParent->right;
} else {
uncle = grandParent->left;
}
if (uncle && uncle->color == RED) {
uncle->color = BLACK;
parent->color = BLACK;
grandParent->color = RED;
node = grandParent;
parent = grandParent->parent;
continue;
}
if (grandParent->left == parent) { // L
// R
if (parent->right == node) {
leftRotate(tree, parent);
tmp = parent;
parent = node;
node = tmp;
}
// LL
rightRotate(tree, grandParent);
grandParent->color = RED;
parent->color = BLACK;
} else {
if (parent->left == node) {
rightRotate(tree, parent);
tmp = parent;
parent = node;
node = tmp;
}
leftRotate(tree, grandParent);
grandParent->color = RED;
parent->color = BLACK;
}
}
tree->root->color = BLACK;
}
void insertRBTree(RBTree *tree, KeyType key) {
// 1. 先创建一个红色的节点
RBNode *node = createRBNode(key);
// 2. 根据二叉搜索树的规则找到待插入的节点
RBNode *cur = tree->root;
RBNode *pre = NULL;
while (cur) {
pre = cur;
if (key < cur->key) {
cur = cur->left;
} else if (key > cur->key) {
cur = cur->right;
} else {
printf("insert %d have exist!\n", key);
return;
}
}
// 3. 在对应位置上插入，若根，更新tree
node->parent = pre;
if (pre) {
if (key < pre->key) {
pre->left = node;
} else {
pre->right = node;
}
} else {
tree->root = node;
}
// 4. 修正红黑树
insertFixup(tree, node);
tree->count++;
}
先来看大的逻辑，由于我们有设置父节点，所以我们在插入的时候需要维护两边的关系，因此我们定义两个指针，一个cur指向往后面走，一个pre指针记录cur指针走过的位置， 首先创建一个默认颜色为红色的新节点，再根据二叉搜索树的规则找到待插入的节点，将其parent设为pre,然后确定新节点node是pre的左孩子还是右孩子，最后修正红黑树。
再来看修正红黑树的代码insertFixup(RBTree *tree, RBNode *node)。
我们定义了几个RBNode指针用于指向我们在代码中需要进行频繁操作的位置，先初始化父指针，注意，写代码的时候一定要记得判空，不要发生NULL->parent类似的段错误，在while循环里处理逻辑。为什么需要while循环呢？当处理一个节点的红色冲突时，通过重新着色和旋转修复后，可能会使祖父节点（grandParent）变成红色。如果祖父节点的父节点也是红色，就会产生新的红色冲突（红红相邻），需要继续向上修复。循环结束条件是当parent == NULL，到达根节点或者parent->color == BLACK：父节点为黑色，不再违反"红红相邻"规则。
在while循环里初始化好各个指针，当叔叔节点存在且为红色的时候，我们采用3.2叔叔节点是红色逻辑处理情况，将红色传递给上层，然后跳过此次循环，若遇到叔叔节点存在且为黑色时，我们采用3.1叔叔节点是黑色逻辑处理情况，注意在LR和RL中，由于先旋转了一次，会导致parent和node的指向发生改变，所以还需要更新两者的指向。
最后当节点被提升到根节点时，最后需要将根节点设为黑色（tree->root->color = BLACK）
遍历：void printRBTree(const RBTree *tree);
static void printRBNode(RBNode *node, int key, int dir) {
if (node) {
if (dir == 0) {
printf("%2d[B] is root\n", node->key);
} else {
printf("%2d[%c] is %2d's %s\n", node->key, (node->color == RED) ? 'R' : 'B', key,
(dir == 1)? "right child": "left child");
}
printRBNode(node->left, node->key, -1);
printRBNode(node->right, node->key, 1);
}
}
void printRBTree(const RBTree *tree) {
printRBNode(tree->root, tree->root->key, 0);
}
- 当
printRBNode被首次调用（通常是通过printRBTree函数）时，dir参数被设置为 0，表示当前节点是根节点。道理和前面的先序遍历是一样的 - 在递归调用
printRBNode时，dir参数会根据当前节点是左子节点还是右子节点来设置：- 左子节点时，
dir设置为 -1。 - 右子节点时，
dir设置为 1。
- 左子节点时，
来测试一下：
#include "RBTree.h"
int main() {
int data[] = {55, 40, 65, 60, 75, 57, 63, 56};
RBTree *rbTree = createRBTree();
for (int i = 0; i < sizeof(data) / sizeof(data[0]); i++) {
insertRBTree(rbTree, data[i]);
}
printRBTree(rbTree);
releaseRBTree(rbTree);
return 0;
}
结果：
D:\work\DataStruct\cmake-build-debug\05_Search\RedBlackTree.exe
60[B] is root
55[R] is 60's left child
40[B] is 55's left child
57[B] is 55's right child
56[R] is 57's left child
65[R] is 60's right child
63[B] is 65's left child
75[B] is 65's right child
released tree count = 0
进程已结束，退出代码为 0
5.红黑树删除操作思路
删除红黑树中的节点的时候有可能会破坏性质2、4、5，我们写删除操作逻辑的时候就要考虑这些问题，使得删除后的红黑树依旧满足5大性质成为一棵红黑树。
红黑树的大致删除思路是：
a. 将红黑树当作一颗二叉查找树，将该节点从二叉查找树中删除；
b. 通过"旋转和重新着色"等一系列来修正该树，使之重新成为一棵红黑树。
详细描述如下：
假设y是要删除的节点，x是用来替换的节点（当y是叶节点时，x是NULL节点，当做黑色节点处理）
执行标准的BST删除操作
在标准的 BST 删除操作中，我们最终都会以删除一个叶子结点或者只有一个孩子的结点而结束（对于内部节点，就是要删除结点左右孩子都存在的情况，最终都会退化到删除结点是叶子结点或者是只有一个孩子的情况）。所以我们仅需要处理被删除结点是叶结点或者仅有一个孩子的情况。简单情况：y或者x有一个是红色节点
如果 x 或者 y 是红色，我们将替换结点 y 的结点 x 标记为黑色结点（这样黑高就不会变化）。注意这里是 x 或者 y 是红色结点，因为在一棵红黑树中，是不允许有两个相邻的红色结点的，而结点 y 是结点 x 的父结点，因此只能是 x 或者 y 是红色结点。 （如果y本身就是红色节点，那么删除y对黑高没有任何影响；如果y是黑色节点，x是红色节点，由于我们删除y的时候是把x中的值移上去，"y"黑色的性质没有改变。）复杂情况：y和x都是黑色节点
双黑节点的定义：
当要删除结点 y 和孩子结点 x 都是黑色结点，删除结点 y ，导致结点 x 变为双黑结点。当 x 变成双黑结点时，我们的主要任务将变成将该双黑结点 x 变成普通的单黑结点。一定要特别注意，NULL结点为黑色结点 ， 所以删除黑色的叶子结点就会产生一个双黑结点。 （你可以理解为，一个节点占两个黑高）
3.1 当前节点x是双黑节点且不是根节点
（a） x的兄弟节点w是黑色且w的孩子节点至少有一个是红色的
（b）x的兄弟节点w是黑色且它的两个孩子都是黑色的
（c）x的兄弟节点w是红色
3.2 当前节点x是双黑节点且是根节点
5.1 w是黑色且w的孩子节点至少有一个是红色的
如图，我们给各个重要位置标上号，删除25以后它的子节点替换上来，由于要维持黑高相等的特性，此时的x节点是双黑节点。
我们需要把双黑结点 x 变成普通的单黑结点。就需要对红黑树进行旋转，重新上色。由于是有多个黑色在x上，我们就可以想到“推”一个黑色出去，我们想办法把删除节点的父节点的颜色先设为空，然后把多余的黑色给一个给父节点就行，那么我们怎么把父节点的颜色设为设为空呢？我们发现r的颜色是红色，我们知道红色对黑高没有作用，我们就想到能不能把r的红色推出去，然后从r向上一直往下推，直到推到删除节点的父节点的时候，我们不就把父节点的颜色给推空了吗，事实也确实如此，我们把w的颜色给r，把p的颜色给w，如图：
注意此时如果我们直接把x中多余的黑色移到p中，对于p上面的子红黑树而言，依旧是没有黑高相等的，如果我们直接把x中多余的黑色移到p中，对于上面的子红黑树，加上p左边的黑高是4，右边的黑高是2，显然左边的重了，所以很自然联想到以p作为基结点，右旋一次就可以了。我们也可以认为是LL类型。
这样做的前提是一定要有同向红，意思就是红色的节点要一直在删除节点的一侧，像下面这张图就不能这样做，一定要先转成同向红，再按上面的思路来：
我们以w为基节点左旋一次，把右边的红转到左边，并且把旋转之后的w的颜色设为黑色，r的颜色设为红色，这样就转成了我们的同向红，再用LL类型的方法进行修正，我们认为这种类型是LR类型。
此外还有RR类型和RL类型，相信大家应该懂得什么意思，我就不列举了。
5.2w是黑色且w的孩子节点都是黑色
假设以 10 为根结点的子树为整棵树的左子树，删除结点 9 ，产生双黑结点 a 且其兄弟结点 12（w） 为黑色，兄弟结点的左右孩子均为黑色。此时双黑结点的兄弟结点 12 变为红色结点，然后将 x 的父结点 10 变为双黑结点，一直向上判断。
这个情况的处理思想：是将x中多余的一个黑色属性上移(往根方向移动)，此时，需要注意的是：所有经过x的分支中黑节点个数没变化；但是，所有经过x的兄弟节点的分支中黑色节点的个数增加了1(因为x的父节点多了一个黑色属性)！为了解决这个问题，我们需要将“所有经过x的兄弟节点的分支中黑色节点的个数减1”即可，那么就可以通过将x的兄弟节点由黑色变成红色来实现。 直到遇到5.1 w是黑色且w的孩子节点至少有一个是红色的的情况时 ，我们就可以套用上面的代码逻辑。
5.3w是红色节点
红色兄弟节点无法提供额外的黑色：在修正过程中，我们需要从兄弟子树"借"一个黑色节点来补偿被删除的黑色节点。但红色节点不能算作有效的黑色高度贡献者，所以我们想到将兄弟节点染黑：
（1）将w设置为黑色
（2）将p设置为红色
（3）对父进行旋转
（4）重新设置w
如图我们先删除18，x为双黑节点
我们对其进行上述1，2，3，4步操作如图
如图我们重新设置w和p，发现此时双黑节点的兄弟节点就是黑色，就有能力"借"一个黑色节点来补偿被删除的黑色节点，后面的操作逻辑，就继续判断是属于5.1 w是黑色且w的孩子节点至少有一个是红色的 类型还是5.2w是黑色且w的孩子节点都是黑色类型，最后完善了所有的逻辑完备性。
总结：
1.如果我们删除的红色的节点，那么直接删除就行
2.如果删除的是节点是黑色：
2.1：如果删除后的节点的兄弟节点是红色的，转换成黑色
2.2：如果删除后的节点的兄弟节点是黑色的：
2.2.1：兄弟节点的两个子节点都是黑色，"递归"找到双黑兄弟的节点为红色，然后往后继续处理
2.2.2：兄弟有一个异向红，转成同向红
2.2.3：同向红，旋转着色。
最终我们发现，只要删除的节点是黑色的节点，我们都要矛盾转移成同向红，然后处理逻辑。接下来来看代码。
6.红黑树删除代码实现
我们要删除节点，就要先找到这个节点，所以我们封装一个查找函数:
RBNode * searchRBTree(const RBTree *tree, KeyType key);
RBNode * searchRBTree(const RBTree *tree, KeyType key) {
RBNode *node=tree->root;
while (node) {
if (key<node->key) {
node=node->left;
}else if (key>node->key) {
node=node->right;
}else {
return node;
}
}
return NULL;
}
这个函数比较简单，我就不过多叙述，下面来看大的删除逻辑：
static void deleteRBNode(RBTree *tree, RBNode *node) {
RBNode *y; // 真正删除的节点
RBNode *x; // 替换节点
RBNode *parent; // 替换节点是NULL，无法再访问到父节点
if (node->left == NULL || node->right == NULL) {
y = node;
} else { // 拥有左右子树，需要找后继节点
y = node->right;
while (y->left) {
y = y->left;
}
}
// 真正删除的节点首地址找到了，确定替换节点
if (y->left) {
x = y->left;
} else {
x = y->right;
}
parent = y->parent;
// 开始更新替换节点和原父节点的关系
if (x) {
x->parent = parent;
}
if (y->parent == NULL) {
// 说明删除的是根节点
tree->root = x;
} else if (y == y->parent->left) {
y->parent->left = x;
} else {
y->parent->right = x;
}
// 更新有左右孩子的根节点为后继节点的值，处理度为2的情况
if (y != node) {
node->key = y->key;
}
// 如果删除的节点是黑色，那么就需要调整
if (y->color == BLACK) {
deleteFixup(tree, x, parent);
}
// 调整完成，或者删除节点是红色，直接释放
free(y);
}
定义三个重要指针分别表示待删除节点，替换的节点和待删除节点的父节点，以便于处理删除后的节点之间的关系。开始对x，y，parent赋值，如果是度为0或1的节点，y=node，否则矛盾转移找后继节点，把后继节点交给y，随后确定替换节点，如果待删除的左存在就把左边确定为替换节点，反之右边存在就给右边，提前保存y->parent的值，否则如果 x 是 NUL，无法通过 x->parent 获取父节点，会发生段错误必须提前保存 parent，否则在修正函数中无法知道父节点是谁。开始更新替换节点和原父节点的关系，更新有左右孩子的根节点为后继节点的值，处理度为2的情况，最后判断如果删除的节点的颜色是黑色，那么就需要修正，否则直接释放即可。接下来看修正逻辑：static void deleteFixup(RBTree *tree, RBNode *x, RBNode *parent)
static void deleteFixup(RBTree *tree, RBNode *x, RBNode *parent) {
RBNode *w;
while (tree->root != x && (!x || x->color == BLACK)) {
if (parent->left == x) { // x是父节点的左孩子
w = parent->right; // w是x兄弟节点
if (w->color == RED) {
// case1 x的兄弟节点是红色
w->color = BLACK;
parent->color = RED;
leftRotate(tree, parent);
w = parent->right;
}
// 兄弟节点都是黑色
if ((!w->left || w->left->color == BLACK) &&
(!w->right || w->right->color == BLACK)) {
// case2 x的兄弟是黑色，x的兄弟的两个孩子都是黑色
w->color = RED;
x = parent;
parent = x->parent;
} else {
if (!w->right || w->left->color == BLACK) {
// case3 兄弟节点是黑色，x的兄弟节点的左孩子是红色
w->left->color = BLACK;
w->color = RED;
rightRotate(tree, w);
w = parent->right;
}
// case4 x的兄弟节点是黑色，x的兄弟节点右孩子是红色
w->color = parent->color;
parent->color = BLACK;
w->right->color = BLACK;
leftRotate(tree, parent);
x = tree->root;
break;
}
} else {
w = parent->left;
if (w->color == RED) {
// case1: x的兄弟w是红色
w->color = BLACK;
parent->color = RED;
rightRotate(tree, parent);
w = parent->left;
}
if ((!w->left || w->left->color == BLACK) &&
(!w->right || w->right->color == BLACK)) {
// case2 x的兄弟w是黑色，且w的两个孩子都是黑色
w->color = RED;
x = parent;
parent = x->parent;
} else {
if (!w->left || w->left->color == BLACK) {
// case3 x的兄弟w是黑色的，并且w的左孩子是黑色
w->right->color = BLACK;
w->color = RED;
leftRotate(tree, w);
w = parent->left;
}
// case4
w->color = parent->color;
parent->color = BLACK;
w->left->color = BLACK;
rightRotate(tree, parent);
x = tree->root;
break;
}
}
}
if (x) {
x->color = BLACK;
}
}
分大的两种情况，当删除节点是父节点的左边和当删除节点是父节点的右边，两边的逻辑处理是一样的，只是方向不同，我这里就只删除节点是父节点的右边举例。进入修正函数，开始循环处理逻辑，循环条件包括两部分
1.tree->root != x，因为如果 x 已经是根节点，就不需要继续修正了（根节点总是黑色）
为什么根节点不需要修正？
- 1双黑问题的本质
在红黑树删除中，我们修正的是"双黑"问题，这表示某条路径上缺少了一个黑色节点。但根节点很特殊：
根节点没有父节点：无法从其他路径"借"黑色节点
根节点是所有路径的起点：如果根节点是双黑，意味着整棵树都缺少黑色高度
1.2. 根节点的处理方式
如果修正过程中 x 变成了根节点：
while (tree->root != x && (!x || x->color == BLACK)) {
// 修正逻辑...
}
// 循环退出后：
if (x) {
x->color = BLACK; // 确保根节点为黑色
}
处理逻辑：
如果 x 是根节点，退出修正循环最后统一将 x 染成黑色（确保根节点为黑色）这样既简单又保证了红黑树性质
2.!x || x->color == BLACK，这个条件表示：只有当 x 是黑色节点或 NIL 节点时才需要继续修正，因为在红黑树删除中，只有删除黑色节点才会破坏红黑树的性质（黑色高度）。如果x 是红色：直接染黑即可，不会破坏平衡
当删除节点是父节点的右边的时候，对应的兄弟节点w就是父节点的左边。
进入第一个case，如果w的颜色是红色的，我们走5.3w是红色节点的逻辑，注意右旋后，由于C语言是值传递，我们在外部函数还要更新一下w，让他重新指向parent->left，此时w的颜色为黑色。这样在进入后续判断中，我们的兄弟节点就是黑色，可以套用后面的代码
进入case2，w的子节点都是黑色，注意由于红黑树中的叶子节点是黑色的，所以if判断条件中还要加!w->left和!w->right，我们走5.2w是黑色且w的孩子节点都是黑色"递归"到上层去寻找满足后续条件的节点，然后继续往下完善逻辑。
进入case3，当红色节点为异向红，我们进入5.1 w是黑色且w的孩子节点至少有一个是红色的 的异向红逻辑，把 w->right->color设为BLACK，把w设为RED,然后左旋一下兄弟节点w，还是注意由于C语言是值传递，我们在外部函数还要更新一下w。
进入case4，经过上面3个case，如果进入到了第四步，即我们在5.1 w是黑色且w的孩子节点至少有一个是红色的 中写的同向红逻辑，x = tree->root 在Case 4中的作用是，告诉循环问题已解决，可以退出，最后break。
在修正的最后要确保x->color为黑色可以把 x 想象成一个"问题气泡"：初始时，气泡在删除位置修正过程中，气泡不断上浮最后气泡可能：
1.浮到根节点（最多情况）
2.中途变成红色而破裂
3.通过Case 4直接爆炸无论哪种情况
最后都需要处理这个气泡。
调用接口：void deleteRBTree(RBTree *tree, KeyType key)
void deleteRBTree(RBTree *tree, KeyType key) {
RBNode *node = searchRBTree(tree, key);
if (node) {
deleteRBNode(tree, node);
tree->count--;
}
}
最后来测试一下：
#include "RBTree.h"
int main() {
int data[] = {55, 40, 65, 60, 75, 57, 63, 56};
RBTree *rbTree = createRBTree();
for (int i = 0; i < sizeof(data) / sizeof(data[0]); i++) {
insertRBTree(rbTree, data[i]);
}
// printRBTree(rbTree);
deleteRBTree(rbTree, 57);
printRBTree(rbTree);
releaseRBTree(rbTree);
return 0;
}
结果：
D:\work\DataStruct\cmake-build-debug\05_Search\RedBlackTree.exe
60[B] is root
55[R] is 60's left child
40[B] is 55's left child
56[R] is 55's right child
65[R] is 60's right child
63[B] is 65's left child
75[B] is 65's right child
released tree count = 0
进程已结束，退出代码为 0
红黑树的代码挺多的，好好消化一下，大概先写这些吧，今天的博客就先写到这，谢谢您的观看。