1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
| 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.
// 左子节点存在，则 replacement 为左子节点，否则为右子节点
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) //p 就是根节点
root = replacement;
else if (p == p.parent.left)//p 是父节点的左子节点
p.parent.left = replacement;
else//p 是父节点的右子节点
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;
}
}
} |
