TreeMap分析(下)

 1     /**
 2      * 删除节点，并平衡红黑树的操作
 3      * 
 4      * @Param Entry<K,V> p  要删除的节点Entry
 5      */
 6     private void deleteEntry(Entry<K,V> p) {
 7         modCount++;
 8         size--;  //节点总数-1
 9 
10         if (p.left != null && p.right != null) {  //当前要删除的节点左右子节点都不为空
11             Entry<K,V> s = successor(p);  //找到一个待删除节点的继承者节点s
12             //将指向s节点,后续所有对p的节点判断其实都是对s节点判断
13             p.key = s.key;
14             p.value = s.value;
15             p = s;
16         }
17 
18         //替代节点选择为当前被删除节点的左子节点(优先)或右子节点
19         Entry<K,V> replacement = (p.left != null ? p.left : p.right);
20 
21         if (replacement != null) {  //替代节点(被删除节点的子节点)不为空
22             
23             replacement.parent = p.parent;  //将替代节点的父节点指向被删除节点的父节点
24             if (p.parent == null)  //如果被删除节点的父节点为null (即被删除的节点就是树的根节点,且根节点下面还有其他节点)
25                 root = replacement;  //将根节点设置为替换节点
26             else if (p == p.parent.left)  //如果原先被删除节点是左子树 插入
27                 p.parent.left  = replacement;  //则将替换节点也保持左子树插入（将替换节点与被删除节点的父节点左子节点建立引用）
28             else   //如果原先被删除节点是右子树 插入
29                 p.parent.right = replacement;  //则将替换节点也保持右子树插入（将替换节点与被删除节点的父节点右子节点建立引用）
30 
31             //将被删除节点的左子节点、右子节点、父节点引用全部置为null
32             p.left = p.right = p.parent = null;
33 
34             //删除后要执行后续的保证红黑树规则的操作
35             if (p.color == BLACK)  //如果被删除节点是黑色的
36                 fixAfterDeletion(replacement);  //调用删除后修正红黑树规则的方法
37         } else if (p.parent == null) { //被删除节点就是根节点，且整个树中就只有一个根节点的情况
38             root = null;  //将根节点置为null（此时整个树中就没有节点了）
39         } else {  //被删除节点没有子节点可替代的情况 (被删除节点是叶子节点)
40             if (p.color == BLACK)   //如果被删除节点是黑色的
41                 fixAfterDeletion(p);  //调用删除后修正红黑树规则的方法
42 
43             if (p.parent != null) {  //如果被删除节点的父节点不为null
44                 if (p == p.parent.left) //如果原先被删除节点是左子树 插入
45                     p.parent.left = null;  //删除节点后将被删除节点的父节点的左子节点置为null
46                 else if (p == p.parent.right)  //如果原先被删除节点是右子树 插入
47                     p.parent.right = null;  //删除节点后将被删除节点的父节点的右子节点置为null
48                 p.parent = null;  //将被删除节点的父节点引用置为null(即将被删除节点从树中移除)
49             }
50         }
51     }

 1    /** 
 2      * 树删除一个节点后，将其根据红黑树的规则进行修正
 3      * @param x  当前删除的节点
 4      */
 5     private void fixAfterDeletion(Entry<K,V> x) {
 6        //循环遍历，x刚开始为被删除的节点
 7         while (x != root && colorOf(x) == BLACK) {  //如果当前遍历到的节点不是根节点且为黑色
 8             if (x == leftOf(parentOf(x))) {  //如果当前遍历到的节点是其父节点的左子节点
 9                 Entry<K,V> sib = rightOf(parentOf(x));  //将当前遍历到的节点的父节点的右子节点用sib变量保存(即和当前节点平级的另一个节点)
10 
11                 if (colorOf(sib) == RED) {  //如果sib引用的节点是红色的
12                     setColor(sib, BLACK);  //将sib引用的节点设置为黑色
13                     setColor(parentOf(x), RED);  //将当前遍历到节点的父节点设置为红色
14                     rotateLeft(parentOf(x));  //对当前遍历到节点的父节点进行一次左旋操作
15                     sib = rightOf(parentOf(x)); //sib引用的节点变更为旋转后被删除节点的父节点的右子节点
16                 }
17 
18                 if (colorOf(leftOf(sib))  == BLACK &&
19                     colorOf(rightOf(sib)) == BLACK) { //如果sib引用节点的左、右子节点都是黑色的
20                     setColor(sib, RED);  //将sib引用的节点设置为红色
21                     x = parentOf(x);  //下一次遍历的节点变更为当前遍历到节点的父节点
22                 } else {  //如果sib引用节点的左、右子节点不全是黑色的
23                     if (colorOf(rightOf(sib)) == BLACK) {  //如果sib引用节点的右子节点是黑色的
24                         setColor(leftOf(sib), BLACK);  //将sib引用节点的左子节点设置为黑色
25                         setColor(sib, RED);   //sib引用节点设置为红色
26                         rotateRight(sib);  //对sib节点进行一次右旋操作
27                         sib = rightOf(parentOf(x)); //sib引用的节点变更为当前遍历到的节点的父节点的右子节点
28                     }
29                     setColor(sib, colorOf(parentOf(x)));  //将sib引用节点的颜色设置为 当前遍历到节点的父节点 一样的颜色
30                     setColor(parentOf(x), BLACK);  //将当前遍历到节点的父节点设置为黑色
31                     setColor(rightOf(sib), BLACK);  //将sib引用节点的右子节点设置为黑色
32                     rotateLeft(parentOf(x));  //对当前遍历到的节点的父节点进行一次左旋操作
33                     x = root;  //下一次遍历的节点变更为根节点
34                 }
35             } else { // 当前遍历到的节点是其父节点的右子节点，和上述情况相似，不再赘述
36                 Entry<K,V> sib = leftOf(parentOf(x));
37 
38                 if (colorOf(sib) == RED) {
39                     setColor(sib, BLACK);
40                     setColor(parentOf(x), RED);
41                     rotateRight(parentOf(x));
42                     sib = leftOf(parentOf(x));
43                 }
44 
45                 if (colorOf(rightOf(sib)) == BLACK &&
46                     colorOf(leftOf(sib)) == BLACK) {
47                     setColor(sib, RED);
48                     x = parentOf(x);
49                 } else {
50                     if (colorOf(leftOf(sib)) == BLACK) {
51                         setColor(rightOf(sib), BLACK);
52                         setColor(sib, RED);
53                         rotateLeft(sib);
54                         sib = leftOf(parentOf(x));
55                     }
56                     setColor(sib, colorOf(parentOf(x)));
57                     setColor(parentOf(x), BLACK);
58                     setColor(leftOf(sib), BLACK);
59                     rotateRight(parentOf(x));
60                     x = root;
61                 }
62             }
63         }
64 
65         setColor(x, BLACK);
66     }