1 引言
在《算法导论 之 红黑树 - 插入》中已经对红黑树的5个性质做了较详细的分析，同时也给出了insert操作的C语言实现。首先我们再回顾一下红黑树的5个性质：
①、每个节点要么是红色的，要么是黑色的；
②、根结点是黑色的；
③、所有叶子结点（NIL）都是黑色的；
④、如果一个结点是红色，则它的两个儿子都是黑色的；
⑤、对任何一个结点，从该结点通过其子孙结点到达叶子结点（NIL）的所有路径上包含相同数目的黑结点。
和插入操作一样，结点的删除操作的时间复杂度也是O（log2@N）[注：以2为底数，N为对数]，但删除操作的处理更复杂一些。
2 删除处理
2.1 删除过程
假如需要删除结点D，则删除操作的过程有如下几种情况：[注：在以下所有绘制的红黑树中，均未绘制叶子结点]
情况1：被删结点D的左孩子为叶子结点，右孩子无限制（可为叶子结点，也可为非叶子结点）
处理过程：删除结点D，并用右孩子结点替代结点D的位置。如果被删结点D为红色，则红黑树性质未被破坏，因此无需做其他调整；如果被删结点D为黑色，则需进一步做调整处理。
图1 情况1-1：左右孩子均为叶子结点< http://www.2cto.com/kf/ware/vc/" target="_blank" class="keylink">vcD4KPHA+W9K219O94bXjyKG0+sHLveG140S1xM671sNdPC9wPgoKPGJyPgoKPGltZyBzcmM9"https://www.cppentry.com/upload_files/article/45/1_i0ldm__.jpg" alt="\">
图2 情况1-2：左孩子为叶子结点 右孩子不为叶子结点
[结点DR取代了叶子结点的位置]
情况2: 被删结点D的右孩子为叶子结点，左孩子不为叶子结点
处理过程：删除结点D，并用左孩子节点替代结点D的位置。如果被删结点D为红色，则红黑树性质未被破坏，因此不需做其他调整；如果被删结点D为黑色， 则需进一步做调整处理。
图3 情况2：右孩子为叶子结点 左孩子不为叶子结点
[结点DL取代结点D的位置]
情况3: 被删结点D的左右孩子均不为叶子节点
处理过程：找到结点D的后继结点S，将结点S的key值赋给结点D，再将结点S从树中删除，并用结点S的右孩子替代结点S的位置。从前面的描述可以看出，其实被删的是结点D的后继结点S。如果被删结点S为红色，则红黑树性质未被破坏，因此不需做其他调整；如果被删结点S为黑色，则需进一步做调整处理。
图4 情况3：左右孩子均不为叶子结点
[后继结点的右孩子SR取代后继结点S的位置]
综合情况1、2、3可知，当实际被删的结点为黑色时，才需进一步做调整处理 ―― 实际被删的结点为红色时，并不会破坏红黑树的5点性质。
2.2 调整过程
当红黑树中实际被删除的结点为黑色时，则可能破坏红黑树的5个性质。经过分析总结，破坏红黑树性质的情况有如下几种：
============================================================================
前提1：参照结点N为父结点P的左孩子
============================================================================
情况1）：参照结点N的兄弟B是红色的
处理过程：首先，将父结点P的颜色改为红色，兄弟结点的颜色改为黑色；其次，以父结点P为支点进行左旋处理 ――情况1转变为情况2或3、4。如下图所示：[注意：请注意图中处理前后node、brother指针的变化，这将是后续处理的参照]
图5 调整情况1
情况2）：参照结点N的兄弟B是黑色的，且B的两个孩子都是黑色的
处理过程：将兄弟结点B的颜色改为红色 ――情况2处理完成后，不必再进行情况3、4的判断，重新判断前提1、2。如下图所示：[注意：请注意图中处理前后node、brother指针的变化，这将是后续处理的参照]
图6 调整情况2
情况3）：参照结点N的兄弟B是黑色的，且B的左孩子是红色的，右孩子是黑色的
处理过程：首先，将兄弟结点B的颜色改为红色，结点B的左孩子改为黑色；其次，以结点B为支点进行右旋处理 ――情况3转化为情况4，后续必须进行情况4的处理。如下图所示：[注意：请注意图中处理前后node、brother指针的变化，这将是后续处理的参照]
图7 调整情况3
情况4）：参照结点N的兄弟B是黑色的，且B的左孩子是黑色的，右孩子是红色的
处理过程：首先，将父结点P的颜色拷贝给兄弟结点B，再将父结点P的颜色改为黑色，兄弟结点的颜色改为黑色；其次，以父结点P为支点，进行左旋处理；再次，将node改为树的根结点，也意味着调整结束。如下图所示：[注意：请注意图中处理前后node指针的变化，这将是后续处理的参照]
图8 调整情况4
[注：蓝色表示结点颜色可能为红，也可能为黑，在此也更能突出复制结点P的颜色给结点B]
============================================================================
前提2：参照结点N为父结点P的右孩子
============================================================================
其处理流程与前提1的四种情况正好相反，后续再补充...
3 编码实现
如果以下代码中出现的数据类型、宏、枚举或函数接口等未在此代码中定义，则可到《算法导论 之 红黑树 - 插入》中找到其具体的定义。
/******************************************************************************
**函数名称: rbt_delete
**功 能: 删除操作(外部接口)
**输入参数:
** tree: 红黑树
** key: 关键字
**输出参数: NONE
**返 回: RBT_SUCCESS:成功 RBT_FAILED:失败
**实现描述:
** 通过key找到需要被删除的结点，再调用_rbt_delete()执行删除操作
**注意事项:
**作 者: # Qifeng.zou # 2013.12.27 #
******************************************************************************/
int rbt_delete(rbt_tree_t *tree, int key)
{
rbt_node_t *node = tree->root;
if(tree->sentinel == node)
{
return RBT_SUCCESS;
}
while(tree->sentinel != node)
{
if(key == node->key)
{
return _rb_delete(tree, node); /* 删除结点 */
}
else if(key < node->key)
{
node = node->lchild;
}
else
{
node = node->rchild;
}
}
return RBT_SUCCESS;
}
代码1 删除操作（外部接口）
/******************************************************************************
**函数名称: rbt_delete
**功 能: 删除结点(内部接口)
**输入参数:
** tree: 红黑树
** dnode: 将被删除的结点
**输出参数: NONE
**返 回: RBT_SUCCESS:成功 RBT_FAILED:失败
**实现描述:
** 1. 如果将被删除的结点dnode无后继结点，则直接被删除，并被其左孩子或右孩子替代其位置
** 2. 如果将被删除的结点dnode有后继结点，则将后继结点的其赋给dnode，并删除后继结点，
** 再将后继结点的右孩子取代后继结点的位置
** 3. 完成1、2的处理之后，如果红黑树的性质被破坏，则调用rbt_delete_fixup()进行调整
**注意事项:
**作 者: # Qifeng.zou # 2013.12.28 #
******************************************************************************/
int _rb_delete(rbt_tree_t *tree, rbt_node_t *dnode)
{
rbt_node_t *parent = NULL, *next = NULL, *refer = NULL;
/* 查找dnode的后继结点next */
if((tree->sentinel == dnode->lchild)
|| (tree->sentinel == dnode->rchild))
{
next = dnode;
}
else
{
next = dnode->rchild;
while(tree->sentinel != next->lchild)
{
next = next->lchild;
}
}
/* 设置替代后继结点的结点refer(参考结点) */
if(tree->sentinel != next->lchild)
{
refer = next->lchild;
}
else
{
refer = next->rchild;
}
refer->parent = next->parent;
if(tree->sentinel == next->parent)
{
tree->root = refer;
}
else
{
if(next == next->parent->lchild)
{
next->parent->lchild = refer;
}
else
{
next->parent->rchild = refer;
}
}
if(next != dnode)
{
dnode->key = next->key;
/* Copy next's satellite data into dnode */
}
if(rbt_is_red(next)) /* Not black */
{
free(next);
return RBT_SUCCESS;
}
free(next);
return rbt_delete_fixup(tree, refer); /* 修复红黑树性质 */
}
代码2 删除结点（内部接口）
/******************************************************************************
**函数名称: rbt_delete_fixup
**功 能: 修复删除操作造成的黑红树性质的破坏(内部接口)
**输入参数:
** tree: 红黑树
** node: 实际被删结点的替代结点(注: node有可能是叶子结点)
**输出参数: NONE
**返 回: RBT_SUCCESS:成功 RBT_FAILED:失败
**实现描述:
**注意事项:
** 注意: 被删结点为黑色结点，才能调用此函数进行性质调整
**作 者: # Qifeng.zou # 2013.12.28 #
******************************************************************************/
int rbt_delete_fixup(rbt_tree_t *tree, rbt_node_t *node)
{
rbt_node_t *parent = NULL, *brother = NULL;
while(rbt_is_black(node) && (tree->root != node))
{
/* Set parent and brother */
parent = node->parent;
if(node == parent->lchild)
{
brother = parent->rchild;
/* Case 1: 兄弟结点为红色: 以parent为支点, 左旋处理 */
if(rbt_is_red(brother))
{
rbt_set_red(parent);
rbt_set_black(brother);
rbt_left_rotate(tree, parent);
/* 参照结点node不变, 兄弟结点改为parent->rchild */
brother = parent->rchild;
/* 注意: 此时处理还没有结束，还需要做后续的调整处理 */
}
/* Case 2: 兄弟结点为黑色(默认), 且兄弟结点的2个子结点都为黑色 */
if(rbt_is_black(brother->lchild) && rbt_is_black(brother->rchild))
{
rbt_set_red(brother);
node = parent;
}
else
{
/* Case 3: 兄弟结点为黑色(默认),
兄弟节点的左子结点为红色, 右子结点为黑色: 以brother为支点, 右旋处理 */
if(rbt_is_black(brother->rchild))
{
rbt_set_black(brother->lchild);
rbt_set_red(brother);
rbt_right_rotate(tree, brother);
/* 参照结点node不变 */
brother = parent->rchild;
}
/* Case 4: 兄弟结点为黑色(默认),
兄弟结点右孩子结点为红色: 以parent为支点, 左旋处理 */
rbt_copy_color(brother, parent);
rbt_set_black(brother->rchild);
rbt_set_black(parent);
rbt_left_rotate(tree, parent);
node = tree->root;
}
}
else
{
brother = parent->lchild;
/* Case 1: 兄弟结点为红色: 以parent为支点, 右旋处理 */
if(rbt_is_red(brother))
{
rbt_set_red(parent);
rbt_set_black(brother);
rbt_right_rotate(tree, parent);
/* 参照结点node不变 */
brother = parent->lchild;
/* 注意: 此时处理还没有结束，还需要做后续的调整处理 */
}
/* Case 2: 兄弟结点为黑色(默认), 且兄弟结点的2个子结点都为黑色 */
if(rbt_is_black(brother->lchild) && rbt_is_black(brother->rchild))
{
rbt_set_red(brother);
node = parent;
}
else
{
/* Case 3: 兄弟结点为黑色(默认),
兄弟节点的右子结点为红色, 左子结点为黑色: 以brother为支点, 左旋处理 */
if(rbt_is_black(brother->lchild))
{
rbt_set_red(brother);
rbt_set_black(brother->rchild);
rbt_left_rotate(tree, brother);
/* 参照结点node不变 */
brother = parent->lchild;
}
/* Case 4: 兄弟结点为黑色(默认), 兄弟结点左孩子结点为红色: 以parent为支点, 右旋处理 */
rbt_copy_color(brother, parent);
rbt_set_black(brother->lchild);
rbt_set_black(parent);
rbt_right_rotate(tree, parent);
node = tree->root;
}
}
}
rbt_set_black(node);
return RBT_SUCCESS;
}
代码3 删除调整
处理结果：
首先，随机生成左图树，再随机的任意个结点后，得到右图树，经过分析可以发现：右图也是一个红黑树。经过反复验证后，可以判断以上代码的处理是正确的。
―― 邹祁峰
2014.01.18 01:21