删除一个元素
我们看看 java 代码是怎么实现的：
public V remove(Object key) {
// 先用二分法获取这个元素，如果为 null ，不需要继续了
Entry<K,V> p = getEntry(key);
if (p == null)
return null;
V oldValue = p.value;
deleteEntry(p);
return oldValue;
}
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.
// 如果 p 有两个儿子，就把 p 指向它的后继者，也就是它后边的元素
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.
// p 有一个儿子，外汇跟单gendan5.com或者没有儿子，获取到之后放在 replacement 中
Entry<K,V> replacement = (p.left != null ? p.left : p.right);
// p 有儿子
if (replacement != null) {
// Link replacement to parent
// 把 p 的子孙接在 p 的父级
replacement.parent = p.parent;
//p 是根节点
if (p.parent == null)
root = replacement;
//p 是左儿子
else if (p == p.parent.left)
p.parent.left = replacement;
// p 是右儿子
else
p.parent.right = replacement;
// 把 p 的链接都删掉
// 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 {
//p 没有儿子
// No children. Use self as phantom replacement and unlink.
if (p.color == BLACK)
fixAfterDeletion(p);
// 把其父节点链接到 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;
}
}
}
修正调整的方法：
private void fixAfterDeletion(Entry<K,V> x) {
while (x != root && colorOf(x) == BLACK) {
// x 是左儿子
if (x == leftOf(parentOf(x))) {
// sib 是 x 的兄弟
Entry<K,V> sib = rightOf(parentOf(x));
// 兄弟是红色的
if (colorOf(sib) == RED) {
setColor(sib, BLACK);
setColor(parentOf(x), RED);
rotateLeft(parentOf(x));
sib = rightOf(parentOf(x));
}
// 兄弟没有孩子或者孩子是黑色的
if (colorOf(leftOf(sib)) == BLACK &&
colorOf(rightOf(sib)) == BLACK) {
setColor(sib, RED);
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;
}
} 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 = 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;
}
}
}
setColor(x, BLACK);
}
来自 “ ITPUB博客 ” ，链接：https://blog.itpub.net/69946337/viewspace-2773715/ ，如需转载，请注明出处，否则将追究法律责任。
