首页 | 新闻 | 新品 | 文库 | 方案 | 视频 | 下载 | 商城 | 开发板 | 数据中心 | 座谈新版 | 培训 | 工具 | 博客 | 论坛 | 百科 | GEC | 活动 | 主题月 | 电子展
返回列表 回复 发帖

Java 容器源码分析之 TreeMap(4)

Java 容器源码分析之 TreeMap(4)

删除从红黑树中删除一个节点比插入更为复杂,这里不作展开。
1
2
3
4
5
6
7
8
9
public V remove(Object key) {
    Entry<K,V> p = getEntry(key); //先查找该节点
    if (p == null)
        return null;

    V oldValue = p.value;
    deleteEntry(p); //删除节点
    return oldValue;
}
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;
        }
    }
}
返回列表