日韩无码专区无码一级三级片|91人人爱网站中日韩无码电影|厨房大战丰满熟妇|AV高清无码在线免费观看|另类AV日韩少妇熟女|中文日本大黄一级黄色片|色情在线视频免费|亚洲成人特黄a片|黄片wwwav色图欧美|欧亚乱色一区二区三区

RELATEED CONSULTING
相關咨詢
選擇下列產(chǎn)品馬上在線溝通
服務時間：8:30-17:00
你可能遇到了下面的問題
關閉右側工具欄

新聞中心

這里有您想知道的互聯(lián)網(wǎng)營銷解決方案
3分鐘讓你明白：HashMap之紅黑樹樹化過程

 01 概述

HashMap是Java程序員使用頻率最高的用于映射(鍵值對)處理的數(shù)據(jù)類型。隨著JDK(Java Developmet Kit)版本的更新，JDK1.8對HashMap底層的實現(xiàn)進行了優(yōu)化，例如引入紅黑樹的數(shù)據(jù)結構和擴容的優(yōu)化等。本文主要分析一下HashMap中紅黑樹樹化的過程。

02 紅黑樹(red black tree)

一個節(jié)點標記為紅色或者黑色。 根是黑色的。 如果一個節(jié)點是紅色的，那么它的子節(jié)點必須是黑色的(這就是為什么叫紅黑樹)。 一個節(jié)點到到一個null引用的每一條路徑必須包含相同數(shù)目的黑色節(jié)點(所以紅色節(jié)點不影響)。 其實RB Tree和著名的AVL Tree有很多相同的地方，困難的地方都在于將一個新項插入到樹中。了解AVL Tree的朋友應該都知道為了維持樹的高度必須在插入一個新的項后必須在樹的結構上進行改變，這里主要是通過旋轉，當然在RB Tree中原理也是如此。

03 兩種旋轉和一種典型的變換

旋轉的方向：

變換過程：

互相關聯(lián)：

單向關聯(lián)：

代表紅色的節(jié)點：

代表黑色的節(jié)點：

代表一個不會破壞紅黑樹結構的部分，可能是節(jié)點，或者是一個子樹，總之不會破環(huán)當前樹的結構。這個部分會由于旋轉而連接到其他的節(jié)點后面，我們可以理解成由于重力原因它掉到了下面的節(jié)點上：

  • 單旋轉變換。
  • 雙旋轉變換(需要兩次反方向的單旋轉)。
  • 當遇到兩個子幾點都為紅色的話執(zhí)行顏色變換，因為插入 是紅色的會產(chǎn)生沖突。如果根節(jié)點兩邊的子節(jié)點都是紅色，兩個葉子節(jié)點變成黑色，根節(jié)點變成紅色，然后再將根節(jié)點變成黑色。

上面的圖中描述了紅黑樹中三種典型的變換，其實前兩種變換這正是AVL Tree中的兩種典型的變換。

04 幾個問題

4.1 為什么要進行旋轉?

由于P和X節(jié)點都為紅色節(jié)點這破環(huán)了紅節(jié)點下面的節(jié)點必須為黑色節(jié)點的規(guī)則。

4.2 新加入的節(jié)點總是紅色的，這是為什么呢?

因為被插入前的樹結構是構建好的，一但我們進行添加黑色的節(jié)點，無論添加在哪里都會破壞原有路徑上的黑色節(jié)點的數(shù)量平等關系，所以插入紅色節(jié)點是正確的選擇。

4.3 為什么要進行顏色變換?

正如第一種旋轉新加入的節(jié)點X破壞了紅黑樹的結構不得不進行旋轉，后面的就是旋轉后的結果，旋轉后形成新的結構，此時我們發(fā)現(xiàn)兩個子節(jié)點都是紅色的所以執(zhí)行第三個變換特性，顏色變換，因為如果子節(jié)點是紅色的那么我們在添加的時候只能添加黑色的節(jié)點，然而添加任何黑色葉子節(jié)點都會破壞樹的第四條性質，所以要對其進行變換。當進行變換后葉子節(jié)點是紅色的而且我們默認添加的葉子節(jié)點是紅色的，所以添加到黑色節(jié)點后并不會破壞樹的第四條結構，所以這種變換很有用。

第二種雙變換中在樹的內(nèi)部怎么出現(xiàn)的紅色的節(jié)點? 正是由于上面的顏色變換導致新顏色變換后的節(jié)點與他的父節(jié)點產(chǎn)生了顏色沖突。

與AVL樹相比? 比AVL樹相比優(yōu)點是不用在節(jié)點類中保存一個節(jié)點高度這個變量，節(jié)省了內(nèi)存。

而且紅黑樹一般不是以遞歸方式實現(xiàn)的而是以循環(huán)的形式實現(xiàn)。

一般的操作在最壞情形下花費O(logN)時間。

05 好了有了這些基本的概念讓我們?nèi)タ匆幌翲ashMap中的代碼的實現(xiàn)

 
 
 
 
    
  
  
  
  
  1. final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) 
    2. 
  
  
  
  
  2.  { 
    3. 
  
  
  
  
  3.  Node[] tab; 
    4. 
  
  
  
  
  4.  Node p; 
    5. 
  
  
  
  
  5.  int n, i; 
    6. 
  
  
  
  
  6.  if ((tab = table) == null || (n = tab.length) == 0) 
    7. 
  
  
  
  
  7.  n = (tab = resize()).length; 
    8. 
  
  
  
  
  8.  if ((p = tab[i = (n - 1) & hash]) == null) 
    9. 
  
  
  
  
  9.  tab[i] = newNode(hash, key, value, null); 
    10. 
  
  
  
  
  10.  else 
    11. 
  
  
  
  
  11.  { 
    12. 
  
  
  
  
  12.  Node e; 
    13. 
  
  
  
  
  13.  K k; 
    14. 
  
  
  
  
  14.  if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) 
    15. 
  
  
  
  
  15.  e = p; 
    16. 
  
  
  
  
  16.  else if (p instanceof TreeNode) 
    17. 
  
  
  
  
  17.  // 如果當前的bucket里面已經(jīng)是紅黑樹的話，執(zhí)行紅黑樹的添加操作 
    18. 
  
  
  
  
  18.  e = ((TreeNode) p).putTreeVal(this, tab, hash, key, value); 
    19. 
  
  
  
  
  19.  else 
    20. 
  
  
  
  
  20.  { 
    21. 
  
  
  
  
  21.  for (int binCount = 0;; ++binCount) 
    22. 
  
  
  
  
  22.  { 
    23. 
  
  
  
  
  23.  if ((e = p.next) == null) 
    24. 
  
  
  
  
  24.  { 
    25. 
  
  
  
  
  25.  p.next = newNode(hash, key, value, null); 
    26. 
  
  
  
  
  26.  // TREEIFY_THRESHOLD = 8，判斷如果當前bucket的位置鏈表長度大于8的話就將此鏈表變成紅黑樹。 
    27. 
  
  
  
  
  27.  if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st 
    28. 
  
  
  
  
  28.  treeifyBin(tab, hash); 
    29. 
  
  
  
  
  29.  break; 
    30. 
  
  
  
  
  30.  } 
    31. 
  
  
  
  
  31.  if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) 
    32. 
  
  
  
  
  32.  break; 
    33. 
  
  
  
  
  33.  p = e; 
    34. 
  
  
  
  
  34.  } 
    35. 
  
  
  
  
  35.  } 
    36. 
  
  
  
  
  36.  if (e != null) 
    37. 
  
  
  
  
  37.  { // existing mapping for key 
    38. 
  
  
  
  
  38.  V oldValue = e.value; 
    39. 
  
  
  
  
  39.  if (!onlyIfAbsent || oldValue == null) 
    40. 
  
  
  
  
  40.  e.value = value; 
    41. 
  
  
  
  
  41.  afterNodeAccess(e); 
    42. 
  
  
  
  
  42.  return oldValue; 
    43. 
  
  
  
  
  43.  } 
    44. 
  
  
  
  
  44.  } 
    45. 
  
  
  
  
  45.  ++modCount; 
    46. 
  
  
  
  
  46.  if (++size > threshold) 
    47. 
  
  
  
  
  47.  resize(); 
    48. 
  
  
  
  
  48.  afterNodeInsertion(evict); 
    49. 
  
  
  
  
  49.  return null; 
    50. 
  
  
  
  
  50.  } 
    51.

上面的方法通過hash計算插入的項的槽位，如果有是一樣的key則根據(jù)設置的參數(shù)是否執(zhí)行覆蓋，如果相應槽位空的話直接插入，如果對應的槽位有項則判斷是紅黑樹結構還是鏈表結構的槽位，鏈表的話則順著鏈表尋找如果找到一樣的key則根據(jù)參數(shù)選擇覆蓋，沒有找到則鏈接在鏈表最后面，鏈表項的數(shù)目大于8則對其進行樹化，如果是紅黑樹結構則按照樹的添加方式添加項。

讓我們看一下treeifyBin這個方法。

 
 
 
 
    
  
  
  
  
  1. final void treeifyBin(Node[] tab, int hash) 
    2. 
  
  
  
  
  2.  { 
    3. 
  
  
  
  
  3.  int n, index; 
    4. 
  
  
  
  
  4.  Node e; 
    5. 
  
  
  
  
  5.  if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) 
    6. 
  
  
  
  
  6.  // resize()方法這里不過多介紹，感興趣的可以去看上面的鏈接。 
    7. 
  
  
  
  
  7.  resize(); 
    8. 
  
  
  
  
  8.  // 通過hash求出bucket的位置。 
    9. 
  
  
  
  
  9.  else if ((e = tab[index = (n - 1) & hash]) != null) 
    10. 
  
  
  
  
  10.  { 
    11. 
  
  
  
  
  11.  TreeNode hd = null, tl = null; 
    12. 
  
  
  
  
  12.  do 
    13. 
  
  
  
  
  13.  { 
    14. 
  
  
  
  
  14.  // 將每個節(jié)點包裝成TreeNode。 
    15. 
  
  
  
  
  15.  TreeNode p = replacementTreeNode(e, null); 
    16. 
  
  
  
  
  16.  if (tl == null) 
    17. 
  
  
  
  
  17.  hd = p; 
    18. 
  
  
  
  
  18.  else 
    19. 
  
  
  
  
  19.  { 
    20. 
  
  
  
  
  20.  // 將所有TreeNode連接在一起此時只是鏈表結構。 
    21. 
  
  
  
  
  21.  p.prev = tl; 
    22. 
  
  
  
  
  22.  tl.next = p; 
    23. 
  
  
  
  
  23.  } 
    24. 
  
  
  
  
  24.  tl = p; 
    25. 
  
  
  
  
  25.  } while ((e = e.next) != null); 
    26. 
  
  
  
  
  26.  if ((tab[index] = hd) != null) 
    27. 
  
  
  
  
  27.  // 對TreeNode鏈表進行樹化。 
    28. 
  
  
  
  
  28.  hd.treeify(tab); 
    29. 
  
  
  
  
  29.  } 
    30. 
  
  
  
  
  30.  } 
    31.

找個方法所做的事情就是將剛才九個項以鏈表的方式連接在一起，然后通過它構建紅黑樹。

看代碼之前我們先了解一下TreeNode

 
 
 
 
    
  
  
  
  
  1. static final class TreeNode extends LinkedHashMap.Entry 
    2. 
  
  
  
  
  2.  { 
    3. 
  
  
  
  
  3.  TreeNode parent; // red-black tree links 
    4. 
  
  
  
  
  4.  TreeNode left; 
    5. 
  
  
  
  
  5.  TreeNode right; 
    6. 
  
  
  
  
  6.  TreeNode prev; // needed to unlink next upon deletion 
    7. 
  
  
  
  
  7.  boolean red; 
    8. 
  
  
  
  
  8.  TreeNode(int hash, K key, V val, Node next) 
    9. 
  
  
  
  
  9.  { 
    10. 
  
  
  
  
  10.  super(hash, key, val, next); 
    11. 
  
  
  
  
  11.  } 
    12. 
  
  
  
  
  12.   
    13. 
  
  
  
  
  13.  final void treeify(Node[] tab) 
    14. 
  
  
  
  
  14.  { 
    15. 
  
  
  
  
  15.  // ...... 
    16. 
  
  
  
  
  16.  } 
    17. 
  
  
  
  
  17.   
    18. 
  
  
  
  
  18.  static  TreeNode balanceInsertion(TreeNode root, TreeNode x) 
    19. 
  
  
  
  
  19.  { 
    20. 
  
  
  
  
  20.  // ...... 
    21. 
  
  
  
  
  21.  } 
    22. 
  
  
  
  
  22.   
    23. 
  
  
  
  
  23.  static  TreeNode rotateLeft(TreeNode root, TreeNode p) 
    24. 
  
  
  
  
  24.  { 
    25. 
  
  
  
  
  25.  // ...... 
    26. 
  
  
  
  
  26.  } 
    27. 
  
  
  
  
  27.   
    28. 
  
  
  
  
  28.  static  TreeNode rotateRight(TreeNode root, TreeNode p) 
    29. 
  
  
  
  
  29.  { 
    30. 
  
  
  
  
  30.  // ...... 
    31. 
  
  
  
  
  31.  } 
    32. 
  
  
  
  
  32.   
    33. 
  
  
  
  
  33.  // ......其余方法省略 
    34. 
  
  
  
  
  34.  } 
    35.

可以看出出真正的維護紅黑樹結構的方法并沒有在HashMap中，全部都在TreeNode類內(nèi)部。

我們看一下treeify代碼

 
 
 
 
    
  
  
  
  
  1. final void treeify(Node[] tab) 
    2. 
  
  
  
  
  2.  { 
    3. 
  
  
  
  
  3.  TreeNode root = null; 
    4. 
  
  
  
  
  4.  // 以for循環(huán)的方式遍歷剛才我們創(chuàng)建的鏈表。 
    5. 
  
  
  
  
  5.  for (TreeNode x = this, next; x != null; x = next) 
    6. 
  
  
  
  
  6.  { 
    7. 
  
  
  
  
  7.  // next向前推進。 
    8. 
  
  
  
  
  8.  next = (TreeNode) x.next; 
    9. 
  
  
  
  
  9.  x.left = x.right = null; 
    10. 
  
  
  
  
  10.  // 為樹根節(jié)點賦值。 
    11. 
  
  
  
  
  11.  if (root == null) 
    12. 
  
  
  
  
  12.  { 
    13. 
  
  
  
  
  13.  x.parent = null; 
    14. 
  
  
  
  
  14.  x.red = false; 
    15. 
  
  
  
  
  15.  root = x; 
    16. 
  
  
  
  
  16.  } else 
    17. 
  
  
  
  
  17.  { 
    18. 
  
  
  
  
  18.  // x即為當前訪問鏈表中的項。 
    19. 
  
  
  
  
  19.  K k = x.key; 
    20. 
  
  
  
  
  20.  int h = x.hash; 
    21. 
  
  
  
  
  21.  Class kc = null; 
    22. 
  
  
  
  
  22.  // 此時紅黑樹已經(jīng)有了根節(jié)點，上面獲取了當前加入紅黑樹的項的key和hash值進入核心循環(huán)。 
    23. 
  
  
  
  
  23.  // 這里從root開始，是以一個自頂向下的方式遍歷添加。 
    24. 
  
  
  
  
  24.  // for循環(huán)沒有控制條件，由代碼內(nèi)break跳出循環(huán)。 
    25. 
  
  
  
  
  25.  for (TreeNode p = root;;) 
    26. 
  
  
  
  
  26.  { 
    27. 
  
  
  
  
  27.  // dir：directory，比較添加項與當前樹中訪問節(jié)點的hash值判斷加入項的路徑，-1為左子樹，+1為右子樹。 
    28. 
  
  
  
  
  28.  // ph：parent hash。 
    29. 
  
  
  
  
  29.  int dir, ph; 
    30. 
  
  
  
  
  30.  K pk = p.key; 
    31. 
  
  
  
  
  31.  if ((ph = p.hash) > h) 
    32. 
  
  
  
  
  32.  dir = -1; 
    33. 
  
  
  
  
  33.  else if (ph < h) 
    34. 
  
  
  
  
  34.  dir = 1; 
    35. 
  
  
  
  
  35.  else if ((kc == null && (kc = comparableClassFor(k)) == null) 
    36. 
  
  
  
  
  36.  || (dir = compareComparables(kc, k, pk)) == 0) 
    37. 
  
  
  
  
  37.  dir = tieBreakOrder(k, pk); 
    38. 
  
  
  
  
  38.  // xp：x parent。 
    39. 
  
  
  
  
  39.  TreeNode xp = p; 
    40. 
  
  
  
  
  40.  // 找到符合x添加條件的節(jié)點。 
    41. 
  
  
  
  
  41.  if ((p = (dir <= 0) ? p.left : p.right) == null) 
    42. 
  
  
  
  
  42.  { 
    43. 
  
  
  
  
  43.  x.parent = xp; 
    44. 
  
  
  
  
  44.  // 如果xp的hash值大于x的hash值，將x添加在xp的左邊。 
    45. 
  
  
  
  
  45.  if (dir <= 0) 
    46. 
  
  
  
  
  46.  xp.left = x; 
    47. 
  
  
  
  
  47.  // 反之添加在xp的右邊。 
    48. 
  
  
  
  
  48.  else 
    49. 
  
  
  
  
  49.  xp.right = x; 
    50. 
  
  
  
  
  50.  // 維護添加后紅黑樹的紅黑結構。 
    51. 
  
  
  
  
  51.  root = balanceInsertion(root, x); 
    52. 
  
  
  
  
  52.   
    53. 
  
  
  
  
  53.  // 跳出循環(huán)當前鏈表中的項成功的添加到了紅黑樹中。 
    54. 
  
  
  
  
  54.  break; 
    55. 
  
  
  
  
  55.  } 
    56. 
  
  
  
  
  56.  } 
    57. 
  
  
  
  
  57.  } 
    58. 
  
  
  
  
  58.  } 
    59. 
  
  
  
  
  59.  // Ensures that the given root is the first node of its bin，自己翻譯一下。 
    60. 
  
  
  
  
  60.  moveRootToFront(tab, root); 
    61. 
  
  
  
  
  61.  } 
    62.

第一次循環(huán)會將鏈表中的首節(jié)點作為紅黑樹的根，而后的循環(huán)會將鏈表中的的項通過比較hash值然后連接到相應樹節(jié)點的左邊或者右邊，插入可能會破壞樹的結構所以接著執(zhí)行balanceInsertion。

我們看balanceInsertion

 
 
 
 
    
  
  
  
  
  1. static  TreeNode balanceInsertion(TreeNode root, TreeNode x) 
    2. 
  
  
  
  
  2.  { 
    3. 
  
  
  
  
  3.  // 正如開頭所說，新加入樹節(jié)點默認都是紅色的，不會破壞樹的結構。 
    4. 
  
  
  
  
  4.  x.red = true; 
    5. 
  
  
  
  
  5.  // 這些變量名不是作者隨便定義的都是有意義的。 
    6. 
  
  
  
  
  6.  // xp：x parent，代表x的父節(jié)點。 
    7. 
  
  
  
  
  7.  // xpp：x parent parent，代表x的祖父節(jié)點 
    8. 
  
  
  
  
  8.  // xppl：x parent parent left，代表x的祖父的左節(jié)點。 
    9. 
  
  
  
  
  9.  // xppr：x parent parent right，代表x的祖父的右節(jié)點。 
    10. 
  
  
  
  
  10.  for (TreeNode xp, xpp, xppl, xppr;;) 
    11. 
  
  
  
  
  11.  { 
    12. 
  
  
  
  
  12.  // 如果x的父節(jié)點為null說明只有一個節(jié)點，該節(jié)點為根節(jié)點，根節(jié)點為黑色，red = false。 
    13. 
  
  
  
  
  13.  if ((xp = x.parent) == null) 
    14. 
  
  
  
  
  14.  { 
    15. 
  
  
  
  
  15.  x.red = false; 
    16. 
  
  
  
  
  16.  return x; 
    17. 
  
  
  
  
  17.  }  
    18. 
  
  
  
  
  18.  // 進入else說明不是根節(jié)點。 
    19. 
  
  
  
  
  19.  // 如果父節(jié)點是黑色，那么大吉大利（今晚吃雞），紅色的x節(jié)點可以直接添加到黑色節(jié)點后面，返回根就行了不需要任何多余的操作。 
    20. 
  
  
  
  
  20.  // 如果父節(jié)點是紅色的，但祖父節(jié)點為空的話也可以直接返回根此時父節(jié)點就是根節(jié)點，因為根必須是黑色的，添加在后面沒有任何問題。 
    21. 
  
  
  
  
  21.  else if (!xp.red || (xpp = xp.parent) == null) 
    22. 
  
  
  
  
  22.  return root; 
    23. 
  
  
  
  
  23.   
    24. 
  
  
  
  
  24.  // 一旦我們進入到這里就說明了兩件是情 
    25. 
  
  
  
  
  25.  // 1.x的父節(jié)點xp是紅色的，這樣就遇到兩個紅色節(jié)點相連的問題，所以必須經(jīng)過旋轉變換。 
    26. 
  
  
  
  
  26.  // 2.x的祖父節(jié)點xpp不為空。 
    27. 
  
  
  
  
  27.   
    28. 
  
  
  
  
  28.  // 判斷如果父節(jié)點是否是祖父節(jié)點的左節(jié)點 
    29. 
  
  
  
  
  29.  if (xp == (xppl = xpp.left)) 
    30. 
  
  
  
  
  30.  { 
    31. 
  
  
  
  
  31.  // 父節(jié)點xp是祖父的左節(jié)點xppr 
    32. 
  
  
  
  
  32.  // 判斷祖父節(jié)點的右節(jié)點不為空并且是否是紅色的 
    33. 
  
  
  
  
  33.  // 此時xpp的左右節(jié)點都是紅的，所以直接進行上面所說的第三種變換，將兩個子節(jié)點變成黑色，將xpp變成紅色，然后將紅色節(jié)點x順利的添加到了xp的后面。 
    34. 
  
  
  
  
  34.  // 這里大家有疑問為什么將x = xpp？ 
    35. 
  
  
  
  
  35.  // 這是由于將xpp變成紅色以后可能與xpp的父節(jié)點發(fā)生兩個相連紅色節(jié)點的沖突，這就又構成了第二種旋轉變換，所以必須從底向上的進行變換，直到根。 
    36. 
  
  
  
  
  36.  // 所以令x = xpp，然后進行下下一層循環(huán)，接著往上走。 
    37. 
  
  
  
  
  37.  if ((xppr = xpp.right) != null && xppr.red) 
    38. 
  
  
  
  
  38.  { 
    39. 
  
  
  
  
  39.  xppr.red = false; 
    40. 
  
  
  
  
  40.  xp.red = false; 
    41. 
  
  
  
  
  41.  xpp.red = true; 
    42. 
  
  
  
  
  42.  x = xpp; 
    43. 
  
  
  
  
  43.  } 
    44. 
  
  
  
  
  44.  // 進入到這個else里面說明。 
    45. 
  
  
  
  
  45.  // 父節(jié)點xp是祖父的左節(jié)點xppr。 
    46. 
  
  
  
  
  46.  // 祖父節(jié)點xpp的右節(jié)點xppr是黑色節(jié)點或者為空，默認規(guī)定空節(jié)點也是黑色的。 
    47. 
  
  
  
  
  47.  // 下面要判斷x是xp的左節(jié)點還是右節(jié)點。 
    48. 
  
  
  
  
  48.  else 
    49. 
  
  
  
  
  49.  { 
    50. 
  
  
  
  
  50.  // x是xp的右節(jié)點，此時的結構是：xpp左->xp右->x。這明顯是第二中變換需要進行兩次旋轉，這里先進行一次旋轉。 
    51. 
  
  
  
  
  51.  // 下面是第一次旋轉。 
    52. 
  
  
  
  
  52.  if (x == xp.right) 
    53. 
  
  
  
  
  53.  { 
    54. 
  
  
  
  
  54.  root = rotateLeft(root, x = xp); 
    55. 
  
  
  
  
  55.  xpp = (xp = x.parent) == null ? null : xp.parent; 
    56. 
  
  
  
  
  56.  } 
    57. 
  
  
  
  
  57.  // 針對本身就是xpp左->xp左->x的結構或者由于上面的旋轉造成的這種結構進行一次旋轉。 
    58. 
  
  
  
  
  58.  if (xp != null) 
    59. 
  
  
  
  
  59.  { 
    60. 
  
  
  
  
  60.  xp.red = false; 
    61. 
  
  
  
  
  61.  if (xpp != null) 
    62. 
  
  
  
  
  62.  { 
    63. 
  
  
  
  
  63.  xpp.red = true; 
    64. 
  
  
  
  
  64.  root = rotateRight(root, xpp); 
    65. 
  
  
  
  
  65.  } 
    66. 
  
  
  
  
  66.  } 
    67. 
  
  
  
  
  67.  } 
    68. 
  
  
  
  
  68.  }  
    69. 
  
  
  
  
  69.  // 這里的分析方式和前面的相對稱只不過全部在右測不再重復分析。 
    70. 
  
  
  
  
  70.  else 
    71. 
  
  
  
  
  71.  { 
    72. 
  
  
  
  
  72.  if (xppl != null && xppl.red) 
    73. 
  
  
  
  
  73.  { 
    74. 
  
  
  
  
  74.  xppl.red = false; 
    75. 
  
  
  
  
  75.  xp.red = false; 
    76. 
  
  
  
  
  76.  xpp.red = true; 
    77. 
  
  
  
  
  77.  x = xpp; 
    78. 
  
  
  
  
  78.  } else 
    79. 
  
  
  
  
  79.  { 
    80. 
  
  
  
  
  80.  if (x == xp.left) 
    81. 
  
  
  
  
  81.  { 
    82. 
  
  
  
  
  82.  root = rotateRight(root, x = xp); 
    83. 
  
  
  
  
  83.  xpp = (xp = x.parent) == null ? null : xp.parent; 
    84. 
  
  
  
  
  84.  } 
    85. 
  
  
  
  
  85.  if (xp != null) 
    86. 
  
  
  
  
  86.  { 
    87. 
  
  
  
  
  87.  xp.red = false; 
    88. 
  
  
  
  
  88.  if (xpp != null) 
    89. 
  
  
  
  
  89.  { 
    90. 
  
  
  
  
  90.  xpp.red = true; 
    91. 
  
  
  
  
  91.  root = rotateLeft(root, xpp); 
    92. 
  
  
  
  
  92.  } 
    93. 
  
  
  
  
  93.  } 
    94. 
  
  
  
  
  94.  } 
    95. 
  
  
  
  
  95.  } 
    96. 
  
  
  
  
  96.  } 
    97. 
  
  
  
  
  97.  } 
    98.

如果您的聯(lián)想能力很強的話估計到這里應該已經(jīng)理解這集中變換的主要的關系。

下面簡述一下前面的兩種種幸運的情況

x本身為根節(jié)點返回x。 x的父節(jié)點為黑色或者x的父節(jié)點是根節(jié)點直接返回不需要變換。 如若上述兩個條件不滿足的話，就要進行變換了，允許我再貼一點代碼......沒有代碼分析起來很困難。

06 顏色變換

 
 
 
 
    
  
  
  
  
  1. if (xp == (xppl = xpp.left)) 
    2. 
  
  
  
  
  2.  { 
    3. 
  
  
  
  
  3.  if ((xppr = xpp.right) != null && xppr.red) 
    4. 
  
  
  
  
  4.  { 
    5. 
  
  
  
  
  5.  xppr.red = false; 
    6. 
  
  
  
  
  6.  xp.red = false; 
    7. 
  
  
  
  
  7.  xpp.red = true; 
    8. 
  
  
  
  
  8.  x = xpp; 
    9. 
  
  
  
  
  9.  } 
    10. 
  
  
  
  
  10. } 
    11.

這里是一個典型的一個黑色節(jié)點的兩個子節(jié)點都是紅色的所以要進行顏色變換，因為插入的都是紅色節(jié)點，當檢測到祖父節(jié)點的左右子節(jié)點都是紅色的時候兩個紅色就產(chǎn)生了沖突，所以先將節(jié)點進行這種顏色變換，將祖父節(jié)點變成紅色，然后將祖父的兩個子節(jié)點變成黑色，這樣我們插入的紅色節(jié)點就不會違背紅黑樹的規(guī)則了。

這里有人會有疑問，如果祖父節(jié)點是根節(jié)點呢，那樣的話祖父節(jié)點也會變成黑色，因為每次循環(huán)進行插入平衡的操作當進行這種顏色變換之后都會將插入節(jié)點的引用指向祖父節(jié)點，當進行下一輪循環(huán)的時候會優(yōu)先檢測當前節(jié)點是否是根節(jié)點，如果是根節(jié)點那就將顏色變成黑色，下面看圖：

當將節(jié)點指向祖父節(jié)點進行下一輪循環(huán)時：

07 兩個核心旋轉(左旋轉和右旋轉)

 
 
 
 
    
  
  
  
  
  1. // 一旦我們進入到這里就說明了兩件是情 
    2. 
  
  
  
  
  2.  // 1.x的父節(jié)點xp是紅色的，這樣就遇到兩個紅色節(jié)點相連的問題，所以必須經(jīng)過旋轉變換。 
    3. 
  
  
  
  
  3.  // 2.x的祖父節(jié)點xpp不為空。 
    4. 
  
  
  
  
  4.   
    5. 
  
  
  
  
  5.  // 判斷如果父節(jié)點是否是祖父節(jié)點的左節(jié)點 
    6. 
  
  
  
  
  6.  if (xp == (xppl = xpp.left)) 
    7. 
  
  
  
  
  7.  { 
    8. 
  
  
  
  
  8.  if ((xppr = xpp.right) != null && xppr.red) 
    9. 
  
  
  
  
  9.  {// ...... 
    10. 
  
  
  
  
  10.  } 
    11. 
  
  
  
  
  11.  // 進入到這個else里面說明。 
    12. 
  
  
  
  
  12.  // 父節(jié)點xp是祖父的左節(jié)點xppr。 
    13. 
  
  
  
  
  13.  // 祖父節(jié)點xpp的右節(jié)點xppr是黑色節(jié)點或者為空，默認規(guī)定空節(jié)點也是黑色的。 
    14. 
  
  
  
  
  14.  // 下面要判斷x是xp的左節(jié)點還是右節(jié)點。 
    15. 
  
  
  
  
  15.  else 
    16. 
  
  
  
  
  16.  { 
    17. 
  
  
  
  
  17.  // x是xp的右節(jié)點，此時的結構是：xpp左->xp右->x。這明顯是第二中變換需要進行兩次旋轉，這里先進行一次旋轉。 
    18. 
  
  
  
  
  18.  // 下面是第一次旋轉。 
    19. 
  
  
  
  
  19.  if (x == xp.right) 
    20. 
  
  
  
  
  20.  { 
    21. 
  
  
  
  
  21.  root = rotateLeft(root, x = xp); 
    22. 
  
  
  
  
  22.  xpp = (xp = x.parent) == null ? null : xp.parent; 
    23. 
  
  
  
  
  23.  } 
    24. 
  
  
  
  
  24.  // 針對本身就是xpp左->xp左->x的結構或者由于上面的旋轉造成的這種結構進行一次旋轉。 
    25. 
  
  
  
  
  25.  if (xp != null) 
    26. 
  
  
  
  
  26.  { 
    27. 
  
  
  
  
  27.  xp.red = false; 
    28. 
  
  
  
  
  28.  if (xpp != null) 
    29. 
  
  
  
  
  29.  { 
    30. 
  
  
  
  
  30.  xpp.red = true; 
    31. 
  
  
  
  
  31.  root = rotateRight(root, xpp); 
    32. 
  
  
  
  
  32.  } 
    33. 
  
  
  
  
  33.  } 
    34. 
  
  
  
  
  34.  } 
    35. 
  
  
  
  
  35.  }  
    36.

顏色變換完成后進入下面的else塊

我們已知xp是xpp的左節(jié)點，首先判斷了x是xp的左節(jié)點還是右節(jié)點，如果是右節(jié)點的話構成了下面的結構。

這中結構需要進行雙旋轉，首先先進行一次向左旋轉。

7.1 左旋轉

 
 
 
 
    
  
  
  
  
  1.  1 static  TreeNode rotateLeft(TreeNode root, TreeNode p) 
    2. 
  
  
  
  
  2.  2 { 
    3. 
  
  
  
  
  3.  3 // r：right，右節(jié)點。 
    4. 
  
  
  
  
  4.  4 // pp：parent parent，父節(jié)點的父節(jié)點。 
    5. 
  
  
  
  
  5.  5 // rl：right left，右節(jié)點的左節(jié)點。 
    6. 
  
  
  
  
  6.  6 TreeNode r, pp, rl; 
    7. 
  
  
  
  
  7.  7 if (p != null && (r = p.right) != null) 
    8. 
  
  
  
  
  8.  8 { 
    9. 
  
  
  
  
  9.  9 if ((rl = p.right = r.left) != null) 
    10. 
  
  
  
  
  10. 10 rl.parent = p; 
    11. 
  
  
  
  
  11. 11 if ((pp = r.parent = p.parent) == null) 
    12. 
  
  
  
  
  12. 12 (root = r).red = false; 
    13. 
  
  
  
  
  13. 13 else if (pp.left == p) 
    14. 
  
  
  
  
  14. 14 pp.left = r; 
    15. 
  
  
  
  
  15. 15 else 
    16. 
  
  
  
  
  16. 16 pp.right = r; 
    17. 
  
  
  
  
  17. 17 r.left = p; 
    18. 
  
  
  
  
  18. 18 p.parent = r; 
    19. 
  
  
  
  
  19. 19 } 
    20. 
  
  
  
  
  20. 20 return root; 
    21. 
  
  
  
  
  21. 21 } 
    22.

1.剛進入方法時，狀態(tài)如下圖。(RL可能是空的)

2.進入了if塊后執(zhí)行到第10行后。

 
 
 
 
    
  
  
  
  
  1. 9 if ((rl = p.right = r.left) != null) 
    2. 
  
  
  
  
  2. 10 rl.parent = p; 
    3.

此時如果9行的條件符合的話執(zhí)行10行RL指向P，如果RL為null的話，P的右節(jié)點指向null。

3.接著看11和12行代碼。

 
 
 
 
    
  
  
  
  
  1. 11 if ((pp = r.parent = p.parent) == null) 
    2. 
  
  
  
  
  2. 12 (root = r).red = false; 
    3.

首先我們看11行if里面的賦值語句所造成的影響。

在if里面的表達式不管符不符合條件()內(nèi)的內(nèi)容都會執(zhí)行。

如果符合條件的話會執(zhí)行12行的代碼，變成了下面的結果。

由于PP為空所以只剩下這三個。

4.如果11行的條件為假的話，執(zhí)行完11行()內(nèi)的表達式后執(zhí)行13行

 
 
 
 
    
  
  
  
  
  1. 13 else if (pp.left == p) 
    2. 
  
  
  
  
  2. 14 pp.left = r; 
    3.

滿足條件的話R和PP互相關聯(lián)。

5.由于進入了13和14行所以不進入15和16行的else語句。

 
 
 
 
    
  
  
  
  
  1. 15 else 
    2. 
  
  
  
  
  2. 16 pp.right = r; 
    3.

6.看17和18行。

 
 
 
 
    
  
  
  
  
  1. 17 r.left = p; 
    2. 
  
  
  
  
  2. 18 p.parent = r; 
    3.

最終執(zhí)行完了一個旋轉變成了我們開始說的第一種旋轉的形式，這個結構還需要向右旋轉一次。

 
 
 
 
    
  
  
  
  
  1. if (x == xp.right) 
    2. 
  
  
  
  
  2.  { 
    3. 
  
  
  
  
  3.  root = rotateLeft(root, x = xp); 
    4. 
  
  
  
  
  4.  xpp = (xp = x.parent) == null ? null : xp.parent; 
    5. 
  
  
  
  
  5.  } 
    6. 
  
  
  
  
  6. xpp = (xp = x.parent) == null ? null : xp.parent; 
    7.

執(zhí)行完上面的代碼，旋轉后調(diào)整x，xp，和xpp的關系得到下圖。

7.2 右旋轉

 
 
 
 
    
  
  
  
  
  1. if (xp != null) 
    2. 
  
  
  
  
  2. { 
    3. 
  
  
  
  
  3. xp.red = false; 
    4. 
  
  
  
  
  4. if (xpp != null) 
    5. 
  
  
  
  
  5. { 
    6. 
  
  
  
  
  6. xpp.red = true; 
    7. 
  
  
  
  
  7. root = rotateLeft(root, xpp); 
    8. 
  
  
  
  
  8. } 
    9. 
  
  
  
  
  9. } 
    10.

1.首先讓XP變成黑色。

2.如果XPP不為空的話變成紅色。

由于我們在rotateLeft(root, xpp)，傳進來的是XXP所以下面的的旋轉中實際上就是對XP和XXP執(zhí)行了一次與上面的方向相反其他完全相同的旋轉。

接著我們看向右旋轉的代碼

 
 
 
 
    
  
  
  
  
  1. static  TreeNode rotateRight(TreeNode root, TreeNode p) 
    2. 
  
  
  
  
  2.  { 
    3. 
  
  
  
  
  3.  // l：left，左節(jié)點。 
    4. 
  
  
  
  
  4.  // pp：parent parent，父節(jié)點的父節(jié)點。 
    5. 
  
  
  
  
  5.  // lr：left right，左節(jié)點的右節(jié)點。 
    6. 
  
  
  
  
  6.  TreeNode l, pp, lr; 
    7. 
  
  
  
  
  7.  if (p != null && (l = p.left) != null) 
    8. 
  
  
  
  
  8.  { 
    9. 
  
  
  
  
  9.  if ((lr = p.left = l.right) != null) 
    10. 
  
  
  
  
  10.  lr.parent = p; 
    11. 
  
  
  
  
  11.  if ((pp = l.parent = p.parent) == null) 
    12. 
  
  
  
  
  12.  (root = l).red = false; 
    13. 
  
  
  
  
  13.  else if (pp.right == p) 
    14. 
  
  
  
  
  14.  pp.right = l; 
    15. 
  
  
  
  
  15.  else 
    16. 
  
  
  
  
  16.  pp.left = l; 
    17. 
  
  
  
  
  17.  l.right = p; 
    18. 
  
  
  
  
  18.  p.parent = l; 
    19. 
  
  
  
  
  19.  } 
    20. 
  
  
  
  
  20.  return root; 
    21. 
  
  
  
  
  21.  } 
    22.

3.剛進來的時候結構是這個樣子。

在這里的P就是剛才傳進來的XPP。

4.這里我們認為LR是存在的，其實這個不影響主要的旋轉，為空就指向null唄，直接執(zhí)行完9和10行。

 
 
 
 
    
  
  
  
  
  1. 9 if ((lr = p.left = l.right) != null) 
    2. 
  
  
  
  
  2. 0 lr.parent = p; 
    3.

5.在這里我們假使PP是存在的，直接執(zhí)行完11的表達式不再執(zhí)行12行。(不再分析不存在的情況)。

 
 
 
 
    
  
  
  
  
  1. 11 if ((pp = l.parent = p.parent) == null) 
    2. 
  
  
  
  
  2. 12 (root = l).red = false; 
    3.

6.由于11行的條件不符合，現(xiàn)在直接執(zhí)行13行的表達式，不符合執(zhí)行15行else，執(zhí)行16行。

 
 
 
 
    
  
  
  
  
  1. 15 else 
    2. 
  
  
  
  
  2. 16 pp.left = l; 
    3.

7.最后執(zhí)行層17和18行。

 
 
 
 
    
  
  
  
  
  1. 17 l.right = p; 
    2. 
  
  
  
  
  2. 18 p.parent = l; 
    3.

最終完成兩次的旋轉。

08 疑問?

大家可能覺得和剛才接不上其實是這樣的，剛才在右旋轉前的時候的圖像是這個樣的。

因為我們傳進來的是XPP，所以結合上一次的向左旋轉我們在向右旋轉的時候看到全圖應該是這個樣子的。(注：XPPP可能是XPP的左父節(jié)點也可能是右父節(jié)點這里不影響，而且可以是任意顏色)

現(xiàn)在知道為什么XPPP可以是任意顏色的了吧，因為旋轉過后X是黑色的即便XPPP是紅色，此時我們又可以對兩個紅色的子節(jié)點進行顏色變換了，變換后X和XPPP有發(fā)生了顏色沖突，接著進行旋轉直到根。

 
 
 
 
    
  
  
  
  
  1. static  TreeNode balanceInsertion(TreeNode root, TreeNode x) 
    2. 
  
  
  
  
  2.  { 
    3. 
  
  
  
  
  3.  x.red = true; 
    4. 
  
  
  
  
  4.  for (TreeNode xp, xpp, xppl, xppr;;) 
    5. 
  
  
  
  
  5.  { 
    6. 
  
  
  
  
  6.  if ((xp = x.parent) == null) 
    7. 
  
  
  
  
  7.  { 
    8. 
  
  
  
  
  8.  x.red = false; 
    9. 
  
  
  
  
  9.  return x; 
    10. 
  
  
  
  
  10.  } 
    11. 
  
  
  
  
  11.  else if (!xp.red || (xpp = xp.parent) == null) 
    12. 
  
  
  
  
  12.  return root; 
    13. 
  
  
  
  
  13.  if (xp == (xppl = xpp.left)) 
    14. 
  
  
  
  
  14.  { 
    15. 
  
  
  
  
  15.  // 插入位置父節(jié)點在祖父節(jié)點的左邊。 
    16. 
  
  
  
  
  16.  } 
    17. 
  
  
  
  
  17.  else 
    18. 
  
  
  
  
  18.  { 
    19. 
  
  
  
  
  19.  // 插入位置父節(jié)點在祖父節(jié)點的右邊。 
    20. 
  
  
  
  
  20.  } 
    21. 
  
  
  
  
  21.  } 
    22. 
  
  
  
  
  22.  } 
    23.

我們值分析了插入位置父節(jié)點在祖父節(jié)點的左邊的情況，并沒有分析另外一面的對稱情況，其實是一樣的因為調(diào)用的都是相同的方法。

以上就是在1.8中的HashMap新引進的紅黑樹樹化的過程，與原來的鏈表相比當同一個bucket上存儲很多entry的話樹形的查找結構明顯要比鏈表線性的的效率要高。


網(wǎng)頁標題：3分鐘讓你明白：HashMap之紅黑樹樹化過程
網(wǎng)站URL：http://www.5511xx.com/article/cosjppo.html