红黑树删除的详细实例


阅读算法导论中关于红黑树删除的部分,关于节点的删除的几种情况,有一些不是很明了,现在画图说明。

    情况1:x的兄弟是红色。

此时,红黑树如图1。其中Z表示待删除节点。

                        

                                                图1.  红黑树a

删除B节点之后,红黑树的节点情况如图2所示

                    

                                                图2. 删除被删节点后


满足情况1:x位NIL或黑色节点,兄弟节点是红色。此时将w着为黑色,parent[x]为红色,在对parent[x]做一次左旋转。此时x的新兄弟w是黑色,这样将情况1转换为情况2、3或4。

    染色->旋转之后的情况如图3

        

                            图3. 情况1变换后

    查看此时的w,对应于情况2.

情况2,x的兄弟w是黑色的,且w的两个孩子都是黑色节点。

    继续以上面的例子为例。此时情形2如图3所示。对于情形2,处理过程是将w改为红色,x节点移动到原来的parent[x],parent则为新x的parent. 将维持红黑树性质的操作向上移动。处理过程如下图4所示:

        

                                    图4. 情况2变换后

    经过变换后,x的节点是红色,此时可以退出循环,将x节点置为黑色即可。到此,关于图1所示的红黑树经过情形1和情形2之后,再次成为一颗红黑树。反之,如果变换后,x节点是黑色,则继续循环。只是此时,x已经向上移动了一层。


情况3,x的兄弟是w黑色,而w的左孩子红,右孩子黑

    先说明下情况3的执行过程:交换w和其左孩子left[w]的颜色,并对w进行右旋转。旋转后x的新兄弟w是一个有红色右孩子的黑结点,转换成了情况4。

对于情况3,我们需要另外一个红黑树的示例。我们使用图5所示的红黑色来进行分析。Z表示待删除节点。PS:G后面的两个NIL节点漏了。请读者自行脑补吧。


        

                                                    图5. 红黑树b

删除了节点C后,原先的C节点成为NIL节点,此时红黑树如图6所示。

            

                                                图6. 删除节点后的待维持平衡红黑树

    此时x是黑色,兄弟w节点是黑色。w的左右节点都是黑色。符合情况2.所以,我们根据情况2进行转换。转换的过程如图7所示。

    

                                                    图7. 情况2的转换过程

    这个时候我们可以看到,x节点是黑色节点。所以还得继续进行循环。

我们再从情况1-4进行分析,判断符合哪个情况。情况1:要求x是黑色,兄弟w是红色。不符合。情况2:要求兄弟w是黑色,并且w的左右节点是黑色,不符合。情况3:要求兄弟w是黑色,并且w的左孩子红色,右孩子是黑色。符合。

    符合情况3之后,我们要先进行颜色的修改。交换w和左孩子的颜色。即设置w为红色,左孩子为黑色。颜色交换过程如图8所示。

                                                                图8. 情况3的颜色交换

    经历了颜色交换之后,接下来就是旋转。我们要对w节点进行右旋转。右旋转过程如图9所示。

                                        图9.右旋转的过程

    右旋转之后,新的w兄弟节点是旧的w节点的左节点。而原来红色的w节点,则成为了新的w节点的右节点。所以,此时x黑色,w黑色,w的右孩子红色。满足情况4。接下来是情况4的分析。

情况4,x的兄弟是w黑色,而w的右孩子红

    先说明下情况4的处理过程:.将w的颜色设置为parent[x]的颜色,将parent[x]的颜色设置为黑色,将w的右孩子着为黑色,然后在parent[x]做一次左旋,最后将x设置为根root.

    颜色交换过程如图10所示。

                                                                     图10. 情况4的颜色交换

    进行了颜色交换之后,接下来就是对父节点p的左旋操作了。查看图11.

                                                        图11.情况4对p节点的左旋操作。

    左旋操作之后,设置x节点为root节点,然后,退出循环。退出循环之后,设置x节点为黑色。得到一颗新的红黑树。

前面对于情况4的分析,是接着情况3变换得来的。现在我们再拿另外一颗红黑树来分析,这颗红黑树不经过情况3.红黑树的节点情况如图12所示。Z表示待删除节点。

        

                                                        图12.  红黑树b

    删除了节点C后,红黑树的图形如图13所示。

            

                                                                图13. 删除节点C后的待重新维持平衡的红黑树


此时,w黑色,w的两个孩子节点是黑色,所以满足情况2,经过情2的变换后的红黑树如图14所示。

 

                                                                    图14. 情2的变换过程

    经过情2后,此时x指向的节点颜色是黑色,继续执行循环。这时候,x的兄弟w是黑色,先判断情2,情2要求w的两个节点都是黑色,不满足。情况3,要求左孩子红,右孩子黑,不满足。情况4,要求右孩子红。满足。

    经过四个情况的对比分析后,我们知道,当前满足情况4。颜色变化过程如图15所示:

 

                                                                图15. 情况4的颜色变化过程

    颜色变化之后,对父节点p进行左旋。变换过程如图16所示。

    

                                                    图16. 情况4对p节点的左旋操作

    好了。红黑树删除的4种情况介绍完了。注意,这四种情况是针对节点是父节点的左节点来分析的。当节点是父节点的右节点时,操作类似,方向相反。

                        



评论

发表评论