红黑树结点的删除与修复

字数统计: 2.9k字   |   阅读时长≈ 11分

-

RB-DELETE

基于TREE-DELETE过程而来

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
def RB_delete(T : rbTree, deln : rbTreeNode):
    substitude = deln
    substitude_original_color = deln.color

    if deln.left == T.nil:
        substitude_original_child = deln.right
        RB_transplant(T, deln, deln.right)
    elif deln.right == T.nil:
        substitude_original_child = deln.left
        RB_transplant(T, deln, deln.left)
    else:
        substitude = tree_minimum(T, deln.right)
        substitude_original_color = substitude.color
        substitude_original_child = substitude.right

        #处理substitude结点原来的位置
        if substitude.parent == deln:
            substitude_original_child.parent = substitude  #这一句是否有必要,还是说，存在substitude.right.parent != substitude T.nil? 并不多余，存在substitude_original_child.parent = T.nil
        else:
            RB_transplant(T,substitude ,substitude.right)
            substitude.right = deln.right
            substitude.right.parent = substitude
        RB_transplant(T, deln, substitude)  
        substitude.left = deln.left
        substitude.left.parent = substitude
        substitude.color = deln.color

    # 如果挖过来的substitude是黑色的，将会引起它原来位置红黑性质改变 详见算法导论p184
    if substitude_original_color == Color.black:
        RB_delete_fixup(T, substitude_original_child)

对于else部分的解释

1
2
3
4
5
6
7
#处理substitude结点原来的位置
if substitude.parent == deln:
    substitude_original_child.parent = substitude  #这一句是否有必要,还是说，存在substitude.right.parent != substitude T.nil? 并不多余，存在substitude_original_child.parent = T.nil
else:
    RB_transplant(T,substitude ,substitude.right)
    substitude.right = deln.right
    substitude.right.parent = substitude

作用：让substitude.right.parent始终指向代码执行前subsitude的父节点，为了可以在substitude被拿去替代deln后替代subsitude的位置，有以下两种情形：

  1. 当subsititude的父结点就是要被删除的结点deln时：

    substitude相当于自己替换自己，根本不用动，所以也根本不存在要用substitude.right去替代substitude，让substitude.right.parent指向substitude就好

  2. 当substitude的父节点不是deln时: substitude要离开原来的位置，就需要substitude.right来取代substitude, 然后substitude去取代deln

几个疑问:

  1. 第一个if是否多余

并不多余，存在substitude_original_child.parent == T.nil,此时需要将T.nil的父节点设为substitude，不然我们无法以x.parent.(left/right)取到它的兄弟节点

删除后的修复-RB-DELETE-FIXUP

修复的原因

1
2
3
# 如果挖过来的substitude是黑色的，将会引起它原来位置红黑性质改变 详见算法导论p184
if substitude_original_color == Color.black:
    RB_delete_fixup(T, substitude_original_child)

如果结点substitude是红色的，当substitude被删除或者移动，红黑性质仍然保持，原因如下：

  1. 树的黑高没有发生变化

  2. 不存在两个相邻的红结点。因为substitude在书中占据了deln的位置，再考虑到deln的颜色 (因为substitude过去后是染成了deln一样的颜色了的)，树中substitude的新位置不可能有两个相邻的红结点。
    另外, 如果substitude不是deln的右孩子，则substitude的原右孩子substitude_original_child代替substitude。

    • 如果substitude是红色，则substitude_original_child一定是黑色，因此用substitude_originnal_child代替substitude不可能使两个红结点相等

    • 如果substitude是红色，就不可能是根节点，所以根节点仍然是黑色

replaceandstainpng

如果结点substitude是黑色的，那么会产生三个问题，可以用后面的方法修复：

  1. 如果substitude是原来的根结点，而substitude的一个 红色孩子成为新的根节点，就违反了性质2
  2. 如果substitude_original_child和substitude_original_child.parent是红色的，则违反了性质4
  3. 在树中移动substitude将导致先前包含substitude的任何简单路径上黑色结点个数减1。因此，substitude的任何祖先都不满足性质5。
    改正这一问题的办法是将现在占有substitude原来位置的结点substitude_original_child视为还有一重额外的黑色。也就是说，如果将任意包含结点substitude_original_child的简单路径上黑结点个数加1，则在这种假设下,性质5成立。
    当将黑结点substitude删除或移动时，将其黑色”下推”给结点substitude_original_child。现在问题变为 结点substitude_original_child可能既不是红色，也不是黑色 ，从而违反性质1。现在的结点x是双重黑色或者黑红色，这就给包含substitude_original_child的简单路径上黑结点数贡献了2或1。substitude_original_child的color实现仍然是 RED (如果substitude_original_child是黑红色)或者= BLACK (如果substitude_original_child是双重黑色的)。换句话说，结点额外的黑色是针对substitude_original_child结点的，但不反映在它的color属性上。

为什么substitude的左边一定是T.nil结点

1
substitude = tree_minimum(T, deln.right)

因为substitude是由tree_minimun得来的，由[[红黑树#性质5]],可知substitude.left 一定 是 T.nil，同理，substitude的右边要么也是一个T.nil，要么就是一个红色结点连着T.nil Pasted image 20230329194947

RB-DELETE-FIXUP实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
def RB_delete_fixup(T : rbTree, fixn : rbTreeNode):
    while fixn != T.root and fixn.is_black():
        if fixn.is_left_child(): #判断是左孩子还是右孩子
            slibing = fixn.parent.right  #由于x是双重黑色的，slibing不可能是T.nil,不然从fixn.parent到叶子slibing的简单路径上的黑节点个数 就会 小于从fixn.parent到fixn的简单路径上的黑节点数
            if slibing.is_red():
                slibing.color = Color.black  #case1
                fixn.parent.color = Color.red
                left_rotate(T, fixn.parent)
                slibing = fixn.parent.right

            #经过上面的if分支处理，保证了fixn的兄弟是黑的
            if slibing.left.is_black() and slibing.right.is_black(): #case2：两个子节点都是黑的
                slibing.color = Color.red           
                fixn = fixn.parent

            else:
                if slibing.left.is_black(): 
                    slibing.left.color = Color.black        
                    slibing.color = Color.red
                    right_rotate(T, slibing)
                    slibing = fixn.parent.right             

                slibing.color = fixn.parent.color      
                fixn.parent.color = Color.black
                slibing.right.color = Color.black
                left_rotate(T, fixn.parent)
                # fixn = T.nil oh,no
                fixn = T.root

        elif fixn.is_right_child():
            slibing = fixn.parent.left 
            if slibing.is_red():
                slibing.color = Color.black  #case1
                fixn.parent.color = Color.red
                right_rotate(T, fixn.parent)
                slibing = fixn.parent.left

            if slibing.right.is_black() and slibing.left.is_black(): #case2：两个子节点都是黑的
                slibing.color = Color.red           
                fixn = fixn.parent

            else:
                if slibing.right.is_black():
                    slibing.right.color = Color.black        
                    slibing.color = Color.red
                    left_rotate(T, slibing)
                    slibing = fixn.parent.left             

                slibing.color = fixn.parent.color       
                fixn.parent.color = Color.black
                slibing.left.color = Color.black
                right_rotate(T, fixn.parent)
                fixn = T.nil
    fixn.color = Color.black

过程PB-DELETE-FIXUP恢复性质1、性质2、和性质4。性质2,4的恢复详见练习[[算法导论-13.4-1]] 和 [[算法导论-13.4-2]]

下面说明如何恢复性质1:
传进来的fixn一定带有至少一重黑色
![[红黑树-删除：RB-DELETE#^30b0f2]]

while循环的目标是将额外的黑色沿树上移，直到：

  1. fixn指向黑红结点，根本不进while循环，此时在最后，将fixn着为单个黑色
  2. finx指向根结点，此时可以简单地“移除”额外的黑色
  3. 执行适当的旋转和重新着色，退出循环

在while循环中，fixn总是指向一个具有双重黑色的非根结点。

1
2
if fixn.is_left_child: #判断是左孩子还是右孩子
    slibing = fixn.parent.right

由于fixn是双重黑色的，slibing不可能是T.nil，不然从fixn.parent到叶子slibing的简单路径上的黑节点个数 就会 小于从fixn.parent到fixn的简单路径上的黑节点数

我的理解： 既然被拿走的结点为黑色(整个循环的前提)，那兄弟结点那边至少还有一个非T.nil的黑色节点，才能保证[[红黑树#性质5|性质5]]

从子树的根(包括根)到每棵子树\alpha,\beta,…,\zeta 之间的黑结点个数(==包括x(fixn)的额外黑色==)并不会被变换改变，因此，如果性质5在变换之前成立，那么变换之后也仍然成立。比如[[#case1]] ,在变换前后，根结点至子树\alpha或\beta之前的黑结点数都是3

因为x(fixn)没有插入到根节点到其他结点的简单路径上

==tips: 下面的图片中，x对应fixn，w对应slibing==

case1

1
2
3
4
5
if slibing.is_red():
    slibing.color = Color.black  #case1
    fixn.parent.color = Color.red
    left_rotate(T, fixn.parent)
    slibing = fixn.parent.right

通过交换结点B和结点D的颜色以及执行一次左旋，可以将[[#case1]]转化为[[#case2]]，[[#case3]]或者[[#case4]]

因为w结点必须有黑色子节点，所以可以改变w和x.p的颜色，然后对x.p做一次左旋而不违反红黑性质。现在，==x的新兄弟结点是旋转之前w的某个子节点，其颜色为黑色==，就能转换成其他情况进行处理

case1slibingredpng

case2

1
2
3
if slibing.left.is_black() and slibing.right.is_black():
    slibing.color = Color.red           #case2
    fixn = fixn.parent

在将结点D着为红色，并将x设为指向结点B后，由指针x所表示的额外黑色沿树上升。如果通过[[#case1]]进入[[#case2]]，则while循环结束，因为新的结点x是红黑的，因此其color属性c是RED。

w的两个子结点都是黑色的，因为w也是黑色的，==所以从x和w上去掉一重黑色，使得x只有一重黑色而w为红色。
为了补偿从x和w去掉的一重黑色，在原来是红色或黑色的x.p新增一重额外的黑色(在此处，被x指着就是代表了一重黑色)==。通过将x.p作为新节点x来重复while循环来处理 case2allSlibingChildsblackpng

基于红色结点的删除移动对黑高无影响

case3

1
2
3
4
5
if slibing.left.is_black():
    slibing.left.color = Color.black        #case3
    slibing.color = Color.red
    right_rotate(T, slibing)
    slibing = fixn.parent.right

通过交换结点C和D的颜色并执行一次右旋，将[[#case3]]转换成[[#case4]]

w为黑，且其左孩子为红，右孩子为黑，可以交换w和其左孩子w.left的颜色，然后对w进行右旋而不违反红黑树的任何性质。现在x的新兄弟结点w是一个有红色右孩子的黑色节点，完成了case3到case4的转换 case3slibingLeftChildblackpng

(w为左子节点，那么我称w的左子节点与w同比边)
和w不同边的子节点为红，同边子节点为黑，可以通过旋转让同边的子节点变成红色

case4

1
2
3
4
5
slibing.color = fixn.parent.color           #case4
fixn.parent.color = Color.black
slibing.right.color = Color.black
left_rotate(T, fixn.parent)
fixn = T.nil

在[[#case4]]中，通过改变某些结点的颜色并执行一次左旋(不改变红黑性质)，可以将由x表示的额外黑色去掉，然后循环终止

x的兄弟结点w为黑且w的右孩子为红色，通过进行某些颜色修改(父结点和兄弟结点颜色交换)并对x.p进行一次左旋，可以去掉x的额外黑色，从而使它变成单重黑色，而且不破坏任何性质。将x设置为根后，while循环终止

其实就是把自己的一重黑色分给红色的爸爸，让兄弟去当爷爷，把爸爸移下来。从根节点来看，根结点本身的颜色变，x兄弟那边的黑高也没变，而x这边的黑高也没变，因为x这边多了一个黑结点，x少了一重黑色 case4remove2blackpng

总结

删除操作前面基本与BTS删除相同

修复时，除了待处理结点是红色，可以简单得将红色染黑，以及处理结点是黑色，上升到root结点去除双重黑色

基本上都是通过处理前三种情形，达成情形4: 即兄弟节点为黑色，与兄弟结点同边的子节点为红色，来进行我称之为“拉皮条”的变动来修复，然后将fixn指向root退出循环
(此处用白色结点表示该节点红黑不重要)

2blackleftpng

2blackrightpng

时间分析

含有n个结点的红黑树的高度为\mathrm{O}(lgn)，不调用RB-DELTE-FIXUP时，该过程的总时间代价为\mathrm{O}(lgn)。在RB-DELETE-FIXUP中，情况1、3、4在各执行常数次数的颜色改变和最多3次旋转后就终止了。情况2是while循环可以重复执行的唯一情况，然后指针x沿树上升最多\mathrm{O}(lgn)次，且不执行任何旋转。

所以，过程PB-DELETE-FIXUP要花费\mathrm{O}(lgn)时间，做最多3次旋转，因此RB-DELETE运行的总时间是\mathrm{O}(lgn)

参考文章：

  1. 算法导论: 算法导论（原书第2版） (豆瓣)
赏

谢谢你请我吃糖果

支付宝
微信

扫一扫，分享到微信

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia-plus根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

小太阳

发一点微光
让世界多一点温暖