數(shù)據(jù)結(jié)構(gòu)之 樹

• 二叉樹

  每個節(jié)點最多有兩個子樹的樹結(jié)構(gòu)膜廊，在二叉樹的概念下又衍生出滿二叉樹和完全二叉樹乏沸。

  • 滿二叉樹

    除最后一層無任何子節(jié)點外，每一層上的所有節(jié)點都有兩個子節(jié)點溃论。也可以理解為屎蜓，除葉子節(jié)點外的所有節(jié)點均有兩個子節(jié)點。節(jié)點數(shù)達到最大值钥勋，所有葉子節(jié)點必須在同一層上炬转。

  • 完全二叉樹

    若設二叉樹的高度為h，除第h層外算灸，其它各層（1～h-1）的節(jié)點數(shù)都達到最大個數(shù)扼劈，第h層所有的節(jié)點都連續(xù)集中在最左邊。

  • 二叉查找樹

    二叉查找樹是二叉樹的衍生概念菲驴，Binary Serarch Tree荐吵，也稱為二叉搜索樹、有序二叉樹（Ordered Binary Tree）或排序二叉樹（Sorted Binary Tree）赊瞬，是指一顆空樹或具有下列性質(zhì)的二叉樹先煎。

    • 若任意節(jié)點的左子樹不為空，則左子樹上所有節(jié)點的值均小于它的根節(jié)點的值巧涧。
    • 若任意節(jié)點的右子樹不為空薯蝎，則右子樹上所有節(jié)點的值均大于它的根節(jié)點的值。
    • 任意節(jié)點的左谤绳、右子樹也分別為二叉查找樹占锯。

  • 沒有鍵值相等的節(jié)點。

    二叉查找樹相比于其它數(shù)據(jù)結(jié)構(gòu)的優(yōu)勢在于查找缩筛、插入的時間復雜度較低消略，O(log n)。二叉查找樹是基礎性數(shù)據(jù)結(jié)構(gòu)瞎抛，用于構(gòu)建更為抽象的數(shù)據(jù)結(jié)構(gòu)艺演，如集合，多重集桐臊，關(guān)聯(lián)數(shù)組等钞艇。

  • 平衡二叉樹（AVL樹）

    當且僅當任何節(jié)點的兩個子樹的高度差不大于1的二叉樹。

    其中AVL樹是最先發(fā)明的自平衡二叉查找樹豪硅，是最原始典型的平衡二叉樹。

    平衡二叉樹是基于二叉查找樹的改進挺物。由于某些極端的情況下（插入的序列是有序時）懒浮，二叉查找樹將退化程近似鏈表的數(shù)據(jù)結(jié)構(gòu)，此時其操作的時間復雜度將退化成線性的，即O(n)砚著。所以通過自平衡操作（旋轉(zhuǎn)）構(gòu)建兩個子樹高度差不超過1的平衡二叉樹次伶。

    如果執(zhí)行插入或者刪除操作，只要不滿足平衡條件的稽穆，就要通過旋轉(zhuǎn)來保持平衡冠王，但是旋轉(zhuǎn)是非常耗時的。

    使用場景：

    AVL樹適用于插入舌镶、刪除次數(shù)比較少柱彻，查比較多的情況。

  • 紅黑樹

    紅黑樹是自平衡的二叉查找樹餐胀。它是一種查找哟楷、增加、刪除效率都比較均衡的二叉查找樹否灾，增加或者刪除的時候卖擅，只要能夠保證操作后的樹結(jié)構(gòu)從根到葉子節(jié)點的最長路徑不會是最短路徑的兩倍，那么就不會觸發(fā)平衡策略進行旋轉(zhuǎn)墨技，要知道惩阶，旋轉(zhuǎn)真的是非常耗時的。

    具有以下性質(zhì)：

    • 每個節(jié)點要么是紅的扣汪，要么是黑的断楷。
    • 根節(jié)點一定是黑的。
    • 每個葉子節(jié)點都是黑色的空節(jié)點（NIL節(jié)點）私痹。
    • 如果一個節(jié)點是紅的脐嫂，那么它的兩個子節(jié)點都是黑的。
    • 從任意節(jié)點到其每個葉子的所有路徑都包含相同數(shù)目的黑色節(jié)點紊遵。

    用上面五個條件账千，我們可以模擬推導出一個結(jié)論：即紅黑樹確保從根到葉子節(jié)點的最長路徑不會是最短路徑的兩倍，用非嚴格的平衡策略來換取增暗膜、刪節(jié)點時匀奏，旋轉(zhuǎn)次數(shù)的降低，任何不平衡都會在三次旋轉(zhuǎn)之內(nèi)解決学搜。

    使用場景：

    • 廣泛用在C++的STL中娃善。
    • 注明的linux進程調(diào)度Completely Fair Scheduler，用紅黑樹管理進程控制塊瑞佩。
    • epoll在內(nèi)核中的實現(xiàn)聚磺，用紅黑樹管理事件塊。
    • nginx中炬丸，用紅黑樹管理timer等瘫寝。
    • Java 8中的HashMap當鏈表長度大于8時蜒蕾，轉(zhuǎn)為紅黑樹進行存儲。

    紅黑樹的查詢性能略遜于AVL樹焕阿，因為AVL樹會稍微不平衡最多一層咪啡，也就是說紅黑樹的查詢性能只比相同內(nèi)容的AVL樹最多多一次比較，但是暮屡，紅黑樹在插入和刪除上完爆AVL樹撤摸，AVL樹每次插入刪除會進行大量的平衡度計算，而紅黑樹為了維持紅黑性質(zhì)所做的紅黑轉(zhuǎn)變和旋轉(zhuǎn)的開銷褒纲，相較于AVL樹為了維持平衡的開銷要小得多准夷。

    旋轉(zhuǎn)程序

    當前節(jié)點用node表示；

    父節(jié)點用father表示外厂；

    爺爺節(jié)點用grandpa表示冕象；

    叔叔節(jié)點用uncle表示；

    while (node != null && node != root && node.parent.color == RED) {
      // 父節(jié)點是爺爺節(jié)點的左子樹
      if (parentOf(node) == leftOf(grandpaOf(node))) {
          RBTreeNode uncleRight = rightOf(grandpaOf(node));
          /*
           判斷父節(jié)點和叔叔節(jié)點是否都為紅色
           父節(jié)肯定為紅色汁蝶，除非是根節(jié)點渐扮，一旦是黑色，壓根就不用左旋轉(zhuǎn)或者右旋轉(zhuǎn)
           */
          if (colorOf(uncleRight) == RED) {
              setColor(parentOf(node), BLACK);
              setColor(uncleRight, BLACK);
              setColor(grandpaOf(node), RED);
              node = grandpaOf(node);
          } else {
              // ①左右情況使用左旋轉(zhuǎn)掖棉，
              if (node == rightOf(parentOf(node))) {
                  node = parentOf(node);
                  this.leftRotate(node);
              }
              /*
               經(jīng)過步驟1后墓律，變成了左左，或者直接就是左左幔亥，進行爺爺節(jié)點的右旋
               */
              this.setColor(parentOf(node), BLACK);
              this.setColor(grandpaOf(node), RED);
              this.rightRotate(grandpaOf(node));
          }
      } else { // 否則就是右子樹
          RBTreeNode uncleLeft = leftOf(grandpaOf(node));
          if (colorOf(uncleLeft) == RED) {
              setColor(parentOf(node), BLACK);
              setColor(uncleLeft, BLACK);
              setColor(grandpaOf(node), RED);
              node = grandpaOf(node);
          } else {
              // ②右左情況使用右旋
              if (node == leftOf(parentOf(node))) {
                  node = parentOf(node);
                  this.rightRotate(node);
              }
              /*
               經(jīng)過步驟2后變成了右右耻讽，或者直接就是右右，左旋
               */
              this.setColor(parentOf(node), BLACK);
              this.setColor(grandpaOf(node), RED);
              this.leftRotate(grandpaOf(node));
          }
      }
    }
    
    root.color = BLACK;
    

• 哈夫曼樹（Huffman Tree）

  哈夫曼樹是一種帶權(quán)路徑長度最短的二叉樹帕棉，也稱為最優(yōu)二叉樹针肥。

  這個比較抽象，暫時還沒理解香伴。

• B樹（B-Tree）

  B樹就時B-樹慰枕，-難道只是一個符號而已？

  B樹是一種自平衡的樹即纲，它是一種多路搜索樹（不是二叉樹）具帮，能夠保證數(shù)據(jù)有序。同時它還保證了在查找低斋、插入蜂厅、刪除等操作時性能都保持在O(log n)，對大塊數(shù)據(jù)的讀寫操作做了優(yōu)化膊畴，同時它也可以用來描述外部存儲（支持對保存在磁盤或者網(wǎng)絡上的符號表進行外部查找）掘猿。

  具有以下性質(zhì)：

  • 定義任意非葉子節(jié)點最多只有M個子節(jié)點，且M>2唇跨。
  • 根節(jié)點的子節(jié)點數(shù)為[2, M]稠通。
  • 除根節(jié)點外的非葉子節(jié)點的子節(jié)點數(shù)為[M/2, M]礁遵。
  • 每個節(jié)點存放至少M/2 -1（向上取整）和之多M-1個關(guān)鍵字（至少2個關(guān)鍵字）。
  • 非葉子節(jié)點的關(guān)鍵字個數(shù)等于(指向子節(jié)點的指針個數(shù)-1)采记。
  • 非葉子節(jié)點的關(guān)鍵字：K[1], K[2], …, K[M-1]；且K[i] < K[i+1]政勃。
  • 非葉子節(jié)點的指針：P[1], P[2], …, P[M]唧龄，其中P[1]指向關(guān)鍵字小于K[1]的子樹，P[M]指向關(guān)鍵字大于K[M-1]的子樹奸远，其它P[i]指向關(guān)鍵字屬于(K[i-1], K[i])的子樹既棺。
  • 所有葉子節(jié)點位于同一層。

  有序數(shù)組+平衡多叉樹

• B+樹

  B+樹是B-樹的變體懒叛，也是一種多路搜索樹丸冕。

  B+的搜索與B-樹基本相同，區(qū)別是B+樹只有達到葉子節(jié)點才命中（B-樹可以在非葉子節(jié)點命中）薛窥，其性能也等價于在關(guān)鍵字全集做一次二分查找胖烛。

  具有以下性質(zhì)：

  • 所有關(guān)鍵字都出現(xiàn)在葉子節(jié)點的鏈表中（稠密索引），且鏈表中的關(guān)鍵字恰好是有序的诅迷。
  • 不可能在非葉子節(jié)點命中佩番。
  • 非葉子節(jié)點相當于是葉子節(jié)點的索引（稀疏索引），葉子節(jié)點相當于是存儲（關(guān)鍵字）數(shù)據(jù)的數(shù)據(jù)層罢杉。

• 非葉子節(jié)點的子樹指針與關(guān)鍵字個數(shù)相同趟畏。

  • 非葉子節(jié)點的子樹指針P[i]，指向關(guān)鍵字值屬于[k[i], K[i+1]]滩租。

• 為所有葉子節(jié)點增加一個鏈指針（也就是同級的后續(xù)鏈表赋秀，這也是B+為什么特別適合范圍查找的原因）。

B+樹更適合文件索引系統(tǒng)律想，因為：

增刪文件（節(jié)點）時猎莲，效率更高，因為B+樹的葉子節(jié)點包含所有關(guān)鍵字蜘欲，并以有序的鏈表結(jié)構(gòu)存儲益眉，可以很好的提高增刪效率。

**使用場景：**

+ Mac：HFS姥份，HFS+文件系統(tǒng)

• DB：Oracle郭脂、MySQL等

有序數(shù)組鏈表+平衡多叉樹

**優(yōu)點：**

• 層級更低，IO次數(shù)更少澈歉。
  • 每次都需要查詢到葉子節(jié)點展鸡，查詢性能穩(wěn)定。
• 葉子節(jié)點行程是有序鏈表埃难，范圍查詢方便莹弊。

相比較于B樹涤久，B+樹還有一個最大的好處，方便掃庫忍弛，B樹必須用中序遍歷的方法按序掃庫响迂，而B+樹直接從葉子節(jié)點挨個掃一遍就ok了，B+樹支持range-query非常方便细疚，而B樹不支持蔗彤。這是數(shù)據(jù)庫選用B+樹的最主要原因。

• B*樹

  B*樹是B+樹的變體疯兼，在B+樹的非根和非葉子節(jié)點再增加指向兄弟的指針然遏。

  在B+樹基礎上，為非葉子節(jié)點也增加鏈表指針吧彪，將節(jié)點的最低利用率從1/2提到到2/3待侵。

• R樹

  R樹是用來左空間數(shù)據(jù)存儲的樹狀數(shù)據(jù)結(jié)構(gòu)。例如地理位置姨裸，舉行和多邊形這類多維數(shù)據(jù)建立索引秧倾。

  R樹的核心思想是聚合距離相近的節(jié)點并在樹結(jié)構(gòu)的上一層講起表示為這些節(jié)點的最小外接矩形（（MBR），這個最小外接舉行就成為上一層的一個節(jié)點啦扬。因為所有節(jié)點都在它們的最小外接矩形中中狂，所以跟某個矩形不相交的查詢就一定跟這個矩形中的所有節(jié)點都不相交。葉子節(jié)點上的每個矩形都代表一個對象扑毡，節(jié)點都是對象的聚合胃榕，并且越往上層聚合的對象就越多。也可以把每一層看作是對數(shù)據(jù)集的近似瞄摊，葉子節(jié)點層是最細粒度的近似勋又，與數(shù)據(jù)集相似度100%，越往上層越粗糙换帜。