java TreeMap 集合中的源码问题

个人觉得Java TreeMap中的删除操作源码有问题, 但是我感觉是我个人理解有问题,所以贴出来让大家帮我看看。我看了2天,还是感觉逻辑过不去,希望大家帮我看看。

情况是:当红黑树进行删除操作时,并且要删除的结点有左子树和右子树,那么就会执行successor()方法。从successor方法中,可以看到他会返回要删除结点的右子树的最左分支结点。(至于successor的else里面的代码,根本执行不到)。关键的地方来了,找到可替换结点后,源码中有条语句

 Entry<K,V> replacement = (p.left != null ? p.left : p.right);

个人非常的不明白,为什么找到了替换结点,还要执行这个语句(我不明白的点就是这个,希望有人帮我解释下,感谢万分)。
执行这个语句的结果是:替换结点根本根本就没有左子树(这边假设也没有右子树)。也就是说replacement = null; 代码往下走,就会将他当成是没有孩子的结点进行处理。

java TreeMap jdk1.8 源码如下:

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;
            }
        }
    }
 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;
        }
    }
阅读 1.8k
1 个回答
新手上路,请多包涵
 // 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
        

你看一下这里,如果p有两个子节点,那么进入if语句得到删除结点的右子树的最左分支结点,并将将s覆盖了p,
p没有左子节点,但是右子节点还是可能存在的, 若p没有两个子节点,则没有进入if语句,则需要判断p是有左子节点,还是右子节点,所以需要

 Entry<K,V> replacement = (p.left != null ? p.left : p.right);

这语句存在来判断p的子节点情况的

撰写回答
你尚未登录,登录后可以
  • 和开发者交流问题的细节
  • 关注并接收问题和回答的更新提醒
  • 参与内容的编辑和改进,让解决方法与时俱进
推荐问题