Java 集合类 TreeSet、TreeMap

 1 public class TreeSet<E> extends AbstractSet<E>
 2     implements NavigableSet<E>, Cloneable, java.io.Serializable
 3 {
 4 　　/**
 5     * The backing map.
 6     */
 7 　　private transient NavigableMap<E,Object> m;
 8 
 9     // Dummy value to associate with an Object in the backing Map
10     private static final Object PRESENT = new Object();
11 
12 　　/**
13      * Constructs a set backed by the specified navigable map.
14      */
15     TreeSet(NavigableMap<E,Object> m) {
16         this.m = m;
17     }
18 
19     /**
20      * Constructs a new, empty tree set, sorted according to the
21      * natural ordering of its elements.  All elements inserted into
22      * the set must implement the {@link Comparable} interface.
23      * Furthermore, all such elements must be <i>mutually
24      * comparable</i>: {@code e1.compareTo(e2)} must not throw a
25      * {@code ClassCastException} for any elements {@code e1} and
26      * {@code e2} in the set.  If the user attempts to add an element
27      * to the set that violates this constraint (for example, the user
28      * attempts to add a string element to a set whose elements are
29      * integers), the {@code add} call will throw a
30      * {@code ClassCastException}.
31      */
32     public TreeSet() {
33         this(new TreeMap<E,Object>());
34     }
35 　　.......
36 }

 1   public TreeMap() {
 2         comparator = null;
 3   }
 4 
 5  public TreeMap(Comparator<? super K> comparator) {
 6         this.comparator = comparator;
 7    }
 8 .....(其他构造方法不一一列举)
 9 //这里列举put方法详细讲解
10  public V put(K key, V value) {
11         Entry<K,V> t = root;
12         if (t == null) {
13             compare(key, key); // type (and possibly null) check
14 
15             root = new Entry<>(key, value, null);
16             size = 1;
17             modCount++;
18             return null;
19         }
20         int cmp;
21         Entry<K,V> parent;
22         // split comparator and comparable paths
23         Comparator<? super K> cpr = comparator;
24         if (cpr != null) {
25             do {
26                 parent = t;
27                 cmp = cpr.compare(key, t.key);
28                 if (cmp < 0)
29                     t = t.left;
30                 else if (cmp > 0)
31                     t = t.right;
32                 else
33                     return t.setValue(value);
34             } while (t != null);
35         }
36         else {
37             if (key == null)
38                 throw new NullPointerException();
39             Comparable<? super K> k = (Comparable<? super K>) key;
40             do {
41                 parent = t;
42                 cmp = k.compareTo(t.key);
43                 if (cmp < 0)
44                     t = t.left;
45                 else if (cmp > 0)
46                     t = t.right;
47                 else
48                     return t.setValue(value);
49             } while (t != null);
50         }
51         Entry<K,V> e = new Entry<>(key, value, parent);
52         if (cmp < 0)
53             parent.left = e;
54         else
55             parent.right = e;
56         fixAfterInsertion(e);
57         size++;
58         modCount++;
59         return null;
60     }

1         K key;
2         V value;
3         Entry<K,V> left = null;
4         Entry<K,V> right = null;
5         Entry<K,V> parent;