數(shù)據(jù)結構之 樹

• 二叉樹

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

  • 滿二叉樹

    除最后一層無任何子節(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），是指一顆空樹或具有下列性質的二叉樹。

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

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

    二叉查找樹相比于其它數(shù)據(jù)結構的優(yōu)勢在于查找、插入的時間復雜度較低，O(log n)。二叉查找樹是基礎性數(shù)據(jù)結構，用于構建更為抽象的數(shù)據(jù)結構，如集合，多重集，關聯(lián)數(shù)組等。

  • 平衡二叉樹（AVL樹）

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

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

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

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

    使用場景：

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

  • 紅黑樹

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

    具有以下性質：

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

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

    使用場景：

    • 廣泛用在C++的STL中。
    • 注明的linux進程調度Completely Fair Scheduler，用紅黑樹管理進程控制塊。
    • epoll在內核中的實現(xiàn)，用紅黑樹管理事件塊。
    • nginx中，用紅黑樹管理timer等。
    • Java 8中的HashMap當鏈表長度大于8時，轉為紅黑樹進行存儲。

    紅黑樹的查詢性能略遜于AVL樹，因為AVL樹會稍微不平衡最多一層，也就是說紅黑樹的查詢性能只比相同內容的AVL樹最多多一次比較，但是，紅黑樹在插入和刪除上完爆AVL樹，AVL樹每次插入刪除會進行大量的平衡度計算，而紅黑樹為了維持紅黑性質所做的紅黑轉變和旋轉的開銷，相較于AVL樹為了維持平衡的開銷要小得多。

    旋轉程序

    當前節(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é)點，一旦是黑色，壓根就不用左旋轉或者右旋轉
           */
          if (colorOf(uncleRight) == RED) {
              setColor(parentOf(node), BLACK);
              setColor(uncleRight, BLACK);
              setColor(grandpaOf(node), RED);
              node = grandpaOf(node);
          } else {
              // ①左右情況使用左旋轉，
              if (node == rightOf(parentOf(node))) {
                  node = parentOf(node);
                  this.leftRotate(node);
              }
              /*
               經過步驟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);
              }
              /*
               經過步驟2后變成了右右，或者直接就是右右，左旋
               */
              this.setColor(parentOf(node), BLACK);
              this.setColor(grandpaOf(node), RED);
              this.leftRotate(grandpaOf(node));
          }
      }
    }
    
    root.color = BLACK;
    

• 哈夫曼樹（Huffman Tree）

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

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

• B樹（B-Tree）

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

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

  具有以下性質：

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

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

• B+樹

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

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

  具有以下性質：

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

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

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

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

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

增刪文件（節(jié)點）時，效率更高，因為B+樹的葉子節(jié)點包含所有關鍵字，并以有序的鏈表結構存儲，可以很好的提高增刪效率。

**使用場景：**

+ 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ù)結構。例如地理位置，舉行和多邊形這類多維數(shù)據(jù)建立索引。

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