6.3 插入调整函数fixAfterInsertion()解析

/** From CLR */
private void fixAfterInsertion(Entry<K,V> x) {
    x.color = RED;  //新增节点默认为红色，再进行规则判断
    // 从树末端开始遍历：父节点是红色，则需要对树进行调整
    while (x != null && x != root && x.parent.color == RED) {
        if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
            Entry<K,V> y = rightOf(parentOf(parentOf(x)));
            if (colorOf(y) == RED) {
                setColor(parentOf(x), BLACK);
                setColor(y, BLACK);
                setColor(parentOf(parentOf(x)), RED);
                x = parentOf(parentOf(x));
            } else {
                if (x == rightOf(parentOf(x))) {
                    x = parentOf(x);
                    rotateLeft(x);
                }
                setColor(parentOf(x), BLACK);
                setColor(parentOf(parentOf(x)), RED);
                rotateRight(parentOf(parentOf(x)));
            }
        } else {
            Entry<K,V> y = leftOf(parentOf(parentOf(x)));
            if (colorOf(y) == RED) {
                setColor(parentOf(x), BLACK);
                setColor(y, BLACK);
                setColor(parentOf(parentOf(x)), RED);
                x = parentOf(parentOf(x));
            } else {
                if (x == leftOf(parentOf(x))) {
                    x = parentOf(x);
                    rotateRight(x);
                }
                setColor(parentOf(x), BLACK);
                setColor(parentOf(parentOf(x)), RED);
                rotateLeft(parentOf(parentOf(x)));
            }
        }
    }
    root.color = BLACK;  //在遍历外面，确保root一定是黑色
}

方法说明：

1. 新增的节点默认为红色，并从树末端往上遍历
2. 如果新增节点的父亲是红色，则需要进行结构调整
3. 结构调整这部分有点复杂，回头再深入理解todo

6.4 删除方法remove()解析

知识回顾：
二叉排序树的删除过程：（情况一，treeMap用后继代替，其实用前驱或者后继是一样的）

源码如下：

// 调用getEntry(key)找到对应entry，调用deleteEntry 删除节点
public V remove(Object key) {
    Entry<K,V> p = getEntry(key);
    if (p == null)
        return null;

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

//执行删除操作
private void deleteEntry(Entry<K,V> p) {
     //先对全局变量modCount、size 进行调整
    modCount++;
    size--;
    
    //情况1：左右孩子都不为空：后继节点代替
    if (p.left != null && p.right != null) {
        Entry<K,V> s = successor(p); //寻找后继 （另外分析）
        //将删除点的key、value、引用分别更新为代替节点
        p.key = s.key;  
        p.value = s.value;
        p = s;   //
    }

    //情况2：有1个孩子
    Entry<K,V> replacement = (p.left != null ? p.left : p.right);

    if (replacement != null) {
        replacement.parent = p.parent;  //左孩子父亲更新删除节点的父亲
        //父亲为root，则后继变为新的root
        if (p.parent == null)
            root = replacement;  
        //左孩子顶上
        else if (p == p.parent.left)
            p.parent.left  = replacement;
        //右孩子顶上
        else
            p.parent.right = replacement;

        // 删除节点的left、right、parent置空：被移除出树
        p.left = p.right = p.parent = null;

        // 删除黑色节点：调整结构
        if (p.color == BLACK)
            fixAfterDeletion(replacement);
    } else if (p.parent == null) { //删除root节点
        root = null;
    } else { //  情况1：没孩子
        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;
        }
    }
}

删除说明：

1. 删除过程遵从二叉排序树的删除特点（1、有一个孩子则孩子顶上；2两个孩子就用后继顶上，没有孩子则直接移除）
2. 节点删除，即left、right、parent置空；删除后，需要更新父亲节点的的左孩子或右孩子
3. 考虑是否需要更新全局变量root节点
4. 只有删除点是BLACK的时候，才会触发调整函数，因为删除RED节点不会破坏红黑树的任何约束，而删除BLACK节点会破坏规则4。

6.5 删除调整函数fixAfterDeletion()解析