TreeMap 的實(shí)現(xiàn)就是紅黑樹(shù)數(shù)據(jù)結(jié)構(gòu)，也就說(shuō)是一棵自平衡的排序二叉樹(shù)，這樣就可以保證當(dāng)需要快速檢索指定節(jié)點(diǎn)。

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 來(lái)保存 Set 集合的元素
 private transient NavigableMap<E,Object> m; 
 // 使用一個(gè) PRESENT 作為 Map 集合的所有 value。
 private static final Object PRESENT = new Object(); 
 // 包訪問(wèn)權(quán)限的構(gòu)造器，以指定的 NavigableMap 對(duì)象創(chuàng)建 Set 集合
 TreeSet(NavigableMap<E,Object> m) 
 { 
 this.m = m; 
 } 
 public TreeSet()     // ①
 { 
 // 以自然排序方式創(chuàng)建一個(gè)新的 TreeMap，
 // 根據(jù)該 TreeSet 創(chuàng)建一個(gè) TreeSet，
 // 使用該 TreeMap 的 key 來(lái)保存 Set 集合的元素
 this(new TreeMap<E,Object>()); 
 } 
 public TreeSet(Comparator<? super E> comparator) // ②
 { 
 // 以定制排序方式創(chuàng)建一個(gè)新的 TreeMap，
 // 根據(jù)該 TreeSet 創(chuàng)建一個(gè) TreeSet，
 // 使用該 TreeMap 的 key 來(lái)保存 Set 集合的元素
 this(new TreeMap<E,Object>(comparator)); 
 } 
 public TreeSet(Collection<? extends E> c) 
 { 
 // 調(diào)用①號(hào)構(gòu)造器創(chuàng)建一個(gè) TreeSet，底層以 TreeMap 保存集合元素
 this(); 
 // 向 TreeSet 中添加 Collection 集合 c 里的所有元素
 addAll(c); 
 } 
 public TreeSet(SortedSet<E> s) 
 { 
 // 調(diào)用②號(hào)構(gòu)造器創(chuàng)建一個(gè) TreeSet，底層以 TreeMap 保存集合元素
 this(s.comparator()); 
 // 向 TreeSet 中添加 SortedSet 集合 s 里的所有元素
 addAll(s); 
 } 
 //TreeSet 的其他方法都只是直接調(diào)用 TreeMap 的方法來(lái)提供實(shí)現(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 兩個(gè) Comparator 相等
  if (cc == mc || (cc != null && cc.equals(mc))) 
  { 
  // 把 Collection 中所有元素添加成 TreeMap 集合的 key 
  map.addAllForTreeSet(set, PRESENT); 
  return true; 
  } 
 } 
 // 直接調(diào)用父類的 addAll() 方法來(lái)實(shí)現(xiàn)
 return super.addAll(c); 
 } 
 ... 
 } 

從上面代碼可以看出，TreeSet 的 ① 號(hào)、② 號(hào)構(gòu)造器的都是新建一個(gè) TreeMap 作為實(shí)際存儲(chǔ) Set 元素的容器，而另外 2 個(gè)構(gòu)造器則分別依賴于 ① 號(hào)和 ② 號(hào)構(gòu)造器，由此可見(jiàn)，TreeSet 底層實(shí)際使用的存儲(chǔ)容器就是 TreeMap。

與 HashSet 完全類似的是，TreeSet 里絕大部分方法都是直接調(diào)用 TreeMap 的方法來(lái)實(shí)現(xiàn)的，這一點(diǎn)讀者可以自行參閱 TreeSet 的源代碼，此處就不再給出了。

對(duì)于 TreeMap 而言，它采用一種被稱為“紅黑樹(shù)”的排序二叉樹(shù)來(lái)保存 Map 中每個(gè) Entry —— 每個(gè) Entry 都被當(dāng)成“紅黑樹(shù)”的一個(gè)節(jié)點(diǎn)對(duì)待。例如對(duì)于如下程序而言：

 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); 時(shí)，系統(tǒng)將直接把 "ccc"-89.0 這個(gè) Entry 放入 Map 中，這個(gè) Entry 就是該“紅黑樹(shù)”的根節(jié)點(diǎn)。接著程序執(zhí)行 map.put("aaa" , 80.0); 時(shí)，程序會(huì)將 "aaa"-80.0 作為新節(jié)點(diǎn)添加到已有的紅黑樹(shù)中。

以后每向 TreeMap 中放入一個(gè) key-value 對(duì)，系統(tǒng)都需要將該 Entry 當(dāng)成一個(gè)新節(jié)點(diǎn)，添加成已有紅黑樹(shù)中，通過(guò)這種方式就可保證 TreeMap 中所有 key 總是由小到大地排列。例如我們輸出上面程序，將看到如下結(jié)果（所有 key 由小到大地排列）：

 {aaa=80.0, bbb=89.0, ccc=89.0, zzz=80.0} 

TreeMap 的添加節(jié)點(diǎn)

紅黑樹(shù)

紅黑樹(shù)是一種自平衡排序二叉樹(shù)，樹(shù)中每個(gè)節(jié)點(diǎn)的值，都大于或等于在它的左子樹(shù)中的所有節(jié)點(diǎn)的值，并且小于或等于在它的右子樹(shù)中的所有節(jié)點(diǎn)的值，這確保紅黑樹(shù)運(yùn)行時(shí)可以快速地在樹(shù)中查找和定位的所需節(jié)點(diǎn)。

對(duì)于 TreeMap 而言，由于它底層采用一棵“紅黑樹(shù)”來(lái)保存集合中的 Entry，這意味這 TreeMap 添加元素、取出元素的性能都比 HashMap 低：當(dāng) TreeMap 添加元素時(shí)，需要通過(guò)循環(huán)找到新增 Entry 的插入位置，因此比較耗性能；當(dāng)從 TreeMap 中取出元素時(shí)，需要通過(guò)循環(huán)才能找到合適的 Entry，也比較耗性能。但 TreeMap、TreeSet 比 HashMap、HashSet 的優(yōu)勢(shì)在于：TreeMap 中的所有 Entry 總是按 key 根據(jù)指定排序規(guī)則保持有序狀態(tài)，TreeSet 中所有元素總是根據(jù)指定排序規(guī)則保持有序狀態(tài)。

為了理解 TreeMap 的底層實(shí)現(xiàn)，必須先介紹排序二叉樹(shù)和紅黑樹(shù)這兩種數(shù)據(jù)結(jié)構(gòu)。其中紅黑樹(shù)又是一種特殊的排序二叉樹(shù)。

排序二叉樹(shù)是一種特殊結(jié)構(gòu)的二叉樹(shù)，可以非常方便地對(duì)樹(shù)中所有節(jié)點(diǎn)進(jìn)行排序和檢索。

排序二叉樹(shù)要么是一棵空二叉樹(shù)，要么是具有下列性質(zhì)的二叉樹(shù)：

• 若它的左子樹(shù)不空，則左子樹(shù)上所有節(jié)點(diǎn)的值均小于它的根節(jié)點(diǎn)的值；
• 若它的右子樹(shù)不空，則右子樹(shù)上所有節(jié)點(diǎn)的值均大于它的根節(jié)點(diǎn)的值；
• 它的左、右子樹(shù)也分別為排序二叉樹(shù)。

圖 1 顯示了一棵排序二叉樹(shù)：

圖 1. 排序二叉樹(shù)

對(duì)排序二叉樹(shù)，若按中序遍歷就可以得到由小到大的有序序列。如圖 1 所示二叉樹(shù)，中序遍歷得：

{2，3，4，8，9，9，10，13，15，18} 

創(chuàng)建排序二叉樹(shù)的步驟，也就是不斷地向排序二叉樹(shù)添加節(jié)點(diǎn)的過(guò)程，向排序二叉樹(shù)添加節(jié)點(diǎn)的步驟如下：

• 以根節(jié)點(diǎn)當(dāng)前節(jié)點(diǎn)開(kāi)始搜索。
• 拿新節(jié)點(diǎn)的值和當(dāng)前節(jié)點(diǎn)的值比較。
• 如果新節(jié)點(diǎn)的值更大，則以當(dāng)前節(jié)點(diǎn)的右子節(jié)點(diǎn)作為新的當(dāng)前節(jié)點(diǎn)；如果新節(jié)點(diǎn)的值更小，則以當(dāng)前節(jié)點(diǎn)的左子節(jié)點(diǎn)作為新的當(dāng)前節(jié)點(diǎn)。
• 重復(fù) 2、3 兩個(gè)步驟，直到搜索到合適的葉子節(jié)點(diǎn)為止。
• 將新節(jié)點(diǎn)添加為第 4 步找到的葉子節(jié)點(diǎn)的子節(jié)點(diǎn)；如果新節(jié)點(diǎn)更大，則添加為右子節(jié)點(diǎn)；否則添加為左子節(jié)點(diǎn)。

掌握上面理論之后，下面我們來(lái)分析 TreeMap 添加節(jié)點(diǎn)（TreeMap 中使用 Entry 內(nèi)部類代表節(jié)點(diǎn)）的實(shí)現(xiàn)，TreeMap 集合的 put(K key, V value) 方法實(shí)現(xiàn)了將 Entry 放入排序二叉樹(shù)中，下面是該方法的源代碼：

 public V put(K key, V value) 
 { 
 // 先以 t 保存鏈表的 root 節(jié)點(diǎn)
 Entry<K,V> t = root; 
 // 如果 t==null，表明是一個(gè)空鏈表，即該 TreeMap 里沒(méi)有任何 Entry 
 if (t == null) 
 { 
 // 將新的 key-value 創(chuàng)建一個(gè) Entry，并將該 Entry 作為 root 
 root = new Entry<K,V>(key, value, null); 
 // 設(shè)置該 Map 集合的 size 為 1，代表包含一個(gè) 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é)點(diǎn)
  if (cmp < 0) 
  t = t.left; 
  // 如果新插入的 key 大于 t 的 key，t 等于 t 的右邊節(jié)點(diǎn)
  else if (cmp > 0) 
  t = t.right; 
  // 如果兩個(gè) 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é)點(diǎn)
  if (cmp < 0) 
  t = t.left; 
  // 如果新插入的 key 大于 t 的 key，t 等于 t 的右邊節(jié)點(diǎn)
  else if (cmp > 0) 
  t = t.right; 
  // 如果兩個(gè) key 相等，新的 value 覆蓋原有的 value，
  // 并返回原有的 value 
  else 
  return t.setValue(value); 
 } while (t != null); 
 } 
 // 將新插入的節(jié)點(diǎn)作為 parent 節(jié)點(diǎn)的子節(jié)點(diǎn)
 Entry<K,V> e = new Entry<K,V>(key, value, parent); 
 // 如果新插入 key 小于 parent 的 key，則 e 作為 parent 的左子節(jié)點(diǎn)
 if (cmp < 0) 
 parent.left = e; 
 // 如果新插入 key 小于 parent 的 key，則 e 作為 parent 的右子節(jié)點(diǎn)
 else 
 parent.right = e; 
 // 修復(fù)紅黑樹(shù)
 fixAfterInsertion(e);    // ①
 size++; 
 modCount++; 
 return null; 
 }

上面程序中粗體字代碼就是實(shí)現(xiàn)“排序二叉樹(shù)”的關(guān)鍵算法，每當(dāng)程序希望添加新節(jié)點(diǎn)時(shí)：系統(tǒng)總是從樹(shù)的根節(jié)點(diǎn)開(kāi)始比較 —— 即將根節(jié)點(diǎn)當(dāng)成當(dāng)前節(jié)點(diǎn)，如果新增節(jié)點(diǎn)大于當(dāng)前節(jié)點(diǎn)、并且當(dāng)前節(jié)點(diǎn)的右子節(jié)點(diǎn)存在，則以右子節(jié)點(diǎn)作為當(dāng)前節(jié)點(diǎn)；如果新增節(jié)點(diǎn)小于當(dāng)前節(jié)點(diǎn)、并且當(dāng)前節(jié)點(diǎn)的左子節(jié)點(diǎn)存在，則以左子節(jié)點(diǎn)作為當(dāng)前節(jié)點(diǎn)；如果新增節(jié)點(diǎn)等于當(dāng)前節(jié)點(diǎn)，則用新增節(jié)點(diǎn)覆蓋當(dāng)前節(jié)點(diǎn)，并結(jié)束循環(huán) —— 直到找到某個(gè)節(jié)點(diǎn)的左、右子節(jié)點(diǎn)不存在，將新節(jié)點(diǎn)添加該節(jié)點(diǎn)的子節(jié)點(diǎn) —— 如果新節(jié)點(diǎn)比該節(jié)點(diǎn)大，則添加為右子節(jié)點(diǎn)；如果新節(jié)點(diǎn)比該節(jié)點(diǎn)小，則添加為左子節(jié)點(diǎn)。

TreeMap 的刪除節(jié)點(diǎn)

當(dāng)程序從排序二叉樹(shù)中刪除一個(gè)節(jié)點(diǎn)之后，為了讓它依然保持為排序二叉樹(shù)，程序必須對(duì)該排序二叉樹(shù)進(jìn)行維護(hù)。維護(hù)可分為如下幾種情況：

（1）被刪除的節(jié)點(diǎn)是葉子節(jié)點(diǎn)，則只需將它從其父節(jié)點(diǎn)中刪除即可。

（2）被刪除節(jié)點(diǎn) p 只有左子樹(shù)，將 p 的左子樹(shù) pL 添加成 p 的父節(jié)點(diǎn)的左子樹(shù)即可；被刪除節(jié)點(diǎn) p 只有右子樹(shù)，將 p 的右子樹(shù) pR 添加成 p 的父節(jié)點(diǎn)的右子樹(shù)即可。

（3）若被刪除節(jié)點(diǎn) p 的左、右子樹(shù)均非空，有兩種做法：

將 pL 設(shè)為 p 的父節(jié)點(diǎn) q 的左或右子節(jié)點(diǎn)（取決于 p 是其父節(jié)點(diǎn) q 的左、右子節(jié)點(diǎn)），將 pR 設(shè)為 p 節(jié)點(diǎn)的中序前趨節(jié)點(diǎn) s 的右子節(jié)點(diǎn)（s 是 pL 最右下的節(jié)點(diǎn)，也就是 pL 子樹(shù)中最大的節(jié)點(diǎn)）。以 p 節(jié)點(diǎn)的中序前趨或后繼替代 p 所指節(jié)點(diǎn)，然后再?gòu)脑判蚨鏄?shù)中刪去中序前趨或后繼節(jié)點(diǎn)即可。（也就是用大于 p 的最小節(jié)點(diǎn)或小于 p 的最大節(jié)點(diǎn)代替 p 節(jié)點(diǎn)即可）。

圖 2 顯示了被刪除節(jié)點(diǎn)只有左子樹(shù)的示意圖：

圖 2. 被刪除節(jié)點(diǎn)只有左子樹(shù)

圖 3 顯示了被刪除節(jié)點(diǎn)只有右子樹(shù)的示意圖：

圖 3. 被刪除節(jié)點(diǎn)只有右子樹(shù)

圖 4 顯示了被刪除節(jié)點(diǎn)既有左子節(jié)點(diǎn)，又有右子節(jié)點(diǎn)的情形，此時(shí)我們采用到是第一種方式進(jìn)行維護(hù)：

圖 4. 被刪除節(jié)點(diǎn)既有左子樹(shù)，又有右子樹(shù)

圖 5 顯示了被刪除節(jié)點(diǎn)既有左子樹(shù)，又有右子樹(shù)的情形，此時(shí)我們采用到是第二種方式進(jìn)行維護(hù)：

圖 5. 被刪除節(jié)點(diǎn)既有左子樹(shù)，又有右子樹(shù)

TreeMap 刪除節(jié)點(diǎn)采用圖 5 所示右邊的情形進(jìn)行維護(hù)——也就是用被刪除節(jié)點(diǎn)的右子樹(shù)中最小節(jié)點(diǎn)與被刪節(jié)點(diǎn)交換的方式進(jìn)行維護(hù)。

TreeMap 刪除節(jié)點(diǎn)的方法由如下方法實(shí)現(xiàn)：

 private void deleteEntry(Entry<K,V> p) 
 { 
 modCount++; 
 size--; 
 // 如果被刪除節(jié)點(diǎn)的左子樹(shù)、右子樹(shù)都不為空
 if (p.left != null && p.right != null) 
 { 
 // 用 p 節(jié)點(diǎn)的中序后繼節(jié)點(diǎn)代替 p 節(jié)點(diǎn)
 Entry<K,V> s = successor (p); 
 p.key = s.key; 
 p.value = s.value; 
 p = s; 
 } 
 // 如果 p 節(jié)點(diǎn)的左節(jié)點(diǎn)存在，replacement 代表左節(jié)點(diǎn)；否則代表右節(jié)點(diǎn)。
 Entry<K,V> replacement = (p.left != null ? p.left : p.right); 
 if (replacement != null) 
 { 
 replacement.parent = p.parent; 
 // 如果 p 沒(méi)有父節(jié)點(diǎn)，則 replacemment 變成父節(jié)點(diǎn)
 if (p.parent == null) 
 root = replacement; 
 // 如果 p 節(jié)點(diǎn)是其父節(jié)點(diǎn)的左子節(jié)點(diǎn)
 else if (p == p.parent.left) 
 p.parent.left = replacement; 
 // 如果 p 節(jié)點(diǎn)是其父節(jié)點(diǎn)的右子節(jié)點(diǎn)
 else 
 p.parent.right = replacement; 
 p.left = p.right = p.parent = null; 
 // 修復(fù)紅黑樹(shù)
 if (p.color == BLACK) 
 fixAfterDeletion(replacement); // ①
 } 
 // 如果 p 節(jié)點(diǎn)沒(méi)有父節(jié)點(diǎn)
 else if (p.parent == null) 
 { 
 root = null; 
 } 
 else 
 { 
 if (p.color == BLACK) 
 // 修復(fù)紅黑樹(shù)
 fixAfterDeletion(p);  // ②
 if (p.parent != null) 
 { 
 // 如果 p 是其父節(jié)點(diǎn)的左子節(jié)點(diǎn)
 if (p == p.parent.left) 
 p.parent.left = null; 
 // 如果 p 是其父節(jié)點(diǎn)的右子節(jié)點(diǎn)
 else if (p == p.parent.right) 
 p.parent.right = null; 
 p.parent = null; 
 } 
 } 
 } 

紅黑樹(shù)

排序二叉樹(shù)雖然可以快速檢索，但在最壞的情況下：如果插入的節(jié)點(diǎn)集本身就是有序的，要么是由小到大排列，要么是由大到小排列，那么最后得到的排序二叉樹(shù)將變成鏈表：所有節(jié)點(diǎn)只有左節(jié)點(diǎn)（如果插入節(jié)點(diǎn)集本身是大到小排列）；或所有節(jié)點(diǎn)只有右節(jié)點(diǎn)（如果插入節(jié)點(diǎn)集本身是小到大排列）。在這種情況下，排序二叉樹(shù)就變成了普通鏈表，其檢索效率就會(huì)很差。

為了改變排序二叉樹(shù)存在的不足，Rudolf Bayer 與 1972 年發(fā)明了另一種改進(jìn)后的排序二叉樹(shù)：紅黑樹(shù)，他將這種排序二叉樹(shù)稱為“對(duì)稱二叉 B 樹(shù)”，而紅黑樹(shù)這個(gè)名字則由 Leo J. Guibas 和 Robert Sedgewick 于 1978 年首次提出。

紅黑樹(shù)是一個(gè)更高效的檢索二叉樹(shù)，因此常常用來(lái)實(shí)現(xiàn)關(guān)聯(lián)數(shù)組。典型地，JDK 提供的集合類 TreeMap 本身就是一個(gè)紅黑樹(shù)的實(shí)現(xiàn)。

紅黑樹(shù)在原有的排序二叉樹(shù)增加了如下幾個(gè)要求：

Java 實(shí)現(xiàn)的紅黑樹(shù)

上面的性質(zhì) 3 中指定紅黑樹(shù)的每個(gè)葉子節(jié)點(diǎn)都是空節(jié)點(diǎn)，而且并葉子節(jié)點(diǎn)都是黑色。但 Java 實(shí)現(xiàn)的紅黑樹(shù)將使用 null 來(lái)代表空節(jié)點(diǎn)，因此遍歷紅黑樹(shù)時(shí)將看不到黑色的葉子節(jié)點(diǎn)，反而看到每個(gè)葉子節(jié)點(diǎn)都是紅色的。

性質(zhì) 1：每個(gè)節(jié)點(diǎn)要么是紅色，要么是黑色。

性質(zhì) 2：根節(jié)點(diǎn)永遠(yuǎn)是黑色的。

性質(zhì) 3：所有的葉節(jié)點(diǎn)都是空節(jié)點(diǎn)（即 null），并且是黑色的。

性質(zhì) 4：每個(gè)紅色節(jié)點(diǎn)的兩個(gè)子節(jié)點(diǎn)都是黑色。（從每個(gè)葉子到根的路徑上不會(huì)有兩個(gè)連續(xù)的紅色節(jié)點(diǎn)）

性質(zhì) 5：從任一節(jié)點(diǎn)到其子樹(shù)中每個(gè)葉子節(jié)點(diǎn)的路徑都包含相同數(shù)量的黑色節(jié)點(diǎn)。

Java 中實(shí)現(xiàn)的紅黑樹(shù)可能有如圖 6 所示結(jié)構(gòu)：

圖 6. Java 紅黑樹(shù)的示意

備注：本文中所有關(guān)于紅黑樹(shù)中的示意圖采用白色代表紅色。黑色節(jié)點(diǎn)還是采用了黑色表示。

根據(jù)性質(zhì) 5：紅黑樹(shù)從根節(jié)點(diǎn)到每個(gè)葉子節(jié)點(diǎn)的路徑都包含相同數(shù)量的黑色節(jié)點(diǎn)，因此從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的路徑中包含的黑色節(jié)點(diǎn)數(shù)被稱為樹(shù)的“黑色高度（black-height）”。

性質(zhì) 4 則保證了從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的最長(zhǎng)路徑的長(zhǎng)度不會(huì)超過(guò)任何其他路徑的兩倍。假如有一棵黑色高度為 3 的紅黑樹(shù)：從根節(jié)點(diǎn)到葉節(jié)點(diǎn)的最短路徑長(zhǎng)度是 2，該路徑上全是黑色節(jié)點(diǎn)（黑節(jié)點(diǎn) - 黑節(jié)點(diǎn) - 黑節(jié)點(diǎn)）。最長(zhǎng)路徑也只可能為 4，在每個(gè)黑色節(jié)點(diǎn)之間插入一個(gè)紅色節(jié)點(diǎn)（黑節(jié)點(diǎn) - 紅節(jié)點(diǎn) - 黑節(jié)點(diǎn) - 紅節(jié)點(diǎn) - 黑節(jié)點(diǎn)），性質(zhì) 4 保證絕不可能插入更多的紅色節(jié)點(diǎn)。由此可見(jiàn)，紅黑樹(shù)中最長(zhǎng)路徑就是一條紅黑交替的路徑。

紅黑樹(shù)和平衡二叉樹(shù)

紅黑樹(shù)并不是真正的平衡二叉樹(shù)，但在實(shí)際應(yīng)用中，紅黑樹(shù)的統(tǒng)計(jì)性能要高于平衡二叉樹(shù)，但極端性能略差。

由此我們可以得出結(jié)論：對(duì)于給定的黑色高度為 N 的紅黑樹(shù)，從根到葉子節(jié)點(diǎn)的最短路徑長(zhǎng)度為 N-1，最長(zhǎng)路徑長(zhǎng)度為 2 * (N-1)。

提示：排序二叉樹(shù)的深度直接影響了檢索的性能，正如前面指出，當(dāng)插入節(jié)點(diǎn)本身就是由小到大排列時(shí)，排序二叉樹(shù)將變成一個(gè)鏈表，這種排序二叉樹(shù)的檢索性能最低：N 個(gè)節(jié)點(diǎn)的二叉樹(shù)深度就是 N-1。

紅黑樹(shù)通過(guò)上面這種限制來(lái)保證它大致是平衡的——因?yàn)榧t黑樹(shù)的高度不會(huì)無(wú)限增高，這樣保證紅黑樹(shù)在最壞情況下都是高效的，不會(huì)出現(xiàn)普通排序二叉樹(shù)的情況。

由于紅黑樹(shù)只是一個(gè)特殊的排序二叉樹(shù)，因此對(duì)紅黑樹(shù)上的只讀操作與普通排序二叉樹(shù)上的只讀操作完全相同，只是紅黑樹(shù)保持了大致平衡，因此檢索性能比排序二叉樹(shù)要好很多。

但在紅黑樹(shù)上進(jìn)行插入操作和刪除操作會(huì)導(dǎo)致樹(shù)不再符合紅黑樹(shù)的特征，因此插入操作和刪除操作都需要進(jìn)行一定的維護(hù)，以保證插入節(jié)點(diǎn)、刪除節(jié)點(diǎn)后的樹(shù)依然是紅黑樹(shù)。

添加點(diǎn)后的修復(fù)

上面 put(K key, V value) 方法中①號(hào)代碼處使用fixAfterInsertion(e) 方法來(lái)修復(fù)紅黑樹(shù)——因此每次插入節(jié)點(diǎn)后必須進(jìn)行簡(jiǎn)單修復(fù)，使該排序二叉樹(shù)滿足紅黑樹(shù)的要求。

插入操作按如下步驟進(jìn)行：

（1）以排序二叉樹(shù)的方法插入新節(jié)點(diǎn)，并將它設(shè)為紅色。

（2）進(jìn)行顏色調(diào)換和樹(shù)旋轉(zhuǎn)。

插入后的修復(fù)

在插入操作中，紅黑樹(shù)的性質(zhì) 1 和性質(zhì) 3 兩個(gè)永遠(yuǎn)不會(huì)發(fā)生改變，因此無(wú)需考慮紅黑樹(shù)的這兩個(gè)特性。

這種顏色調(diào)用和樹(shù)旋轉(zhuǎn)就比較復(fù)雜了，下面將分情況進(jìn)行介紹。在介紹中，我們把新插入的節(jié)點(diǎn)定義為 N 節(jié)點(diǎn)，N 節(jié)點(diǎn)的父節(jié)點(diǎn)定義為 P 節(jié)點(diǎn)，P 節(jié)點(diǎn)的兄弟節(jié)點(diǎn)定義為 U 節(jié)點(diǎn)，P 節(jié)點(diǎn)父節(jié)點(diǎn)定義為 G 節(jié)點(diǎn)。

下面分成不同情形來(lái)分析插入操作

情形 1：新節(jié)點(diǎn) N 是樹(shù)的根節(jié)點(diǎn)，沒(méi)有父節(jié)點(diǎn)

在這種情形下，直接將它設(shè)置為黑色以滿足性質(zhì) 2。

情形 2：新節(jié)點(diǎn)的父節(jié)點(diǎn) P 是黑色

在這種情況下，新插入的節(jié)點(diǎn)是紅色的，因此依然滿足性質(zhì) 4。而且因?yàn)樾鹿?jié)點(diǎn) N 有兩個(gè)黑色葉子節(jié)點(diǎn)；但是由于新節(jié)點(diǎn) N 是紅色，通過(guò)它的每個(gè)子節(jié)點(diǎn)的路徑依然保持相同的黑色節(jié)點(diǎn)數(shù)，因此依然滿足性質(zhì) 5。

情形 3：如果父節(jié)點(diǎn) P 和父節(jié)點(diǎn)的兄弟節(jié)點(diǎn) U 都是紅色

在這種情況下，程序應(yīng)該將 P 節(jié)點(diǎn)、U 節(jié)點(diǎn)都設(shè)置為黑色，并將 P 節(jié)點(diǎn)的父節(jié)點(diǎn)設(shè)為紅色（用來(lái)保持性質(zhì) 5）?，F(xiàn)在新節(jié)點(diǎn) N 有了一個(gè)黑色的父節(jié)點(diǎn) P。由于從 P 節(jié)點(diǎn)、U 節(jié)點(diǎn)到根節(jié)點(diǎn)的任何路徑都必須通過(guò) G 節(jié)點(diǎn)，在這些路徑上的黑節(jié)點(diǎn)數(shù)目沒(méi)有改變（原來(lái)有葉子和 G 節(jié)點(diǎn)兩個(gè)黑色節(jié)點(diǎn)，現(xiàn)在有葉子和 P 兩個(gè)黑色節(jié)點(diǎn)）。

經(jīng)過(guò)上面處理后，紅色的 G 節(jié)點(diǎn)的父節(jié)點(diǎn)也有可能是紅色的，這就違反了性質(zhì) 4，因此還需要對(duì) G 節(jié)點(diǎn)遞歸地進(jìn)行整個(gè)過(guò)程（把 G 當(dāng)成是新插入的節(jié)點(diǎn)進(jìn)行處理即可）。

圖 7 顯示了這種處理過(guò)程：

圖 7. 插入節(jié)點(diǎn)后進(jìn)行顏色調(diào)換

備注：雖然圖 11.28 繪制的是新節(jié)點(diǎn) N 作為父節(jié)點(diǎn) P 左子節(jié)點(diǎn)的情形，其實(shí)新節(jié)點(diǎn) N 作為父節(jié)點(diǎn) P 右子節(jié)點(diǎn)的情況與圖 11.28 完全相同。

情形 4：父節(jié)點(diǎn) P 是紅色、而其兄弟節(jié)點(diǎn) U 是黑色或缺少；且新節(jié)點(diǎn) N 是父節(jié)點(diǎn) P 的右子節(jié)點(diǎn)，而父節(jié)點(diǎn) P 又是其父節(jié)點(diǎn) G 的左子節(jié)點(diǎn)。

在這種情形下，我們進(jìn)行一次左旋轉(zhuǎn)對(duì)新節(jié)點(diǎn)和其父節(jié)點(diǎn)進(jìn)行，接著按情形 5 處理以前的父節(jié)點(diǎn) P（也就是把 P 當(dāng)成新插入的節(jié)點(diǎn)即可）。這導(dǎo)致某些路徑通過(guò)它們以前不通過(guò)的新節(jié)點(diǎn) N 或父節(jié)點(diǎn) P 的其中之一，但是這兩個(gè)節(jié)點(diǎn)都是紅色的，因此不會(huì)影響性質(zhì) 5。

圖 8 顯示了對(duì)情形 4 的處理：

圖 8. 插入節(jié)點(diǎn)后的樹(shù)旋轉(zhuǎn)

備注：圖 11.29 中 P 節(jié)點(diǎn)是 G 節(jié)點(diǎn)的左子節(jié)點(diǎn)，如果 P 節(jié)點(diǎn)是其父節(jié)點(diǎn) G 節(jié)點(diǎn)的右子節(jié)點(diǎn)，那么上 面的處理情況應(yīng)該左、右對(duì)調(diào)一下。

情形 5：父節(jié)點(diǎn) P 是紅色、而其兄弟節(jié)點(diǎn) U 是黑色或缺少；且新節(jié)點(diǎn) N 是其父節(jié)點(diǎn)的左子節(jié)點(diǎn)，而父節(jié)點(diǎn) P 又是其父節(jié)點(diǎn) G 的左子節(jié)點(diǎn)。

在這種情形下，需要對(duì)節(jié)點(diǎn) G 的一次右旋轉(zhuǎn)，在旋轉(zhuǎn)產(chǎn)生的樹(shù)中，以前的父節(jié)點(diǎn) P 現(xiàn)在是新節(jié)點(diǎn) N 和節(jié)點(diǎn) G 的父節(jié)點(diǎn)。由于以前的節(jié)點(diǎn) G 是黑色，否則父節(jié)點(diǎn) P 就不可能是紅色，我們切換以前的父節(jié)點(diǎn) P 和節(jié)點(diǎn) G 的顏色，使之滿足性質(zhì) 4，性質(zhì) 5 也仍然保持滿足，因?yàn)橥ㄟ^(guò)這三個(gè)節(jié)點(diǎn)中任何一個(gè)的所有路徑以前都通過(guò)節(jié)點(diǎn) G，現(xiàn)在它們都通過(guò)以前的父節(jié)點(diǎn) P。在各自的情形下，這都是三個(gè)節(jié)點(diǎn)中唯一的黑色節(jié)點(diǎn)。

圖 9 顯示了情形 5 的處理過(guò)程：

圖 9. 插入節(jié)點(diǎn)后的顏色調(diào)整、樹(shù)旋轉(zhuǎn)

備注：圖 11.30 中 P 節(jié)點(diǎn)是 G 節(jié)點(diǎn)的左子節(jié)點(diǎn)，如果 P 節(jié)點(diǎn)是其父節(jié)點(diǎn) G 節(jié)點(diǎn)的右子節(jié)點(diǎn)，那么上面的處理情況應(yīng)該左、右對(duì)調(diào)一下。

TreeMap 為插入節(jié)點(diǎn)后的修復(fù)操作由 fixAfterInsertion(Entry<K,V> x) 方法提供，該方法的源代碼如下：

 // 插入節(jié)點(diǎn)后修復(fù)紅黑樹(shù)
 private void fixAfterInsertion(Entry<K,V> x) 
 { 
 x.color = RED; 
 // 直到 x 節(jié)點(diǎn)的父節(jié)點(diǎn)不是根，且 x 的父節(jié)點(diǎn)不是紅色
 while (x != null && x != root 
 && x.parent.color == RED) 
 { 
 // 如果 x 的父節(jié)點(diǎn)是其父節(jié)點(diǎn)的左子節(jié)點(diǎn)
 if (parentOf(x) == leftOf(parentOf(parentOf(x)))) 
 { 
  // 獲取 x 的父節(jié)點(diǎn)的兄弟節(jié)點(diǎn)
  Entry<K,V> y = rightOf(parentOf(parentOf(x))); 
  // 如果 x 的父節(jié)點(diǎn)的兄弟節(jié)點(diǎn)是紅色
  if (colorOf(y) == RED) 
  { 
  // 將 x 的父節(jié)點(diǎn)設(shè)為黑色
  setColor(parentOf(x), BLACK); 
  // 將 x 的父節(jié)點(diǎn)的兄弟節(jié)點(diǎn)設(shè)為黑色
  setColor(y, BLACK); 
  // 將 x 的父節(jié)點(diǎn)的父節(jié)點(diǎn)設(shè)為紅色
  setColor(parentOf(parentOf(x)), RED); 
  x = parentOf(parentOf(x)); 
  } 
  // 如果 x 的父節(jié)點(diǎn)的兄弟節(jié)點(diǎn)是黑色
  else 
  { 
  // 如果 x 是其父節(jié)點(diǎn)的右子節(jié)點(diǎn)
  if (x == rightOf(parentOf(x))) 
  { 
   // 將 x 的父節(jié)點(diǎn)設(shè)為 x 
   x = parentOf(x); 
   rotateLeft(x); 
  } 
  // 把 x 的父節(jié)點(diǎn)設(shè)為黑色
  setColor(parentOf(x), BLACK); 
  // 把 x 的父節(jié)點(diǎn)的父節(jié)點(diǎn)設(shè)為紅色
  setColor(parentOf(parentOf(x)), RED); 
  rotateRight(parentOf(parentOf(x))); 
  } 
 } 
 // 如果 x 的父節(jié)點(diǎn)是其父節(jié)點(diǎn)的右子節(jié)點(diǎn)
 else 
 { 
  // 獲取 x 的父節(jié)點(diǎn)的兄弟節(jié)點(diǎn)
  Entry<K,V> y = leftOf(parentOf(parentOf(x))); 
  // 如果 x 的父節(jié)點(diǎn)的兄弟節(jié)點(diǎn)是紅色
  if (colorOf(y) == RED) 
  { 
  // 將 x 的父節(jié)點(diǎn)設(shè)為黑色。
  setColor(parentOf(x), BLACK); 
  // 將 x 的父節(jié)點(diǎn)的兄弟節(jié)點(diǎn)設(shè)為黑色
  setColor(y, BLACK); 
  // 將 x 的父節(jié)點(diǎn)的父節(jié)點(diǎn)設(shè)為紅色
  setColor(parentOf(parentOf(x)), RED); 
  // 將 x 設(shè)為 x 的父節(jié)點(diǎn)的節(jié)點(diǎn)
  x = parentOf(parentOf(x)); 
  } 
  // 如果 x 的父節(jié)點(diǎn)的兄弟節(jié)點(diǎn)是黑色
  else 
  { 
  // 如果 x 是其父節(jié)點(diǎn)的左子節(jié)點(diǎn)
  if (x == leftOf(parentOf(x))) 
  { 
   // 將 x 的父節(jié)點(diǎn)設(shè)為 x 
   x = parentOf(x); 
   rotateRight(x); 
  } 
  // 把 x 的父節(jié)點(diǎn)設(shè)為黑色
  setColor(parentOf(x), BLACK); 
  // 把 x 的父節(jié)點(diǎn)的父節(jié)點(diǎn)設(shè)為紅色
  setColor(parentOf(parentOf(x)), RED); 
  rotateLeft(parentOf(parentOf(x))); 
  } 
 } 
 } 
 // 將根節(jié)點(diǎn)設(shè)為黑色
 root.color = BLACK; 
 } 

 刪除節(jié)點(diǎn)后的修復(fù)

與添加節(jié)點(diǎn)之后的修復(fù)類似的是，TreeMap 刪除節(jié)點(diǎn)之后也需要進(jìn)行類似的修復(fù)操作，通過(guò)這種修復(fù)來(lái)保證該排序二叉樹(shù)依然滿足紅黑樹(shù)特征。大家可以參考插入節(jié)點(diǎn)之后的修復(fù)來(lái)分析刪除之后的修復(fù)。TreeMap 在刪除之后的修復(fù)操作由 fixAfterDeletion(Entry<K,V> x) 方法提供，該方法源代碼如下：

 // 刪除節(jié)點(diǎn)后修復(fù)紅黑樹(shù)
 private void fixAfterDeletion(Entry<K,V> x) 
 { 
 // 直到 x 不是根節(jié)點(diǎn)，且 x 的顏色是黑色
 while (x != root && colorOf(x) == BLACK) 
 { 
 // 如果 x 是其父節(jié)點(diǎn)的左子節(jié)點(diǎn)
 if (x == leftOf(parentOf(x))) 
 { 
  // 獲取 x 節(jié)點(diǎn)的兄弟節(jié)點(diǎn)
  Entry<K,V> sib = rightOf(parentOf(x)); 
  // 如果 sib 節(jié)點(diǎn)是紅色
  if (colorOf(sib) == RED) 
  { 
  // 將 sib 節(jié)點(diǎn)設(shè)為黑色
  setColor(sib, BLACK); 
  // 將 x 的父節(jié)點(diǎn)設(shè)為紅色
  setColor(parentOf(x), RED); 
  rotateLeft(parentOf(x)); 
  // 再次將 sib 設(shè)為 x 的父節(jié)點(diǎn)的右子節(jié)點(diǎn)
  sib = rightOf(parentOf(x)); 
  } 
  // 如果 sib 的兩個(gè)子節(jié)點(diǎn)都是黑色
  if (colorOf(leftOf(sib)) == BLACK 
  && colorOf(rightOf(sib)) == BLACK) 
  { 
  // 將 sib 設(shè)為紅色
  setColor(sib, RED); 
  // 讓 x 等于 x 的父節(jié)點(diǎn)
  x = parentOf(x); 
  } 
  else 
  { 
  // 如果 sib 的只有右子節(jié)點(diǎn)是黑色
  if (colorOf(rightOf(sib)) == BLACK) 
  { 
   // 將 sib 的左子節(jié)點(diǎn)也設(shè)為黑色
   setColor(leftOf(sib), BLACK); 
   // 將 sib 設(shè)為紅色
   setColor(sib, RED); 
   rotateRight(sib); 
   sib = rightOf(parentOf(x)); 
  } 
  // 設(shè)置 sib 的顏色與 x 的父節(jié)點(diǎn)的顏色相同
  setColor(sib, colorOf(parentOf(x))); 
  // 將 x 的父節(jié)點(diǎn)設(shè)為黑色
  setColor(parentOf(x), BLACK); 
  // 將 sib 的右子節(jié)點(diǎn)設(shè)為黑色
  setColor(rightOf(sib), BLACK); 
  rotateLeft(parentOf(x)); 
  x = root; 
  } 
 } 
 // 如果 x 是其父節(jié)點(diǎn)的右子節(jié)點(diǎn)
 else 
 { 
  // 獲取 x 節(jié)點(diǎn)的兄弟節(jié)點(diǎn)
  Entry<K,V> sib = leftOf(parentOf(x)); 
  // 如果 sib 的顏色是紅色
  if (colorOf(sib) == RED) 
  { 
  // 將 sib 的顏色設(shè)為黑色
  setColor(sib, BLACK); 
  // 將 sib 的父節(jié)點(diǎn)設(shè)為紅色
  setColor(parentOf(x), RED); 
  rotateRight(parentOf(x)); 
  sib = leftOf(parentOf(x)); 
  } 
  // 如果 sib 的兩個(gè)子節(jié)點(diǎn)都是黑色
  if (colorOf(rightOf(sib)) == BLACK 
  && colorOf(leftOf(sib)) == BLACK) 
  { 
  // 將 sib 設(shè)為紅色
  setColor(sib, RED); 
  // 讓 x 等于 x 的父節(jié)點(diǎn)
  x = parentOf(x); 
  } 
  else 
  { 
  // 如果 sib 只有左子節(jié)點(diǎn)是黑色
  if (colorOf(leftOf(sib)) == BLACK) 
  { 
   // 將 sib 的右子節(jié)點(diǎn)也設(shè)為黑色
   setColor(rightOf(sib), BLACK); 
   // 將 sib 設(shè)為紅色
   setColor(sib, RED); 
   rotateLeft(sib); 
   sib = leftOf(parentOf(x)); 
  } 
  // 將 sib 的顏色設(shè)為與 x 的父節(jié)點(diǎn)顏色相同
  setColor(sib, colorOf(parentOf(x))); 
  // 將 x 的父節(jié)點(diǎn)設(shè)為黑色
  setColor(parentOf(x), BLACK); 
  // 將 sib 的左子節(jié)點(diǎn)設(shè)為黑色
  setColor(leftOf(sib), BLACK); 
  rotateRight(parentOf(x)); 
  x = root; 
  } 
 } 
 } 
 setColor(x, BLACK); 
 } 

檢索節(jié)點(diǎn)

當(dāng) TreeMap 根據(jù) key 來(lái)取出 value 時(shí)，TreeMap 對(duì)應(yīng)的方法如下：

 public V get(Object key) 
 { 
 // 根據(jù)指定 key 取出對(duì)應(yīng)的 Entry 
 Entry>K,V< p = getEntry(key); 
 // 返回該 Entry 所包含的 value 
 return (p==null ? null : p.value); 
 } 

從上面程序的粗體字代碼可以看出，get(Object key) 方法實(shí)質(zhì)是由于 getEntry() 方法實(shí)現(xiàn)的，這個(gè) getEntry() 方法的代碼如下：

 final Entry<K,V> getEntry(Object key) 
 { 
 // 如果 comparator 不為 null，表明程序采用定制排序
 if (comparator != null) 
 // 調(diào)用 getEntryUsingComparator 方法來(lái)取出對(duì)應(yīng)的 key 
 return getEntryUsingComparator(key); 
 // 如果 key 形參的值為 null，拋出 NullPointerException 異常
 if (key == null) 
 throw new NullPointerException(); 
 // 將 key 強(qiáng)制類型轉(zhuǎn)換為 Comparable 實(shí)例
 Comparable<? super K> k = (Comparable<? super K>) key; 
 // 從樹(shù)的根節(jié)點(diǎn)開(kāi)始
 Entry<K,V> p = root; 
 while (p != null) 
 { 
 // 拿 key 與當(dāng)前節(jié)點(diǎn)的 key 進(jìn)行比較
 int cmp = k.compareTo(p.key); 
 // 如果 key 小于當(dāng)前節(jié)點(diǎn)的 key，向“左子樹(shù)”搜索
 if (cmp < 0) 
  p = p.left; 
 // 如果 key 大于當(dāng)前節(jié)點(diǎn)的 key，向“右子樹(shù)”搜索
 else if (cmp > 0) 
  p = p.right; 
 // 不大于、不小于，就是找到了目標(biāo) Entry 
 else 
  return p; 
 } 
 return null; 
 } 

上面的 getEntry(Object obj) 方法也是充分利用排序二叉樹(shù)的特征來(lái)搜索目標(biāo) Entry，程序依然從二叉樹(shù)的根節(jié)點(diǎn)開(kāi)始，如果被搜索節(jié)點(diǎn)大于當(dāng)前節(jié)點(diǎn)，程序向“右子樹(shù)”搜索；如果被搜索節(jié)點(diǎn)小于當(dāng)前節(jié)點(diǎn)，程序向“左子樹(shù)”搜索；如果相等，那就是找到了指定節(jié)點(diǎn)。

當(dāng) TreeMap 里的 comparator != null 即表明該 TreeMap 采用了定制排序，在采用定制排序的方式下，TreeMap 采用 getEntryUsingComparator(key) 方法來(lái)根據(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é)點(diǎn)開(kāi)始
 Entry<K,V> p = root; 
 while (p != null) 
 { 
  // 拿 key 與當(dāng)前節(jié)點(diǎn)的 key 進(jìn)行比較
  int cmp = cpr.compare(k, p.key); 
  // 如果 key 小于當(dāng)前節(jié)點(diǎn)的 key，向“左子樹(shù)”搜索
  if (cmp < 0) 
  p = p.left; 
  // 如果 key 大于當(dāng)前節(jié)點(diǎn)的 key，向“右子樹(shù)”搜索
  else if (cmp > 0) 
  p = p.right; 
  // 不大于、不小于，就是找到了目標(biāo) Entry 
  else 
  return p; 
 } 
 } 
 return null; 
 } 

其實(shí) getEntry、getEntryUsingComparator 兩個(gè)方法的實(shí)現(xiàn)思路完全類似，只是前者對(duì)自然排序的 TreeMap 獲取有效，后者對(duì)定制排序的 TreeMap 有效。

通過(guò)上面源代碼的分析不難看出，TreeMap 這個(gè)工具類的實(shí)現(xiàn)其實(shí)很簡(jiǎn)單?；蛘哒f(shuō)：從內(nèi)部結(jié)構(gòu)來(lái)看，TreeMap 本質(zhì)上就是一棵“紅黑樹(shù)”，而 TreeMap 的每個(gè) Entry 就是該紅黑樹(shù)的一個(gè)節(jié)點(diǎn)。

以上就是本文的全部?jī)?nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。