? ? ??常見的數(shù)據(jù)結(jié)構(gòu)有數(shù)組、鏈表，還有一種結(jié)構(gòu)也很常見，那就是樹。前面介紹的集合類有基于數(shù)組的ArrayList，有基于鏈表的LinkedList，還有鏈表和數(shù)組結(jié)合的HashMap，今天介紹基于樹的TreeMap。
? ? ?TreeMap基于紅黑樹（）實(shí)現(xiàn)。查看“鍵”或“鍵值對”時(shí)，它們會被排序（次序由Comparable或Comparator決定）。TreeMap的特點(diǎn)在于，所得到的結(jié)果是經(jīng)過排序的。TreeMap是唯一的帶有subMap()方法的Map，它可以返回一個(gè)子樹。?
? ? ?在介紹TreeMap前先介紹Comparable和Comparator接口。?
? ? ?Comparable接口：
1 public interface Comparable<T> { 2 public int compareTo(T o); 3 }
? ? ?Comparable接口支持泛型，只有一個(gè)方法，該方法返回負(fù)數(shù)、零、正數(shù)分別表示當(dāng)前對象“小于”、“等于”、“大于”傳入對象o。
? ? ?Comparamtor接口：
1 public interface Comparator<T> { 2 int compare(T o1, T o2); 3 boolean equals(Object obj); 4 }
? ? ?compare(T o1,T o2)方法比較o1和o2兩個(gè)對象，o1“大于”o2，返回正數(shù)，相等返回零，“小于”返回負(fù)數(shù)。
? ? ?equals(Object obj)返回true的唯一情況是obj也是一個(gè)比較器（Comparator）并且比較結(jié)果和此比較器的結(jié)果的大小次序是一致的。即comp1.equals(comp2)意味著sgn(comp1.compare(o1, * o2))==sgn(comp2.compare(o1, o2))。
? ? ?補(bǔ)充：符號sgn(expression)表示數(shù)學(xué)上的signum函數(shù)，該函數(shù)根據(jù)expression的值是負(fù)數(shù)、零或正數(shù)，分別返回-1、0或1。
? ? ?小結(jié)一下，實(shí)現(xiàn)Comparable結(jié)構(gòu)的類可以和其他對象進(jìn)行比較，即實(shí)現(xiàn)Comparable可以進(jìn)行比較的類。而實(shí)現(xiàn)Comparator接口的類是比較器，用于比較兩個(gè)對象的大小。
? ? ?下面正式分析TreeMap的源碼。
? ? ?既然TreeMap底層使用的是樹結(jié)構(gòu)，那么必然有表示節(jié)點(diǎn)的對象。下面先看TreeMap中表示節(jié)點(diǎn)的內(nèi)部類Entry。
1 static final class Entry<K,V> implements Map.Entry<K,V> { 2 // 鍵值對的“鍵” 3 K key; 4 // 鍵值對的“值” 5 V value; 6 // 左孩子 7 Entry<K,V> left = null; 8 // 右孩子 9 Entry<K,V> right = null; 10 // 父節(jié)點(diǎn) 11 Entry<K,V> parent; 12 // 紅黑樹的節(jié)點(diǎn)表示顏色的屬性 13 boolean color = BLACK; 14 /** 15 * 根據(jù)給定的鍵、值、父節(jié)點(diǎn)構(gòu)造一個(gè)節(jié)點(diǎn)，顏色為默認(rèn)的黑色 16 */ 17 Entry(K key, V value, Entry<K,V> parent) { 18 this.key = key; 19 this.value = value; 20 this.parent = parent; 21 } 22 // 獲取節(jié)點(diǎn)的key 23 public K getKey() { 24 return key; 25 } 26 // 獲取節(jié)點(diǎn)的value 27 public V getValue() { 28 return value; 29 } 30 /** 31 * 修改并返回當(dāng)前節(jié)點(diǎn)的value 32 */ 33 public V setValue(V value) { 34 V oldValue = this.value; 35 this.value = value; 36 return oldValue; 37 } 38 // 判斷節(jié)點(diǎn)相等的方法（兩個(gè)節(jié)點(diǎn)為同一類型且key值和value值都相等時(shí)兩個(gè)節(jié)點(diǎn)相等） 39 public boolean equals(Object o) { 40 if (!(o instanceof Map.Entry)) 41 return false; 42 Map.Entry<?,?> e = (Map.Entry<?,?>)o; 43 return valEquals(key,e.getKey()) && valEquals(value,e.getValue()); 44 } 45 // 節(jié)點(diǎn)的哈希值計(jì)算方法 46 public int hashCode() { 47 int keyHash = (key==null ? 0 : key.hashCode()); 48 int valueHash = (value==null ? 0 : value.hashCode()); 49 return keyHash ^ valueHash; 50 } 51 public String toString() { 52 return key + "=" + value; 53 } }
? ? 上面的Entry類比較簡單，實(shí)現(xiàn)了樹節(jié)點(diǎn)的必要內(nèi)容，提供了hashCode方法等。下面看TreeMap類的定義。
1 public class TreeMap<K,V> 2 extends AbstractMap<K,V> 3 implements NavigableMap<K,V>, Cloneable, java.io.Serializable
? ? ?上面只有一個(gè)接口需要說明，那就是NavigableMap接口。
? ? ?NavigableMap接口擴(kuò)展的SortedMap，具有了針對給定搜索目標(biāo)返回最接近匹配項(xiàng)的導(dǎo)航方法。方法lowerEntry、floorEntry、ceilingEntry和higherEntry分別返回與小于、小于等于、大于等于、大于給定鍵的鍵關(guān)聯(lián)的Map.Entry對象，如果不存在這樣的鍵，則返回null。類似地，方法lowerKey、floorKey、ceilingKey和higherKey只返回關(guān)聯(lián)的鍵。所有這些方法是為查找條目而不是遍歷條目而設(shè)計(jì)的（后面會逐個(gè)介紹這些方法）。
? ? ?下面是TreeMap的屬性：
1 // 用于保持順序的比較器，如果為空的話使用自然順保持Key的順序 2 private final Comparator<? super K> comparator; 3 // 根節(jié)點(diǎn) 4 private transient Entry<K,V> root = null; 5 // 樹中的節(jié)點(diǎn)數(shù)量 6 private transient int size = 0; 7 // 多次在集合類中提到了，用于舉了結(jié)構(gòu)行的改變次數(shù) 8 private transient int modCount = 0;
? ? 注釋中已經(jīng)給出了屬性的解釋，下面看TreeMap的構(gòu)造方法。
1 // 構(gòu)造方法一，默認(rèn)的構(gòu)造方法，comparator為空，即采用自然順序維持TreeMap中節(jié)點(diǎn)的順序 2 public TreeMap() { 3 comparator = null; 4 } 5 // 構(gòu)造方法二，提供指定的比較器 6 public TreeMap(Comparator<? super K> comparator) { 7 this.comparator = comparator; 8 } 9 // 構(gòu)造方法三，采用自然序維持TreeMap中節(jié)點(diǎn)的順序，同時(shí)將傳入的Map中的內(nèi)容添加到TreeMap中 10 public TreeMap(Map<? extends K, ? extends V> m) { 11 comparator = null; 12 putAll(m); 13 } 14 /** 15 *構(gòu)造方法四，接收SortedMap參數(shù)，根據(jù)SortedMap的比較器維持TreeMap中的節(jié)點(diǎn)順序，* 同時(shí)通過buildFromSorted(int size, Iterator it, java.io.ObjectInputStream str, V defaultVal)方* 法將SortedMap中的內(nèi)容添加到TreeMap中 16 */ 17 public TreeMap(SortedMap<K, ? extends V> m) { 18 comparator = m.comparator(); 19 try { 20 buildFromSorted(m.size(), m.entrySet().iterator(), null, null); 21 } catch (java.io.IOException cannotHappen) { 22 } catch (ClassNotFoundException cannotHappen) { 23 } 24 }
? ? ?TreeMap提供了四個(gè)構(gòu)造方法，已經(jīng)在注釋中給出說明。構(gòu)造方法中涉及到的方法在下文中會有介紹。
? ? ?下面從put/get方法開始，逐個(gè)分析TreeMap的方法。
? ? ?put(K key, V value)
1 public V put(K key, V value) { 2 Entry<K,V> t = root; 3 if (t == null) { 4 //如果根節(jié)點(diǎn)為null，將傳入的鍵值對構(gòu)造成根節(jié)點(diǎn)（根節(jié)點(diǎn)沒有父節(jié)點(diǎn)，所以傳入的父節(jié)點(diǎn)為null） 5 root = new Entry<K,V>(key, value, null); 6 size = 1; 7 modCount++; 8 return null; 9 } 10 // 記錄比較結(jié)果 11 int cmp; 12 Entry<K,V> parent; 13 // 分割比較器和可比較接口的處理 14 Comparator<? super K> cpr = comparator; 15 // 有比較器的處理 16 if (cpr != null) { 17 // do while實(shí)現(xiàn)在root為根節(jié)點(diǎn)移動尋找傳入鍵值對需要插入的位置 18 do { 19 // 記錄將要被摻入新的鍵值對將要節(jié)點(diǎn)(即新節(jié)點(diǎn)的父節(jié)點(diǎn)) 20 parent = t; 21 // 使用比較器比較父節(jié)點(diǎn)和插入鍵值對的key值的大小 22 cmp = cpr.compare(key, t.key); 23 // 插入的key較大 24 if (cmp < 0) 25 t = t.left; 26 // 插入的key較小 27 else if (cmp > 0) 28 t = t.right; 29 // key值相等，替換并返回t節(jié)點(diǎn)的value(put方法結(jié)束) 30 else 31 return t.setValue(value); 32 } while (t != null); 33 } 34 // 沒有比較器的處理 35 else { 36 // key為null拋出NullPointerException異常 37 if (key == null) 38 throw new NullPointerException(); 39 Comparable<? super K> k = (Comparable<? super K>) key; 40 // 與if中的do while類似，只是比較的方式不同 41 do { 42 parent = t; 43 cmp = k.compareTo(t.key); 44 if (cmp < 0) 45 t = t.left; 46 else if (cmp > 0) 47 t = t.right; 48 else 49 return t.setValue(value); 50 } while (t != null); 51 } 52 // 沒有找到key相同的節(jié)點(diǎn)才會有下面的操作 53 // 根據(jù)傳入的鍵值對和找到的“父節(jié)點(diǎn)”創(chuàng)建新節(jié)點(diǎn) Entry<K,V> e = new Entry<K,V>(key, value, parent); 55 // 根據(jù)最后一次的判斷結(jié)果確認(rèn)新節(jié)點(diǎn)是“父節(jié)點(diǎn)”的左孩子還是又孩子 56 if (cmp < 0) 57 parent.left = e; 58 else 59 parent.right = e; 60 // 對加入新節(jié)點(diǎn)的樹進(jìn)行調(diào)整 61 fixAfterInsertion(e); 62 // 記錄size和modCount 63 size++; modCount++; 65 // 因?yàn)槭遣迦胄鹿?jié)點(diǎn)，所以返回的是null 66 return null; 67 }
? ? ?首先一點(diǎn)通性是TreeMap的put方法和其他Map的put方法一樣，向Map中加入鍵值對，若原先“鍵（key）”已經(jīng)存在則替換“值（value）”，并返回原先的值。
? ? ?在put(K key,V value)方法的末尾調(diào)用了fixAfterInsertion(Entry<K,V> x)方法，這個(gè)方法負(fù)責(zé)在插入節(jié)點(diǎn)后調(diào)整樹結(jié)構(gòu)和著色，以滿足的要求。
? ? ?在看fixAfterInsertion(Entry<K,V> x)方法前先看一個(gè)紅黑樹的內(nèi)容：紅黑樹不是嚴(yán)格的平衡二叉樹，它并不嚴(yán)格的保證左右子樹的高度差不超過1，但紅黑樹高度依然是平均log(n)，且最壞情況高度不會超過2log(n)，所以它算是平衡樹。
? ? ?下面看具體實(shí)現(xiàn)代碼。
? ? ?fixAfterInsertion(Entry<K,V> x)
1 private void fixAfterInsertion(Entry<K,V> x) { 2 // 插入節(jié)點(diǎn)默認(rèn)為紅色 3 x.color = RED; 4 // 循環(huán)條件是x不為空、不是根節(jié)點(diǎn)、父節(jié)點(diǎn)的顏色是紅色（如果父節(jié)點(diǎn)不是紅色，則沒有連續(xù)的紅色節(jié)點(diǎn)，不再調(diào)整） 5 while (x != null && x != root && x.parent.color == RED) { 6 // x節(jié)點(diǎn)的父節(jié)點(diǎn)p（記作p）是其父節(jié)點(diǎn)pp（p的父節(jié)點(diǎn)，記作pp）的左孩子（pp的左孩子） 7 if (parentOf(x) == leftOf(parentOf(parentOf(x)))) { 8 // 獲取pp節(jié)點(diǎn)的右孩子r 9 Entry<K,V> y = rightOf(parentOf(parentOf(x))); 10 // pp右孩子的顏色是紅色（colorOf(Entry e)方法在e為空時(shí)返回BLACK），不需要進(jìn)行旋轉(zhuǎn)操作（因?yàn)榧t黑樹不是嚴(yán)格的平衡二叉樹） 11 if (colorOf(y) == RED) { 12 // 將父節(jié)點(diǎn)設(shè)置為黑色 13 setColor(parentOf(x), BLACK); 14 // y節(jié)點(diǎn)，即r設(shè)置成黑色 15 setColor(y, BLACK); 16 // pp節(jié)點(diǎn)設(shè)置成紅色 17 setColor(parentOf(parentOf(x)), RED); 18 // x“移動”到pp節(jié)點(diǎn) 19 x = parentOf(parentOf(x)); 20 } else {//父親的兄弟是黑色的，這時(shí)需要進(jìn)行旋轉(zhuǎn)操作，根據(jù)是“內(nèi)部”還是“外部”的情況決定是雙旋轉(zhuǎn)還是單旋轉(zhuǎn) 21 // x節(jié)點(diǎn)是父節(jié)點(diǎn)的右孩子（因?yàn)樯厦嬉呀_認(rèn)p是pp的左孩子，所以這是一個(gè)“內(nèi)部，左-右”插入的情況，需要進(jìn)行雙旋轉(zhuǎn)處理） 22 if (x == rightOf(parentOf(x))) { 23 // x移動到它的父節(jié)點(diǎn) 24 x = parentOf(x); 25 // 左旋操作 26 rotateLeft(x); 27 } 28 // x的父節(jié)點(diǎn)設(shè)置成黑色 29 setColor(parentOf(x), BLACK); 30 // x的父節(jié)點(diǎn)的父節(jié)點(diǎn)設(shè)置成紅色 31 setColor(parentOf(parentOf(x)), RED); 32 // 右旋操作 33 rotateRight(parentOf(parentOf(x))); 34 } 35 } else { 36 // 獲取x的父節(jié)點(diǎn)（記作p）的父節(jié)點(diǎn)（記作pp）的左孩子 37 Entry<K,V> y = leftOf(parentOf(parentOf(x))); 38 // y節(jié)點(diǎn)是紅色的 39 if (colorOf(y) == RED) { 40 // x的父節(jié)點(diǎn)，即p節(jié)點(diǎn)，設(shè)置成黑色 41 setColor(parentOf(x), BLACK); 42 // y節(jié)點(diǎn)設(shè)置成黑色 43 setColor(y, BLACK); 44 // pp節(jié)點(diǎn)設(shè)置成紅色 45 setColor(parentOf(parentOf(x)), RED); 46 // x移動到pp節(jié)點(diǎn) 47 x = parentOf(parentOf(x)); 48 } else { 49 // x是父節(jié)點(diǎn)的左孩子（因?yàn)樯厦嬉呀_認(rèn)p是pp的右孩子，所以這是一個(gè)“內(nèi)部，右-左”插入的情況，需要進(jìn)行雙旋轉(zhuǎn)處理）， 50 if (x == leftOf(parentOf(x))) { 51 // x移動到父節(jié)點(diǎn) 52 x = parentOf(x); 53 // 右旋操作 rotateRight(x); 55 } 56 // x的父節(jié)點(diǎn)設(shè)置成黑色 57 setColor(parentOf(x), BLACK); 58 // x的父節(jié)點(diǎn)的父節(jié)點(diǎn)設(shè)置成紅色 59 setColor(parentOf(parentOf(x)), RED); 60 // 左旋操作 61 rotateLeft(parentOf(parentOf(x))); 62 } 63 } } 65 // 根節(jié)點(diǎn)為黑色 66 root.color = BLACK; 67 }
? ? ?fixAfterInsertion(Entry<K,V> x)方法涉及到了左旋和右旋的操作，下面是左旋的代碼及示意圖（右旋操作類似，就不給出代碼和示意圖了）。
1 // 左旋操作 2 private void rotateLeft(Entry<K,V> p) { 3 if (p != null) { 4 Entry<K,V> r = p.right; 5 p.right = r.left; 6 if (r.left != null) 7 r.left.parent = p; 8 r.parent = p.parent; 9 if (p.parent == null) 10 root = r; 11 else if (p.parent.left == p) 12 p.parent.left = r; 13 else 14 p.parent.right = r; 15 r.left = p; 16 p.parent = r; 17 } 18 }
? ? ?看完put操作，下面來看get操作相關(guān)的內(nèi)容。
? ? ?get(Object key)
1 public V get(Object key) { 2 Entry<K,V> p = getEntry(key); 3 return (p==null ? null : p.value); 4 }
? ? ?get(Object key)通過key獲取對應(yīng)的value，它通過調(diào)用getEntry(Object key)獲取節(jié)點(diǎn)，若節(jié)點(diǎn)為null則返回null，否則返回節(jié)點(diǎn)的value值。下面是getEntry(Object key)的內(nèi)容，來看它是怎么尋找節(jié)點(diǎn)的。
? ? ?getEntry(Object key)
1 final Entry<K,V> getEntry(Object key) { 2 // 如果有比較器，返回getEntryUsingComparator(Object key)的結(jié)果 3 if (comparator != null) 4 return getEntryUsingComparator(key); 5 // 查找的key為null，拋出NullPointerException 6 if (key == null) 7 throw new NullPointerException(); 8 // 如果沒有比較器，而是實(shí)現(xiàn)了可比較接口 9 Comparable<? super K> k = (Comparable<? super K>) key; 10 // 獲取根節(jié)點(diǎn) 11 Entry<K,V> p = root; 12 // 對樹進(jìn)行遍歷查找節(jié)點(diǎn) 13 while (p != null) { 14 // 把key和當(dāng)前節(jié)點(diǎn)的key進(jìn)行比較 15 int cmp = k.compareTo(p.key); 16 // key小于當(dāng)前節(jié)點(diǎn)的key 17 if (cmp < 0) 18 // p “移動”到左節(jié)點(diǎn)上 19 p = p.left; 20 // key大于當(dāng)前節(jié)點(diǎn)的key 21 else if (cmp > 0) 22 // p “移動”到右節(jié)點(diǎn)上 23 p = p.right; 24 // key值相等則當(dāng)前節(jié)點(diǎn)就是要找的節(jié)點(diǎn) 25 else 26 // 返回找到的節(jié)點(diǎn) 27 return p; 28 } 29 // 沒找到則返回null 30 return null; 31 }
? ? ?上面主要是處理實(shí)現(xiàn)了可比較接口的情況，而有比較器的情況在getEntryUsingComparator(Object key)中處理了，下面來看處理的代碼。
? ? ?getEntryUsingComparator(Object key)
1 final Entry<K,V> getEntryUsingComparator(Object key) { 2 K k = (K) key; 3 // 獲取比較器 4 Comparator<? super K> cpr = comparator; 5 // 其實(shí)在調(diào)用此方法的get(Object key)中已經(jīng)對比較器為null的情況進(jìn)行判斷，這里是防御性的判斷 6 if (cpr != null) { 7 // 獲取根節(jié)點(diǎn) 8 Entry<K,V> p = root; 9 // 遍歷樹 10 while (p != null) { 11 // 獲取key和當(dāng)前節(jié)點(diǎn)的key的比較結(jié)果 12 int cmp = cpr.compare(k, p.key); 13 // 查找的key值較小 14 if (cmp < 0) 15 // p“移動”到左孩子 16 p = p.left; 17 // 查找的key值較大 18 else if (cmp > 0) 19 // p“移動”到右節(jié)點(diǎn) 20 p = p.right; 21 // key值相等 22 else 23 // 返回找到的節(jié)點(diǎn) 24 return p; 25 } 26 } 27 // 沒找到key值對應(yīng)的節(jié)點(diǎn)，返回null 28 return null; 29 }
? ? ?看完添加（put）和獲?。╣et），下面來看刪除（remove、clear）。
? ? ?remove(Object key)
1 public V remove(Object key) { 2 // 通過getEntry(Object key)獲取節(jié)點(diǎn) getEntry(Object key)方法已經(jīng)在上面介紹過了 3 Entry<K,V> p = getEntry(key); 4 // 指定key的節(jié)點(diǎn)不存在，返回null 5 if (p == null) 6 return null; 7 // 獲取節(jié)點(diǎn)的value 8 V oldValue = p.value; 9 // 刪除節(jié)點(diǎn) 10 deleteEntry(p); 11 // 返回節(jié)點(diǎn)的內(nèi)容 12 return oldValue; 13 }
? ? ?真正實(shí)現(xiàn)刪除節(jié)點(diǎn)的內(nèi)容在deleteEntry(Entry e)中，涉及到樹結(jié)構(gòu)的調(diào)整等。remove(Object key)只是獲取要?jiǎng)h除的節(jié)點(diǎn)并返回被刪除節(jié)點(diǎn)的value。下面來看deleteEntry(Entry e)的內(nèi)容。
? ? ?deleteEntry(Entry e)
1 private void deleteEntry(Entry<K,V> p) { 2 // 記錄樹結(jié)構(gòu)的修改次數(shù) 3 modCount++; 4 // 記錄樹中節(jié)點(diǎn)的個(gè)數(shù) 5 size--; 6 7 // p有左右兩個(gè)孩子的情況 標(biāo)記① 8 if (p.left != null && p.right != null) { 9 // 獲取繼承者節(jié)點(diǎn)（有兩個(gè)孩子的情況下，繼承者肯定是右孩子或右孩子的最左子孫） 10 Entry<K,V> s = successor (p); 11 // 使用繼承者s替換要被刪除的節(jié)點(diǎn)p，將繼承者的key和value復(fù)制到p節(jié)點(diǎn)，之后將p指向繼承者 12 p.key = s.key; 13 p.value = s.value; 14 p = s; 15 } 16 17 // Start fixup at replacement node, if it exists. 18 // 開始修復(fù)被移除節(jié)點(diǎn)處的樹結(jié)構(gòu) 19 // 如果p有左孩子，取左孩子，否則取右孩子 標(biāo)記② 20 Entry<K,V> replacement = (p.left != null ? p.left : p.right); 21 if (replacement != null) { 22 // Link replacement to parent 23 replacement.parent = p.parent; 24 // p節(jié)點(diǎn)沒有父節(jié)點(diǎn)，即p節(jié)點(diǎn)是根節(jié)點(diǎn) 25 if (p.parent == null) 26 // 將根節(jié)點(diǎn)替換為replacement節(jié)點(diǎn) 27 root = replacement; 28 // p是其父節(jié)點(diǎn)的左孩子 29 else if (p == p.parent.left) 30 // 將p的父節(jié)點(diǎn)的left引用指向replacement 31 // 這步操作實(shí)現(xiàn)了刪除p的父節(jié)點(diǎn)到p節(jié)點(diǎn)的引用 32 p.parent.left = replacement; 33 else 34 // 如果p是其父節(jié)點(diǎn)的右孩子，將父節(jié)點(diǎn)的right引用指向replacement 35 p.parent.right = replacement; 36 // 解除p節(jié)點(diǎn)到其左右孩子和父節(jié)點(diǎn)的引用 37 p.left = p.right = p.parent = null; 38 if (p.color == BLACK) 39 // 在刪除節(jié)點(diǎn)后修復(fù)紅黑樹的顏色分配 40 fixAfterDeletion(replacement); 41 } else if (p.parent == null) { 42 /* 進(jìn)入這塊代碼則說明p節(jié)點(diǎn)就是根節(jié)點(diǎn)（這塊比較難理解，如果標(biāo)記①處p有左右孩子，則找到的繼承節(jié)點(diǎn)s是p的一個(gè)祖先節(jié)點(diǎn)或右孩子或右孩子的最左子孫節(jié)點(diǎn)，他們要么有孩子節(jié)點(diǎn)，要么有父節(jié)點(diǎn)，所以如果進(jìn)入這塊代碼，則說明標(biāo)記①除的p節(jié)點(diǎn)沒有左右兩個(gè)孩子。沒有左右孩子，則有沒有孩子、有一個(gè)右孩子、有一個(gè)左孩子三種情況，三種情況中只有沒有孩子的情況會使標(biāo)記②的if判斷不通過，所以p節(jié)點(diǎn)只能是沒有孩子，加上這里的判斷，p沒有父節(jié)點(diǎn)，所以p是一個(gè)節(jié)點(diǎn)，也是樹種的唯一節(jié)點(diǎn)……有點(diǎn)難理解，只能解釋到這里了，讀者只能結(jié)合注釋慢慢體會了），所以將根節(jié)點(diǎn)設(shè)置為null即實(shí)現(xiàn)了對該節(jié)點(diǎn)的刪除 */ 43 root = null; 44 } else { /* 標(biāo)記②的if判斷沒有通過說明被刪除節(jié)點(diǎn)沒有孩子，或它有兩個(gè)孩子但它的繼承者沒有孩子。如果是被刪除節(jié)點(diǎn)沒有孩子，說明p是個(gè)葉子節(jié)點(diǎn)，則不需要找繼承者，直接刪除該節(jié)點(diǎn)。如果是有兩個(gè)孩子，那么繼承者肯定是右孩子或右孩子的最左子孫 */ 45 if (p.color == BLACK) 46 // 調(diào)整樹結(jié)構(gòu) 47 fixAfterDeletion(p); 48 // 這個(gè)判斷也一定會通過，因?yàn)閜.parent如果不是null則在上面的else if塊中已經(jīng)被處理 49 if (p.parent != null) { 50 // p是一個(gè)左孩子 51 if (p == p.parent.left) 52 // 刪除父節(jié)點(diǎn)對p的引用 53 p.parent.left = null; else if (p == p.parent.right)// p是一個(gè)右孩子 55 // 刪除父節(jié)點(diǎn)對p的引用 56 p.parent.right = null; 57 // 刪除p節(jié)點(diǎn)對父節(jié)點(diǎn)的引用 58 p.parent = null; 59 } 60 } 61 }
? ? ?deleteEntry(Entry e)方法中主要有兩個(gè)方法調(diào)用需要分析：successor(Entry<K,V> t)和fixAfterDeletion(Entry<K,V> x)。
? ? ?successor(Entry<K,V> t)返回指定節(jié)點(diǎn)的繼承者。分三種情況處理，第一。t節(jié)點(diǎn)是個(gè)空節(jié)點(diǎn)：返回null；第二，t有右孩子：找到t的右孩子中的最左子孫節(jié)點(diǎn)，如果右孩子沒有左孩子則返回右節(jié)點(diǎn)，否則返回找到的最左子孫節(jié)點(diǎn)；第三，t沒有右孩子：沿著向上（向跟節(jié)點(diǎn)方向）找到第一個(gè)自身是一個(gè)左孩子的節(jié)點(diǎn)或根節(jié)點(diǎn)，返回找到的節(jié)點(diǎn)。下面是具體代碼分析的注釋。
1 static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) { 2 // 如果t本身是一個(gè)空節(jié)點(diǎn)，返回null 3 if (t == null) 4 return null; 5 // 如果t有右孩子，找到右孩子的最左子孫節(jié)點(diǎn) 6 else if (t.right != null) { 7 Entry<K,V> p = t.right; 8 // 獲取p節(jié)點(diǎn)最左的子孫節(jié)點(diǎn)，如果存在的話 9 while (p.left != null) 10 p = p.left; 11 // 返回找到的繼承節(jié)點(diǎn) 12 return p; 13 } else {//t不為null且沒有右孩子 14 Entry<K,V> p = t.parent; 15 Entry<K,V> ch = t; 16 // // 沿著右孩子向上查找繼承者，直到根節(jié)點(diǎn)或找到節(jié)點(diǎn)ch是其父節(jié)點(diǎn)的左孩子的節(jié)點(diǎn) 17 while (p != null && ch == p.right) { 18 ch = p; 19 p = p.parent; 20 } 21 return p; 22 } 23 }
? ? ?與添加節(jié)點(diǎn)之后的修復(fù)類似的是，TreeMap 刪除節(jié)點(diǎn)之后也需要進(jìn)行類似的修復(fù)操作，通過這種修復(fù)來保證該排序二叉樹依然滿足紅黑樹特征。大家可以參考插入節(jié)點(diǎn)之后的修復(fù)來分析刪除之后的修復(fù)。TreeMap 在刪除之后的修復(fù)操作由 fixAfterDeletion(Entry<K,V> x) 方法提供，該方法源代碼如下：
1 private void fixAfterDeletion(Entry<K,V> x) { 2 // 循環(huán)處理，條件為x不是root節(jié)點(diǎn)且是黑色的（因?yàn)榧t色不會對紅黑樹的性質(zhì)造成破壞，所以不需要調(diào)整） 3 while (x != root && colorOf(x) == BLACK) { 4 // x是一個(gè)左孩子 5 if (x == leftOf(parentOf(x))) { 6 // 獲取x的兄弟節(jié)點(diǎn)sib 7 Entry<K,V> sib = rightOf(parentOf(x)); 8 // sib是紅色的 9 if (colorOf(sib) == RED) { 10 // 將sib設(shè)置為黑色 11 setColor(sib, BLACK); 12 // 將父節(jié)點(diǎn)設(shè)置成紅色 13 setColor(parentOf(x), RED); 14 // 左旋父節(jié)點(diǎn) 15 rotateLeft(parentOf(x)); 16 // sib移動到旋轉(zhuǎn)后x的父節(jié)點(diǎn)p的右孩子（參見左旋示意圖，獲取的節(jié)點(diǎn)是旋轉(zhuǎn)前p的右孩子r的左孩子rl） 17 sib = rightOf(parentOf(x)); 18 } 19 // sib的兩個(gè)孩子的顏色都是黑色（null返回黑色） 20 if (colorOf(leftOf(sib)) == BLACK && 21 colorOf(rightOf(sib)) == BLACK) { 22 // 將sib設(shè)置成紅色 23 setColor(sib, RED); 24 // x移動到x的父節(jié)點(diǎn) 25 x = parentOf(x); 26 } else {// sib的左右孩子都是黑色的不成立 27 // sib的右孩子是黑色的 28 if (colorOf(rightOf(sib)) == BLACK) { 29 // 將sib的左孩子設(shè)置成黑色 30 setColor(leftOf(sib), BLACK); 31 // sib節(jié)點(diǎn)設(shè)置成紅色 32 setColor(sib, RED); 33 // 右旋操作 34 rotateRight(sib); 35 // sib移動到旋轉(zhuǎn)后x父節(jié)點(diǎn)的右孩子 36 sib = rightOf(parentOf(x)); 37 } 38 // sib設(shè)置成和x的父節(jié)點(diǎn)一樣的顏色 39 setColor(sib, colorOf(parentOf(x))); 40 // x的父節(jié)點(diǎn)設(shè)置成黑色 41 setColor(parentOf(x), BLACK); 42 // sib的右孩子設(shè)置成黑色 43 setColor(rightOf(sib), BLACK); 44 // 左旋操作 45 rotateLeft(parentOf(x)); 46 // 設(shè)置調(diào)整完的條件：x = root跳出循環(huán) 47 x = root; 48 } 49 } else { // x是一個(gè)右孩子 50 // 獲取x的兄弟節(jié)點(diǎn) 51 Entry<K,V> sib = leftOf(parentOf(x)); 52 // 如果sib是紅色的 53 if (colorOf(sib) == RED) { // 將sib設(shè)置為黑色 55 setColor(sib, BLACK); 56 // 將x的父節(jié)點(diǎn)設(shè)置成紅色 57 setColor(parentOf(x), RED); 58 // 右旋 59 rotateRight(parentOf(x)); 60 // sib移動到旋轉(zhuǎn)后x父節(jié)點(diǎn)的左孩子 61 sib = leftOf(parentOf(x)); 62 } 63 // sib的兩個(gè)孩子的顏色都是黑色（null返回黑色） if (colorOf(rightOf(sib)) == BLACK && 65 colorOf(leftOf(sib)) == BLACK) { 66 // sib設(shè)置為紅色 67 setColor(sib, RED); 68 // x移動到x的父節(jié)點(diǎn) 69 x = parentOf(x); 70 } else { // sib的兩個(gè)孩子的顏色都是黑色（null返回黑色）不成立 71 // sib的左孩子是黑色的，或者沒有左孩子 72 if (colorOf(leftOf(sib)) == BLACK) { 73 // 將sib的右孩子設(shè)置成黑色 74 setColor(rightOf(sib), BLACK); 75 // sib節(jié)點(diǎn)設(shè)置成紅色 76 setColor(sib, RED); 77 // 左旋 78 rotateLeft(sib); 79 // sib移動到x父節(jié)點(diǎn)的左孩子 80 sib = leftOf(parentOf(x)); 81 } 82 // sib設(shè)置成和x的父節(jié)點(diǎn)一個(gè)顏色 83 setColor(sib, colorOf(parentOf(x))); 84 // x的父節(jié)點(diǎn)設(shè)置成黑色 85 setColor(parentOf(x), BLACK); 86 // sib的左孩子設(shè)置成黑色 87 setColor(leftOf(sib), BLACK); 88 // 右旋 rotateRight(parentOf(x)); 90 // 設(shè)置跳出循環(huán)的標(biāo)識 91 x = root; 92 } 93 } 94 } 95 // 將x設(shè)置為黑色 96 setColor(x, BLACK); 97 }
? ? ?光看調(diào)整的代碼，一大堆設(shè)置顏色，還有左旋和右旋，非常的抽象，下面是一個(gè)構(gòu)造紅黑樹的視屏，包括了著色和旋轉(zhuǎn)。
? ? ??
? ? ?clear()
1 public void clear() { 2 modCount++; 3 size = 0; 4 root = null; 5 }
? ? ?clear()方法很簡單，只是記錄結(jié)構(gòu)修改次數(shù)，將size修改為0，將root設(shè)置為null，這樣就沒法通過root訪問樹的其他節(jié)點(diǎn)，所以數(shù)的內(nèi)容會被GC回收。
? ? ?添加（修改）、獲取、刪除的原碼都已經(jīng)看了，下面看判斷是否包含的方法。
? ? ?containKey(Object key)
1 public boolean containsKey(Object key) { 2 return getEntry(key) != null; 3 }
? ? ?這個(gè)方法判斷獲取key對應(yīng)的節(jié)點(diǎn)是否為空，getEntry(Object key)方法已經(jīng)在上面介紹過了。
? ? ?contain(Object value)
1 public boolean containsValue(Object value) { 2 // 通過e = successor(e)實(shí)現(xiàn)對樹的遍歷 3 for (Entry<K,V> e = getFirstEntry(); e != null; e = successor(e)) 4 // 判斷節(jié)點(diǎn)值是否和value相等 5 if (valEquals(value, e.value)) 6 return true; 7 // 默認(rèn)返回false 8 return false; 9 }
? ? ?contain(Object value)涉及到了getFirstEntry()方法和successor(Entry<K,V> e)。getFirstEntry()是獲取第一個(gè)節(jié)點(diǎn)，successor(Entry<K,V> e)是獲取節(jié)點(diǎn)e的繼承者，在for循環(huán)中配合使用getFirstEntry()方法和successor(Entry<K,V> e)及e!=null是遍歷樹的一種方法。
? ? ?下面介紹getFirstEntry()方法。
? ? ?getFirstEntry()
1 final Entry<K,V> getFirstEntry() { 2 Entry<K,V> p = root; 3 if (p != null) 4 while (p.left != null) 5 p = p.left; 6 return p; 7 }
? ? ?從名字上看是獲取第一個(gè)節(jié)點(diǎn)，實(shí)際是獲取的整棵樹中“最左”的節(jié)點(diǎn)（第一個(gè)節(jié)點(diǎn)具體指哪一個(gè)節(jié)點(diǎn)和樹的遍歷次序有關(guān)，如果是先根遍歷，則第一個(gè)節(jié)點(diǎn)是根節(jié)點(diǎn)）。又因?yàn)榧t黑樹是排序的樹，所以“最左”的節(jié)點(diǎn)也是值最小的節(jié)點(diǎn)。
? ? ?上面是getFirstEntry()方法，下面介紹getLastEntry()方法。
? ? ?getLastEntry()
1 final Entry<K,V> getLastEntry() { 2 Entry<K,V> p = root; 3 if (p != null) 4 while (p.right != null) 5 p = p.right; 6 return p; 7 }
? ? ?getLastEntry()和getFirstEntry()對應(yīng)，獲取的是“最右”的節(jié)點(diǎn)。
? ? ?TreeMap中提供了獲取并移除最小和最大節(jié)點(diǎn)的兩個(gè)方法：pollFirstEntry()和pollLastEntry()。
? ? ?pollFirstEntry()
1 public Map.Entry<K,V> pollFirstEntry() { 2 Entry<K,V> p = getFirstEntry(); 3 Map.Entry<K,V> result = exportEntry(p); 4 if (p != null) 5 deleteEntry(p); 6 return result; 7 }
? ? ?pollLastEntry()
1 public Map.Entry<K,V> pollLastEntry() { 2 Entry<K,V> p = getLastEntry(); 3 Map.Entry<K,V> result = exportEntry(p); 4 if (p != null) 5 deleteEntry(p); 6 return result; 7 }
? ? ?pollFirstEntry()和pollLastEntry()分別通過getFirstEntry()和getLastEntry()獲取節(jié)點(diǎn)，exportEntry(TreeMap.Entry<K,V> e)應(yīng)該是保留這個(gè)對象用于在刪除這個(gè)節(jié)點(diǎn)后返回。具體實(shí)現(xiàn)看下面的代碼。
1 static <K,V> Map.Entry<K,V> exportEntry(TreeMap.Entry<K,V> e) { 2 return e == null? null : 3 new AbstractMap.SimpleImmutableEntry<K,V>(e); 4 }
? ? ?返回了一個(gè)SimpleImmutableEntry對象，調(diào)用的構(gòu)造方法如下：
1 public SimpleImmutableEntry(Entry<? extends K, ? extends V> entry) { 2 this.key = entry.getKey(); 3 this.value = entry.getValue(); 4 }
? ? ?可以看到返回的節(jié)點(diǎn)內(nèi)容只包含key和value。
? ? ?下面看其他具體的獲取鍵、值、鍵值對的方法。
1 public Map.Entry<K,V> ceilingEntry(K key) { 2 return exportEntry(getCeilingEntry(key)); 3 } 4 public K ceilingKey(K key) { 5 return keyOrNull(getCeilingEntry(key)); 6 }
? ? ?上面這兩個(gè)方法很簡單，只是對exportEntry和keyOrNull的調(diào)用。keyOrNull根據(jù)傳入的Entry是否為null，選擇方法null或Entry的key。
1 // 獲取最小的節(jié)點(diǎn)的key 2 public K firstKey() { 3 return key(getFirstEntry()); 4 } 5 // 獲取最大節(jié)點(diǎn)的key 6 public K lastKey() { 7 return key(getLastEntry()); 8 } 9 // 獲取最小的鍵值對 10 public Map.Entry<K,V> firstEntry() { 11 return exportEntry(getFirstEntry()); 12 } 13 // 獲取最大的鍵值對 14 public Map.Entry<K,V> lastEntry() { 15 return exportEntry(getLastEntry()); 16 }
? ? ?這幾個(gè)方法涉及到的內(nèi)容都在上面介紹過了，就不在說明了。
1 public Map.Entry<K,V> floorEntry(K key) { 2 return exportEntry(getFloorEntry(key)); 3 } 4 public K floorKey(K key) { 5 return keyOrNull(getFloorEntry(key)); 6 } 7 public Map.Entry<K,V> higherEntry(K key) { 8 return exportEntry(getHigherEntry(key)); 9 } 10 public K higherKey(K key) { 11 return keyOrNull(getHigherEntry(key)); 12 }
? ? ?這幾個(gè)獲取key的Entry的方法都是對getFloorEntry和getHigherEntry的處理。下面介紹這兩個(gè)方法。
? ? ?getFloorEntry(K key)
1 final Entry<K,V> getFloorEntry(K key) { 2 // 獲取根節(jié)點(diǎn) 3 Entry<K,V> p = root; 4 // 不是空樹，最樹進(jìn)行遍歷 5 while (p != null) { 6 int cmp = compare(key, p.key); 7 // key較大 8 if (cmp > 0) { 9 // 找到節(jié)點(diǎn)有右孩子，則繼續(xù)向右孩子遍歷 10 if (p.right != null) 11 p = p.right; 12 else// 沒有右孩子，那么p節(jié)點(diǎn)就是樹中比key值比傳入key值小且最接近傳入key的節(jié)點(diǎn)，就是要找的節(jié)點(diǎn) 13 return p; 14 } else if (cmp < 0) {// key值較小 15 // 有左孩子向左孩子遍歷 16 if (p.left != null) { 17 p = p.left; 18 } else {// 沒有左孩子，這個(gè)節(jié)點(diǎn)比key值大，返回內(nèi)容是向上尋找到的根節(jié)點(diǎn)或比傳入key值小的最后一個(gè)節(jié)點(diǎn)（這塊比較難理解，仔細(xì)模擬尋找節(jié)點(diǎn)的過程就會明白） 19 Entry<K,V> parent = p.parent; 20 Entry<K,V> ch = p; 21 while (parent != null && ch == parent.left) { 22 ch = parent; 23 parent = parent.parent; 24 } 25 return parent; 26 } 27 } else // key值相等 28 return p; 29 } 30 return null; 31 }
? ? ?getHigherEntry(K key)
1 final Entry<K,V> getHigherEntry(K key) { 2 Entry<K,V> p = root; 3 while (p != null) { 4 int cmp = compare(key, p.key); 5 if (cmp < 0) { 6 if (p.left != null) 7 p = p.left; 8 else 9 return p; 10 } else { 11 if (p.right != null) { 12 p = p.right; 13 } else { 14 Entry<K,V> parent = p.parent; 15 Entry<K,V> ch = p; 16 while (parent != null && ch == parent.right) { 17 ch = parent; 18 parent = parent.parent; 19 } 20 return parent; 21 } 22 } 23 } 24 return null; 25 }
? ? ?getFloorEntry和getHigherEntry方法遍歷和尋找節(jié)點(diǎn)的方法類似，區(qū)別在于getFloorEntry尋找的是小于等于，優(yōu)先返回小于的節(jié)點(diǎn)，而getHigherEntry尋找的是嚴(yán)格大于的節(jié)點(diǎn)，不包括等于的情況。
? ? ?以上內(nèi)容是TreeMap的基礎(chǔ)方法，TreeMap的內(nèi)部類及涉及到內(nèi)部類的方法等都將在中給出。
?
?