HashMap紅黑樹(shù)樹(shù)化過(guò)程是怎樣的

本篇內(nèi)容主要講解“HashMap紅黑樹(shù)樹(shù)化過(guò)程是怎樣的”，感興趣的朋友不妨來(lái)看看。本文介紹的方法操作簡(jiǎn)單快捷，實(shí)用性強(qiáng)。下面就讓小編來(lái)帶大家學(xué)習(xí)“HashMap紅黑樹(shù)樹(shù)化過(guò)程是怎樣的”吧!

 01 概述

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

02 紅黑樹(shù)(red black tree)

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

03 兩種旋轉(zhuǎn)和一種典型的變換

旋轉(zhuǎn)的方向：

變換過(guò)程：

互相關(guān)聯(lián)：

單向關(guān)聯(lián)：

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

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

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

• 單旋轉(zhuǎn)變換。

• 雙旋轉(zhuǎn)變換(需要兩次反方向的單旋轉(zhuǎn))。

• 當(dāng)遇到兩個(gè)子幾點(diǎn)都為紅色的話執(zhí)行顏色變換，因?yàn)椴迦? 是紅色的會(huì)產(chǎn)生沖突。如果根節(jié)點(diǎn)兩邊的子節(jié)點(diǎn)都是紅色，兩個(gè)葉子節(jié)點(diǎn)變成黑色，根節(jié)點(diǎn)變成紅色，然后再將根節(jié)點(diǎn)變成黑色。

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

04 幾個(gè)問(wèn)題

4.1 為什么要進(jìn)行旋轉(zhuǎn)?

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

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

因?yàn)楸徊迦肭暗臉?shù)結(jié)構(gòu)是構(gòu)建好的，一但我們進(jìn)行添加黑色的節(jié)點(diǎn)，無(wú)論添加在哪里都會(huì)破壞原有路徑上的黑色節(jié)點(diǎn)的數(shù)量平等關(guān)系，所以插入紅色節(jié)點(diǎn)是正確的選擇。

4.3 為什么要進(jìn)行顏色變換?

正如第一種旋轉(zhuǎn)新加入的節(jié)點(diǎn)X破壞了紅黑樹(shù)的結(jié)構(gòu)不得不進(jìn)行旋轉(zhuǎn)，后面的就是旋轉(zhuǎn)后的結(jié)果，旋轉(zhuǎn)后形成新的結(jié)構(gòu)，此時(shí)我們發(fā)現(xiàn)兩個(gè)子節(jié)點(diǎn)都是紅色的所以執(zhí)行第三個(gè)變換特性，顏色變換，因?yàn)槿绻庸?jié)點(diǎn)是紅色的那么我們?cè)谔砑拥臅r(shí)候只能添加黑色的節(jié)點(diǎn)，然而添加任何黑色葉子節(jié)點(diǎn)都會(huì)破壞樹(shù)的第四條性質(zhì)，所以要對(duì)其進(jìn)行變換。當(dāng)進(jìn)行變換后葉子節(jié)點(diǎn)是紅色的而且我們默認(rèn)添加的葉子節(jié)點(diǎn)是紅色的，所以添加到黑色節(jié)點(diǎn)后并不會(huì)破壞樹(shù)的第四條結(jié)構(gòu)，所以這種變換很有用。

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

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

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

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

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

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict)  {  Node<K, V>[] tab;  Node<K, V> p;  int n, i;  if ((tab = table) == null || (n = tab.length) == 0)  n = (tab = resize()).length;  if ((p = tab[i = (n - 1) & hash]) == null)  tab[i] = newNode(hash, key, value, null);  else  {  Node<K, V> e;  K k;  if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))  e = p;  else if (p instanceof TreeNode)  // 如果當(dāng)前的bucket里面已經(jīng)是紅黑樹(shù)的話，執(zhí)行紅黑樹(shù)的添加操作  e = ((TreeNode<K, V>) p).putTreeVal(this, tab, hash, key, value);  else  {  for (int binCount = 0;; ++binCount)  {  if ((e = p.next) == null)  {  p.next = newNode(hash, key, value, null);  // TREEIFY_THRESHOLD = 8，判斷如果當(dāng)前bucket的位置鏈表長(zhǎng)度大于8的話就將此鏈表變成紅黑樹(shù)。  if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st  treeifyBin(tab, hash);  break;  }  if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))  break;  p = e;  }  }  if (e != null)  { // existing mapping for key  V oldValue = e.value;  if (!onlyIfAbsent || oldValue == null)  e.value = value;  afterNodeAccess(e);  return oldValue;  }  }  ++modCount;  if (++size > threshold)  resize();  afterNodeInsertion(evict);  return null;  }

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

讓我們看一下treeifyBin這個(gè)方法。

final void treeifyBin(Node<K, V>[] tab, int hash)  {  int n, index;  Node<K, V> e;  if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)  // resize()方法這里不過(guò)多介紹，感興趣的可以去看上面的鏈接。  resize();  // 通過(guò)hash求出bucket的位置。  else if ((e = tab[index = (n - 1) & hash]) != null)  {  TreeNode<K, V> hd = null, tl = null;  do  {  // 將每個(gè)節(jié)點(diǎn)包裝成TreeNode。  TreeNode<K, V> p = replacementTreeNode(e, null);  if (tl == null)  hd = p;  else  {  // 將所有TreeNode連接在一起此時(shí)只是鏈表結(jié)構(gòu)。  p.prev = tl;  tl.next = p;  }  tl = p;  } while ((e = e.next) != null);  if ((tab[index] = hd) != null)  // 對(duì)TreeNode鏈表進(jìn)行樹(shù)化。  hd.treeify(tab);  }  }

找個(gè)方法所做的事情就是將剛才九個(gè)項(xiàng)以鏈表的方式連接在一起，然后通過(guò)它構(gòu)建紅黑樹(shù)。

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

static final class TreeNode<K, V> extends LinkedHashMap.Entry<K, V>  {  TreeNode<K, V> parent; // red-black tree links  TreeNode<K, V> left;  TreeNode<K, V> right;  TreeNode<K, V> prev; // needed to unlink next upon deletion  boolean red;  TreeNode(int hash, K key, V val, Node<K, V> next)  {  super(hash, key, val, next);  }    final void treeify(Node<K,V>[] tab)  {  // ......  }    static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root, TreeNode<K,V> x)  {  // ......  }    static <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root, TreeNode<K,V> p)  {  // ......  }    static <K,V> TreeNode<K,V> rotateRight(TreeNode<K,V> root, TreeNode<K,V> p)  {  // ......  }    // ......其余方法省略  }

可以看出出真正的維護(hù)紅黑樹(shù)結(jié)構(gòu)的方法并沒(méi)有在HashMap中，全部都在TreeNode類內(nèi)部。

我們看一下treeify代碼

final void treeify(Node<K, V>[] tab)  {  TreeNode<K, V> root = null;  // 以for循環(huán)的方式遍歷剛才我們創(chuàng)建的鏈表。  for (TreeNode<K, V> x = this, next; x != null; x = next)  {  // next向前推進(jìn)。  next = (TreeNode<K, V>) x.next;  x.left = x.right = null;  // 為樹(shù)根節(jié)點(diǎn)賦值。  if (root == null)  {  x.parent = null;  x.red = false;  root = x;  } else  {  // x即為當(dāng)前訪問(wèn)鏈表中的項(xiàng)。  K k = x.key;  int h = x.hash;  Class<?> kc = null;  // 此時(shí)紅黑樹(shù)已經(jīng)有了根節(jié)點(diǎn)，上面獲取了當(dāng)前加入紅黑樹(shù)的項(xiàng)的key和hash值進(jìn)入核心循環(huán)。  // 這里從root開(kāi)始，是以一個(gè)自頂向下的方式遍歷添加。  // for循環(huán)沒(méi)有控制條件，由代碼內(nèi)break跳出循環(huán)。  for (TreeNode<K, V> p = root;;)  {  // dir：directory，比較添加項(xiàng)與當(dāng)前樹(shù)中訪問(wèn)節(jié)點(diǎn)的hash值判斷加入項(xiàng)的路徑，-1為左子樹(shù)，+1為右子樹(shù)。  // ph：parent hash。  int dir, ph;  K pk = p.key;  if ((ph = p.hash) > h)  dir = -1;  else if (ph < h)  dir = 1;  else if ((kc == null && (kc = comparableClassFor(k)) == null)  || (dir = compareComparables(kc, k, pk)) == 0)  dir = tieBreakOrder(k, pk);  // xp：x parent。  TreeNode<K, V> xp = p;  // 找到符合x添加條件的節(jié)點(diǎn)。  if ((p = (dir <= 0) ? p.left : p.right) == null)  {  x.parent = xp;  // 如果xp的hash值大于x的hash值，將x添加在xp的左邊。  if (dir <= 0)  xp.left = x;  // 反之添加在xp的右邊。  else  xp.right = x;  // 維護(hù)添加后紅黑樹(shù)的紅黑結(jié)構(gòu)。  root = balanceInsertion(root, x);    // 跳出循環(huán)當(dāng)前鏈表中的項(xiàng)成功的添加到了紅黑樹(shù)中。  break;  }  }  }  }  // Ensures that the given root is the first node of its bin，自己翻譯一下。  moveRootToFront(tab, root);  }

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

我們看balanceInsertion

static <K, V> TreeNode<K, V> balanceInsertion(TreeNode<K, V> root, TreeNode<K, V> x)  {  // 正如開(kāi)頭所說(shuō)，新加入樹(shù)節(jié)點(diǎn)默認(rèn)都是紅色的，不會(huì)破壞樹(shù)的結(jié)構(gòu)。  x.red = true;  // 這些變量名不是作者隨便定義的都是有意義的。  // xp：x parent，代表x的父節(jié)點(diǎn)。  // xpp：x parent parent，代表x的祖父節(jié)點(diǎn)  // xppl：x parent parent left，代表x的祖父的左節(jié)點(diǎn)。  // xppr：x parent parent right，代表x的祖父的右節(jié)點(diǎn)。  for (TreeNode<K, V> xp, xpp, xppl, xppr;;)  {  // 如果x的父節(jié)點(diǎn)為null說(shuō)明只有一個(gè)節(jié)點(diǎn)，該節(jié)點(diǎn)為根節(jié)點(diǎn)，根節(jié)點(diǎn)為黑色，red = false。  if ((xp = x.parent) == null)  {  x.red = false;  return x;  }   // 進(jìn)入else說(shuō)明不是根節(jié)點(diǎn)。  // 如果父節(jié)點(diǎn)是黑色，那么大吉大利（今晚吃雞），紅色的x節(jié)點(diǎn)可以直接添加到黑色節(jié)點(diǎn)后面，返回根就行了不需要任何多余的操作。  // 如果父節(jié)點(diǎn)是紅色的，但祖父節(jié)點(diǎn)為空的話也可以直接返回根此時(shí)父節(jié)點(diǎn)就是根節(jié)點(diǎn)，因?yàn)楦仨毷呛谏?，添加在后面沒(méi)有任何問(wèn)題。  else if (!xp.red || (xpp = xp.parent) == null)  return root;    // 一旦我們進(jìn)入到這里就說(shuō)明了兩件是情  // 1.x的父節(jié)點(diǎn)xp是紅色的，這樣就遇到兩個(gè)紅色節(jié)點(diǎn)相連的問(wèn)題，所以必須經(jīng)過(guò)旋轉(zhuǎn)變換。  // 2.x的祖父節(jié)點(diǎn)xpp不為空。    // 判斷如果父節(jié)點(diǎn)是否是祖父節(jié)點(diǎn)的左節(jié)點(diǎn)  if (xp == (xppl = xpp.left))  {  // 父節(jié)點(diǎn)xp是祖父的左節(jié)點(diǎn)xppr  // 判斷祖父節(jié)點(diǎn)的右節(jié)點(diǎn)不為空并且是否是紅色的  // 此時(shí)xpp的左右節(jié)點(diǎn)都是紅的，所以直接進(jìn)行上面所說(shuō)的第三種變換，將兩個(gè)子節(jié)點(diǎn)變成黑色，將xpp變成紅色，然后將紅色節(jié)點(diǎn)x順利的添加到了xp的后面。  // 這里大家有疑問(wèn)為什么將x = xpp？  // 這是由于將xpp變成紅色以后可能與xpp的父節(jié)點(diǎn)發(fā)生兩個(gè)相連紅色節(jié)點(diǎn)的沖突，這就又構(gòu)成了第二種旋轉(zhuǎn)變換，所以必須從底向上的進(jìn)行變換，直到根。  // 所以令x = xpp，然后進(jìn)行下下一層循環(huán)，接著往上走。  if ((xppr = xpp.right) != null && xppr.red)  {  xppr.red = false;  xp.red = false;  xpp.red = true;  x = xpp;  }  // 進(jìn)入到這個(gè)else里面說(shuō)明。  // 父節(jié)點(diǎn)xp是祖父的左節(jié)點(diǎn)xppr。  // 祖父節(jié)點(diǎn)xpp的右節(jié)點(diǎn)xppr是黑色節(jié)點(diǎn)或者為空，默認(rèn)規(guī)定空節(jié)點(diǎn)也是黑色的。  // 下面要判斷x是xp的左節(jié)點(diǎn)還是右節(jié)點(diǎn)。  else  {  // x是xp的右節(jié)點(diǎn)，此時(shí)的結(jié)構(gòu)是：xpp左->xp右->x。這明顯是第二中變換需要進(jìn)行兩次旋轉(zhuǎn)，這里先進(jìn)行一次旋轉(zhuǎn)。  // 下面是第一次旋轉(zhuǎn)。  if (x == xp.right)  {  root = rotateLeft(root, x = xp);  xpp = (xp = x.parent) == null ? null : xp.parent;  }  // 針對(duì)本身就是xpp左->xp左->x的結(jié)構(gòu)或者由于上面的旋轉(zhuǎn)造成的這種結(jié)構(gòu)進(jìn)行一次旋轉(zhuǎn)。  if (xp != null)  {  xp.red = false;  if (xpp != null)  {  xpp.red = true;  root = rotateRight(root, xpp);  }  }  }  }   // 這里的分析方式和前面的相對(duì)稱只不過(guò)全部在右測(cè)不再重復(fù)分析。  else  {  if (xppl != null && xppl.red)  {  xppl.red = false;  xp.red = false;  xpp.red = true;  x = xpp;  } else  {  if (x == xp.left)  {  root = rotateRight(root, x = xp);  xpp = (xp = x.parent) == null ? null : xp.parent;  }  if (xp != null)  {  xp.red = false;  if (xpp != null)  {  xpp.red = true;  root = rotateLeft(root, xpp);  }  }  }  }  }  }

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

下面簡(jiǎn)述一下前面的兩種種幸運(yùn)的情況

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

06 顏色變換

if (xp == (xppl = xpp.left))  {  if ((xppr = xpp.right) != null && xppr.red)  {  xppr.red = false;  xp.red = false;  xpp.red = true;  x = xpp;  } }

這里是一個(gè)典型的一個(gè)黑色節(jié)點(diǎn)的兩個(gè)子節(jié)點(diǎn)都是紅色的所以要進(jìn)行顏色變換，因?yàn)椴迦氲亩际羌t色節(jié)點(diǎn)，當(dāng)檢測(cè)到祖父節(jié)點(diǎn)的左右子節(jié)點(diǎn)都是紅色的時(shí)候兩個(gè)紅色就產(chǎn)生了沖突，所以先將節(jié)點(diǎn)進(jìn)行這種顏色變換，將祖父節(jié)點(diǎn)變成紅色，然后將祖父的兩個(gè)子節(jié)點(diǎn)變成黑色，這樣我們插入的紅色節(jié)點(diǎn)就不會(huì)違背紅黑樹(shù)的規(guī)則了。

這里有人會(huì)有疑問(wèn)，如果祖父節(jié)點(diǎn)是根節(jié)點(diǎn)呢，那樣的話祖父節(jié)點(diǎn)也會(huì)變成黑色，因?yàn)槊看窝h(huán)進(jìn)行插入平衡的操作當(dāng)進(jìn)行這種顏色變換之后都會(huì)將插入節(jié)點(diǎn)的引用指向祖父節(jié)點(diǎn)，當(dāng)進(jìn)行下一輪循環(huán)的時(shí)候會(huì)優(yōu)先檢測(cè)當(dāng)前節(jié)點(diǎn)是否是根節(jié)點(diǎn)，如果是根節(jié)點(diǎn)那就將顏色變成黑色，下面看圖：

當(dāng)將節(jié)點(diǎn)指向祖父節(jié)點(diǎn)進(jìn)行下一輪循環(huán)時(shí)：

07 兩個(gè)核心旋轉(zhuǎn)(左旋轉(zhuǎn)和右旋轉(zhuǎn))

// 一旦我們進(jìn)入到這里就說(shuō)明了兩件是情  // 1.x的父節(jié)點(diǎn)xp是紅色的，這樣就遇到兩個(gè)紅色節(jié)點(diǎn)相連的問(wèn)題，所以必須經(jīng)過(guò)旋轉(zhuǎn)變換。  // 2.x的祖父節(jié)點(diǎn)xpp不為空。    // 判斷如果父節(jié)點(diǎn)是否是祖父節(jié)點(diǎn)的左節(jié)點(diǎn)  if (xp == (xppl = xpp.left))  {  if ((xppr = xpp.right) != null && xppr.red)  {// ......  }  // 進(jìn)入到這個(gè)else里面說(shuō)明。  // 父節(jié)點(diǎn)xp是祖父的左節(jié)點(diǎn)xppr。  // 祖父節(jié)點(diǎn)xpp的右節(jié)點(diǎn)xppr是黑色節(jié)點(diǎn)或者為空，默認(rèn)規(guī)定空節(jié)點(diǎn)也是黑色的。  // 下面要判斷x是xp的左節(jié)點(diǎn)還是右節(jié)點(diǎn)。  else  {  // x是xp的右節(jié)點(diǎn)，此時(shí)的結(jié)構(gòu)是：xpp左->xp右->x。這明顯是第二中變換需要進(jìn)行兩次旋轉(zhuǎn)，這里先進(jìn)行一次旋轉(zhuǎn)。  // 下面是第一次旋轉(zhuǎn)。  if (x == xp.right)  {  root = rotateLeft(root, x = xp);  xpp = (xp = x.parent) == null ? null : xp.parent;  }  // 針對(duì)本身就是xpp左->xp左->x的結(jié)構(gòu)或者由于上面的旋轉(zhuǎn)造成的這種結(jié)構(gòu)進(jìn)行一次旋轉(zhuǎn)。  if (xp != null)  {  xp.red = false;  if (xpp != null)  {  xpp.red = true;  root = rotateRight(root, xpp);  }  }  }  }

顏色變換完成后進(jìn)入下面的else塊

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

這中結(jié)構(gòu)需要進(jìn)行雙旋轉(zhuǎn)，首先先進(jìn)行一次向左旋轉(zhuǎn)。

7.1 左旋轉(zhuǎn)

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

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

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

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

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

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

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

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

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

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

由于PP為空所以只剩下這三個(gè)。

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

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

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

5.由于進(jìn)入了13和14行所以不進(jìn)入15和16行的else語(yǔ)句。

15 else 16 pp.right = r;

6.看17和18行。

17 r.left = p; 18 p.parent = r;

最終執(zhí)行完了一個(gè)旋轉(zhuǎn)變成了我們開(kāi)始說(shuō)的第一種旋轉(zhuǎn)的形式，這個(gè)結(jié)構(gòu)還需要向右旋轉(zhuǎn)一次。

if (x == xp.right)  {  root = rotateLeft(root, x = xp);  xpp = (xp = x.parent) == null ? null : xp.parent;  } xpp = (xp = x.parent) == null ? null : xp.parent;

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

7.2 右旋轉(zhuǎn)

if (xp != null) { xp.red = false; if (xpp != null) { xpp.red = true; root = rotateLeft(root, xpp); } }

1.首先讓XP變成黑色。

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

由于我們?cè)趓otateLeft(root,  xpp)，傳進(jìn)來(lái)的是XXP所以下面的的旋轉(zhuǎn)中實(shí)際上就是對(duì)XP和XXP執(zhí)行了一次與上面的方向相反其他完全相同的旋轉(zhuǎn)。

接著我們看向右旋轉(zhuǎn)的代碼

static <K, V> TreeNode<K, V> rotateRight(TreeNode<K, V> root, TreeNode<K, V> p)  {  // l：left，左節(jié)點(diǎn)。  // pp：parent parent，父節(jié)點(diǎn)的父節(jié)點(diǎn)。  // lr：left right，左節(jié)點(diǎn)的右節(jié)點(diǎn)。  TreeNode<K, V> l, pp, lr;  if (p != null && (l = p.left) != null)  {  if ((lr = p.left = l.right) != null)  lr.parent = p;  if ((pp = l.parent = p.parent) == null)  (root = l).red = false;  else if (pp.right == p)  pp.right = l;  else  pp.left = l;  l.right = p;  p.parent = l;  }  return root;  }

3.剛進(jìn)來(lái)的時(shí)候結(jié)構(gòu)是這個(gè)樣子。

在這里的P就是剛才傳進(jìn)來(lái)的XPP。

4.這里我們認(rèn)為L(zhǎng)R是存在的，其實(shí)這個(gè)不影響主要的旋轉(zhuǎn)，為空就指向null唄，直接執(zhí)行完9和10行。

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

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

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

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

15 else 16 pp.left = l;

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

17 l.right = p; 18 p.parent = l;

最終完成兩次的旋轉(zhuǎn)。

08 疑問(wèn)?

大家可能覺(jué)得和剛才接不上其實(shí)是這樣的，剛才在右旋轉(zhuǎn)前的時(shí)候的圖像是這個(gè)樣的。

因?yàn)槲覀儌鬟M(jìn)來(lái)的是XPP，所以結(jié)合上一次的向左旋轉(zhuǎn)我們?cè)谙蛴倚D(zhuǎn)的時(shí)候看到全圖應(yīng)該是這個(gè)樣子的。(注：XPPP可能是XPP的左父節(jié)點(diǎn)也可能是右父節(jié)點(diǎn)這里不影響，而且可以是任意顏色)

現(xiàn)在知道為什么XPPP可以是任意顏色的了吧，因?yàn)樾D(zhuǎn)過(guò)后X是黑色的即便XPPP是紅色，此時(shí)我們又可以對(duì)兩個(gè)紅色的子節(jié)點(diǎn)進(jìn)行顏色變換了，變換后X和XPPP有發(fā)生了顏色沖突，接著進(jìn)行旋轉(zhuǎn)直到根。

static <K, V> TreeNode<K, V> balanceInsertion(TreeNode<K, V> root, TreeNode<K, V> x)  {  x.red = true;  for (TreeNode<K, V> xp, xpp, xppl, xppr;;)  {  if ((xp = x.parent) == null)  {  x.red = false;  return x;  }  else if (!xp.red || (xpp = xp.parent) == null)  return root;  if (xp == (xppl = xpp.left))  {  // 插入位置父節(jié)點(diǎn)在祖父節(jié)點(diǎn)的左邊。  }  else  {  // 插入位置父節(jié)點(diǎn)在祖父節(jié)點(diǎn)的右邊。  }  }  }

我們值分析了插入位置父節(jié)點(diǎn)在祖父節(jié)點(diǎn)的左邊的情況，并沒(méi)有分析另外一面的對(duì)稱情況，其實(shí)是一樣的因?yàn)檎{(diào)用的都是相同的方法。

到此，相信大家對(duì)“HashMap紅黑樹(shù)樹(shù)化過(guò)程是怎樣的”有了更深的了解，不妨來(lái)實(shí)際操作一番吧！這里是億速云網(wǎng)站，更多相關(guān)內(nèi)容可以進(jìn)入相關(guān)頻道進(jìn)行查詢，關(guān)注我們，繼續(xù)學(xué)習(xí)！