「漫步计算机系统」之数据结构与算法(18):红黑树结点的删除

01

删除

如何将结点从红黑树中删除？三步骤：

1、将红黑树当成一棵二叉搜索树，删除；

2、通过旋转和重新着色，使其满足红黑树的性质。

首先，这棵树本身是一棵自平衡二叉搜索树，删除结点后不改变二叉搜索树的事实，不论是左旋、右旋还是着色，也不改变这个事实；

其次，通过一系列的旋转和重新着色，使新树满足红黑树的所有性质，重新成为一棵红黑树。

第一步：将红黑树当成一棵二叉搜索树，将结点删除：

1. 如果被删除结点没有儿子，即为叶子结点，直接删除即可；
2. 如果被删除结点有一个儿子，删除该结点，其子结点顶替即可；
3. 如果被删除结点有两个儿子，则有两种方法，一种是用前驱即左子树的最右结点顶替，一种是用后继即右子树的最左结点顶替。如果前驱、后继没有儿子，删除它们用上面的第1点处理。如果前驱、后继有一个儿子，删除它们用上面的第2点处理。

设X是顶替的结点，以下X：“红+黑”表示顶替结点为红色、被删除结点为黑色，X:“黑+黑”表示顶替结点和被删除结点均为黑色。

第二步：通过旋转和重新着色，使其满足红黑树的性质：

1. X：“红+黑”，此时直接将红色顶替结点置黑，即完成；
2. X：“黑+黑”，且被删除结点为根结点，此时不须做任何处理，即完成；
3. X：“黑+黑”，且被删除结点不为根结点，分为以下4种情况。

1

X是"黑+黑"结点，X的兄弟结点是红色，X的父结点和X的兄弟结点的子结点都是黑色结点

1) 将x的兄弟结点设为“黑色”。

2) 将x的父结点设为“红色”。

3) 对x的父结点进行左旋。

4) 左旋后，重新设置x的兄弟结点。

2

X是“黑+黑”结点，x的兄弟结点是黑色，x的兄弟结点的两个孩子都是黑色。

1) 将x的兄弟结点设为“红色”。

2) 设置“x的父结点”为“新的x结点”。

3

X是“黑+黑”结点，X的兄弟结点是黑色，X的兄弟结点的左孩子是红色，右孩子是黑色。

1) 将x兄弟结点的左孩子设为“黑色”。

2) 将x兄弟结点设为“红色”。

3) 对x的兄弟结点进行右旋。

4) 右旋后，重新设置x的兄弟结点。

4

X是“黑+黑”结点，X的兄弟结点是黑色；X的兄弟结点的右孩子是红色，X的兄弟结点的左孩子任意颜色。

1) 将x父结点颜色 赋值给 x的兄弟结点。

2) 将x父结点设为“黑色”。

3) 将x兄弟结点的右子结点设为“黑色”。

4) 对x的父结点进行左旋。

5) 设置“x”为“根结点”。

至此，红黑树的讲解告一段落……

注：凡属于本公众号内容，未经允许不得私自转载，否则将依法追究侵权责任。