红黑树删除学习

2021-03-25 本文已影响0人章鱼脑袋

红黑树删除

删除数据

红黑树，删除操作较为复杂，要确保逻辑的正确性，更为麻烦。所以我们仍然需要用自检测代码进行删除逻辑正确性检测。

if(null == root){
    return true;
}
//My own rule, The relationship between children and parent after rotation was always correct.
//Which is really important to help me check my code after any operations.
if(!validateNodeRelationShip(node)){
    throw new AssertionError("The relationship between each node are ruined!");
}
//Check the rule: The path from root-leaf have the same number of the black nodes.
if(!validateBlackNode(node,0,0)){
    throw new AssertionError("The path from root-leaf have the different number of the black nodes.");
}
//Check the rule: the root node should always be black.
if(!validateRootNode(node)){
    throw new AssertionError("The root node was not black.");
}
//Check the rule: There are no consecutive red nodes.
if(!validateConsecutiveRedNode(node)){
    throw new AssertionError("There have two consecutive red node.");
}
return true;

删除操作和正常的BST树操作一致。分为以下几种情况。

被删除节点是叶子节点
被删除节点是包含左侧子(或者)右子树
被删除节点是包含左子树(与)叶子树

这里分类3 与BST/AVL 一致的操作，都是找到后续节点，这里可以找左侧最大节点，或者右侧最小节点，作为后续节点(Successor).

private Node<E> maximumOnLeftSide(Node<E> node){
    if(null == node.right){
        return node;
    }
    return maximumOnLeftSide(node.right);
}

private Node<E> minimumOnRightSide(Node<E> node){
    if(null == node.left){
        return node;
    }
    return minimumOnRightSide(node.left);
}

具体取左侧，还是右侧并无差异，不过我看网上博客一般讲取右侧最小值，但数据结构可视化演示网站删除取左侧最大值。
所以为了方便查看测试，我取左侧最大值。

取了后续节点后，我们将后续节点的值与当前需要删除节点的值替换。这样待删除节点，就会变为，叶子节点，或者仅有一个子节点。所以我们仅需要处理情况1与情况2。

检测红黑树删除是否平衡

根据以上过程，我们清楚仅有两种情况，需要处理。我们清楚插入操作的平衡性检测规律是：不能存在两个相邻的红色节点。与插入不同，删除操作主要检测的规律为：

从根节点到所有叶子的路径中包含相同个数的黑色节点。

这是删除最重要的一条特性，但这并不是代码需要的判断条件。代码需要检测，被删除节点是否为黑色，因为删除黑色节点，会破坏掉这条特性，所以其实只需要查看，最终被删除的节点是否为黑色即可。

根据上面我们分析的三种情况，最终仅需要考虑以下俩种情况。

1. 被删除节点是叶子节点
2. 被删除节点是包含左侧子(或者)右子树

在这两种情况下，会破坏掉红黑树的平衡性。

1. 被删除叶子节点为黑色
2. 被删除的节点与其后继节点都为黑色（否则可以通过置换，将红色节点删除，这样并不破坏平衡性）

因为以上两种情况，会使从根节点到叶子任何一条路径上的黑色节点个数不同。本质上是因为删除了黑色节点，导致的当前路径上的黑色节点减1。所以我们需要修复的问题称为：DoubleBlack(当前路径中某个黑色节点计数为2的平衡性问题)

修复红黑树平衡性

根据以上分析，我们知道，仅有两种情况下，会在删除时，破坏掉红黑树的平衡性

1. 被删除叶子节点为黑色
2. 被删除的节点与其后继节点都为黑色

修正删除节点的平衡性的检测依据（代码检测依据）为兄弟Sibling节点的颜色 , 以下简称(S)。插入时的检测是父亲兄弟节点的颜色，代码依据是指导如何写代码。因为红黑树的规则，并不能让你直接写代码。所以这里我们需要清楚，真正在写代码时，根据什么依据去检测，去重新平衡红黑树。

删除后红黑树的自平衡需要检测以下三种情况

1. S 为黑色,且至少拥有一个红色子节点(执行旋转操作)
2. S 为黑色,且俩个子孩子都是黑色.
3. S 为红色.

S 为黑色,且至少拥有一个红色子节点(执行旋转操作)

当前共种4种不同情况会发生。对应节点旋转的4种不同场景

left-left case. 节点S 在父节点的左侧并且他的(左侧的子孩子/两个孩子)的颜色是红色的

             [23]
             /  \
         [07]    [46]
         /  \    /  \
       |06|[xx][xx][xx]

准备删除节点为：[46], S节点:[07] 为黑色，且左侧节点为红色。

执行染色操作,将S节点颜色赋给左侧子孩子，将S节点父节点颜色赋给S节点。

                 [23]
                 /  \
             [07]    [46]
             /  \    /  \
           [06][xx][xx][xx]

执行RightRotate(parent). 并移除待删除节点[46]

                 [07]
                 /  \
               [06][23]

旋转执行完后，对新的父节点，进行染色操作。确保新的父节点一直为黑色

right-right case. 节点S在父亲的右侧并且他的(右侧的孩子/两个孩子)是红色的.

             [57]
             /  \
         [42]    [92]
         /  \    /  \
       [xx][xx][xx]|99|

准备删除节点为：[42], S节点[92] 为黑色，且右侧节点为红色。

执行染色操作,将S节点颜色赋给右侧子孩子，将S节点父节点颜色赋给S节点。

                 [57]
                 /  \
             [42]    [92]
             /  \    /  \
           [xx][xx][xx][99]

执行LeftRotate(parent),并移除待删除节点[42]

         [92]
         /  \
       [57][99]

left-right case. 节点S在父节点的左侧，并且他的(右侧的孩子/两个孩子)是红色的

                 [78]
                 /  \
             [19]    [83]
             /  \    /  \
           [xx]|62|[xx][xx]

准备删除节点为：[83], 兄弟节点:[19] 为黑色，且右侧节点为红色。

执行染色操作,将S节点颜色赋给右侧子孩子

                 [78]
                 /  \
             [19]    [83]
             /  \    /  \
           [xx][62][xx][xx]

对节点S执行左旋转(leftRotate(sibling))操作，再对父节点执行右旋(rightRotate(parent))操作

             [62]
             /  \
           [19][78]

right-left case. 节点S在父节点的右侧并且他的(左侧的孩子/两个孩子)是红色的

                 [35]
                 /  \
             [25]    [88]
             /  \    /  \
           [xx][xx]|87|[xx]

准备删除节点为：[25], 兄弟节点:[88] 为黑色，且左侧节点为红色。

执行染色操作,将S节点颜色赋给左侧子孩子

                 [35]
                 /  \
             [25]    [88]
             /  \    /  \
           [xx][xx][87][xx]

对节点S执行右旋转(rightRotate(sibling))操作，再对父节点执行左旋(leftRotate(parent))操作

以上为解决了所有节点S 为黑色,且至少拥有一个红色子节点(执行旋转操作)

S 为黑色,且俩个子孩子都是黑色

如果父节点的颜色是黑色(单独示例)

         [59]
         /  \
       [45][78]

准备删除节点为：[78], S节点:[45] 为黑色

* 递归检测父节点
* 将节点S的颜色置为红色

         [59]
         /  \
       |45|[xx]

如果父节点的颜色是红色(单独示例)

                     [56]
                     /  \
             |53|            |87|
             /  \            /  \
         [16]    [55]    [60]    [89]
         /  \    /  \    /  \    /  \
       [xx][xx][xx][xx][xx]|68|[xx][xx]

准备删除节点为：[55], S节点:[16] 为黑色，父节点为红色节点|53|

将父节点颜色改为黑色
将节点S颜色置为红色

                     [56]
                     /  \
             [53]            |87|
             /  \            /  \
         |16|    [xx]    [60]    [89]
         /  \    /  \    /  \    /  \
       [xx][xx][xx][xx][xx]|68|[xx][xx]

以上，为两种兄弟节点是黑色，且两个子孩子都是黑色节点的场景。

S 为红色

在左侧

             [62]
             /  \
         |55|    [90]
         /  \    /  \
       [23][61][xx][xx]

准备删除节点为：[90], S节点:[55] 为红色，且在左侧

对父节点[62]执行右旋转

              |55|      
              /  \      
          [23]    [62]  
          /  \    /  \  
        [xx][xx][61][90]

将旧的父节点重新染色为红色(因为新的父节点变为根节点，所以将其置为黑色)，将旧的S节点染成黑色，并递归从当前节点开始检测冲突直到根结点为止

              [55]      
              /  \      
          [23]    |62|  
          /  \    /  \  
        [xx][xx][61][90]

新的S节点为黑色:[61]，且拥有两个黑色节点(null,null). 返回了第二种情况。

将父节点:[62]颜色改为黑色
将节点S:[61]颜色置为红色

              [55]      
              /  \      
          [23]    [62]  
          /  \    /  \  
        [xx][xx]|61|[xx]

以上，完成了平衡性修正。

在右侧

             [17]
             /  \
         [02]    |59|
         /  \    /  \
       [xx][xx][46][87]

准备删除节点为：[02], 兄弟节点:|59| 为红色，且在右侧

对父节点[17]执行左旋转

          |59|      
          /  \      
      [17]    [87]  
      /  \    /  \  
    [02][46][xx][xx]

将旧的父节点重新染色为红色，将旧的S节点染成黑色(因为新的父节点变为根节点，所以将其置为黑色)，并递归从当前节点开始检测冲突直到根结点为止

          [59]      
          /  \      
      |17|    [87]  
      /  \    /  \  
    [02][46][xx][xx]

新的S节点为[46],且拥有两个黑色节点(null,null)，返回了第二种情况。

将父节点颜色改为黑色
将节点S颜色置为红色

          [59]      
          /  \      
      [17]    [87]  
      /  \    /  \  
    [xx]|46|[xx][xx]

以上，完成了平衡性修正的三种不同情况的说明

下面将分析一个删除例子（很难在少量数据时满足所有情况，所以仅查看遇到的情况即可)，介绍在删除每个元素时的不同判断与操作。

删除演示

以下为一个完整的初始给定红黑树示例。

                  [06]              
                  /  \              
          |03|            |08|      
          /  \            /  \      
      [01]    [05]    [07]    [09]  
      /  \    /  \    /  \    /  \  
    [xx][xx][xx][xx][xx][xx][xx]|10|

删除数据:[1,3,5,7,6,8,9,10]
删除依据
1. S 为黑色,且至少拥有一个红色子节点(执行旋转操作)
  1.1 Left-left case
  1.2 Left-right case
  1.3 Right-left case
  1.4 Right-right case
2. S 为黑色,且俩个子孩子都是黑色.
  2.1 父节点是黑色
  2.2 父节点是红色
3. S 为红色.
  3.1 S节点在左侧
  3.2 S节点在右侧

在下面的示例介绍中，会有(见2.2/1.1) 这种引见的，均为上面列表所列的不同情况。

删除元素:[01]

                  [06]              
                  /  \              
          |03|            |08|      
          /  \            /  \      
      [01]    [05]    [07]    [09]  
      /  \    /  \    /  \    /  \  
    [xx][xx][xx][xx][xx][xx][xx]|10|

删除说明
准备删除元素:[01]为黑色节点，且节点[01]没有子孩子，根据上面提及的，删除黑色叶子节点，需要重新平衡红黑树。
平衡性解决
因为删除元素:[01]为黑色节点，节点S[05]为黑色，且拥有两个黑色节点(null,null)，这时候检测父节点|03|颜色，父节点为红色，满足第二种(见2.2)，所以执行操作:

将父节点颜色改为黑色
将节点S颜色置为红色

                  [06]              
                  /  \              
          [03]            |08|      
          /  \            /  \      
      [01]    |05|    [07]    [09]  
      /  \    /  \    /  \    /  \  
    [xx][xx][xx][xx][xx][xx][xx]|10|

删除后节点[01]满足条件：从根节点到所有叶子节点拥有相同个数的黑色节点

                  [06]              
                  /  \              
          [03]            |08|      
          /  \            /  \      
      [xx]    |05|    [07]    [09]  
      /  \    /  \    /  \    /  \  
    [xx][xx][xx][xx][xx][xx][xx]|10|

删除元素:[03]

                  [06]              
                  /  \              
          [03]            |08|      
          /  \            /  \      
      [xx]    |05|    [07]    [09]  
      /  \    /  \    /  \    /  \  
    [xx][xx][xx][xx][xx][xx][xx]|10|

删除说明
准备删除元素:[03]为黑色节点，且节点[03]有一个右边的子孩子，查找到其继承者(左侧最大/右侧最小)|05|,根据删除上面分析的，如果节点[03]与后继节点|05|,不是都是黑色，替换待删除节点[03]与|05|的值，并将后续节点|05|颜色值为黑色
```
              [06]              
              /  \              
      [05]            |08|      
      /  \            /  \      
  [xx]    [xx]    [07]    [09]  
  /  \    /  \    /  \    /  \  
[xx][xx][xx][xx][xx][xx][xx]|10|
```
平衡性解决
以上并没有任何一条路径上的黑色节点个数不同，所以不需要解决

删除元素:[05]

                  [06]              
                  /  \              
          [05]            |08|      
          /  \            /  \      
      [xx]    [xx]    [07]    [09]  
      /  \    /  \    /  \    /  \  
    [xx][xx][xx][xx][xx][xx][xx]|10|

删除说明
准备删除元素:[05]为黑色节点，且没有左右子树，需要解决平衡性问题，S节点|08|拥有两个黑色节点，所以采用第三种情况(见3.2)解决平衡性问题，因为节点|08|在右侧，采用左旋转进行调整
平衡性调整

左旋转父节点(leftRotate([06]))

  ```
        |08|      
        /  \      
    [06]    [09]  
    /  \    /  \  
  [05][07][xx]|10|
  ```

旋转后对旧的父节点，以及兄弟节点进行染色操作，将旧的父节点变成红色，旧的S节点置为黑色。

              [08]      
              /  \      
          |06|    [09]  
          /  \    /  \  
        [05][07][xx]|10|

使用待删除节点:[05]向上遍历并重新调整当前树结构，左侧新的S结点[07]满足条件2，S结果为黑色，且拥有两个黑色节点(null,null),并且因为父节点是红色(见2.2)，将父节点置为黑色，S节点置为红色。

              [08]      
              /  \      
          [06]    [09]  
          /  \    /  \  
        [xx]|07|[xx]|10|

调整完毕

删除元素:|07|

      [08]      
      /  \      
  [06]    [09]  
  /  \    /  \  
[xx]|07|[xx]|10|

删除说明
准备删除元素:|07|为红色节点，且没有左右子树，不需要解决平衡性问题。
平衡性调整
不需要

删除元素:[06]

      [08]      
      /  \      
  [06]    [09]  
  /  \    /  \  
[xx][xx][xx]|10|

删除说明
准备删除元素:[06]为黑色节点，且没有左右子树，需要解决平衡性问题。S节点[09]拥有一红色节点，满足条件1(1.4 righ-right case),需要对父节点[08]进行左旋转(leftRotate(08))
平衡性调整
- 对S节点以及S的右节点进行染色操作

                  [08]      
                  /  \      
              [06]    [09]  
              /  \    /  \  
            [xx][xx][xx][10]

父节点[08]进行左旋转(leftRotate(08))

              [09]      
              /  \      
          [08]    [10]  
          /  \    /  \  
        [06][xx][xx][xx]

最后将旧的父节点置为黑色,并移除节点[06]

              [09]      
              /  \      
          [08]    [10]

调整完毕

删除元素:[08]

      [09]      
      /  \      
  [08]    [10]

删除说明
准备删除元素:[08]为黑色节点，没有左右子树，S节点为[10],且拥有两个黑色子节点(null,null). 采用于2.1 S节点为黑色且拥有两个黑色子节目，父节点也为黑色。
平衡性调整

以父节点作为遍历对象，向上遍历，直到根节点(因为父节点即为根节点相当于此步骤不做任何事)

调整完后，将S节点置为红色

              [09]      
              /  \      
          [xx]    |10|

调整完毕

删除元素:[09]

              [09]      
              /  \      
          [xx]    |10|

删除说明
准备删除元素:[09]为黑色节点(且为根节点)，后继节点为红色:|10|,根据删除检测条件,如果被删除节点为黑色与后继节点不是两个黑色，则互换节点值，并移除节点，再将后继节点置为黑色，且无须进行平衡性调整。

                [10]

平衡性调整
无须调整

删除元素:[10]
1. 删除说明
  删除节点为根节点，直接删除。
2. 平衡性调整
  无须调整

以上，为所有分须的删除流程，以及步骤。最终将每种删除情况做了具体说明，并以一个具体的树删除作为演示。

为了验证正确性，我们编写了各种测试用例，用于验证每个步骤的正确性。配合内部自检测逻辑，保证了程序的可靠性。

/**
 * Insert and delete randomly to test the red-black tree's logic.
 * This function also helps us to generate test data for each remove test cases
 * {@link RedBlackTree#forceAbort()}
 */
@Test
public void testAddAndRemove(){
    final Random random = new Random();
    //test 10 times, make sure all the operation is correct.
    for(int i=0;i<10;i++){
        RedBlackTree<Integer> tree = new RedBlackTree<>();
        Deque<Integer> deque = new ArrayDeque<>();
        for(int i1=0;i1<1000;i1++){
            int value = random.nextInt(100000);
            while(deque.contains(value)){
                value = random.nextInt(100000);
            }
            deque.push(value);
            tree.add(value);
        }
        //For trace the test data.
//            System.out.println(deque);
        while(!deque.isEmpty()){
            int value = deque.peek();
            //For trace the test data.
//                System.out.print(value+", ");
            tree.remove(value);
            deque.pop();
        }
        //For trace the test data.
//            System.out.println();
        assert 0 == tree.size();
    }
}

以上10*1000次的添加与删除，并且任何一次添加与删除操作，都会在内部校验所有规则的情况下。保证了程序的可靠性。

红黑树删除学习