常見的資料結構有數組、連結清單,還有一種結構也很常見,那就是樹。前面介紹的集合類有基于數組的ArrayList,有基于連結清單的LinkedList,還有連結清單和數組結合的HashMap,今天介紹基于樹的TreeMap。
TreeMap基于紅黑樹(
點選檢視樹、紅黑樹相關内容)實作。檢視“鍵”或“鍵值對”時,它們會被排序(次序由Comparable或Comparator決定)。TreeMap的特點在于,所得到的結果是經過排序的。TreeMap是唯一的帶有subMap()方法的Map,它可以傳回一個子樹。
在介紹TreeMap前先介紹Comparable和Comparator接口。
Comparable接口:
1 public interface Comparable<T> {
2 public int compareTo(T o);
3 }
Comparable接口支援泛型,隻有一個方法,該方法傳回負數、零、正數分别表示目前對象“小于”、“等于”、“大于”傳入對象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兩個對象,o1“大于”o2,傳回正數,相等傳回零,“小于”傳回負數。
equals(Object obj)傳回true的唯一情況是obj也是一個比較器(Comparator)并且比較結果和此比較器的結果的大小次序是一緻的。即comp1.equals(comp2)意味着sgn(comp1.compare(o1, * o2))==sgn(comp2.compare(o1, o2))。
補充:符号sgn(expression)表示數學上的signum函數,該函數根據expression的值是負數、零或正數,分别傳回-1、0或1。
小結一下,實作Comparable結構的類可以和其他對象進行比較,即實作Comparable可以進行比較的類。而實作Comparator接口的類是比較器,用于比較兩個對象的大小。
下面正式分析TreeMap的源碼。
既然TreeMap底層使用的是樹結構,那麼必然有表示節點的對象。下面先看TreeMap中表示節點的内部類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 // 父節點
11 Entry<K,V> parent;
12 // 紅黑樹的節點表示顔色的屬性
13 boolean color = BLACK;
14 /**
15 * 根據給定的鍵、值、父節點構造一個節點,顔色為預設的黑色
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 // 擷取節點的key
23 public K getKey() {
24 return key;
25 }
26 // 擷取節點的value
27 public V getValue() {
28 return value;
29 }
30 /**
31 * 修改并傳回目前節點的value
32 */
33 public V setValue(V value) {
34 V oldValue = this.value;
35 this.value = value;
36 return oldValue;
37 }
38 // 判斷節點相等的方法(兩個節點為同一類型且key值和value值都相等時兩個節點相等)
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 // 節點的哈希值計算方法
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 }
54 }
上面的Entry類比較簡單,實作了樹節點的必要内容,提供了hashCode方法等。下面看TreeMap類的定義。
1 public class TreeMap<K,V>
2 extends AbstractMap<K,V>
3 implements NavigableMap<K,V>, Cloneable, java.io.Serializable
上面隻有一個接口需要說明,那就是NavigableMap接口。
NavigableMap接口擴充的SortedMap,具有了針對給定搜尋目标傳回最接近比對項的導航方法。方法lowerEntry、floorEntry、ceilingEntry和higherEntry分别傳回與小于、小于等于、大于等于、大于給定鍵的鍵關聯的Map.Entry對象,如果不存在這樣的鍵,則傳回null。類似地,方法lowerKey、floorKey、ceilingKey和higherKey隻傳回關聯的鍵。所有這些方法是為查找條目而不是周遊條目而設計的(後面會逐個介紹這些方法)。
下面是TreeMap的屬性:
1 // 用于保持順序的比較器,如果為空的話使用自然順保持Key的順序
2 private final Comparator<? super K> comparator;
3 // 根節點
4 private transient Entry<K,V> root = null;
5 // 樹中的節點數量
6 private transient int size = 0;
7 // 多次在集合類中提到了,用于舉了結構行的改變次數
8 private transient int modCount = 0;
注釋中已經給出了屬性的解釋,下面看TreeMap的構造方法。
1 // 構造方法一,預設的構造方法,comparator為空,即采用自然順序維持TreeMap中節點的順序
2 public TreeMap() {
3 comparator = null;
4 }
5 // 構造方法二,提供指定的比較器
6 public TreeMap(Comparator<? super K> comparator) {
7 this.comparator = comparator;
8 }
9 // 構造方法三,采用自然序維持TreeMap中節點的順序,同時将傳入的Map中的内容添加到TreeMap中
10 public TreeMap(Map<? extends K, ? extends V> m) {
11 comparator = null;
12 putAll(m);
13 }
14 /**
15 *構造方法四,接收SortedMap參數,根據SortedMap的比較器維持TreeMap中的節點順序,* 同時通過buildFromSorted(int size, Iterator it, java.io.ObjectInputStream str, V defaultVal)方* 法将SortedMap中的内容添加到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提供了四個構造方法,已經在注釋中給出說明。構造方法中涉及到的方法在下文中會有介紹。
下面從put/get方法開始,逐個分析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 //如果根節點為null,将傳入的鍵值對構造成根節點(根節點沒有父節點,是以傳入的父節點為null)
5 root = new Entry<K,V>(key, value, null);
6 size = 1;
7 modCount++;
8 return null;
9 }
10 // 記錄比較結果
11 int cmp;
12 Entry<K,V> parent;
13 // 分割比較器和可比較接口的處理
14 Comparator<? super K> cpr = comparator;
15 // 有比較器的處理
16 if (cpr != null) {
17 // do while實作在root為根節點移動尋找傳入鍵值對需要插入的位置
18 do {
19 // 記錄将要被摻入新的鍵值對将要節點(即新節點的父節點)
20 parent = t;
21 // 使用比較器比較父節點和插入鍵值對的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節點的value(put方法結束)
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相同的節點才會有下面的操作
53 // 根據傳入的鍵值對和找到的“父節點”建立新節點
54 Entry<K,V> e = new Entry<K,V>(key, value, parent);
55 // 根據最後一次的判斷結果确認新節點是“父節點”的左孩子還是又孩子
56 if (cmp < 0)
57 parent.left = e;
58 else
59 parent.right = e;
60 // 對加入新節點的樹進行調整
61 fixAfterInsertion(e);
62 // 記錄size和modCount
63 size++;
64 modCount++;
65 // 因為是插入新節點,是以傳回的是null
66 return null;
67 }
首先一點通性是TreeMap的put方法和其他Map的put方法一樣,向Map中加入鍵值對,若原先“鍵(key)”已經存在則替換“值(value)”,并傳回原先的值。
在put(K key,V value)方法的末尾調用了fixAfterInsertion(Entry<K,V> x)方法,這個方法負責在插入節點後調整樹結構和着色,以滿足
紅黑樹的要求。
- 每一個節點或者着成紅色,或者着成黑色。
- 根是黑色的。
- 如果一個節點是紅色的,那麼它的子節點必須是黑色的。
- 一個節點到一個null引用的每一條路徑必須包含相同數量的黑色節點。
在看fixAfterInsertion(Entry<K,V> x)方法前先看一個紅黑樹的内容:紅黑樹不是嚴格的平衡二叉樹,它并不嚴格的保證左右子樹的高度差不超過1,但紅黑樹高度依然是平均log(n),且最壞情況高度不會超過2log(n),是以它算是平衡樹。
下面看具體實作代碼。
fixAfterInsertion(Entry<K,V> x)
1 private void fixAfterInsertion(Entry<K,V> x) {
2 // 插入節點預設為紅色
3 x.color = RED;
4 // 循環條件是x不為空、不是根節點、父節點的顔色是紅色(如果父節點不是紅色,則沒有連續的紅色節點,不再調整)
5 while (x != null && x != root && x.parent.color == RED) {
6 // x節點的父節點p(記作p)是其父節點pp(p的父節點,記作pp)的左孩子(pp的左孩子)
7 if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
8 // 擷取pp節點的右孩子r
9 Entry<K,V> y = rightOf(parentOf(parentOf(x)));
10 // pp右孩子的顔色是紅色(colorOf(Entry e)方法在e為空時傳回BLACK),不需要進行旋轉操作(因為紅黑樹不是嚴格的平衡二叉樹)
11 if (colorOf(y) == RED) {
12 // 将父節點設定為黑色
13 setColor(parentOf(x), BLACK);
14 // y節點,即r設定成黑色
15 setColor(y, BLACK);
16 // pp節點設定成紅色
17 setColor(parentOf(parentOf(x)), RED);
18 // x“移動”到pp節點
19 x = parentOf(parentOf(x));
20 } else {//父親的兄弟是黑色的,這時需要進行旋轉操作,根據是“内部”還是“外部”的情況決定是雙旋轉還是單旋轉
21 // x節點是父節點的右孩子(因為上面已近确認p是pp的左孩子,是以這是一個“内部,左-右”插入的情況,需要進行雙旋轉處理)
22 if (x == rightOf(parentOf(x))) {
23 // x移動到它的父節點
24 x = parentOf(x);
25 // 左旋操作
26 rotateLeft(x);
27 }
28 // x的父節點設定成黑色
29 setColor(parentOf(x), BLACK);
30 // x的父節點的父節點設定成紅色
31 setColor(parentOf(parentOf(x)), RED);
32 // 右旋操作
33 rotateRight(parentOf(parentOf(x)));
34 }
35 } else {
36 // 擷取x的父節點(記作p)的父節點(記作pp)的左孩子
37 Entry<K,V> y = leftOf(parentOf(parentOf(x)));
38 // y節點是紅色的
39 if (colorOf(y) == RED) {
40 // x的父節點,即p節點,設定成黑色
41 setColor(parentOf(x), BLACK);
42 // y節點設定成黑色
43 setColor(y, BLACK);
44 // pp節點設定成紅色
45 setColor(parentOf(parentOf(x)), RED);
46 // x移動到pp節點
47 x = parentOf(parentOf(x));
48 } else {
49 // x是父節點的左孩子(因為上面已近确認p是pp的右孩子,是以這是一個“内部,右-左”插入的情況,需要進行雙旋轉處理),
50 if (x == leftOf(parentOf(x))) {
51 // x移動到父節點
52 x = parentOf(x);
53 // 右旋操作
54 rotateRight(x);
55 }
56 // x的父節點設定成黑色
57 setColor(parentOf(x), BLACK);
58 // x的父節點的父節點設定成紅色
59 setColor(parentOf(parentOf(x)), RED);
60 // 左旋操作
61 rotateLeft(parentOf(parentOf(x)));
62 }
63 }
64 }
65 // 根節點為黑色
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 }
![](https://img.laitimes.com/img/9ZDMuAjOiMmIsIjOiQnIsIyZlBnauMmY2ImZiJWO0IGMzADZlRWNhVTMkNjY5MWN4Q2MjVjZfdWbp9CXt92Yu4GZjlGbh5SZslmZxl3Lc9CX6MHc0RHaiojIsJye.jpeg)
看完put操作,下面來看get操作相關的内容。
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擷取對應的value,它通過調用getEntry(Object key)擷取節點,若節點為null則傳回null,否則傳回節點的value值。下面是getEntry(Object key)的内容,來看它是怎麼尋找節點的。
getEntry(Object key)
1 final Entry<K,V> getEntry(Object key) {
2 // 如果有比較器,傳回getEntryUsingComparator(Object key)的結果
3 if (comparator != null)
4 return getEntryUsingComparator(key);
5 // 查找的key為null,抛出NullPointerException
6 if (key == null)
7 throw new NullPointerException();
8 // 如果沒有比較器,而是實作了可比較接口
9 Comparable<? super K> k = (Comparable<? super K>) key;
10 // 擷取根節點
11 Entry<K,V> p = root;
12 // 對樹進行周遊查找節點
13 while (p != null) {
14 // 把key和目前節點的key進行比較
15 int cmp = k.compareTo(p.key);
16 // key小于目前節點的key
17 if (cmp < 0)
18 // p “移動”到左節點上
19 p = p.left;
20 // key大于目前節點的key
21 else if (cmp > 0)
22 // p “移動”到右節點上
23 p = p.right;
24 // key值相等則目前節點就是要找的節點
25 else
26 // 傳回找到的節點
27 return p;
28 }
29 // 沒找到則傳回null
30 return null;
31 }
上面主要是處理實作了可比較接口的情況,而有比較器的情況在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 // 其實在調用此方法的get(Object key)中已經對比較器為null的情況進行判斷,這裡是防禦性的判斷
6 if (cpr != null) {
7 // 擷取根節點
8 Entry<K,V> p = root;
9 // 周遊樹
10 while (p != null) {
11 // 擷取key和目前節點的key的比較結果
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“移動”到右節點
20 p = p.right;
21 // key值相等
22 else
23 // 傳回找到的節點
24 return p;
25 }
26 }
27 // 沒找到key值對應的節點,傳回null
28 return null;
29 }
看完添加(put)和擷取(get),下面來看删除(remove、clear)。
remove(Object key)
1 public V remove(Object key) {
2 // 通過getEntry(Object key)擷取節點 getEntry(Object key)方法已經在上面介紹過了
3 Entry<K,V> p = getEntry(key);
4 // 指定key的節點不存在,傳回null
5 if (p == null)
6 return null;
7 // 擷取節點的value
8 V oldValue = p.value;
9 // 删除節點
10 deleteEntry(p);
11 // 傳回節點的内容
12 return oldValue;
13 }
真正實作删除節點的内容在deleteEntry(Entry e)中,涉及到樹結構的調整等。remove(Object key)隻是擷取要删除的節點并傳回被删除節點的value。下面來看deleteEntry(Entry e)的内容。
deleteEntry(Entry e)
1 private void deleteEntry(Entry<K,V> p) {
2 // 記錄樹結構的修改次數
3 modCount++;
4 // 記錄樹中節點的個數
5 size--;
6
7 // p有左右兩個孩子的情況 标記①
8 if (p.left != null && p.right != null) {
9 // 擷取繼承者節點(有兩個孩子的情況下,繼承者肯定是右孩子或右孩子的最左子孫)
10 Entry<K,V> s = successor (p);
11 // 使用繼承者s替換要被删除的節點p,将繼承者的key和value複制到p節點,之後将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 // 開始修複被移除節點處的樹結構
19 // 如果p有左孩子,取左孩子,否則取右孩子 标記②
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節點沒有父節點,即p節點是根節點
25 if (p.parent == null)
26 // 将根節點替換為replacement節點
27 root = replacement;
28 // p是其父節點的左孩子
29 else if (p == p.parent.left)
30 // 将p的父節點的left引用指向replacement
31 // 這步操作實作了删除p的父節點到p節點的引用
32 p.parent.left = replacement;
33 else
34 // 如果p是其父節點的右孩子,将父節點的right引用指向replacement
35 p.parent.right = replacement;
36 // 解除p節點到其左右孩子和父節點的引用
37 p.left = p.right = p.parent = null;
38 if (p.color == BLACK)
39 // 在删除節點後修複紅黑樹的顔色配置設定
40 fixAfterDeletion(replacement);
41 } else if (p.parent == null) {
42 /* 進入這塊代碼則說明p節點就是根節點(這塊比較難了解,如果标記①處p有左右孩子,則找到的繼承節點s是p的一個祖先節點或右孩子或右孩子的最左子孫節點,他們要麼有孩子節點,要麼有父節點,是以如果進入這塊代碼,則說明标記①除的p節點沒有左右兩個孩子。沒有左右孩子,則有沒有孩子、有一個右孩子、有一個左孩子三種情況,三種情況中隻有沒有孩子的情況會使标記②的if判斷不通過,是以p節點隻能是沒有孩子,加上這裡的判斷,p沒有父節點,是以p是一個獨立節點,也是樹種的唯一節點……有點難了解,隻能解釋到這裡了,讀者隻能結合注釋慢慢體會了),是以将根節點設定為null即實作了對該節點的删除 */
43 root = null;
44 } else { /* 标記②的if判斷沒有通過說明被删除節點沒有孩子,或它有兩個孩子但它的繼承者沒有孩子。如果是被删除節點沒有孩子,說明p是個葉子節點,則不需要找繼承者,直接删除該節點。如果是有兩個孩子,那麼繼承者肯定是右孩子或右孩子的最左子孫 */
45 if (p.color == BLACK)
46 // 調整樹結構
47 fixAfterDeletion(p);
48 // 這個判斷也一定會通過,因為p.parent如果不是null則在上面的else if塊中已經被處理
49 if (p.parent != null) {
50 // p是一個左孩子
51 if (p == p.parent.left)
52 // 删除父節點對p的引用
53 p.parent.left = null;
54 else if (p == p.parent.right)// p是一個右孩子
55 // 删除父節點對p的引用
56 p.parent.right = null;
57 // 删除p節點對父節點的引用
58 p.parent = null;
59 }
60 }
61 }
deleteEntry(Entry e)方法中主要有兩個方法調用需要分析:successor(Entry<K,V> t)和fixAfterDeletion(Entry<K,V> x)。
successor(Entry<K,V> t)傳回指定節點的繼承者。分三種情況處理,第一。t節點是個空節點:傳回null;第二,t有右孩子:找到t的右孩子中的最左子孫節點,如果右孩子沒有左孩子則傳回右節點,否則傳回找到的最左子孫節點;第三,t沒有右孩子:沿着向上(向跟節點方向)找到第一個自身是一個左孩子的節點或根節點,傳回找到的節點。下面是具體代碼分析的注釋。
1 static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) {
2 // 如果t本身是一個空節點,傳回null
3 if (t == null)
4 return null;
5 // 如果t有右孩子,找到右孩子的最左子孫節點
6 else if (t.right != null) {
7 Entry<K,V> p = t.right;
8 // 擷取p節點最左的子孫節點,如果存在的話
9 while (p.left != null)
10 p = p.left;
11 // 傳回找到的繼承節點
12 return p;
13 } else {//t不為null且沒有右孩子
14 Entry<K,V> p = t.parent;
15 Entry<K,V> ch = t;
16 // // 沿着右孩子向上查找繼承者,直到根節點或找到節點ch是其父節點的左孩子的節點
17 while (p != null && ch == p.right) {
18 ch = p;
19 p = p.parent;
20 }
21 return p;
22 }
23 }
與添加節點之後的修複類似的是,TreeMap 删除節點之後也需要進行類似的修複操作,通過這種修複來保證該排序二叉樹依然滿足紅黑樹特征。大家可以參考插入節點之後的修複來分析删除之後的修複。TreeMap 在删除之後的修複操作由 fixAfterDeletion(Entry<K,V> x) 方法提供,該方法源代碼如下:
1 private void fixAfterDeletion(Entry<K,V> x) {
2 // 循環處理,條件為x不是root節點且是黑色的(因為紅色不會對紅黑樹的性質造成破壞,是以不需要調整)
3 while (x != root && colorOf(x) == BLACK) {
4 // x是一個左孩子
5 if (x == leftOf(parentOf(x))) {
6 // 擷取x的兄弟節點sib
7 Entry<K,V> sib = rightOf(parentOf(x));
8 // sib是紅色的
9 if (colorOf(sib) == RED) {
10 // 将sib設定為黑色
11 setColor(sib, BLACK);
12 // 将父節點設定成紅色
13 setColor(parentOf(x), RED);
14 // 左旋父節點
15 rotateLeft(parentOf(x));
16 // sib移動到旋轉後x的父節點p的右孩子(參見左旋示意圖,擷取的節點是旋轉前p的右孩子r的左孩子rl)
17 sib = rightOf(parentOf(x));
18 }
19 // sib的兩個孩子的顔色都是黑色(null傳回黑色)
20 if (colorOf(leftOf(sib)) == BLACK &&
21 colorOf(rightOf(sib)) == BLACK) {
22 // 将sib設定成紅色
23 setColor(sib, RED);
24 // x移動到x的父節點
25 x = parentOf(x);
26 } else {// sib的左右孩子都是黑色的不成立
27 // sib的右孩子是黑色的
28 if (colorOf(rightOf(sib)) == BLACK) {
29 // 将sib的左孩子設定成黑色
30 setColor(leftOf(sib), BLACK);
31 // sib節點設定成紅色
32 setColor(sib, RED);
33 // 右旋操作
34 rotateRight(sib);
35 // sib移動到旋轉後x父節點的右孩子
36 sib = rightOf(parentOf(x));
37 }
38 // sib設定成和x的父節點一樣的顔色
39 setColor(sib, colorOf(parentOf(x)));
40 // x的父節點設定成黑色
41 setColor(parentOf(x), BLACK);
42 // sib的右孩子設定成黑色
43 setColor(rightOf(sib), BLACK);
44 // 左旋操作
45 rotateLeft(parentOf(x));
46 // 設定調整完的條件:x = root跳出循環
47 x = root;
48 }
49 } else { // x是一個右孩子
50 // 擷取x的兄弟節點
51 Entry<K,V> sib = leftOf(parentOf(x));
52 // 如果sib是紅色的
53 if (colorOf(sib) == RED) {
54 // 将sib設定為黑色
55 setColor(sib, BLACK);
56 // 将x的父節點設定成紅色
57 setColor(parentOf(x), RED);
58 // 右旋
59 rotateRight(parentOf(x));
60 // sib移動到旋轉後x父節點的左孩子
61 sib = leftOf(parentOf(x));
62 }
63 // sib的兩個孩子的顔色都是黑色(null傳回黑色)
64 if (colorOf(rightOf(sib)) == BLACK &&
65 colorOf(leftOf(sib)) == BLACK) {
66 // sib設定為紅色
67 setColor(sib, RED);
68 // x移動到x的父節點
69 x = parentOf(x);
70 } else { // sib的兩個孩子的顔色都是黑色(null傳回黑色)不成立
71 // sib的左孩子是黑色的,或者沒有左孩子
72 if (colorOf(leftOf(sib)) == BLACK) {
73 // 将sib的右孩子設定成黑色
74 setColor(rightOf(sib), BLACK);
75 // sib節點設定成紅色
76 setColor(sib, RED);
77 // 左旋
78 rotateLeft(sib);
79 // sib移動到x父節點的左孩子
80 sib = leftOf(parentOf(x));
81 }
82 // sib設定成和x的父節點一個顔色
83 setColor(sib, colorOf(parentOf(x)));
84 // x的父節點設定成黑色
85 setColor(parentOf(x), BLACK);
86 // sib的左孩子設定成黑色
87 setColor(leftOf(sib), BLACK);
88 // 右旋
89 rotateRight(parentOf(x));
90 // 設定跳出循環的辨別
91 x = root;
92 }
93 }
94 }
95 // 将x設定為黑色
96 setColor(x, BLACK);
97 }
光看調整的代碼,一大堆設定顔色,還有左旋和右旋,非常的抽象,下面是一個構造紅黑樹的視屏,包括了着色和旋轉。
http://v.youku.com/v_show/id_XMjI3NjM0MTgw.htmlclear()
1 public void clear() {
2 modCount++;
3 size = 0;
4 root = null;
5 }
clear()方法很簡單,隻是記錄結構修改次數,将size修改為0,将root設定為null,這樣就沒法通過root通路樹的其他節點,是以數的内容會被GC回收。
添加(修改)、擷取、删除的原碼都已經看了,下面看判斷是否包含的方法。
containKey(Object key)
1 public boolean containsKey(Object key) {
2 return getEntry(key) != null;
3 }
這個方法判斷擷取key對應的節點是否為空,getEntry(Object key)方法已經在上面介紹過了。
contain(Object value)
1 public boolean containsValue(Object value) {
2 // 通過e = successor(e)實作對樹的周遊
3 for (Entry<K,V> e = getFirstEntry(); e != null; e = successor(e))
4 // 判斷節點值是否和value相等
5 if (valEquals(value, e.value))
6 return true;
7 // 預設傳回false
8 return false;
9 }
contain(Object value)涉及到了getFirstEntry()方法和successor(Entry<K,V> e)。getFirstEntry()是擷取第一個節點,successor(Entry<K,V> e)是擷取節點e的繼承者,在for循環中配合使用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 }
從名字上看是擷取第一個節點,實際是擷取的整棵樹中“最左”的節點(第一個節點具體指哪一個節點和樹的周遊次序有關,如果是先根周遊,則第一個節點是根節點)。又因為紅黑樹是排序的樹,是以“最左”的節點也是值最小的節點。
上面是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()對應,擷取的是“最右”的節點。
TreeMap中提供了擷取并移除最小和最大節點的兩個方法: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()擷取節點,exportEntry(TreeMap.Entry<K,V> e)應該是保留這個對象用于在删除這個節點後傳回。具體實作看下面的代碼。
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 }
傳回了一個SimpleImmutableEntry對象,調用的構造方法如下:
1 public SimpleImmutableEntry(Entry<? extends K, ? extends V> entry) {
2 this.key = entry.getKey();
3 this.value = entry.getValue();
4 }
可以看到傳回的節點内容隻包含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 }
上面這兩個方法很簡單,隻是對exportEntry和keyOrNull的調用。keyOrNull根據傳入的Entry是否為null,選擇方法null或Entry的key。
1 // 擷取最小的節點的key
2 public K firstKey() {
3 return key(getFirstEntry());
4 }
5 // 擷取最大節點的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 }
這幾個方法涉及到的内容都在上面介紹過了,就不在說明了。
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 }
這幾個擷取key的Entry的方法都是對getFloorEntry和getHigherEntry的處理。下面介紹這兩個方法。
getFloorEntry(K key)
1 final Entry<K,V> getFloorEntry(K key) {
2 // 擷取根節點
3 Entry<K,V> p = root;
4 // 不是空樹,最樹進行周遊
5 while (p != null) {
6 int cmp = compare(key, p.key);
7 // key較大
8 if (cmp > 0) {
9 // 找到節點有右孩子,則繼續向右孩子周遊
10 if (p.right != null)
11 p = p.right;
12 else// 沒有右孩子,那麼p節點就是樹中比key值比傳入key值小且最接近傳入key的節點,就是要找的節點
13 return p;
14 } else if (cmp < 0) {// key值較小
15 // 有左孩子向左孩子周遊
16 if (p.left != null) {
17 p = p.left;
18 } else {// 沒有左孩子,這個節點比key值大,傳回内容是向上尋找到的根節點或比傳入key值小的最後一個節點(這塊比較難了解,仔細模拟尋找節點的過程就會明白)
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方法周遊和尋找節點的方法類似,差別在于getFloorEntry尋找的是小于等于,優先傳回小于的節點,而getHigherEntry尋找的是嚴格大于的節點,不包括等于的情況。
以上内容是TreeMap的基礎方法,TreeMap的内部類及涉及到内部類的方法等都将在
《TreeMap源碼分析——深入分析》中給出。
如果本文對您有幫助,點一下右下角的“推薦”