TreeMap源码分析(三)【元素删除平衡】

王守钰 2020-03-20 13:03:33

红黑树的删除

image
image

  1. 删除节点为根节点:无需平衡操作
  2. 删除节点的兄弟节点为黑色
    • 兄弟节点的子节点全黑
      • 父亲节点为红色:P节点和S节点互换颜色
        image
      • 父亲节点为黑色:S节点变红,P作为新的C节点进行递归处理
        image
    • 兄弟节点的子节点非全黑
      • 兄弟节点在左
        • 兄弟节点左子节点为黑:以S左旋,S和SR交换颜色;继续平衡
          image
        • 兄弟节点左子节点为红:以P右旋,P和S交换颜色,SL变黑
          image
      • 兄弟节点在右
        • 兄弟节点右子节点为黑:以P左旋,P和S互换颜色,SR变为黑色;继续平衡
          image
        • 兄弟节点右子节点为红:以P右旋,P和S互换颜色,SR变为黑色
          image
  3. 兄弟节点为红色
    • 兄弟节点在左:以P节点进行右旋,互换P和S的颜色;继续第2步平衡操作
      image
    • 兄弟节点在右:以P节点进行左旋,互换P和S的颜色;继续第2步平衡操作
      image

TreeMapremove操作

public V remove(Object key) {
    // 获取要删除的节点
    Entry<K,V> p = getEntry(key);
    // 节点不存在直接返回null
    if (p == null)
        return null;
    // 记录节点的值
    V oldValue = p.value;
    // 删除节点
    deleteEntry(p);
    // 返回原值
    return oldValue;
}

private void deleteEntry(Entry<K,V> p) {
    // 操作次数加1
    modCount++;
    // 容量个数-1
    size--;

    // 判断当前节点是否存在左子节点和右子节点
    if (p.left != null && p.right != null) {
        // 获取后序节点
        Entry<K,V> s = successor(p);
        // 用后续节点的key代替当前key
        p.key = s.key;
        // 用后续节点的value代替当前的value
        p.value = s.value;
        // 用后续节点代替当前节点
        p = s;
    } // p has 2 children

    // 替换节点,如果左节点不为空,直接让左节点代替,否则用右节点代替
    Entry<K,V> replacement = (p.left != null ? p.left : p.right);

    // 判断替换节点是否为空
    if (replacement != null) {
        // 设置替换节点的父节点为选中节点的父节点
        replacement.parent = p.parent;
        // 判断父节点是否为空
        if (p.parent == null)
            // 父节点为空设置替换节点为root节点
            root = replacement;
        // 判断p节点是否是左节点
        else if (p == p.parent.left)
            // 设置p节点的左子节点为替换节点
            p.parent.left  = replacement;
        else
            // 设置p节点的右子节点为替换节点
            p.parent.right = replacement;

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

        // Fix replacement
        // 判断p节点的颜色是否为黑色
        if (p.color == BLACK)
            // 处理删除平衡节点
            fixAfterDeletion(replacement);
    // 判断父节点是否为空,为空的话,说明删除的是root节点
    } else if (p.parent == null) {
        // 设置root节点为空节点
        root = null;
    } else { //  No children. Use self as phantom replacement and unlink.
        // 判断p节点的颜色是否为黑色
        if (p.color == BLACK)
            // 处理删除平衡
            fixAfterDeletion(p);
        // 判断p节点的父节点是否为空
        if (p.parent != null) {
            // 判断p是否为父节点的左子节点
            if (p == p.parent.left)
                // 设置父节点的左子节点为空
                p.parent.left = null;
            // 判断p是否为父节点的右子节点
            else if (p == p.parent.right)
                // 设置父节点的右子节点为空
                p.parent.right = null;
            // 设置父节点为空
            p.parent = null;
        }
    }
}

// 获取后序节点
static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) {
    if (t == null)
        return null;
    // 判断右节点是否为空
    else if (t.right != null) {
        // 获取右节点
        Entry<K,V> p = t.right;
        // 循环获取左节点
        while (p.left != null)
            p = p.left;
        return p;
    } else {
        // 获取父节点
        Entry<K,V> p = t.parent;
        Entry<K,V> ch = t;
        // 循环判断当前节点是父节点的右节点
        while (p != null && ch == p.right) {
            ch = p;
            p = p.parent;
        }
        return p;
    }   
}

// 删除后平衡解决
private void fixAfterDeletion(Entry<K,V> x) {
    // 删除节点不是root节点,并且删除节点颜色是黑色
    while (x != root && colorOf(x) == BLACK) {
        // 判断x节点是否是父节点的左子节点
        if (x == leftOf(parentOf(x))) {
            // 获取兄弟节点
            Entry<K,V> sib = rightOf(parentOf(x));
            // 如果兄弟节点是红色
            if (colorOf(sib) == RED) {
                // 设置兄弟节点为黑色
                setColor(sib, BLACK);
                // 父节点为红色
                setColor(parentOf(x), RED);
                // 左旋
                rotateLeft(parentOf(x));
                // 设置父节点的右子节点为sib
                sib = rightOf(parentOf(x));
            }
            
            // 兄弟节点的子节点双黑
            if (colorOf(leftOf(sib))  == BLACK &&
                colorOf(rightOf(sib)) == BLACK) {
                // 设置兄弟节点为红色
                setColor(sib, RED);
                // 设置x节点为父节点
                x = parentOf(x);
            } else {
                // 兄弟节点右子节点为黑色
                if (colorOf(rightOf(sib)) == BLACK) {
                    // 设置左子节点颜色为黑色
                    setColor(leftOf(sib), BLACK);
                    // 设置兄弟节点为红色
                    setColor(sib, RED);
                    // 右旋兄弟节点
                    rotateRight(sib);
                    // 重新设置兄弟节点信息
                    sib = rightOf(parentOf(x));
                }
                // 设置兄弟节点的颜色为父节点的颜色
                setColor(sib, colorOf(parentOf(x)));
                // 设置父节点颜色为黑色
                setColor(parentOf(x), BLACK);
                // 设置兄弟节点的右子节点颜色为黑色
                setColor(rightOf(sib), BLACK);
                // 左旋父节点
                rotateLeft(parentOf(x));
                // 设置x节点为root
                x = root;
            }
        // x是父节点的右节点
        } else { // symmetric
            // 获取兄弟节点
            Entry<K,V> sib = leftOf(parentOf(x));
            // 兄弟节点是红色
            if (colorOf(sib) == RED) {
                // 设置兄弟节点为黑色
                setColor(sib, BLACK);
                // 设置父节点为黑色
                setColor(parentOf(x), RED);
                // 以父节点进行右旋
                rotateRight(parentOf(x));
                // 设置兄弟节点
                sib = leftOf(parentOf(x));
            }
            // 兄弟节点子节点双黑
            if (colorOf(rightOf(sib)) == BLACK &&
                colorOf(leftOf(sib)) == BLACK) {
                // 设置兄弟节点为红色
                setColor(sib, RED);
                // 设置x节点
                x = parentOf(x);
            // 兄弟节点子节点单黑
            } else {
                // 左子节点为黑色
                if (colorOf(leftOf(sib)) == BLACK) {
                    // 设置兄弟节点右子节点为黑色
                    setColor(rightOf(sib), BLACK);
                    // 设置兄弟节点是黑色
                    setColor(sib, RED);
                    // 以兄弟节点进行左旋
                    rotateLeft(sib);
                    // 重新设置兄弟节点为父节点的左子节点
                    sib = leftOf(parentOf(x));
                }
                // 设置兄弟节点颜色为父节点颜色
                setColor(sib, colorOf(parentOf(x)));
                // 设置父节点颜色为黑色
                setColor(parentOf(x), BLACK);
                // 设置左子节点为黑色
                setColor(leftOf(sib), BLACK);
                // 右旋父节点
                rotateRight(parentOf(x));
                // 设置x为root节点
                x = root;
            }
        }
    }
    // 设置x节点为黑色
    setColor(x, BLACK);
}