红黑树删除

发表于

删除情况图

删除情况

treemap 删除代码

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
 
private void deleteEntry(Entry<K,V> p) {
    modCount++;
    size--;

    // 将 有两个子树的 情况 变成  单子树 或叶子 
    if (p.left != null && p.right != null) {
        Entry<K,V> s = successor(p);
        p.key = s.key;
        p.value = s.value;
        p = s;
    }  

    // 
    Entry<K,V> replacement = (p.left != null ? p.left : p.right);

    // 一个子树 的情况
    if (replacement != null) {
         
        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;

        // 等于删掉这个节点
        p.left = p.right = p.parent = null;

        // 开始平衡
        if (p.color == BLACK)
            fixAfterDeletion(replacement);
    } else if (p.parent == null) { //如果删除根节点
        root = null;
    } else { //  删除叶子节点
        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;
        }
    }
}
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
53
54
55
56
57
58
59
60
61
62
63
// 入参是 黑叶子，或  单子树里用来代替的子节点
//主要是处理 黑叶子情况，因为单子树的情况连循环都不进
   private void fixAfterDeletion(Entry<K,V> x) {
       while (x != root && colorOf(x) == BLACK) {
           if (x == leftOf(parentOf(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 { // 反转情况，操作一样
               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);
   }