数据结构之 树

• 二叉树

  每个节点最多有两个子树的树结构，在二叉树的概念下又衍生出满二叉树和完全二叉树。

  • 满二叉树

    除最后一层无任何子节点外，每一层上的所有节点都有两个子节点。也可以理解为，除叶子节点外的所有节点均有两个子节点。节点数达到最大值，所有叶子节点必须在同一层上。

  • 完全二叉树

    若设二叉树的高度为h，除第h层外，其它各层（1～h-1）的节点数都达到最大个数，第h层所有的节点都连续集中在最左边。

  • 二叉查找树

    二叉查找树是二叉树的衍生概念，Binary Serarch Tree，也称为二叉搜索树、有序二叉树（Ordered Binary Tree）或排序二叉树（Sorted Binary Tree），是指一颗空树或具有下列性质的二叉树。

    • 若任意节点的左子树不为空，则左子树上所有节点的值均小于它的根节点的值。
    • 若任意节点的右子树不为空，则右子树上所有节点的值均大于它的根节点的值。
    • 任意节点的左、右子树也分别为二叉查找树。

  • 没有键值相等的节点。

    二叉查找树相比于其它数据结构的优势在于查找、插入的时间复杂度较低，O(log n)。二叉查找树是基础性数据结构，用于构建更为抽象的数据结构，如集合，多重集，关联数组等。

  • 平衡二叉树（AVL树）

    当且仅当任何节点的两个子树的高度差不大于1的二叉树。

    其中AVL树是最先发明的自平衡二叉查找树，是最原始典型的平衡二叉树。

    平衡二叉树是基于二叉查找树的改进。由于某些极端的情况下（插入的序列是有序时），二叉查找树将退化程近似链表的数据结构，此时其操作的时间复杂度将退化成线性的，即O(n)。所以通过自平衡操作（旋转）构建两个子树高度差不超过1的平衡二叉树。

    如果执行插入或者删除操作，只要不满足平衡条件的，就要通过旋转来保持平衡，但是旋转是非常耗时的。

    使用场景：

    AVL树适用于插入、删除次数比较少，查比较多的情况。

  • 红黑树

    红黑树是自平衡的二叉查找树。它是一种查找、增加、删除效率都比较均衡的二叉查找树，增加或者删除的时候，只要能够保证操作后的树结构从根到叶子节点的最长路径不会是最短路径的两倍，那么就不会触发平衡策略进行旋转，要知道，旋转真的是非常耗时的。

    具有以下性质：

    • 每个节点要么是红的，要么是黑的。
    • 根节点一定是黑的。
    • 每个叶子节点都是黑色的空节点（NIL节点）。
    • 如果一个节点是红的，那么它的两个子节点都是黑的。
    • 从任意节点到其每个叶子的所有路径都包含相同数目的黑色节点。

    用上面五个条件，我们可以模拟推导出一个结论：即红黑树确保从根到叶子节点的最长路径不会是最短路径的两倍，用非严格的平衡策略来换取增、删节点时，旋转次数的降低，任何不平衡都会在三次旋转之内解决。

    使用场景：

    • 广泛用在C++的STL中。
    • 注明的linux进程调度Completely Fair Scheduler，用红黑树管理进程控制块。
    • epoll在内核中的实现，用红黑树管理事件块。
    • nginx中，用红黑树管理timer等。
    • Java 8中的HashMap当链表长度大于8时，转为红黑树进行存储。

    红黑树的查询性能略逊于AVL树，因为AVL树会稍微不平衡最多一层，也就是说红黑树的查询性能只比相同内容的AVL树最多多一次比较，但是，红黑树在插入和删除上完爆AVL树，AVL树每次插入删除会进行大量的平衡度计算，而红黑树为了维持红黑性质所做的红黑转变和旋转的开销，相较于AVL树为了维持平衡的开销要小得多。

    旋转程序

    当前节点用node表示；

    父节点用father表示；

    爷爷节点用grandpa表示；

    叔叔节点用uncle表示；

    while (node != null && node != root && node.parent.color == RED) {
      // 父节点是爷爷节点的左子树
      if (parentOf(node) == leftOf(grandpaOf(node))) {
          RBTreeNode uncleRight = rightOf(grandpaOf(node));
          /*
           判断父节点和叔叔节点是否都为红色
           父节肯定为红色，除非是根节点，一旦是黑色，压根就不用左旋转或者右旋转
           */
          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后，变成了左左，或者直接就是左左，进行爷爷节点的右旋
               */
              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）

  哈夫曼树是一种带权路径长度最短的二叉树，也称为最优二叉树。

  这个比较抽象，暂时还没理解。

• B树（B-Tree）

  B树就时B-树，-难道只是一个符号而已？

  B树是一种自平衡的树，它是一种多路搜索树（不是二叉树），能够保证数据有序。同时它还保证了在查找、插入、删除等操作时性能都保持在O(log n)，对大块数据的读写操作做了优化，同时它也可以用来描述外部存储（支持对保存在磁盘或者网络上的符号表进行外部查找）。

  具有以下性质：

  • 定义任意非叶子节点最多只有M个子节点，且M>2。
  • 根节点的子节点数为[2, M]。
  • 除根节点外的非叶子节点的子节点数为[M/2, M]。
  • 每个节点存放至少M/2 -1（向上取整）和之多M-1个关键字（至少2个关键字）。
  • 非叶子节点的关键字个数等于(指向子节点的指针个数-1)。
  • 非叶子节点的关键字：K[1], K[2], …, K[M-1]；且K[i] < K[i+1]。
  • 非叶子节点的指针：P[1], P[2], …, P[M]，其中P[1]指向关键字小于K[1]的子树，P[M]指向关键字大于K[M-1]的子树，其它P[i]指向关键字属于(K[i-1], K[i])的子树。
  • 所有叶子节点位于同一层。

  有序数组+平衡多叉树

• B+树

  B+树是B-树的变体，也是一种多路搜索树。

  B+的搜索与B-树基本相同，区别是B+树只有达到叶子节点才命中（B-树可以在非叶子节点命中），其性能也等价于在关键字全集做一次二分查找。

  具有以下性质：

  • 所有关键字都出现在叶子节点的链表中（稠密索引），且链表中的关键字恰好是有序的。
  • 不可能在非叶子节点命中。
  • 非叶子节点相当于是叶子节点的索引（稀疏索引），叶子节点相当于是存储（关键字）数据的数据层。

• 非叶子节点的子树指针与关键字个数相同。

  • 非叶子节点的子树指针P[i]，指向关键字值属于[k[i], K[i+1]]。

• 为所有叶子节点增加一个链指针（也就是同级的后续链表，这也是B+为什么特别适合范围查找的原因）。

B+树更适合文件索引系统，因为：

增删文件（节点）时，效率更高，因为B+树的叶子节点包含所有关键字，并以有序的链表结构存储，可以很好的提高增删效率。

**使用场景：**

+ Mac：HFS，HFS+文件系统

• DB：Oracle、MySQL等

有序数组链表+平衡多叉树

**优点：**

• 层级更低，IO次数更少。
  • 每次都需要查询到叶子节点，查询性能稳定。
• 叶子节点行程是有序链表，范围查询方便。

相比较于B树，B+树还有一个最大的好处，方便扫库，B树必须用中序遍历的方法按序扫库，而B+树直接从叶子节点挨个扫一遍就ok了，B+树支持range-query非常方便，而B树不支持。这是数据库选用B+树的最主要原因。

• B*树

  B*树是B+树的变体，在B+树的非根和非叶子节点再增加指向兄弟的指针。

  在B+树基础上，为非叶子节点也增加链表指针，将节点的最低利用率从1/2提到到2/3。

• R树

  R树是用来左空间数据存储的树状数据结构。例如地理位置，举行和多边形这类多维数据建立索引。

  R树的核心思想是聚合距离相近的节点并在树结构的上一层讲起表示为这些节点的最小外接矩形（（MBR），这个最小外接举行就成为上一层的一个节点。因为所有节点都在它们的最小外接矩形中，所以跟某个矩形不相交的查询就一定跟这个矩形中的所有节点都不相交。叶子节点上的每个矩形都代表一个对象，节点都是对象的聚合，并且越往上层聚合的对象就越多。也可以把每一层看作是对数据集的近似，叶子节点层是最细粒度的近似，与数据集相似度100%，越往上层越粗糙。