删除一个元素
我们看看 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 {
