红黑树使用时的删除方法在Documentation/rbtree.txt文件内有定义：
struct mytype *data = mysearch(&mytree, "walrus");
if (data) {
rb_erase(&data->node, &mytree);
myfree(data);
}
删除红黑树节点调用的是函数：
void rb_erase(struct rb_node *victim, struct rb_root *tree);
函数rb_erase的定义在文件linux/lib/rbtree.c文件内，定义如下：
void rb_erase(struct rb_node *node, struct rb_root *root)
{
struct rb_node *rebalance;
rebalance = __rb_erase_augmented(node, root, &dummy_callbacks);
if (rebalance)
____rb_erase_color(rebalance, root, dummy_rotate);
}
EXPORT_SYMBOL(rb_erase);
红黑树的删除操作比插入要更为复杂一些。因为红黑树是有序的，所以首先我们要保证删除某个节点N之后红黑树还是有序的。由于其删除操作过于繁琐，所以它分为两个过程：（1）删除节点、（2）恢复平衡。
1.1、删除节点函数定义删除节点调用的函数是__rb_erase_augmented，定义在include/linux/rbtree_augmented.h文件内。
static __always_inline struct rb_node *
__rb_erase_augmented(struct rb_node *node, struct rb_root *root,
const struct rb_augment_callbacks *augment)
{
struct rb_node *child = node->rb_right, *tmp = node->rb_left;
struct rb_node *parent, *rebalance;
unsigned long pc;
if (!tmp) {
pc = node->__rb_parent_color;
parent = __rb_parent(pc);
__rb_change_child(node, child, parent, root);
if (child) {
child->__rb_parent_color = pc;
rebalance = NULL;
} else
rebalance = __rb_is_black(pc) ? parent : NULL;
tmp = parent;
} else if (!child) {
tmp->__rb_parent_color = pc = node->__rb_parent_color;
parent = __rb_parent(pc);
__rb_change_child(node, tmp, parent, root);
rebalance = NULL;
tmp = parent;
} else {
struct rb_node *successor = child, *child2;
tmp = child->rb_left;
if (!tmp) {
parent = successor;
child2 = successor->rb_right;
augment->copy(node, successor);
} else {
do {
parent = successor;
successor = tmp;
tmp = tmp->rb_left;
} while (tmp);
parent->rb_left = child2 = successor->rb_right;
successor->rb_right = child;
rb_set_parent(child, successor);
augment->copy(node, successor);
augment->propagate(parent, successor);
}
successor->rb_left = tmp = node->rb_left;
rb_set_parent(tmp, successor);
pc = node->__rb_parent_color;
tmp = __rb_parent(pc);
__rb_change_child(node, successor, tmp, root);
if (child2) {
successor->__rb_parent_color = pc;
rb_set_parent_color(child2, parent, RB_BLACK);
rebalance = NULL;
} else {
unsigned long pc2 = successor->__rb_parent_color;
successor->__rb_parent_color = pc;
rebalance = __rb_is_black(pc2) ? parent : NULL;
}
tmp = successor;
}
augment->propagate(tmp, NULL);
return rebalance;
}
1.2、恢复平衡函数定义
恢复平衡调用的函数是____rb_erase_color，定义在linux/lib/rbtree.c文件内。
static __always_inline void
____rb_erase_color(struct rb_node *parent, struct rb_root *root,
void (*augment_rotate)(struct rb_node *old, struct rb_node *new))
{
struct rb_node *node = NULL, *sibling, *tmp1, *tmp2;
while (true) {
sibling = parent->rb_right;
if (node != sibling) {
if (rb_is_red(sibling)) {
parent->rb_right = tmp1 = sibling->rb_left;
sibling->rb_left = parent;
rb_set_parent_color(tmp1, parent, RB_BLACK);
__rb_rotate_set_parents(parent, sibling, root,
RB_RED);
augment_rotate(parent, sibling);
sibling = tmp1;
}
tmp1 = sibling->rb_right;
if (!tmp1 || rb_is_black(tmp1)) {
tmp2 = sibling->rb_left;
if (!tmp2 || rb_is_black(tmp2)) {
rb_set_parent_color(sibling, parent,
RB_RED);
if (rb_is_red(parent))
rb_set_black(parent);
else {
node = parent;
parent = rb_parent(node);
if (parent)
continue;
}
break;
}
sibling->rb_left = tmp1 = tmp2->rb_right;
tmp2->rb_right = sibling;
parent->rb_right = tmp2;
if (tmp1)
rb_set_parent_color(tmp1, sibling,
RB_BLACK);
augment_rotate(sibling, tmp2);
tmp1 = sibling;
sibling = tmp2;
}
parent->rb_right = tmp2 = sibling->rb_left;
sibling->rb_left = parent;
rb_set_parent_color(tmp1, sibling, RB_BLACK);
if (tmp2)
rb_set_parent(tmp2, parent);
__rb_rotate_set_parents(parent, sibling, root,
RB_BLACK);
augment_rotate(parent, sibling);
break;
} else {
sibling = parent->rb_left;
if (rb_is_red(sibling)) {
parent->rb_left = tmp1 = sibling->rb_right;
sibling->rb_right = parent;
rb_set_parent_color(tmp1, parent, RB_BLACK);
__rb_rotate_set_parents(parent, sibling, root,
RB_RED);
augment_rotate(parent, sibling);
sibling = tmp1;
}
tmp1 = sibling->rb_left;
if (!tmp1 || rb_is_black(tmp1)) {
tmp2 = sibling->rb_right;
if (!tmp2 || rb_is_black(tmp2)) {
rb_set_parent_color(sibling, parent,
RB_RED);
if (rb_is_red(parent))
rb_set_black(parent);
else {
node = parent;
parent = rb_parent(node);
if (parent)
continue;
}
break;
}
sibling->rb_right = tmp1 = tmp2->rb_left;
tmp2->rb_left = sibling;
parent->rb_left = tmp2;
if (tmp1)
rb_set_parent_color(tmp1, sibling,
RB_BLACK);
augment_rotate(sibling, tmp2);
tmp1 = sibling;
sibling = tmp2;
}
parent->rb_left = tmp2 = sibling->rb_right;
sibling->rb_right = parent;
rb_set_parent_color(tmp1, sibling, RB_BLACK);
if (tmp2)
rb_set_parent(tmp2, parent);
__rb_rotate_set_parents(parent, sibling, root,
RB_BLACK);
augment_rotate(parent, sibling);
break;
}
}
}
在分析函数之前，为了方便要先进行一些节点名称代号的定义。这里假设最终被删除的节点为N，其孩子节点为C。后继节点为S，其左孩子为SL，右孩子为SR。接下来的讨论是建立在节点N被删除，节点S替换N的基础上进行的。
二、删除节点函数分析 首先了解两个概念：
前驱节点：节点左子树中最大的节点。
后继节点：节点右子树中最小的节点。
删除操作首先要确定待删除节点有几个孩子。
一、若要删除节点只有一个孩子，则情况就相对简单很多。
二、如果有两个孩子，则不能直接删除节点。而是要先找到该节点的前驱节点或者后继节点，习惯上我们使用后继而不是前驱，然后将后继节点的值复制到要删除的节点中，然后再将原本的后继节点删除。
由于后继节点至多只有一个右孩子节点（否则这个节点肯定不是子树中最小的），这样我们就把原来要删除节点时需要修改两个孩子的问题转化为只调整一个节点的问题。能这样做的原因是我们并不关心最终被删除的节点是否是我们开始想要删除的那个节点，只要节点里的值最终被删除了就行，至于树的结构如何变化，这个不是我们关心的。
图1，直接删除N即可，不破坏红黑树的性质。
图2，直接删除N后，破坏了性质5，需要进行重新平衡。
代码为：
static __always_inline struct rb_node *
__rb_erase_augmented(struct rb_node *node, struct rb_root *root,
const struct rb_augment_callbacks *augment)
{
struct rb_node *child = node->rb_right, *tmp = node->rb_left;
struct rb_node *parent, *rebalance;
unsigned long pc;
if (!tmp) {
pc = node->__rb_parent_color;
parent = __rb_parent(pc);
__rb_change_child(node, child, parent, root);
if (child) {
child->__rb_parent_color = pc;
rebalance = NULL;
} else
rebalance = __rb_is_black(pc) ? parent : NULL;
tmp = parent;
}
..........................
}
代码rebalance = __rb_is_black(pc) ? parent : NULL;表明：如果节点颜色为黑，则，返回值rebalance 为父节点，否则为空。当返回值rebalance 为父节点时就是图二的情况，后续需要进行恢复平衡的操作。
2.2、待删除节点N只有一个孩子节点
只有一个孩子，此时N的孩子节点C同时也是后继节点S。C必然只能是红色（性质5），则N只能是黑色（性质4）。此时直接将C变成黑色继承N即可
static __always_inline struct rb_node *
__rb_erase_augmented(struct rb_node *node, struct rb_root *root,
const struct rb_augment_callbacks *augment)
{
struct rb_node *child = node->rb_right;
struct rb_node *tmp = node->rb_left;
struct rb_node *parent, *rebalance;
unsigned long pc;
if (!tmp) {
//----------------------------------------------------情况 1
pc = node->__rb_parent_color;
parent = __rb_parent(pc);
__rb_change_child(node, child, parent, root);
if (child) {
child->__rb_parent_color = pc;
rebalance = NULL;
} else
rebalance = __rb_is_black(pc) ? parent : NULL;
tmp = parent;
} else if (!child) {
//----------------------------------------------------情况 1
tmp->__rb_parent_color = pc = node->__rb_parent_color;
parent = __rb_parent(pc);
__rb_change_child(node, tmp, parent, root);
rebalance = NULL;
tmp = parent;
}
...........................
}
2.3、待删除节点N只有两个孩子节点
待删除节点N有两个孩子，这时首先需要找到N的后继节点S，此时又有两种情况。第一种S是N的右孩子，此时只需要将后继节点S继承N的位置，将N的左孩子（如果有）变为S的左孩子即可（S一定没有左孩子，见下方说明）；第二种情况是S不是N的右孩子，说明是N的右子树中的点。
2.3.1、S是N的右孩子 S是否有右子树的情况分别如下，注意X节点存在的意义就是使初始的红黑树是平衡的，所以我们不必要在意N的左子树的结构。
一、S有右子树，此时无论其他节点的颜色如果，删除N后直接使用S替换即可。所有可能的情况如下：
二、S没有右子树，此时替换就会产生冲突。
一、S有右子树，此时无论其他节点的颜色如果，删除N后直接使用S替换即可，所有可能的情况都可以抽象为下面的三种情况。注意此时以下的结构中S和SR的颜色是确定的。
二、S没有右子树，此时替换显然会产生冲突。
代码如下：
struct rb_node *successor = child, *child2;
tmp = child->rb_left;
if (!tmp) {
parent = successor;
child2 = successor->rb_right;
augment->copy(node, successor);
} else {
do {
parent = successor;
successor = tmp;
tmp = tmp->rb_left;
} while (tmp);
child2 = successor->rb_right;
WRITE_ONCE(parent->rb_left, child2);
WRITE_ONCE(successor->rb_right, child);
rb_set_parent(child, successor);
augment->copy(node, successor);
augment->propagate(parent, successor);
}
tmp = node->rb_left;
WRITE_ONCE(successor->rb_left, tmp);
rb_set_parent(tmp, successor);
pc = node->__rb_parent_color;
tmp = __rb_parent(pc);
__rb_change_child(node, successor, tmp, root);
if (child2) {
successor->__rb_parent_color = pc;
rb_set_parent_color(child2, parent, RB_BLACK);
rebalance = NULL;
} else {
unsigned long pc2 = successor->__rb_parent_color;
successor->__rb_parent_color = pc;
rebalance = __rb_is_black(pc2) ? parent : NULL;
}
tmp = successor;
}
2.4、规律总结
一、当使用S替换N时相当于删除了S节点，如果S节点是叶子节点（即上述没有右子树），且S又是一个黑色节点，这时删掉S必然会破坏红黑树的性质5造成不平衡。
二、后继节点S不可能有左孩子SL，因为如果有左孩子则它的左孩子更有可能成为待删除结点N的后继。因而S结点要不没有孩子，要不则只有右孩子。
一、情况1：后继节点S其兄弟节点X为红色，根据性质5，它肯定有两个黑色的孩子。此类情况做如下的调整：
二、情况2：后继节点S其兄弟节点X为黑色，且有一个左孩子（可以断定左孩子是红色的）。此类情况做如下的调整：
三、情况3：后继节点S其兄弟节点X为黑色，且有一个右孩子（可以断定右孩子是红色的）。此类情况做如下的调整：
四、情况4：后继节点S其兄弟节点X为黑色，且有两个节点（可以断定，左右节点都是红色的）。这个和情况2是相同的。
五、情况5：后继节点S其兄弟节点X为黑色，且没有子节点。
此时N的子树是平衡了，但是删掉S之后，可能上面的树发生不平衡。所以需要递归向上寻找不平衡的点，例如：
代码如下：
static __always_inline void
____rb_erase_color(struct rb_node *parent, struct rb_root *root,
void (*augment_rotate)(struct rb_node *old, struct rb_node *new))
{
struct rb_node *node = NULL, *sibling, *tmp1, *tmp2;
while (true) {
sibling = parent->rb_right;
if (node != sibling) {
} else {
sibling = parent->rb_left;
if (rb_is_red(sibling)) {
//----------------------------------------------- 情况1
parent->rb_left = tmp1 = sibling->rb_right;
sibling->rb_right = parent;
rb_set_parent_color(tmp1, parent, RB_BLACK);
__rb_rotate_set_parents(parent, sibling, root,
RB_RED);
augment_rotate(parent, sibling);
sibling = tmp1;
}
tmp1 = sibling->rb_left;
if (!tmp1 || rb_is_black(tmp1)) {
tmp2 = sibling->rb_right;
if (!tmp2 || rb_is_black(tmp2)) {
rb_set_parent_color(sibling, parent,
RB_RED);
if (rb_is_red(parent))
rb_set_black(parent);
else {
//------------------------------------------ 情况5（递归）
node = parent;
parent = rb_parent(node);
if (parent)
continue;
}
break;
}
//-------------------------------------------------- 情况3
sibling->rb_right = tmp1 = tmp2->rb_left;
tmp2->rb_left = sibling;
parent->rb_left = tmp2;
if (tmp1)
rb_set_parent_color(tmp1, sibling,
RB_BLACK);
augment_rotate(sibling, tmp2);
tmp1 = sibling;
sibling = tmp2;
}
//------------------------------------------------------ 情况4
parent->rb_left = tmp2 = sibling->rb_right;
sibling->rb_right = parent;
rb_set_parent_color(tmp1, sibling, RB_BLACK);
if (tmp2)
rb_set_parent(tmp2, parent);
__rb_rotate_set_parents(parent, sibling, root,
RB_BLACK);
augment_rotate(parent, sibling);
break;
}
}
}
