java - 否则 master 将永远不会在树形图中的 successor() 中执行

Question

我正在学习树形图中 remove() 的源代码。但是有一点我无法理解。

//.......................忽略主要代码，留下这些

private void deleteEntry(Entry<K,V> p) {

if (p.left != null && p.right != null) {





        Entry<K,V> s = successor(p);
        p.key = s.key;
        p.value = s.value;
        p = s;
}

}

static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) {`enter code here`
    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;
    }
}

我对 deleteEntry 函数感到困惑，p 有 2 个孩子。P.left 和 P.right 都不为空。但为什么要判断 t.right 在后继函数中不为空？我的意思是这是绝对的事实。而且因为 t.right 必须不为空。代码永远不会在后继功能中的 else master 中执行。

谁打电话告诉我我的问题在哪里？感谢你们。

标签： javatreemap

Answer 1

如果您查看 TreeMap.java ，您会知道从很多地方调用了后继者，delete() 就是这样一个地方。