个人觉得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;
}
}
你看一下这里,如果p有两个子节点,那么进入if语句得到删除结点的右子树的最左分支结点,并将将s覆盖了p,
p没有左子节点,但是右子节点还是可能存在的, 若p没有两个子节点,则没有进入if语句,则需要判断p是有左子节点,还是右子节点,所以需要
这语句存在来判断p的子节点情况的