红黑树移除节点

上文具体讲授了红黑树的观念，红黑树的插入及旋转操纵，按照测试代码成立起来的红黑树布局为：

本文先研究一下红黑树的移除操纵是如何实现的，移除操纵较量巨大，详细移除的操纵要举办屡次旋转和移除的节点在红黑树中的位置有关，这里也不特意凭据旋转次数选择节点了，就找三种位置举例演示红黑树移除操纵如何举办：

首先来过一下TreeMap的remove要领：

public V remove(Object key) {
    Entry<K,V> p = getEntry(key);
    if (p == null)
        return null;

    V oldValue = p.value;
    deleteEntry(p);
    return oldValue;
}

第2行的代码是获取待移除的节点Entry，做法很简朴，拿key与当前节点按指定算法做一个较量获取cmp，cmp=0暗示当前节点就是待移除的节点；cmp>0，取右子节点继承较量；cmp<0，取左子节点继承较量。

接着重点跟一下第7行的deleteEntry要领：

private void deleteEntry(Entry<K,V> p) {
    modCount++;
    size--;

    // If strictly internal, copy successor's element to p and then make p
    // point to successor.
    if (p.left != null && p.right != null) {
        Entry<K,V> s = successor(p);
        p.key = s.key;
        p.value = s.value;
        p = s;
    } // p has 2 children

    // Start fixup at replacement node, if it exists.
    Entry<K,V> replacement = (p.left != null ? p.left : p.right);

    if (replacement != null) {
        // Link replacement to parent
        replacement.parent = p.parent;
        if (p.parent == null)
            root = replacement;
        else if (p == p.parent.left)
            p.parent.left  = replacement;
        else
            p.parent.right = replacement;

        // Null out links so they are OK to use by fixAfterDeletion.
        p.left = p.right = p.parent = null;

        // Fix replacement
        if (p.color == BLACK)
            fixAfterDeletion(replacement);
    } else if (p.parent == null) { // return if we are the only node.
        root = null;
    } else { //  No children. Use self as phantom replacement and unlink.
        if (p.color == BLACK)
            fixAfterDeletion(p);

        if (p.parent != null) {
            if (p == p.parent.left)
                p.parent.left = null;
            else if (p == p.parent.right)
                p.parent.right = null;
            p.parent = null;
        }
    }
}

用流程图整理一下这里的逻辑：

下面团结实际代码来看下。

移除根节点

按照上面的流程图，根节点30阁下子节点不为空，因此要先选择担任者，选择担任者的流程为：

分点整理一下移除节点30做了什么：

1. 由于节点30的右子节点不为空，因此从节点70开始不绝取左子节点直到取到叶子节点为止，最终取到的节点s为节点50
2. p的key=s的key即50，p的value=s的value即50，由于此时p指向的是root节点，因此root节点的key和value变革，变为50–>50
3. p=s，即p本来指向的是root节点，此刻p指向s节点，p与s指向同一份内存空间，即节点50
4. 接着选择replacement，由于p与s指向同一份内存空间，因此replacement判定的是s是否有左子节点，显然s没有，因此replacement为空
5. replacement为空，可是p有父节点，因此可以判定出来p也就是节点50不是root节点
6. 接着按照流程图可知，节点p是一个赤色节点，这里不需要举办移除数据批改
7. 最后节点p是其父节点的左子节点，因此节点p的左子节点置为null，再将p的父节点置为null，相当于把节点p移除

颠末上述流程，移除根节点30之后的数据布局如下图：

移除中间节点