TreeMap底层

public class TreeMap<K,V>{
    //    重要属性
    //外部比较器
    private final Comparator<? super K> comparator;
    //树的根节点
    private transient Entry<K,V> root;
    private transient int size = 0;
    //空构造器
    public TreeMap() {
        comparator = null;//如果使用空构造器，那么底层就不适用外部比较器
    }
    //有参构造器
    public TreeMap(Comparator<? super K> comparator) {
        this.comparator = comparator;//如果使用有参构造器，那么就相当于指定了外部比较器
    }
    public V put(K key, V value) {//K和V的类型在创建对象的时候就已经确定
    //如果放入的是第一对元素，那么t的值为NULL
    
        Entry<K,V> t = root;//再放入第二个节点的时候，root已经是跟节点了
        //如果放入的是第一个元素的话，走入这个if中
        if (t == null) {
            //自己跟自己比
            compare(key, key); // type (and possibly null) check
            //根节点确定为root
            root = new Entry<>(key, value, null);
            //size=1
            size = 1;
            modCount++;
            return null;
        }
        int cmp;
        Entry<K,V> parent;
        // split comparator and comparable paths
        //将外部比较器赋给cpr
        Comparator<? super K> cpr = comparator;
        //cpr不等于null，意味着你刚才创建对象的时候调用了有参构造器，指定了外部比较器
        if (cpr != null) {
            do {
                parent = t;
                cmp = cpr.compare(key, t.key);//将元素的KEY值作比较
                //cmp返回的值就是int类型的数据：
                //要是这个值<0   =0  >0
                if (cmp < 0)
                    t = t.left;
                else if (cmp > 0)
                    t = t.right;
                else//cmp==0
                //如果Key的值一样，那么新的value替换老的value，但是key不变因为key是唯一的
                    return t.setValue(value);
            } while (t != null);
        }
        //cpr等于null，意味着你刚才创建对象的时候调用了空参构造器，没有指定外部比较器，使用内部比较器
        else {
            if (key == null)
                throw new NullPointerException();
            @SuppressWarnings("unchecked")
                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);
        if (cmp < 0)
            parent.left = e;
        else
            parent.right = e;
        fixAfterInsertion(e);
        size++;
        modCount++;
        return null;
    }
}

static final class Entry<K,V> implements Map.Entry<K,V> {
        K key;
        V value;
        Entry<K,V> left;
        Entry<K,V> right;
        Entry<K,V> parent;
        boolean color = BLACK;