HashMap源码（七）—— 红黑树删除原理分析 动态图解析

红黑书的删除本质上是一个穷举的过程

删除情况说明

• 删除的节点没有子节点的情况

  1. 如果为红色，直接删除即可，不会影响黑色节点的数量
  2. 如果为黑色，删除的时候需要进行平衡操作

• 删除的节点只有一个子节点时，删除节点只能是黑色，子节点也只能是红色。否则无法满足红黑树黑色节点完全平衡的特性（从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点）

• 如果删除节点有两个子节点时，使用后继节点作为替换的删除节点，然后再按照前面两种情况处理

  删除情况具体分析

  删除的节点没有子节点（非null节点）的情况

• a、如果为红色，直接删除即可，不会影响黑色节点的数量

  删除红色节点（13）示例（不影响黑色节点数量，不需要平衡操作）
  

• b、如果为黑色，删除的时候需要进行平衡操作

  删除示例，删除节点11（平衡操作后面会介绍到）
  

删除的节点只有一个子节点时，删除节点只能是黑色，子节点也只能是红色。

为什么该情况下，删除节点只能是黑色，子节点只能是红色,如图所示:

 由于该情况下删除节点的子节点只有一个，并且是红色，删除后直接将删除节点的子节点的颜色变黑，父节点和子节点连接即可。由于删除的黑色节点被变成黑色的红色子节点顶上，整体不影响黑色节点的数量，还是符合红黑树的特性，所以不需要进行平衡操作。

删除节点动态示例，删除节点11（分别是含左子树和右子树的情况）：

如果删除节点有两个子节点时，使用前驱节点或后继节点作为替换的删除节点，然后再按照前面两种情况处理（本文示例以前驱节点为例）

找到的前驱节点有两种情况，分别是前驱节点无子节点的情况和前驱节点只有左子节点的情况.
同时删除节点和找到的前驱节点的颜色都不固定，所以又区分了好多情况。

下面演示示例只演示其中一种，大概了解一下变化规则。具体的平衡逻辑在后面会介绍到。

比如删除节点100，首先会找到前驱节点60，然后替换内容后，将后继节点删除。即将删除情况转变成上面介绍到的两种情况。删除完成后,再做节点平衡操作（后面会介绍具体平衡细节）。

删除示例，删除100节点

红黑树删除平衡情况分析

前面分析的三种情况，1.a 和 2 这两种情况下删除比较简单，不需要做红黑树节点平衡操作，而 3 这种情况之前也分析了，通过用前驱节点或者后继节点替换被删除的节点，将删除情况转换成1、2这种情况然后再删除，又由于1.a 和 2 不需要进行平衡处理，所以后面删除平衡操作主要围绕1.b的情况分析。

首先为了方便后面的描述，对节点进行一个名称的约束，如下图所示：

对于删除平衡操作也是一个穷举的过程（删除黑色节点引起的平衡问题）

分析： 删除节点的时候，找到前驱节点，并替换两个节点的内容

如果找到要删除前驱节点含有子节点的情况时，前驱节点一定是黑色，前驱节点的子节点一定是红色，这种情况就是上述第2种情况，删除前驱节点，将前驱节点变成黑色，不需要进行平衡操作。
如果找到要删除的前驱节点没有子节点，并且前驱节点是红色时。这种情况就是上述1.a 的情况，替换内容后直接删除即可，由于是红色节点，不影响黑色节点的数量。所以不需要进行平衡操作。
如果找到要删除的前驱节点没有子节点，并且前驱节点是黑色时，这种情况就是上述1.b的情况。因为删除的的是黑色节点，直接影响到红黑树中黑色节点的数量，需要进行数的平衡。这种情况比较复杂，后面内容就只针对这种情况处理。

以下内容是删除的节点找到的前驱节点是没有子节点的黑色节点的情况（也就是删除删除黑色叶子节点的情况）

• a、S 是黑色的情况

  a、当 P 是 红 色 \color{red}{当P是红色}当P是红色，SL和SR是 NULL 时，删掉节点4

  删掉节点4后，P变黑色，S变红色即可完成黑色节点平衡。
  

• b、当P是红色，SL是红色，SR是NULL

  删除节点12，因为删除的是黑色节点，SL又是红色的节点，可以利用这个红色节点补充删除的黑色节点达到局部黑色节点平衡。

  先已SL为圆心，右旋S节点，更改SL和S的颜色

  再已SL为圆心，左旋P节点，再次更改P和SL节点的颜色即可
  

• c、当P是红色，SL是null，SR是红色

  类似上面一种场景

  删除节点14后

  以S为圆心，左旋P节点 即可达到平衡操作
  

• d、当P是黑色，SL是null，SR是null

  由于删除的是一个黑色节点，并且相邻兄弟节点没有红色节点

  所以在删除后左侧这一块是不可能平衡，就会影响到叔叔节点的颜色
  

• e、当P是黑色，SL是红色，SR是null
  删除节点16 后，已SL为圆心，右旋S 节点，SL和S均变色

  然后再以SL为原型左旋P节点 最终三个节点的颜色都变成黑色
  

• f、当P是黑色，SL是null，SR是null红色
  同上面类似，以S为圆心，左旋P节点 最后都红色节点变成黑色节点即可
  

• S 是红色的情况

  和上面类似

  具体变化细节可以用下面的网站工具实践：

  http://www.u396.com/wp-content/collection/data-structure-visualizations/RedBlack.html

  保持平衡的原则就是节点的每个分支的黑色节点数是相同的

  HashMap红黑树删除源码分析

remove方法

/**
* 从HashMap中删除掉指定key对应的键值对，并返回被删除的键值对的值
* 如果返回空，说明key可能不存在，也可能key对应的值就是null
* 如果想确定到底key是否存在可以使用containsKey方法
*/
public V remove(Object key) {
   Node<K,V> e; // 定义节点变量，用来存储要被删除的节点（键值对）
   return (e = removeNode(hash(key), key, null, false, true)) == null ?
       null : e.value; // 调用removeNode方法
}

removeNode 方法

final Node<K,V> removeNode(int hash, Object key, Object value,boolean matchValue, boolean movable) {
		/**
		 * tab 当前当前结点数组
		 * hash 对应的节点
		 * n 数组长度 
		 * index 节点索引，通过hash 和 n计算得到
		 */
        Node<K,V>[] tab; Node<K,V> p; int n, index;
        // 根据hash找到 index位置的节点，即树的根节点或者链表的首节点
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (p = tab[index = (n - 1) & hash]) != null) {
            Node<K,V> node = null, e; K k; V v;
            // 首节点或者根节点是当前key对应的节点的情况
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                node = p;
            else if ((e = p.next) != null) { // 首节点或者根节点不是当前要删除对象的情况
            	// 树结构的处理逻辑
                if (p instanceof TreeNode) 
                    node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
                else { // 链表结构   遍历找到链表中当前key 对应的node节点
                    do {
                        if (e.hash == hash &&
                            ((k = e.key) == key ||
                             (key != null && key.equals(k)))) {
                            node = e;
                            break;
                        }
                        p = e;
                    } while ((e = e.next) != null);
                }
            }
            if (node != null && (!matchValue || (v = node.value) == value ||
                                 (value != null && value.equals(v)))) {
                if (node instanceof TreeNode)
                	// 树节点的删除逻辑
                	// 穷举删除节点以及红黑书的平衡逻辑
                    ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
                else if (node == p) // 链表结构的情况，并且是首节点
                    tab[index] = node.next; //直接将数据位置指向下一个节点即可
                else //不是首节点的情况，将p的下一个节点指向要删除的下一个节点
                    p.next = node.next;
                ++modCount;  //修改次数+1
                --size;  //size -1
                afterNodeRemoval(node);
                return node; // 返回要删除的node节点
            }
        }
        return null;
    }