听说你还不懂红黑树? 二

方家小白 2019-09-05

278

红黑树的删除过程

红黑树的删除节点和常规二叉树删除方法是一样的.

如果它的子结点都是空结点，那就用空结点顶替它的位置
如果被删除的结点只有一个子节点，则直接删除这个结点
如果它的双子全为非空，我们就把它的直接后继结点内容复制到它的位置，之后以同样的方式删除它的后继结点，它的后继结点不可能是双子非空，因此此传递过程最多只进行一次。

二叉树的删除算法:

if left[z] = NIL or right[z] = NIL
    then y ← z
    else y ← TREE-SUCCESSOR(z)
if left[y] ≠ NIL
    then x ← left[y]
    else x ← right[y]
if x ≠ NIL
    then p[x] ← p[y]
if p[y] = NIL
    then root[T] ← x
    else if y = left[p[y]]
            then left[p[y]] ← x
            else right[p[y]] ← x
if y ≠ z
    then key[z] ← key[y]
         copy y's satellite data into z
return y

红黑树的删除算法:

if left[z] = nil[T] or right[z] = nil[T]
   then y ← z
   else y ← TREE-SUCCESSOR(z)
if left[y] ≠ nil[T]
   then x ← left[y]
   else x ← right[y]
p[x] ← p[y]
if p[y] = nil[T]
   then root[T] ← x
   else if y = left[p[y]]
           then left[p[y]] ← x
           else right[p[y]] ← x
if y ≠ z
   then key[z] ← key[y]
        copy y's satellite data into z
if color[y] = BLACK
   then RB-DELETE-FIXUP(T, x)
return y

在删除结点后，原红黑树的性质可能被改变，如果删除的是红色结点，那么原红黑树的性质依旧保持，此时不用做修正操作，如果删除的结点是黑色结点，原红黑树的性质可能会被改变，我们要对其做修正操作。那么哪些树的性质会发生变化呢，如果删除结点不是树唯一结点，那么删除结点的那一个支的到各叶结点的黑色结点数会发生变化，此时性质5被破坏。如果被删结点的唯一非空子结点是红色，而被删结点的父结点也是红色，那么性质4被破坏。如果被删结点是根结点，而它的唯一非空子结点是红色，则删除后新根结点将变成红色，违背性质2

红黑树修复属性使用的算法:

while x ≠ root[T] and color[x] = BLACK
    do if x = left[p[x]]
          then w ← right[p[x]]
               if color[w] = RED
                  then color[w] ← BLACK                        ▹  Case 1
                       color[p[x]] ← RED                       ▹  Case 1
                       LEFT-ROTATE(T, p[x])                    ▹  Case 1
                       w ← right[p[x]]                         ▹  Case 1
               if color[left[w]] = BLACK and color[right[w]] = BLACK
                  then color[w] ← RED                          ▹  Case 2
                       x ← p[x]                                ▹  Case 2
                  else if color[right[w]] = BLACK
                          then color[left[w]] ← BLACK          ▹  Case 3
                               color[w] ← RED                  ▹  Case 3
                               RIGHT-ROTATE(T, w)              ▹  Case 3
                               w ← right[p[x]]                 ▹  Case 3
                        color[w] ← color[p[x]]                 ▹  Case 4
                        color[p[x]] ← BLACK                    ▹  Case 4
                        color[right[w]] ← BLACK                ▹  Case 4
                        LEFT-ROTATE(T, p[x])                   ▹  Case 4
                        x ← root[T]                            ▹  Case 4
       else (same as then clause with "right" and "left" exchanged)
color[x] ← BLACK

上面的修复情况看起来有些复杂，下面我们用一个分析技巧：我们从被删结点后来顶替它的那个结点开始调整，并认为它有额外的一重黑色。这里额外一种黑色是什么意思呢，我们不是把红黑树的结点加上除红与黑的另一种颜色，这里只是一种假设，我们认为我们当前指向它，因此空有额外一种黑色，可以认为它的黑色是从它的父结点被删除后继承给它的，它现在可以容纳两种颜色，如果它原来是红色，那么现在是红+黑，如果原来是黑色，那么它现在的颜色是黑+黑。有了这种额外的黑色，原红黑树性质5就能保持不变。现在只要恢复其它性质就可以了，做法还是尽量向根移动和穷举所有可能性。

有如下情况:

当前结点是红+黑色解法，直接把当前结点染成黑色，结束此时红黑树性质全部恢复。
当前结点是黑+黑且是根结点，解法：什么都不做，结束。
删除修复情况1：当前结点是黑+黑且兄弟结点为红色(此时父结点和兄弟结点的子结点分别为黑) ==> 把父结点染成红色，把兄弟结点染成黑色，之后重新进入算法。
删除修复情况2：当前结点是黑加黑且兄弟是黑色且兄弟结点的两个子结点全为黑色
删除修复情况3：当前结点颜色是黑+黑，兄弟结点是黑色，兄弟的左子是红色，右子是黑色
删除修复情况4：当前结点颜色是黑-黑色，它的兄弟结点是黑色，但是兄弟结点的右子是红色，兄弟结点左子的颜色任意

现在分别先说下

情景1: 当前节点是黑+黑，且兄弟节点为红色(此时父节点和兄弟节点的子节点为黑)

解法：把父结点染成红色，把兄弟结点染成黑色，之后重新进入算法（我们只讨论当前结点是其父结点左孩子时的情况）。此变换后原红黑树性质5不变，而把问题转化为兄弟结点为黑色的情况(注：变化前，原本就未违反性质5，只是为了把问题转化为兄弟结点为黑色的情况)。即如下代码操作：

//调用RB-DELETE-FIXUP(T, x) 的1-8行代码
while x ≠ root[T] and color[x] = BLACK
    do if x = left[p[x]]
          then w ← right[p[x]]
               if color[w] = RED
                  then color[w] ← BLACK                        ▹  Case 1
                       color[p[x]] ← RED                       ▹  Case 1
                       LEFT-ROTATE(T, p[x])                    ▹  Case 1
                       w ← right[p[x]]                         ▹  Case 1

变化前:

02红黑树-03删除01

变化后:

删除修复情况2：当前结点是黑加黑且兄弟是黑色且兄弟结点的两个子结点全为黑色。

解法：把当前结点和兄弟结点中抽取一种黑色追加到父结点上，把父结点当成新的当前结点，重新进入算法。（此变换后性质5不变），即调用RB-INSERT-FIXUP(T, z) 的第9-10行代码操作，如下：

//调用RB-DELETE-FIXUP(T, x) 的9-11行代码
if color[left[w]] = BLACK and color[right[w]] = BLACK
    then color[w] ← RED                          ▹  Case 2
         x p[x]                                  ▹  Case 2

变化前：

变化后:

删除修复情况3：当前结点颜色是黑+黑，兄弟结点是黑色，兄弟的左子是红色，右子是黑色。

解法：把兄弟结点染红，兄弟左子结点染黑，之后再在兄弟结点为支点进行右旋，之后重新进入算法。此是把当前的情况转化为情况4，而性质5得以保持，即调用RB-INSERT-FIXUP(T, z) 的第12-16行代码，如下所示：

//调用RB-DELETE-FIXUP(T, x) 的第12-16行代码
else if color[right[w]] = BLACK
        then color[left[w]] ← BLACK          ▹  Case 3
             color[w] ← RED                  ▹  Case 3
             RIGHT-ROTATE(T, w)              ▹  Case 3
             w ← right[p[x]]                 ▹  Case 3

变化前

02红黑树-03删除05.jpg

变化后

2红黑树-03删除06.jpg

删除修复情况4：当前结点颜色是黑-黑色，它的兄弟结点是黑色，但是兄弟结点的右子是红色，兄弟结点左子的颜色任意。

解法：把兄弟结点染成当前结点父结点的颜色，把当前结点父结点染成黑色，兄弟结点右子染成黑色，之后以当前结点的父结点为支点进行左旋，此时算法结束，红黑树所有性质调整正确，即调用RB-INSERT-FIXUP(T, z)的第17-21行代码，如下所示：

//调用RB-DELETE-FIXUP(T, x) 的第17-21行代码
color[w] ← color[p[x]]                 ▹  Case 4
color[p[x]] ← BLACK                    ▹  Case 4
color[right[w]] ← BLACK                ▹  Case 4
LEFT-ROTATE(T, p[x])                   ▹  Case 4
x ← root[T]                            ▹  Case 4

变化前: