史上最清晰的红黑树讲解（下）

正文

请到「今天看啥」查看全文

getEntry() 函数前面已经讲解过，这里重点放 deleteEntry() 上，该函数删除指定的 entry 并在红黑树的约束被破坏时进行调用 fixAfterDeletion(Entry x) 进行调整。

由于红黑树是一棵增强版的二叉查找树，红黑树的删除操作跟普通二叉查找树的删除操作也就非常相似，唯一的区别是红黑树在节点删除之后可能需要进行调整 。现在考虑一棵普通二叉查找树的删除过程，可以简单分为两种情况：

1. 删除点p的左右子树都为空，或者只有一棵子树非空。

2. 删除点p的左右子树都非空。

对于上述情况1，处理起来比较简单，直接将p删除（左右子树都为空时），或者用非空子树替代p（只有一棵子树非空时）；对于情况2，可以用p的后继s（树中大于x的最小的那个元素）代替p，然后使用情况1删除s（此时s一定满足情况1，可以画画看）。

基于以上逻辑，红黑树的节点删除函数 deleteEntry() 代码如下：

// 红黑树entry删除函数deleteEntry()private void deleteEntry(Entry p) {
    modCount++;
    size--;    if (p.left != null && p.right != null) {// 2. 删除点p的左右子树都非空。
        Entry s = successor(p);// 后继
        p.key = s.key;
        p.value = s.value;
        p = s;
    }
    Entry replacement = (p.left != null ? p.left : p.right);    if (replacement != null) {// 1. 删除点p只有一棵子树非空。
        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;
        p.left = p.right = p.parent = null;        if (p.color == BLACK)            fixAfterDeletion(replacement);// 调整
    } else if

请到「今天看啥」查看全文