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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78

  // Red-black mechanics

  private static final boolean RED   = false;
  private static final boolean BLACK = true;

  /**
   * Node in the Tree.  Doubles as a means to pass key-value pairs back to
   * user (see Map.Entry).
   */

  static final class Entry<K,V> implements Map.Entry<K,V> {
      K key;  
      V value;  
      Entry<K,V> left = null;  //左节点
      Entry<K,V> right = null; // 右节点
      Entry<K,V> parent;       // 父节点
      boolean color = BLACK;  //用boolean类型区分红(false)黑(ture)

      /**
       * Make a new cell with given key, value, and parent, and with
       * {@code null} child links, and BLACK color.
       */
      Entry(K key, V value, Entry<K,V> parent) {
          this.key = key;
          this.value = value;
          this.parent = parent;
      }

      /**
       * Returns the key.
       *
       * @return the key
       */
      public K getKey() {
          return key;
      }

      /**
       * Returns the value associated with the key.
       *
       * @return the value associated with the key
       */
      public V getValue() {
          return value;
      }

      /**
       * Replaces the value currently associated with the key with the given
       * value.
       *
       * @return the value associated with the key before this method was
       *         called
       */
      public V setValue(V value) {
          V oldValue = this.value;
          this.value = value;
          return oldValue;
      }

      public boolean equals(Object o) {
          if (!(o instanceof Map.Entry))
              return false;
          Map.Entry<?,?> e = (Map.Entry<?,?>)o;

          return valEquals(key,e.getKey()) && valEquals(value,e.getValue());
      }

      public int hashCode() {
          int keyHash = (key==null ? 0 : key.hashCode());
          int valueHash = (value==null ? 0 : value.hashCode());
          return keyHash ^ valueHash;
      }

      public String toString() {
          return key + "=" + value;
      }
  }

 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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97

public class TreeMap<K,V>
    extends AbstractMap<K,V>
    implements NavigableMap<K,V>, Cloneable, java.io.Serializable
{
    /**
     * The comparator used to maintain order in this tree map, or
     * null if it uses the natural ordering of its keys.
     * key值比较器
     * @serial
     */
    private final Comparator<? super K> comparator;
    //根节点
    private transient Entry<K,V> root = null;

    /**
     * The number of entries in the tree
     * 大小
     */
    private transient int size = 0;

    /**
     * The number of structural modifications to the tree.
     * //对树进行结构修改的次数
     */
    private transient int modCount = 0;

    /**
     * Constructs a new, empty tree map, using the natural ordering of its
     * keys.  All keys inserted into the map must implement the {@link
     * Comparable} interface.  Furthermore, all such keys must be
     * <em>mutually comparable</em>: {@code k1.compareTo(k2)} must not throw
     * a {@code ClassCastException} for any keys {@code k1} and
     * {@code k2} in the map.  If the user attempts to put a key into the
     * map that violates this constraint (for example, the user attempts to
     * put a string key into a map whose keys are integers), the
     * {@code put(Object key, Object value)} call will throw a
     * {@code ClassCastException}.
     */
    public TreeMap() {
        comparator = null;
    }

    /**
     * Constructs a new, empty tree map, ordered according to the given
     * comparator.  All keys inserted into the map must be <em>mutually
     * comparable</em> by the given comparator: {@code comparator.compare(k1,
     * k2)} must not throw a {@code ClassCastException} for any keys
     * {@code k1} and {@code k2} in the map.  If the user attempts to put
     * a key into the map that violates this constraint, the {@code put(Object
     * key, Object value)} call will throw a
     * {@code ClassCastException}.
     *
     * @param comparator the comparator that will be used to order this map.
     *        If {@code null}, the {@linkplain Comparable natural
     *        ordering} of the keys will be used.
     */
    public TreeMap(Comparator<? super K> comparator) {
        this.comparator = comparator;
    }

    /**
     * Constructs a new tree map containing the same mappings as the given
     * map, ordered according to the <em>natural ordering</em> of its keys.
     * All keys inserted into the new map must implement the {@link
     * Comparable} interface.  Furthermore, all such keys must be
     * <em>mutually comparable</em>: {@code k1.compareTo(k2)} must not throw
     * a {@code ClassCastException} for any keys {@code k1} and
     * {@code k2} in the map.  This method runs in n*log(n) time.
     *
     * @param  m the map whose mappings are to be placed in this map
     * @throws ClassCastException if the keys in m are not {@link Comparable},
     *         or are not mutually comparable
     * @throws NullPointerException if the specified map is null
     */
    public TreeMap(Map<? extends K, ? extends V> m) {
        comparator = null;
        putAll(m);
    }

    /**
     * Constructs a new tree map containing the same mappings and
     * using the same ordering as the specified sorted map.  This
     * method runs in linear time.
     *
     * @param  m the sorted map whose mappings are to be placed in this map,
     *         and whose comparator is to be used to sort this map
     * @throws NullPointerException if the specified map is null
     */
    public TreeMap(SortedMap<K, ? extends V> m) {
        comparator = m.comparator();
        try {
            buildFromSorted(m.size(), m.entrySet().iterator(), null, null);
        } catch (java.io.IOException cannotHappen) {
        } catch (ClassNotFoundException cannotHappen) {
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

    private void rotateLeft(Entry<K,V> p) {
        if (p != null) {
            Entry<K,V> r = p.right;
            p.right = r.left;
            if (r.left != null)
                r.left.parent = p;
            r.parent = p.parent;
            if (p.parent == null)
                root = r;
            else if (p.parent.left == p)
                p.parent.left = r;
            else
                p.parent.right = r;
            r.left = p;
            p.parent = r;
        }
    }

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

   /** From CLR */
   private void rotateRight(Entry<K,V> p) {
       if (p != null) {
           Entry<K,V> l = p.left;
           p.left = l.right;
           if (l.right != null) l.right.parent = p;
           l.parent = p.parent;
           if (p.parent == null)
               root = l;
           else if (p.parent.right == p)
               p.parent.right = l;
           else p.parent.left = l;
           l.right = p;
           p.parent = l;
       }
   }

 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
64
65
66
67
68
69
70
71
72
73
74
75
76

 /**
     * Associates the specified value with the specified key in this map.
     * If the map previously contained a mapping for the key, the old
     * value is replaced.
     *
     * @param key key with which the specified value is to be associated
     * @param value value to be associated with the specified key
     *
     * @return the previous value associated with {@code key}, or
     *         {@code null} if there was no mapping for {@code key}.
     *         (A {@code null} return can also indicate that the map
     *         previously associated {@code null} with {@code key}.)
     * @throws ClassCastException if the specified key cannot be compared
     *         with the keys currently in the map
     * @throws NullPointerException if the specified key is null
     *         and this map uses natural ordering, or its comparator
     *         does not permit null keys
     */
    public V put(K key, V value) {
        Entry<K,V> t = root;
        if (t == null) {  //根节点为空情况
            compare(key, key); // type (and possibly null) check 这里主要做验证key 是否为空

            root = new Entry<>(key, value, null);
            size = 1;
            modCount++;
            return null;
        }
        int cmp;
        Entry<K,V> parent;
        // split comparator and comparable paths
        Comparator<? super K> cpr = comparator;
        if (cpr != null) {
            do {
                parent = t;
                cmp = cpr.compare(key, t.key);
                if (cmp < 0)
                    t = t.left;
                else if (cmp > 0)
                    t = t.right;
                else                    // 相同key值时，覆盖value值
                    return t.setValue(value);  
            } while (t != null);    // while 处理 查询key节点父类，类似于二叉树查询
        }
        else {
            if (key == null)
                throw new NullPointerException();
            Comparable<? super K> k = (Comparable<? super K>) key;
            do {
                parent = t;
                cmp = k.compareTo(t.key);
                if (cmp < 0)
                    t = t.left;
                else if (cmp > 0)
                    t = t.right;
                else
                    return t.setValue(value);
            } while (t != null);           
        }
        Entry<K,V> e = new Entry<>(key, value, parent);//创建一个节点 默认颜色是黑色，调用fixAfterInsertion时把颜色改成红色，插入一个节点为红色，不违背红黑树特性5
        if (cmp < 0)
            parent.left = e;
        else
            parent.right = e;
        fixAfterInsertion(e);     //保持红黑树特性
        size++;
        modCount++;
        return null;
    }
    /**
     * Compares two keys using the correct comparison method for this TreeMap.
     */
    final int compare(Object k1, Object k2) {
        return comparator==null ? ((Comparable<? super K>)k1).compareTo((K)k2)
            : comparator.compare((K)k1, (K)k2);
    }    

 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

  /** From CLR */
    private void fixAfterInsertion(Entry<K,V> x) {
        x.color = RED; //设置红色

        while (x != null && x != root && x.parent.color == RED) {
            if (parentOf(x) == leftOf(parentOf(parentOf(x)))) { //父节点是祖父的左孩子
                Entry<K,V> y = rightOf(parentOf(parentOf(x)));  //  祖父的右孩子(叔叔节点)
                if (colorOf(y) == RED) {                        //    叔叔节点是红色 这种情况场景1:
                    setColor(parentOf(x), BLACK);                                          // (1). 将"父节点"设为黑色。
                    setColor(y, BLACK);                                                    // (2).将"叔叔节点"设为黑色。
                    setColor(parentOf(parentOf(x)), RED);                                  // (3). 将"祖父节点"设为"红色"。
                    x = parentOf(parentOf(x));                                             // (4). 将"祖父节点"设为"当前节点"(红色节点)；即，之后继续对"当前节点"进行操作。
                } else {                       
                    if (x == rightOf(parentOf(x))) {         //     当前节点是其父节点的右孩子 这种情况场景2:    
                        x = parentOf(x);                                                       // (1).将"父节点"作为"新的当前节点"。
                        rotateLeft(x);                                                         // (2). 以"新的当前节点"为支点进行左旋。  必然发现场景3情况
                    }
                                                            //      当前节点是其父节点的左孩子 这种情况场景3：
                    setColor(parentOf(x), BLACK);                                              // (1). 将"父节点"设为"黑色"。
                    setColor(parentOf(parentOf(x)), RED);                                      // (2). 将"祖父节点"设为"红色"。
                    rotateRight(parentOf(parentOf(x)));                                        // (3). 以"祖父节点"为支点进行右旋。
                }
            } else {           //树对称情况 所以不管叔叔节点在左在右，都要做场景3种情况做处理，不同之处：
                              // 父节点是祖父的左孩子时，情况场景2下，当前节点是其父节点的左孩子。进行右旋转
                              // 父节点是祖父的左孩子时，情况场景3下，当前节点是其父节点的右孩子。进行左旋转
                Entry<K,V> y = leftOf(parentOf(parentOf(x)));
                if (colorOf(y) == RED) {
                    setColor(parentOf(x), BLACK);
                    setColor(y, BLACK);
                    setColor(parentOf(parentOf(x)), RED);
                    x = parentOf(parentOf(x));
                } else {                                         
                    if (x == leftOf(parentOf(x))) {             
                        x = parentOf(x);
                        rotateRight(x);
                    }
                    setColor(parentOf(x), BLACK);
                    setColor(parentOf(parentOf(x)), RED);
                    rotateLeft(parentOf(parentOf(x)));
                }
            }
        }
        root.color = BLACK;
    }

 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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80

    /**
     * Returns the value to which the specified key is mapped,
     * or {@code null} if this map contains no mapping for the key.
     *
     * <p>More formally, if this map contains a mapping from a key
     * {@code k} to a value {@code v} such that {@code key} compares
     * equal to {@code k} according to the map's ordering, then this
     * method returns {@code v}; otherwise it returns {@code null}.
     * (There can be at most one such mapping.)
     *
     * <p>A return value of {@code null} does not <em>necessarily</em>
     * indicate that the map contains no mapping for the key; it's also
     * possible that the map explicitly maps the key to {@code null}.
     * The {@link #containsKey containsKey} operation may be used to
     * distinguish these two cases.
     *
     * @throws ClassCastException if the specified key cannot be compared
     *         with the keys currently in the map
     * @throws NullPointerException if the specified key is null
     *         and this map uses natural ordering, or its comparator
     *         does not permit null keys
     */
    public V get(Object key) {
        Entry<K,V> p = getEntry(key);
        return (p==null ? null : p.value);
    }
    /**
     * Returns this map's entry for the given key, or {@code null} if the map
     * does not contain an entry for the key.
     *
     * @return this map's entry for the given key, or {@code null} if the map
     *         does not contain an entry for the key
     * @throws ClassCastException if the specified key cannot be compared
     *         with the keys currently in the map
     * @throws NullPointerException if the specified key is null
     *         and this map uses natural ordering, or its comparator
     *         does not permit null keys
     */
    final Entry<K,V> getEntry(Object key) {
        // Offload comparator-based version for sake of performance
        if (comparator != null)
            return getEntryUsingComparator(key);  //使用比较器获取值
        if (key == null)
            throw new NullPointerException();
        Comparable<? super K> k = (Comparable<? super K>) key;
        Entry<K,V> p = root;
        while (p != null) {
            int cmp = k.compareTo(p.key);
            if (cmp < 0)
                p = p.left;
            else if (cmp > 0)
                p = p.right;
            else
                return p;
        }
        return null;
    } 
  /**
     * Version of getEntry using comparator. Split off from getEntry
     * for performance. (This is not worth doing for most methods,
     * that are less dependent on comparator performance, but is
     * worthwhile here.)
     */
    final Entry<K,V> getEntryUsingComparator(Object key) {
        K k = (K) key;
        Comparator<? super K> cpr = comparator;
        if (cpr != null) {
            Entry<K,V> p = root;
            while (p != null) {
                int cmp = cpr.compare(k, p.key);
                if (cmp < 0)
                    p = p.left;
                else if (cmp > 0)
                    p = p.right;
                else
                    return p;
            }
        }
        return 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
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159

/**
     * Removes the mapping for this key from this TreeMap if present.
     *
     * @param  key key for which mapping should be removed
     * @return the previous value associated with {@code key}, or
     *         {@code null} if there was no mapping for {@code key}.
     *         (A {@code null} return can also indicate that the map
     *         previously associated {@code null} with {@code key}.)
     * @throws ClassCastException if the specified key cannot be compared
     *         with the keys currently in the map
     * @throws NullPointerException if the specified key is null
     *         and this map uses natural ordering, or its comparator
     *         does not permit null keys
     */
    public V remove(Object key) {
        Entry<K,V> p = getEntry(key);
        if (p == null)
            return null;

        V oldValue = p.value;
        deleteEntry(p);
        return oldValue;
    }
   /**
     * Delete node p, and then rebalance the tree.
     */
    private void deleteEntry(Entry<K,V> p) {
        modCount++;
        size--;

        // If strictly internal, copy successor's element to p and then make p 如果严格的内部，将继承的元素复制到p，然后生成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. 如果存在替换节点，请开始修复。 
        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)         // 父节点为空，把当前替换节点赋值为根节点
                root = replacement;
            else if (p == p.parent.left)
                p.parent.left  = replacement;
            else
                p.parent.right = replacement;

            // Null out links so they are OK to use by fixAfterDeletion.
            p.left = p.right = p.parent = null;  //gc 

            // Fix replacement
            if (p.color == BLACK) // 删除的是黑色节点, 那么这个路径上就会少一个黑色节点,破坏黑红树特性5。
                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;
            }
        }
    }
     /**
      * Returns the successor of the specified Entry, or null if no such.
      * 
      */
     static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) {
         if (t == null)
             return null;
         else if (t.right != null) {
             Entry<K,V> p = t.right;
             while (p.left != null)
                 p = p.left;
             return p;
         } else {
             Entry<K,V> p = t.parent;
             Entry<K,V> ch = t;
             while (p != null && ch == p.right) {
                 ch = p;
                 p = p.parent;
             }
             return p;
         }
     }   
  /** From CLR */
    private void fixAfterDeletion(Entry<K,V> x) {
        while (x != root && colorOf(x) == BLACK) {    
            if (x == leftOf(parentOf(x))) {                      //x节点为父节点左孩子
                Entry<K,V> sib = rightOf(parentOf(x));

                if (colorOf(sib) == RED) {                      //x的兄弟节点是红色;场景1:
                    setColor(sib, BLACK);                                         //(1).将x的兄弟节点设为"黑色"。
                    setColor(parentOf(x), RED);                                   //(2).将x的父节点设为"红色"。
                    rotateLeft(parentOf(x));                                      //(3).对x的父节点进行左旋。
                    sib = rightOf(parentOf(x));                                   //(4).左旋后，重新设置x的兄弟节点。
                }

                if (colorOf(leftOf(sib))  == BLACK &&           //x的兄弟节点是黑色，x的兄弟节点的两个孩子都是黑色;
                    colorOf(rightOf(sib)) == BLACK) {                                             //场景2:
                    setColor(sib, RED);                                                           //(1).将x的兄弟节点设为"红色"。    
                    x = parentOf(x);                                                              //(2).设置"x的父节点"为"新的x节点"。
                } else {                   
                    if (colorOf(rightOf(sib)) == BLACK) {      //x的兄弟节点是黑色；x的兄弟节点的左孩子是红色，右孩子是黑色的。场景3:
                        setColor(leftOf(sib), BLACK);                                                //(1). 将x兄弟节点的左孩子设为"黑色"。
                        setColor(sib, RED);                                                          //(2). 将x兄弟节点设为"红色"。
                        rotateRight(sib);                                                            //(3). 对x的兄弟节点进行右旋。
                        sib = rightOf(parentOf(x));                                                  //(4). 右旋后，重新设置x的兄弟节点。
                    }
                                                             //x的兄弟节点是黑色；x的兄弟节点的右孩子是红色的，x的兄弟节点的左孩子任意颜色。场景4:
                    setColor(sib, colorOf(parentOf(x)));                                             //(1). 将x父节点颜色 赋值给x的兄弟节点。
                    setColor(parentOf(x), BLACK);                                                    //(2). 将x父节点设为"黑色"。
                    setColor(rightOf(sib), BLACK);                                                   //(3). 将x兄弟节点的右子节设为"黑色"。
                    rotateLeft(parentOf(x));                                                         //(4). 对x的父节点进行左旋。
                    x = root;                                                                        //(5). 设置"x"为"根节点"。
                }
            } else { // symmetric  红黑树对称的；             x节点为父节点右孩子
                Entry<K,V> sib = leftOf(parentOf(x));

                if (colorOf(sib) == RED) {                   //x的兄弟节点是红色;场景1:
                    setColor(sib, BLACK);
                    setColor(parentOf(x), RED);
                    rotateRight(parentOf(x));                               //(3).对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) {    //x的兄弟节点是黑色；x的兄弟节点的右孩子是红色，右孩子是黑色的。场景3:
                        setColor(rightOf(sib), BLACK);
                        setColor(sib, RED);
                        rotateLeft(sib);                                                                       //(3). 对x的兄弟节点进行左旋。
                        sib = leftOf(parentOf(x));
                    }
                                                           //x的兄弟节点是黑色；x的兄弟节点的左孩子是红色的，x的兄弟节点的左孩子任意颜色。场景3:
                    setColor(sib, colorOf(parentOf(x)));
                    setColor(parentOf(x), BLACK);
                    setColor(leftOf(sib), BLACK);
                    rotateRight(parentOf(x));                                                                     //(4). 对x的父节点进行右旋。
                    x = root;
                }
            }
        }

        setColor(x, BLACK);                                                                                  //当前x设置为黑
    }