小編給大家分享一下Java數(shù)據(jù)結(jié)構(gòu)之紅黑樹的示例分析，相信大部分人都還不怎么了解，因此分享這篇文章給大家參考一下，希望大家閱讀完這篇文章后大有收獲，下面讓我們一起去了解一下吧！

十多年的蕉城網(wǎng)站建設(shè)經(jīng)驗，針對設(shè)計、前端、開發(fā)、售后、文案、推廣等六對一服務(wù)，響應(yīng)快，48小時及時工作處理。成都營銷網(wǎng)站建設(shè)的優(yōu)勢是能夠根據(jù)用戶設(shè)備顯示端的尺寸不同，自動調(diào)整蕉城建站的顯示方式，使網(wǎng)站能夠適用不同顯示終端，在瀏覽器中調(diào)整網(wǎng)站的寬度，無論在任何一種瀏覽器上瀏覽網(wǎng)站，都能展現(xiàn)優(yōu)雅布局與設(shè)計，從而大程度地提升瀏覽體驗。成都創(chuàng)新互聯(lián)從事“蕉城網(wǎng)站設(shè)計”,“蕉城網(wǎng)站推廣”以來，每個客戶項目都認(rèn)真落實執(zhí)行。

一、紅黑樹所處數(shù)據(jù)結(jié)構(gòu)的位置：

在JDK源碼中, 有treeMap和JDK8的HashMap都用到了紅黑樹去存儲

紅黑樹可以看成B樹的一種:

從二叉樹看，紅黑樹是一顆相對平衡的二叉樹

二叉樹-->搜索二叉樹-->平衡搜索二叉樹--> 紅黑樹

從N階樹看，紅黑樹就是一顆 2-3-4樹

N階樹-->B（B-）樹

 故我提取出了紅黑樹部分的源碼，去說明紅黑樹的理解

看之前，理解紅黑樹的幾個特性，后面的操作都是為了讓樹符合紅黑樹的這幾個特性，從而滿足對查找效率的O(logn)

二、紅黑樹特性，以及保持的手段

1.根和葉子節(jié)點都是黑色的

2.不能有有連續(xù)兩個紅色的節(jié)點

3.從任一節(jié)點到它所能到達(dá)得葉子節(jié)點的所有簡單路徑都包含相同數(shù)目的黑色節(jié)點 

這幾個特效，個人理解就是規(guī)定了紅黑樹是一顆2-3-4的B樹了，從而滿足了O(logn)查找效率 

保持特性的手段，通過下面這些手段，讓紅黑樹滿足紅黑樹的特性，如果要嘗試?yán)斫猓梢詮?-3-4樹的向上增長，后面有詳細(xì)介紹 

當(dāng)然，這些改變也都是在O(logn)內(nèi)完成的，主要改變方式有

1.改變顏色

2.左旋

3.右旋 

三、從JDK源碼來理解

主要看我的注釋，邏輯的理解

先看TreeMap

//對treeMap的紅黑樹理解注解. 2017.02.16 by 何錦彬 JDK,1.7.51
 
/** From CLR */
 private void fixAfterInsertion(Entry x) {
 
   
   
  //新加入紅黑樹的默認(rèn)節(jié)點就是紅色
  x.color = RED;
  /**
   * 1. 如為根節(jié)點直接跳出
   */
  while (x != null && x != root && x.parent.color == RED) {
    
   if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
     
    //如果X的父節(jié)點（P）是其父節(jié)點的父節(jié)點（G）的左節(jié)點
    //即 下面這種情況
    /**
     *       G
     *    P(RED)    U
     */    
    //獲取其叔(U)節(jié)點
    Entry y = rightOf(parentOf(parentOf(x)));
    if (colorOf(y) == RED) {
     // 這種情況，對應(yīng)下面 圖：情況一
     /**
      *       G
      *    P(RED)    U(RED)
      *   X
      */
     //如果叔節(jié)點是紅色的（父節(jié)點有判斷是紅色）. 即是雙紅色，比較好辦，通過改變顏色就行. 把P和U都設(shè)置成黑色然后,X加到P節(jié)點。 G節(jié)點當(dāng)作新加入節(jié)點繼續(xù)迭代
     setColor(parentOf(x), BLACK);
     setColor(y, BLACK);
     setColor(parentOf(parentOf(x)), RED);
     x = parentOf(parentOf(x));
    } else {
     //處理紅父，黑叔的情況
     if (x == rightOf(parentOf(x))) {
      // 這種情況，對應(yīng)下面 圖：情況二
      /**
       *       G
       *   P(RED)      U(BLACK)
       *      X
       */
      //如果X是右邊節(jié)點
      x = parentOf(x);
      // 進(jìn)行左旋
      rotateLeft(x);
     }
     //左旋后，是這種情況了，對應(yīng)下面 圖：情況三
     /**
      *       G
      *   P(RED)      U(BLACK)
      *  X
      */
      
     // 到這，X只能是左節(jié)點了，而且P是紅色，U是黑色的情況
     //把P改成黑色，G改成紅色，以G為節(jié)點進(jìn)行右旋
     setColor(parentOf(x), BLACK);
     setColor(parentOf(parentOf(x)), RED);
     rotateRight(parentOf(parentOf(x)));
    }
   } else {
    //父節(jié)點在右邊的
    /**
     *       G
     *     U    P(RED)
     */    
    //獲取U
    Entry y = leftOf(parentOf(parentOf(x)));
     
    if (colorOf(y) == RED) {
     //紅父紅叔的情況
     /**
      *       G
      *    U(RED)    P(RED)
      */ 
     setColor(parentOf(x), BLACK);
     setColor(y, BLACK);
     setColor(parentOf(parentOf(x)), RED);
     //把G當(dāng)作新插入的節(jié)點繼續(xù)進(jìn)行迭代
     x = parentOf(parentOf(x));
    } else {
     //紅父黑叔，并且是右父的情況
     /**
      *       G
      *    U(RED)    P(RED)
      */ 
     if (x == leftOf(parentOf(x))) {
     //如果插入的X是左節(jié)點
      /**
      *       G
      *   U(BLACK)      P(RED)
      *          X    
      */
      x = parentOf(x);
      //以P為節(jié)點進(jìn)行右旋
      rotateRight(x);
     }
     //右旋后
     /**
      *       G
      *   U(BLACK)      P(RED)
      *              X
      */
     setColor(parentOf(x), BLACK);
     setColor(parentOf(parentOf(x)), RED);
     //以G為節(jié)點進(jìn)行左旋
     rotateLeft(parentOf(parentOf(x)));
    }
   }
  }
  //紅黑樹的根節(jié)點始終是黑色
  root.color = BLACK;
 }

再看看HashMap的實現(xiàn)，在HashMap中，在JDK8后開始用紅黑樹代替鏈表，查找由O(n) 變成了 O(Logn)

源碼分析如下:

for (int binCount = 0; ; ++binCount) {
     if ((e = p.next) == null) {
      p.next = newNode(hash, key, value, null);
      //JDK8 的hashmap，鏈表到了8就需要變成顆紅黑樹了
      if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
       treeifyBin(tab, hash);
      break;
     }

紅黑樹的維護(hù)代碼部分如下：

//hashmap的紅黑樹平衡
   static  TreeNode balanceInsertion(TreeNode root,
               TreeNode x) {
     x.red = true;
     //死循環(huán)加變量定義，總感覺JAVA很少這樣寫代碼 哈
     for (TreeNode xp, xpp, xppl, xppr;;) {
      //xp X父節(jié)點， XPP X的祖父節(jié)點， XPPL 祖父左節(jié)點 XXPR 祖父右節(jié)點 
      if ((xp = x.parent) == null) {
       x.red = false;
       return x;
      }
      // 如果父節(jié)點是黑色， 或者XP父節(jié)點是空，直接返回
      else if (!xp.red || (xpp = xp.parent) == null)
       return root;
      
      // 下面的代碼就和上面的很treeMap像了，
      
      if (xp == (xppl = xpp.left)) {
        // 第一種情況, 賦值xppl
       //父節(jié)點是左節(jié)點的情況,下面這種
       /**
        *       G
        *    P(RED)    U
        */    
       if ((xppr = xpp.right) != null && xppr.red) {
        //如果紅叔的情況
         // 這種情況，對應(yīng)下面 圖：情況一
        /**
         *       G
         *    P(RED)    U(RED)
         *   X
         */
         //改變其顏色，
        xppr.red = false;
        xp.red = false;
        xpp.red = true;
        x = xpp;
       }
       else {
         // 黑叔的情況
        // 這種情況
        /**
         *       G
         *    P(RED)    U(BLACK)
         */
        if (x == xp.right) {
         //如果插入節(jié)點在右邊 這種
          // 這種情況，對應(yīng)下面 圖：情況二
         /**
          *       G
          *   P(RED)      U(BLACK)
          *      X
          */
         //需要進(jìn)行左旋
         root = rotateLeft(root, x = xp);
         xpp = (xp = x.parent) == null ? null : xp.parent;
        }
        //左旋后情況都是這種了，對應(yīng)下面 圖：情況三
        /**
         *       G
         *   P(RED)      U(BLACK)
         *  X
         */
        // 到這，X只能是左節(jié)點了，而且P是紅色，U是黑色的情況
        if (xp != null) {
        //把P改成黑色，G改成紅色, 以G為節(jié)點進(jìn)行右旋
         xp.red = false;
         if (xpp != null) {
          xpp.red = true;
          root = rotateRight(root, xpp);
         }
        }
       }
      }
      else {
        //父節(jié)點在右邊的
       /**
        *       G
        *     U    P(RED)
        */    
       //獲取U
       if (xppl != null && xppl.red) {
        //紅父紅叔的情況
         /**
         *       G
         *     U(RED)    P(RED)
         */    
        xppl.red = false;
        xp.red = false;
        xpp.red = true;
        x = xpp;
       }
       else {
        
        if (x == xp.left) {
         //如果插入的X是右節(jié)點
         /**
          *       G
          *   U(BLACK)      P(RED)
          *          X    
          */
         root = rotateRight(root, x = xp);
         xpp = (xp = x.parent) == null ? null : xp.parent;
        }
        //右旋后
        /**
         *       G
         *   U(BLACK)      P(RED)
         *              X
         */
        if (xp != null) {
         //把P改成黑色，G改成紅色,
         xp.red = false;
         if (xpp != null) {
          xpp.red = true;
          //以G節(jié)點左旋
          root = rotateLeft(root, xpp);
         }
        }
       }
      }
 }

情況圖如下

情況1

情況2

情況3

JDK源碼處理紅黑樹的流程圖

可見，其實處理邏輯實現(xiàn)都一樣的

三、個人對紅黑樹理解的方法

1. 如何理解紅黑樹的O(lgN)的特性？

從2-3-4樹去理解

紅黑樹，其實是一顆 2-3-4的B樹，B樹都是向上增長的，如果不理解向上增長可以先看看2-3樹，這樣理解就能知道為什么能O（logn）的查找了

2.如何理解紅黑樹的紅黑節(jié)點意義？

可以把紅色節(jié)點看成是連接父節(jié)點的組成的一個大節(jié)點(2個或3個或4個節(jié)點組成的一個key)，如下:

（此圖轉(zhuǎn)自網(wǎng)上）

紅色的就是和父節(jié)點組成了大節(jié)點，

比如

節(jié)點7和6，6是紅色節(jié)點組成，故和它父節(jié)點7組成了一個大節(jié)點，即 2-3-4樹的 6, 7節(jié)點

又如

節(jié)點 9和10和11，9和10為紅色節(jié)點，故和10組成了一個2-3-4的3階節(jié)點， 9,10,11（注意順序有的關(guān)性）

3.B樹是如何保持O(lgn)的復(fù)雜度的呢?

B+樹都是從底布開始往上生長，自動平衡，如 2-3-4樹，當(dāng)節(jié)點達(dá)到了3個時晉升到上個節(jié)點，所以不會產(chǎn)生單獨生長一邊的情況，形成平衡。

以上是“Java數(shù)據(jù)結(jié)構(gòu)之紅黑樹的示例分析”這篇文章的所有內(nèi)容，感謝各位的閱讀！相信大家都有了一定的了解，希望分享的內(nèi)容對大家有所幫助，如果還想學(xué)習(xí)更多知識，歡迎關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道！