溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務(wù)條款》
您好，登錄后才能下訂單哦！
TreeMap 的實現(xiàn)就是紅黑樹數(shù)據(jù)結(jié)構(gòu)，也就說是一棵自平衡的排序二叉樹，這樣就可以保證當(dāng)需要快速檢索指定節(jié)點。
TreeSet 和 TreeMap 的關(guān)系
為了讓大家了解 TreeMap 和 TreeSet 之間的關(guān)系，下面先看 TreeSet 類的部分源代碼：
public class TreeSet<E> extends AbstractSet<E>
implements NavigableSet<E>, Cloneable, java.io.Serializable
{
// 使用 NavigableMap 的 key 來保存 Set 集合的元素
private transient NavigableMap<E,Object> m;
// 使用一個 PRESENT 作為 Map 集合的所有 value。
private static final Object PRESENT = new Object();
// 包訪問權(quán)限的構(gòu)造器，以指定的 NavigableMap 對象創(chuàng)建 Set 集合
TreeSet(NavigableMap<E,Object> m)
{
this.m = m;
}
public TreeSet() // ①
{
// 以自然排序方式創(chuàng)建一個新的 TreeMap，
// 根據(jù)該 TreeSet 創(chuàng)建一個 TreeSet，
// 使用該 TreeMap 的 key 來保存 Set 集合的元素
this(new TreeMap<E,Object>());
}
public TreeSet(Comparator<? super E> comparator) // ②
{
// 以定制排序方式創(chuàng)建一個新的 TreeMap，
// 根據(jù)該 TreeSet 創(chuàng)建一個 TreeSet，
// 使用該 TreeMap 的 key 來保存 Set 集合的元素
this(new TreeMap<E,Object>(comparator));
}
public TreeSet(Collection<? extends E> c)
{
// 調(diào)用①號構(gòu)造器創(chuàng)建一個 TreeSet，底層以 TreeMap 保存集合元素
this();
// 向 TreeSet 中添加 Collection 集合 c 里的所有元素
addAll(c);
}
public TreeSet(SortedSet<E> s)
{
// 調(diào)用②號構(gòu)造器創(chuàng)建一個 TreeSet，底層以 TreeMap 保存集合元素
this(s.comparator());
// 向 TreeSet 中添加 SortedSet 集合 s 里的所有元素
addAll(s);
}
//TreeSet 的其他方法都只是直接調(diào)用 TreeMap 的方法來提供實現(xiàn)
...
public boolean addAll(Collection<? extends E> c)
{
if (m.size() == 0 && c.size() > 0 &&
c instanceof SortedSet &&
m instanceof TreeMap)
{
// 把 c 集合強(qiáng)制轉(zhuǎn)換為 SortedSet 集合
SortedSet<? extends E> set = (SortedSet<? extends E>) c;
// 把 m 集合強(qiáng)制轉(zhuǎn)換為 TreeMap 集合
TreeMap<E,Object> map = (TreeMap<E, Object>) m;
Comparator<? super E> cc = (Comparator<? super E>) set.comparator();
Comparator<? super E> mc = map.comparator();
// 如果 cc 和 mc 兩個 Comparator 相等
if (cc == mc || (cc != null && cc.equals(mc)))
{
// 把 Collection 中所有元素添加成 TreeMap 集合的 key
map.addAllForTreeSet(set, PRESENT);
return true;
}
}
// 直接調(diào)用父類的 addAll() 方法來實現(xiàn)
return super.addAll(c);
}
...
}
從上面代碼可以看出，TreeSet 的 ① 號、② 號構(gòu)造器的都是新建一個 TreeMap 作為實際存儲 Set 元素的容器，而另外 2 個構(gòu)造器則分別依賴于 ① 號和 ② 號構(gòu)造器，由此可見，TreeSet 底層實際使用的存儲容器就是 TreeMap。
與 HashSet 完全類似的是，TreeSet 里絕大部分方法都是直接調(diào)用 TreeMap 的方法來實現(xiàn)的，這一點讀者可以自行參閱 TreeSet 的源代碼，此處就不再給出了。
對于 TreeMap 而言，它采用一種被稱為“紅黑樹”的排序二叉樹來保存 Map 中每個 Entry —— 每個 Entry 都被當(dāng)成“紅黑樹”的一個節(jié)點對待。例如對于如下程序而言：
public class TreeMapTest
{
public static void main(String[] args)
{
TreeMap<String , Double> map =
new TreeMap<String , Double>();
map.put("ccc" , 89.0);
map.put("aaa" , 80.0);
map.put("zzz" , 80.0);
map.put("bbb" , 89.0);
System.out.println(map);
}
}
當(dāng)程序執(zhí)行 map.put("ccc" , 89.0); 時，系統(tǒng)將直接把 "ccc"-89.0 這個 Entry 放入 Map 中，這個 Entry 就是該“紅黑樹”的根節(jié)點。接著程序執(zhí)行 map.put("aaa" , 80.0); 時，程序會將 "aaa"-80.0 作為新節(jié)點添加到已有的紅黑樹中。
以后每向 TreeMap 中放入一個 key-value 對，系統(tǒng)都需要將該 Entry 當(dāng)成一個新節(jié)點，添加成已有紅黑樹中，通過這種方式就可保證 TreeMap 中所有 key 總是由小到大地排列。例如我們輸出上面程序，將看到如下結(jié)果（所有 key 由小到大地排列）：
{aaa=80.0, bbb=89.0, ccc=89.0, zzz=80.0}
TreeMap 的添加節(jié)點
紅黑樹
紅黑樹是一種自平衡排序二叉樹，樹中每個節(jié)點的值，都大于或等于在它的左子樹中的所有節(jié)點的值，并且小于或等于在它的右子樹中的所有節(jié)點的值，這確保紅黑樹運行時可以快速地在樹中查找和定位的所需節(jié)點。
對于 TreeMap 而言，由于它底層采用一棵“紅黑樹”來保存集合中的 Entry，這意味這 TreeMap 添加元素、取出元素的性能都比 HashMap 低：當(dāng) TreeMap 添加元素時，需要通過循環(huán)找到新增 Entry 的插入位置，因此比較耗性能；當(dāng)從 TreeMap 中取出元素時，需要通過循環(huán)才能找到合適的 Entry，也比較耗性能。但 TreeMap、TreeSet 比 HashMap、HashSet 的優(yōu)勢在于：TreeMap 中的所有 Entry 總是按 key 根據(jù)指定排序規(guī)則保持有序狀態(tài)，TreeSet 中所有元素總是根據(jù)指定排序規(guī)則保持有序狀態(tài)。
為了理解 TreeMap 的底層實現(xiàn)，必須先介紹排序二叉樹和紅黑樹這兩種數(shù)據(jù)結(jié)構(gòu)。其中紅黑樹又是一種特殊的排序二叉樹。
排序二叉樹是一種特殊結(jié)構(gòu)的二叉樹，可以非常方便地對樹中所有節(jié)點進(jìn)行排序和檢索。
排序二叉樹要么是一棵空二叉樹，要么是具有下列性質(zhì)的二叉樹：
圖 1 顯示了一棵排序二叉樹：
圖 1. 排序二叉樹
對排序二叉樹，若按中序遍歷就可以得到由小到大的有序序列。如圖 1 所示二叉樹，中序遍歷得：
{2，3，4，8，9，9，10，13，15，18}
創(chuàng)建排序二叉樹的步驟，也就是不斷地向排序二叉樹添加節(jié)點的過程，向排序二叉樹添加節(jié)點的步驟如下：
掌握上面理論之后，下面我們來分析 TreeMap 添加節(jié)點（TreeMap 中使用 Entry 內(nèi)部類代表節(jié)點）的實現(xiàn)，TreeMap 集合的 put(K key, V value) 方法實現(xiàn)了將 Entry 放入排序二叉樹中，下面是該方法的源代碼：
public V put(K key, V value)
{
// 先以 t 保存鏈表的 root 節(jié)點
Entry<K,V> t = root;
// 如果 t==null，表明是一個空鏈表，即該 TreeMap 里沒有任何 Entry
if (t == null)
{
// 將新的 key-value 創(chuàng)建一個 Entry，并將該 Entry 作為 root
root = new Entry<K,V>(key, value, null);
// 設(shè)置該 Map 集合的 size 為 1，代表包含一個 Entry
size = 1;
// 記錄修改次數(shù)為 1
modCount++;
return null;
}
int cmp;
Entry<K,V> parent;
Comparator<? super K> cpr = comparator;
// 如果比較器 cpr 不為 null，即表明采用定制排序
if (cpr != null)
{
do {
// 使用 parent 上次循環(huán)后的 t 所引用的 Entry
parent = t;
// 拿新插入 key 和 t 的 key 進(jìn)行比較
cmp = cpr.compare(key, t.key);
// 如果新插入的 key 小于 t 的 key，t 等于 t 的左邊節(jié)點
if (cmp < 0)
t = t.left;
// 如果新插入的 key 大于 t 的 key，t 等于 t 的右邊節(jié)點
else if (cmp > 0)
t = t.right;
// 如果兩個 key 相等，新的 value 覆蓋原有的 value，
// 并返回原有的 value
else
return t.setValue(value);
} while (t != null);
}
else
{
if (key == null)
throw new NullPointerException();
Comparable<? super K> k = (Comparable<? super K>) key;
do {
// 使用 parent 上次循環(huán)后的 t 所引用的 Entry
parent = t;
// 拿新插入 key 和 t 的 key 進(jìn)行比較
cmp = k.compareTo(t.key);
// 如果新插入的 key 小于 t 的 key，t 等于 t 的左邊節(jié)點
if (cmp < 0)
t = t.left;
// 如果新插入的 key 大于 t 的 key，t 等于 t 的右邊節(jié)點
else if (cmp > 0)
t = t.right;
// 如果兩個 key 相等，新的 value 覆蓋原有的 value，
// 并返回原有的 value
else
return t.setValue(value);
} while (t != null);
}
// 將新插入的節(jié)點作為 parent 節(jié)點的子節(jié)點
Entry<K,V> e = new Entry<K,V>(key, value, parent);
// 如果新插入 key 小于 parent 的 key，則 e 作為 parent 的左子節(jié)點
if (cmp < 0)
parent.left = e;
// 如果新插入 key 小于 parent 的 key，則 e 作為 parent 的右子節(jié)點
else
parent.right = e;
// 修復(fù)紅黑樹
fixAfterInsertion(e); // ①
size++;
modCount++;
return null;
}
上面程序中粗體字代碼就是實現(xiàn)“排序二叉樹”的關(guān)鍵算法，每當(dāng)程序希望添加新節(jié)點時：系統(tǒng)總是從樹的根節(jié)點開始比較 —— 即將根節(jié)點當(dāng)成當(dāng)前節(jié)點，如果新增節(jié)點大于當(dāng)前節(jié)點、并且當(dāng)前節(jié)點的右子節(jié)點存在，則以右子節(jié)點作為當(dāng)前節(jié)點；如果新增節(jié)點小于當(dāng)前節(jié)點、并且當(dāng)前節(jié)點的左子節(jié)點存在，則以左子節(jié)點作為當(dāng)前節(jié)點；如果新增節(jié)點等于當(dāng)前節(jié)點，則用新增節(jié)點覆蓋當(dāng)前節(jié)點，并結(jié)束循環(huán) —— 直到找到某個節(jié)點的左、右子節(jié)點不存在，將新節(jié)點添加該節(jié)點的子節(jié)點 —— 如果新節(jié)點比該節(jié)點大，則添加為右子節(jié)點；如果新節(jié)點比該節(jié)點小，則添加為左子節(jié)點。
TreeMap 的刪除節(jié)點
當(dāng)程序從排序二叉樹中刪除一個節(jié)點之后，為了讓它依然保持為排序二叉樹，程序必須對該排序二叉樹進(jìn)行維護(hù)。維護(hù)可分為如下幾種情況：
（1）被刪除的節(jié)點是葉子節(jié)點，則只需將它從其父節(jié)點中刪除即可。
（2）被刪除節(jié)點 p 只有左子樹，將 p 的左子樹 pL 添加成 p 的父節(jié)點的左子樹即可；被刪除節(jié)點 p 只有右子樹，將 p 的右子樹 pR 添加成 p 的父節(jié)點的右子樹即可。
（3）若被刪除節(jié)點 p 的左、右子樹均非空，有兩種做法：
將 pL 設(shè)為 p 的父節(jié)點 q 的左或右子節(jié)點（取決于 p 是其父節(jié)點 q 的左、右子節(jié)點），將 pR 設(shè)為 p 節(jié)點的中序前趨節(jié)點 s 的右子節(jié)點（s 是 pL 最右下的節(jié)點，也就是 pL 子樹中最大的節(jié)點）。以 p 節(jié)點的中序前趨或后繼替代 p 所指節(jié)點，然后再從原排序二叉樹中刪去中序前趨或后繼節(jié)點即可。（也就是用大于 p 的最小節(jié)點或小于 p 的最大節(jié)點代替 p 節(jié)點即可）。
圖 2 顯示了被刪除節(jié)點只有左子樹的示意圖：
圖 2. 被刪除節(jié)點只有左子樹
圖 3 顯示了被刪除節(jié)點只有右子樹的示意圖：
圖 3. 被刪除節(jié)點只有右子樹
圖 4 顯示了被刪除節(jié)點既有左子節(jié)點，又有右子節(jié)點的情形，此時我們采用到是第一種方式進(jìn)行維護(hù)：
圖 4. 被刪除節(jié)點既有左子樹，又有右子樹
圖 5 顯示了被刪除節(jié)點既有左子樹，又有右子樹的情形，此時我們采用到是第二種方式進(jìn)行維護(hù)：
圖 5. 被刪除節(jié)點既有左子樹，又有右子樹
TreeMap 刪除節(jié)點采用圖 5 所示右邊的情形進(jìn)行維護(hù)——也就是用被刪除節(jié)點的右子樹中最小節(jié)點與被刪節(jié)點交換的方式進(jìn)行維護(hù)。
TreeMap 刪除節(jié)點的方法由如下方法實現(xiàn)：
private void deleteEntry(Entry<K,V> p)
{
modCount++;
size--;
// 如果被刪除節(jié)點的左子樹、右子樹都不為空
if (p.left != null && p.right != null)
{
// 用 p 節(jié)點的中序后繼節(jié)點代替 p 節(jié)點
Entry<K,V> s = successor (p);
p.key = s.key;
p.value = s.value;
p = s;
}
// 如果 p 節(jié)點的左節(jié)點存在，replacement 代表左節(jié)點；否則代表右節(jié)點。
Entry<K,V> replacement = (p.left != null ? p.left : p.right);
if (replacement != null)
{
replacement.parent = p.parent;
// 如果 p 沒有父節(jié)點，則 replacemment 變成父節(jié)點
if (p.parent == null)
root = replacement;
// 如果 p 節(jié)點是其父節(jié)點的左子節(jié)點
else if (p == p.parent.left)
p.parent.left = replacement;
// 如果 p 節(jié)點是其父節(jié)點的右子節(jié)點
else
p.parent.right = replacement;
p.left = p.right = p.parent = null;
// 修復(fù)紅黑樹
if (p.color == BLACK)
fixAfterDeletion(replacement); // ①
}
// 如果 p 節(jié)點沒有父節(jié)點
else if (p.parent == null)
{
root = null;
}
else
{
if (p.color == BLACK)
// 修復(fù)紅黑樹
fixAfterDeletion(p); // ②
if (p.parent != null)
{
// 如果 p 是其父節(jié)點的左子節(jié)點
if (p == p.parent.left)
p.parent.left = null;
// 如果 p 是其父節(jié)點的右子節(jié)點
else if (p == p.parent.right)
p.parent.right = null;
p.parent = null;
}
}
}
紅黑樹
排序二叉樹雖然可以快速檢索，但在最壞的情況下：如果插入的節(jié)點集本身就是有序的，要么是由小到大排列，要么是由大到小排列，那么最后得到的排序二叉樹將變成鏈表：所有節(jié)點只有左節(jié)點（如果插入節(jié)點集本身是大到小排列）；或所有節(jié)點只有右節(jié)點（如果插入節(jié)點集本身是小到大排列）。在這種情況下，排序二叉樹就變成了普通鏈表，其檢索效率就會很差。
為了改變排序二叉樹存在的不足，Rudolf Bayer 與 1972 年發(fā)明了另一種改進(jìn)后的排序二叉樹：紅黑樹，他將這種排序二叉樹稱為“對稱二叉 B 樹”，而紅黑樹這個名字則由 Leo J. Guibas 和 Robert Sedgewick 于 1978 年首次提出。
紅黑樹是一個更高效的檢索二叉樹，因此常常用來實現(xiàn)關(guān)聯(lián)數(shù)組。典型地，JDK 提供的集合類 TreeMap 本身就是一個紅黑樹的實現(xiàn)。
紅黑樹在原有的排序二叉樹增加了如下幾個要求：
Java 實現(xiàn)的紅黑樹
上面的性質(zhì) 3 中指定紅黑樹的每個葉子節(jié)點都是空節(jié)點，而且并葉子節(jié)點都是黑色。但 Java 實現(xiàn)的紅黑樹將使用 null 來代表空節(jié)點，因此遍歷紅黑樹時將看不到黑色的葉子節(jié)點，反而看到每個葉子節(jié)點都是紅色的。
性質(zhì) 1：每個節(jié)點要么是紅色，要么是黑色。
性質(zhì) 2：根節(jié)點永遠(yuǎn)是黑色的。
性質(zhì) 3：所有的葉節(jié)點都是空節(jié)點（即 null），并且是黑色的。
性質(zhì) 4：每個紅色節(jié)點的兩個子節(jié)點都是黑色。（從每個葉子到根的路徑上不會有兩個連續(xù)的紅色節(jié)點）
性質(zhì) 5：從任一節(jié)點到其子樹中每個葉子節(jié)點的路徑都包含相同數(shù)量的黑色節(jié)點。
Java 中實現(xiàn)的紅黑樹可能有如圖 6 所示結(jié)構(gòu)：
圖 6. Java 紅黑樹的示意
備注：本文中所有關(guān)于紅黑樹中的示意圖采用白色代表紅色。黑色節(jié)點還是采用了黑色表示。
根據(jù)性質(zhì) 5：紅黑樹從根節(jié)點到每個葉子節(jié)點的路徑都包含相同數(shù)量的黑色節(jié)點，因此從根節(jié)點到葉子節(jié)點的路徑中包含的黑色節(jié)點數(shù)被稱為樹的“黑色高度（black-height）”。
性質(zhì) 4 則保證了從根節(jié)點到葉子節(jié)點的最長路徑的長度不會超過任何其他路徑的兩倍。假如有一棵黑色高度為 3 的紅黑樹：從根節(jié)點到葉節(jié)點的最短路徑長度是 2，該路徑上全是黑色節(jié)點（黑節(jié)點 - 黑節(jié)點 - 黑節(jié)點）。最長路徑也只可能為 4，在每個黑色節(jié)點之間插入一個紅色節(jié)點（黑節(jié)點 - 紅節(jié)點 - 黑節(jié)點 - 紅節(jié)點 - 黑節(jié)點），性質(zhì) 4 保證絕不可能插入更多的紅色節(jié)點。由此可見，紅黑樹中最長路徑就是一條紅黑交替的路徑。
紅黑樹和平衡二叉樹
紅黑樹并不是真正的平衡二叉樹，但在實際應(yīng)用中，紅黑樹的統(tǒng)計性能要高于平衡二叉樹，但極端性能略差。
由此我們可以得出結(jié)論：對于給定的黑色高度為 N 的紅黑樹，從根到葉子節(jié)點的最短路徑長度為 N-1，最長路徑長度為 2 * (N-1)。
提示：排序二叉樹的深度直接影響了檢索的性能，正如前面指出，當(dāng)插入節(jié)點本身就是由小到大排列時，排序二叉樹將變成一個鏈表，這種排序二叉樹的檢索性能最低：N 個節(jié)點的二叉樹深度就是 N-1。
紅黑樹通過上面這種限制來保證它大致是平衡的——因為紅黑樹的高度不會無限增高，這樣保證紅黑樹在最壞情況下都是高效的，不會出現(xiàn)普通排序二叉樹的情況。
由于紅黑樹只是一個特殊的排序二叉樹，因此對紅黑樹上的只讀操作與普通排序二叉樹上的只讀操作完全相同，只是紅黑樹保持了大致平衡，因此檢索性能比排序二叉樹要好很多。
但在紅黑樹上進(jìn)行插入操作和刪除操作會導(dǎo)致樹不再符合紅黑樹的特征，因此插入操作和刪除操作都需要進(jìn)行一定的維護(hù)，以保證插入節(jié)點、刪除節(jié)點后的樹依然是紅黑樹。
添加點后的修復(fù)
上面 put(K key, V value) 方法中①號代碼處使用fixAfterInsertion(e) 方法來修復(fù)紅黑樹——因此每次插入節(jié)點后必須進(jìn)行簡單修復(fù)，使該排序二叉樹滿足紅黑樹的要求。
插入操作按如下步驟進(jìn)行：
（1）以排序二叉樹的方法插入新節(jié)點，并將它設(shè)為紅色。
（2）進(jìn)行顏色調(diào)換和樹旋轉(zhuǎn)。
插入后的修復(fù)
在插入操作中，紅黑樹的性質(zhì) 1 和性質(zhì) 3 兩個永遠(yuǎn)不會發(fā)生改變，因此無需考慮紅黑樹的這兩個特性。
這種顏色調(diào)用和樹旋轉(zhuǎn)就比較復(fù)雜了，下面將分情況進(jìn)行介紹。在介紹中，我們把新插入的節(jié)點定義為 N 節(jié)點，N 節(jié)點的父節(jié)點定義為 P 節(jié)點，P 節(jié)點的兄弟節(jié)點定義為 U 節(jié)點，P 節(jié)點父節(jié)點定義為 G 節(jié)點。
下面分成不同情形來分析插入操作
情形 1：新節(jié)點 N 是樹的根節(jié)點，沒有父節(jié)點
在這種情形下，直接將它設(shè)置為黑色以滿足性質(zhì) 2。
情形 2：新節(jié)點的父節(jié)點 P 是黑色
在這種情況下，新插入的節(jié)點是紅色的，因此依然滿足性質(zhì) 4。而且因為新節(jié)點 N 有兩個黑色葉子節(jié)點；但是由于新節(jié)點 N 是紅色，通過它的每個子節(jié)點的路徑依然保持相同的黑色節(jié)點數(shù)，因此依然滿足性質(zhì) 5。
情形 3：如果父節(jié)點 P 和父節(jié)點的兄弟節(jié)點 U 都是紅色
在這種情況下，程序應(yīng)該將 P 節(jié)點、U 節(jié)點都設(shè)置為黑色，并將 P 節(jié)點的父節(jié)點設(shè)為紅色（用來保持性質(zhì) 5）?，F(xiàn)在新節(jié)點 N 有了一個黑色的父節(jié)點 P。由于從 P 節(jié)點、U 節(jié)點到根節(jié)點的任何路徑都必須通過 G 節(jié)點，在這些路徑上的黑節(jié)點數(shù)目沒有改變（原來有葉子和 G 節(jié)點兩個黑色節(jié)點，現(xiàn)在有葉子和 P 兩個黑色節(jié)點）。
經(jīng)過上面處理后，紅色的 G 節(jié)點的父節(jié)點也有可能是紅色的，這就違反了性質(zhì) 4，因此還需要對 G 節(jié)點遞歸地進(jìn)行整個過程（把 G 當(dāng)成是新插入的節(jié)點進(jìn)行處理即可）。
圖 7 顯示了這種處理過程：
圖 7. 插入節(jié)點后進(jìn)行顏色調(diào)換
備注：雖然圖 11.28 繪制的是新節(jié)點 N 作為父節(jié)點 P 左子節(jié)點的情形，其實新節(jié)點 N 作為父節(jié)點 P 右子節(jié)點的情況與圖 11.28 完全相同。
情形 4：父節(jié)點 P 是紅色、而其兄弟節(jié)點 U 是黑色或缺少；且新節(jié)點 N 是父節(jié)點 P 的右子節(jié)點，而父節(jié)點 P 又是其父節(jié)點 G 的左子節(jié)點。
在這種情形下，我們進(jìn)行一次左旋轉(zhuǎn)對新節(jié)點和其父節(jié)點進(jìn)行，接著按情形 5 處理以前的父節(jié)點 P（也就是把 P 當(dāng)成新插入的節(jié)點即可）。這導(dǎo)致某些路徑通過它們以前不通過的新節(jié)點 N 或父節(jié)點 P 的其中之一，但是這兩個節(jié)點都是紅色的，因此不會影響性質(zhì) 5。
圖 8 顯示了對情形 4 的處理：
圖 8. 插入節(jié)點后的樹旋轉(zhuǎn)
備注：圖 11.29 中 P 節(jié)點是 G 節(jié)點的左子節(jié)點，如果 P 節(jié)點是其父節(jié)點 G 節(jié)點的右子節(jié)點，那么上 面的處理情況應(yīng)該左、右對調(diào)一下。
情形 5：父節(jié)點 P 是紅色、而其兄弟節(jié)點 U 是黑色或缺少；且新節(jié)點 N 是其父節(jié)點的左子節(jié)點，而父節(jié)點 P 又是其父節(jié)點 G 的左子節(jié)點。
在這種情形下，需要對節(jié)點 G 的一次右旋轉(zhuǎn)，在旋轉(zhuǎn)產(chǎn)生的樹中，以前的父節(jié)點 P 現(xiàn)在是新節(jié)點 N 和節(jié)點 G 的父節(jié)點。由于以前的節(jié)點 G 是黑色，否則父節(jié)點 P 就不可能是紅色，我們切換以前的父節(jié)點 P 和節(jié)點 G 的顏色，使之滿足性質(zhì) 4，性質(zhì) 5 也仍然保持滿足，因為通過這三個節(jié)點中任何一個的所有路徑以前都通過節(jié)點 G，現(xiàn)在它們都通過以前的父節(jié)點 P。在各自的情形下，這都是三個節(jié)點中唯一的黑色節(jié)點。
圖 9 顯示了情形 5 的處理過程：
圖 9. 插入節(jié)點后的顏色調(diào)整、樹旋轉(zhuǎn)
備注：圖 11.30 中 P 節(jié)點是 G 節(jié)點的左子節(jié)點，如果 P 節(jié)點是其父節(jié)點 G 節(jié)點的右子節(jié)點，那么上面的處理情況應(yīng)該左、右對調(diào)一下。
TreeMap 為插入節(jié)點后的修復(fù)操作由 fixAfterInsertion(Entry<K,V> x) 方法提供，該方法的源代碼如下：
// 插入節(jié)點后修復(fù)紅黑樹
private void fixAfterInsertion(Entry<K,V> x)
{
x.color = RED;
// 直到 x 節(jié)點的父節(jié)點不是根，且 x 的父節(jié)點不是紅色
while (x != null && x != root
&& x.parent.color == RED)
{
// 如果 x 的父節(jié)點是其父節(jié)點的左子節(jié)點
if (parentOf(x) == leftOf(parentOf(parentOf(x))))
{
// 獲取 x 的父節(jié)點的兄弟節(jié)點
Entry<K,V> y = rightOf(parentOf(parentOf(x)));
// 如果 x 的父節(jié)點的兄弟節(jié)點是紅色
if (colorOf(y) == RED)
{
// 將 x 的父節(jié)點設(shè)為黑色
setColor(parentOf(x), BLACK);
// 將 x 的父節(jié)點的兄弟節(jié)點設(shè)為黑色
setColor(y, BLACK);
// 將 x 的父節(jié)點的父節(jié)點設(shè)為紅色
setColor(parentOf(parentOf(x)), RED);
x = parentOf(parentOf(x));
}
// 如果 x 的父節(jié)點的兄弟節(jié)點是黑色
else
{
// 如果 x 是其父節(jié)點的右子節(jié)點
if (x == rightOf(parentOf(x)))
{
// 將 x 的父節(jié)點設(shè)為 x
x = parentOf(x);
rotateLeft(x);
}
// 把 x 的父節(jié)點設(shè)為黑色
setColor(parentOf(x), BLACK);
// 把 x 的父節(jié)點的父節(jié)點設(shè)為紅色
setColor(parentOf(parentOf(x)), RED);
rotateRight(parentOf(parentOf(x)));
}
}
// 如果 x 的父節(jié)點是其父節(jié)點的右子節(jié)點
else
{
// 獲取 x 的父節(jié)點的兄弟節(jié)點
Entry<K,V> y = leftOf(parentOf(parentOf(x)));
// 如果 x 的父節(jié)點的兄弟節(jié)點是紅色
if (colorOf(y) == RED)
{
// 將 x 的父節(jié)點設(shè)為黑色。
setColor(parentOf(x), BLACK);
// 將 x 的父節(jié)點的兄弟節(jié)點設(shè)為黑色
setColor(y, BLACK);
// 將 x 的父節(jié)點的父節(jié)點設(shè)為紅色
setColor(parentOf(parentOf(x)), RED);
// 將 x 設(shè)為 x 的父節(jié)點的節(jié)點
x = parentOf(parentOf(x));
}
// 如果 x 的父節(jié)點的兄弟節(jié)點是黑色
else
{
// 如果 x 是其父節(jié)點的左子節(jié)點
if (x == leftOf(parentOf(x)))
{
// 將 x 的父節(jié)點設(shè)為 x
x = parentOf(x);
rotateRight(x);
}
// 把 x 的父節(jié)點設(shè)為黑色
setColor(parentOf(x), BLACK);
// 把 x 的父節(jié)點的父節(jié)點設(shè)為紅色
setColor(parentOf(parentOf(x)), RED);
rotateLeft(parentOf(parentOf(x)));
}
}
}
// 將根節(jié)點設(shè)為黑色
root.color = BLACK;
}
刪除節(jié)點后的修復(fù)
與添加節(jié)點之后的修復(fù)類似的是，TreeMap 刪除節(jié)點之后也需要進(jìn)行類似的修復(fù)操作，通過這種修復(fù)來保證該排序二叉樹依然滿足紅黑樹特征。大家可以參考插入節(jié)點之后的修復(fù)來分析刪除之后的修復(fù)。TreeMap 在刪除之后的修復(fù)操作由 fixAfterDeletion(Entry<K,V> x) 方法提供，該方法源代碼如下：
// 刪除節(jié)點后修復(fù)紅黑樹
private void fixAfterDeletion(Entry<K,V> x)
{
// 直到 x 不是根節(jié)點，且 x 的顏色是黑色
while (x != root && colorOf(x) == BLACK)
{
// 如果 x 是其父節(jié)點的左子節(jié)點
if (x == leftOf(parentOf(x)))
{
// 獲取 x 節(jié)點的兄弟節(jié)點
Entry<K,V> sib = rightOf(parentOf(x));
// 如果 sib 節(jié)點是紅色
if (colorOf(sib) == RED)
{
// 將 sib 節(jié)點設(shè)為黑色
setColor(sib, BLACK);
// 將 x 的父節(jié)點設(shè)為紅色
setColor(parentOf(x), RED);
rotateLeft(parentOf(x));
// 再次將 sib 設(shè)為 x 的父節(jié)點的右子節(jié)點
sib = rightOf(parentOf(x));
}
// 如果 sib 的兩個子節(jié)點都是黑色
if (colorOf(leftOf(sib)) == BLACK
&& colorOf(rightOf(sib)) == BLACK)
{
// 將 sib 設(shè)為紅色
setColor(sib, RED);
// 讓 x 等于 x 的父節(jié)點
x = parentOf(x);
}
else
{
// 如果 sib 的只有右子節(jié)點是黑色
if (colorOf(rightOf(sib)) == BLACK)
{
// 將 sib 的左子節(jié)點也設(shè)為黑色
setColor(leftOf(sib), BLACK);
// 將 sib 設(shè)為紅色
setColor(sib, RED);
rotateRight(sib);
sib = rightOf(parentOf(x));
}
// 設(shè)置 sib 的顏色與 x 的父節(jié)點的顏色相同
setColor(sib, colorOf(parentOf(x)));
// 將 x 的父節(jié)點設(shè)為黑色
setColor(parentOf(x), BLACK);
// 將 sib 的右子節(jié)點設(shè)為黑色
setColor(rightOf(sib), BLACK);
rotateLeft(parentOf(x));
x = root;
}
}
// 如果 x 是其父節(jié)點的右子節(jié)點
else
{
// 獲取 x 節(jié)點的兄弟節(jié)點
Entry<K,V> sib = leftOf(parentOf(x));
// 如果 sib 的顏色是紅色
if (colorOf(sib) == RED)
{
// 將 sib 的顏色設(shè)為黑色
setColor(sib, BLACK);
// 將 sib 的父節(jié)點設(shè)為紅色
setColor(parentOf(x), RED);
rotateRight(parentOf(x));
sib = leftOf(parentOf(x));
}
// 如果 sib 的兩個子節(jié)點都是黑色
if (colorOf(rightOf(sib)) == BLACK
&& colorOf(leftOf(sib)) == BLACK)
{
// 將 sib 設(shè)為紅色
setColor(sib, RED);
// 讓 x 等于 x 的父節(jié)點
x = parentOf(x);
}
else
{
// 如果 sib 只有左子節(jié)點是黑色
if (colorOf(leftOf(sib)) == BLACK)
{
// 將 sib 的右子節(jié)點也設(shè)為黑色
setColor(rightOf(sib), BLACK);
// 將 sib 設(shè)為紅色
setColor(sib, RED);
rotateLeft(sib);
sib = leftOf(parentOf(x));
}
// 將 sib 的顏色設(shè)為與 x 的父節(jié)點顏色相同
setColor(sib, colorOf(parentOf(x)));
// 將 x 的父節(jié)點設(shè)為黑色
setColor(parentOf(x), BLACK);
// 將 sib 的左子節(jié)點設(shè)為黑色
setColor(leftOf(sib), BLACK);
rotateRight(parentOf(x));
x = root;
}
}
}
setColor(x, BLACK);
}
檢索節(jié)點
當(dāng) TreeMap 根據(jù) key 來取出 value 時，TreeMap 對應(yīng)的方法如下：
public V get(Object key)
{
// 根據(jù)指定 key 取出對應(yīng)的 Entry
Entry>K,V< p = getEntry(key);
// 返回該 Entry 所包含的 value
return (p==null ? null : p.value);
}
從上面程序的粗體字代碼可以看出，get(Object key) 方法實質(zhì)是由于 getEntry() 方法實現(xiàn)的，這個 getEntry() 方法的代碼如下：
final Entry<K,V> getEntry(Object key)
{
// 如果 comparator 不為 null，表明程序采用定制排序
if (comparator != null)
// 調(diào)用 getEntryUsingComparator 方法來取出對應(yīng)的 key
return getEntryUsingComparator(key);
// 如果 key 形參的值為 null，拋出 NullPointerException 異常
if (key == null)
throw new NullPointerException();
// 將 key 強(qiáng)制類型轉(zhuǎn)換為 Comparable 實例
Comparable<? super K> k = (Comparable<? super K>) key;
// 從樹的根節(jié)點開始
Entry<K,V> p = root;
while (p != null)
{
// 拿 key 與當(dāng)前節(jié)點的 key 進(jìn)行比較
int cmp = k.compareTo(p.key);
// 如果 key 小于當(dāng)前節(jié)點的 key，向“左子樹”搜索
if (cmp < 0)
p = p.left;
// 如果 key 大于當(dāng)前節(jié)點的 key，向“右子樹”搜索
else if (cmp > 0)
p = p.right;
// 不大于、不小于，就是找到了目標(biāo) Entry
else
return p;
}
return null;
}
上面的 getEntry(Object obj) 方法也是充分利用排序二叉樹的特征來搜索目標(biāo) Entry，程序依然從二叉樹的根節(jié)點開始，如果被搜索節(jié)點大于當(dāng)前節(jié)點，程序向“右子樹”搜索；如果被搜索節(jié)點小于當(dāng)前節(jié)點，程序向“左子樹”搜索；如果相等，那就是找到了指定節(jié)點。
當(dāng) TreeMap 里的 comparator != null 即表明該 TreeMap 采用了定制排序，在采用定制排序的方式下，TreeMap 采用 getEntryUsingComparator(key) 方法來根據(jù) key 獲取 Entry。下面是該方法的代碼：
final Entry<K,V> getEntryUsingComparator(Object key)
{
K k = (K) key;
// 獲取該 TreeMap 的 comparator
Comparator<? super K> cpr = comparator;
if (cpr != null)
{
// 從根節(jié)點開始
Entry<K,V> p = root;
while (p != null)
{
// 拿 key 與當(dāng)前節(jié)點的 key 進(jìn)行比較
int cmp = cpr.compare(k, p.key);
// 如果 key 小于當(dāng)前節(jié)點的 key，向“左子樹”搜索
if (cmp < 0)
p = p.left;
// 如果 key 大于當(dāng)前節(jié)點的 key，向“右子樹”搜索
else if (cmp > 0)
p = p.right;
// 不大于、不小于，就是找到了目標(biāo) Entry
else
return p;
}
}
return null;
}
其實 getEntry、getEntryUsingComparator 兩個方法的實現(xiàn)思路完全類似，只是前者對自然排序的 TreeMap 獲取有效，后者對定制排序的 TreeMap 有效。
通過上面源代碼的分析不難看出，TreeMap 這個工具類的實現(xiàn)其實很簡單?；蛘哒f：從內(nèi)部結(jié)構(gòu)來看，TreeMap 本質(zhì)上就是一棵“紅黑樹”，而 TreeMap 的每個 Entry 就是該紅黑樹的一個節(jié)點。
以上就是本文的全部內(nèi)容，希望對大家的學(xué)習(xí)有所幫助，也希望大家多多支持億速云。
免責(zé)聲明：本站發(fā)布的內(nèi)容（圖片、視頻和文字）以原創(chuàng)、轉(zhuǎn)載和分享為主，文章觀點不代表本網(wǎng)站立場，如果涉及侵權(quán)請聯(lián)系站長郵箱：is@yisu.com進(jìn)行舉報，并提供相關(guān)證據(jù)，一經(jīng)查實，將立刻刪除涉嫌侵權(quán)內(nèi)容。
億速云公眾號
手機(jī)網(wǎng)站二維碼