TreeMap的源碼分析

創(chuàng)建對象：

????public TreeMap() {

????????comparator = null;//沒有比較器

????}

public TreeMap(Comparator<? super K> comparator) {

????????this.comparator = comparator;//自定義一個比較器--暫存你的比較器

}

???public V put(K key, V value) {//如果替換了就把被替換的值返給你

????????Entry<K,V> t = root;//用t這個臨時變量來暫存根節(jié)點，第一次根節(jié)點為null

????????if (t == null) {

????????????//第一次放元素進來，先驗證比較器有沒有

????????????compare(key, key); // type (and possibly null) check

????????????root = new Entry<>(key, value, null);//創(chuàng)建出根節(jié)點

????????????size = 1;//第一個節(jié)點

????????????modCount++;//增加和刪除的次數(shù)

????????????return null;//表示沒有替換別的節(jié)點

????????}

????????int cmp;//定義一個臨時變量

????????Entry<K,V> parent;//定義一個臨時存父節(jié)點的變量

????????Comparator<? super K> cpr = comparator;//獲取自定義比較器

????????if (cpr != null) {//有自定義比較器

????????????do {

????????????????parent = t;//把根節(jié)點給父節(jié)點

????????????????cmp = cpr.compare(key, t.key);//key是要加入的鍵?t.key父節(jié)點的鍵

????????????????if (cmp < 0)//左邊

????????????????????t = t.left;

????????????????else if (cmp > 0)

????????????????????t = t.right;//右邊

????????????????else

????????????????????return t.setValue(value);//如果找到相同的key,替換你的值，并且把你的值返回給調(diào)用者

????????????} while (t != null);//只要這個循環(huán)結束，parent里面存的就是我要添加節(jié)點的父節(jié)點

????????}

????????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);

????????}

???????//parent里面存的父節(jié)點，cmp里面存的左邊還是右邊

????????Entry<K,V> e = new Entry<>(key, value, parent);

????????if (cmp < 0)

????????????parent.left = e;//父節(jié)點指向左子節(jié)點

????????else

????????????parent.right = e;//父節(jié)點指向右子節(jié)點

????????fixAfterInsertion(e);

????????size++;

????????modCount++;

????????return null;

????}