个人笔记-《高级数据结构》

内容

1. Why and how O(log n) access time?
2. Dynamic data structure and Analysis
3. Randomized Data Structure
4. Augmented Data Structure
5. Data Structures in Distributed Environments
6. Data Structures in Frontiers of Research
7. Exam

---

逆序对

1. 随即序列 逆序对为 n(n-1)/4
   1. 证明:全逆序序列 ,如 5,4,3,2,1，则总计4+3+2+1，共Cn(2)个，即n(n-1)/2
   2. 交换相邻元素的本质：消除一对逆序

---

跳表

1. 跳表(Skip List)
2. 说明：wiki
3. 图解：
4. 参考代码： 链接 链接

查找：

p=top
While(1){
    while (p->next->key < x ) p=p->next;
    If (p->down == NULL ) return p->next
    p=p->down ;
}

插入：

int insert(val x){

    int i;
    int j = n; //n是当前表所拥有的level数

    cell *p[k]; //指针数组，用来保存每一层要插入元素的前驱

    cell *p1;
    p1 = top->next;

    while(p1){
        while(p1->next->val < x) p1=p1->next;
        if(j <= k){
            p[j-1] = p1; //保存每一层的指针
            p1 = p1->down; //指向下一层
            j--;
        }
    }

    //下面的代码是将x插入到各层
    for (i = 0; i<k; i++){
        if(p[i]==NULL){//k>n的情况，需要创建一个层
            //创建层的第一个元素，并将top指向它
            cell *elementhead = (cell *) malloc(sizeof(cell));
            element->val = -1;
            element->down = top;
            top = elementhead; 

            //创建最后一个元素
            cell *elementtail = (cell *) malloc(sizeof(cell));
            elementtail->val = 1;
            elementtail->next = elementtail->down = NULL;

            //在该层中创建并插入x
            cell *element = (cell *) malloc(sizeof(cell));
            element->val = x;
            elementhead->next = element;
            element->next = elementtail;
            element->down = p[i-1]->next;
        }

        //正常插入一个元素
        cell *element = (cell *) malloc(sizeof(cell));
        element->val = x;
        element->next = p[i]->next;
        element->down = (i=0?NULL:(p[i-1]->next));
        p[i]->next = element;
    }

    return 0;
}

删除：

int delete(val x){

    int i = n; //n表示当前总层数
    cell *p, *p1;
    p = top;

    while(n>0){
        while(p->next->val < x) p=p->next;
        if(p->next->val == x){//假如当前层存在节点x,删除
            if(p = top && p->next->next->val == INT_MAX){//该层之存在一个节点
                top = p->down;
                free(p->next->next);
                free(p->next);
                free(p);
                p = top;
            }
            else{
                p1 = p->next;
                p->next = p1->next;
                free(p1);
            }
        }
        p = p->down;
        n--;
    }
}

---

一致哈希表

1. 定义：按照常用的hash算法来将对应的key哈希到一个具有2^32次方个桶的空间中，即0~(2^32)-1的数字空间中。现在我们可以将这些数字头尾相连，想象成一个闭合的环形。

2. 图解：

3. 代码

   import java.util.Collection;  
   import java.util.SortedMap;  
   import java.util.TreeMap;  
   
   public class ConsistentHash<T> {  
   
    private final HashFunction hashFunction;  
    private final int numberOfReplicas;  
    private final SortedMap<Integer, T> circle = new TreeMap<Integer, T>();  
   
    public ConsistentHash(HashFunction hashFunction, int numberOfReplicas,  
        Collection<T> nodes) {  
      this.hashFunction = hashFunction;  
      this.numberOfReplicas = numberOfReplicas;  
   
      for (T node : nodes) {  
        add(node);  
      }  
    }  
   
    public void add(T node) {  
      for (int i = 0; i < numberOfReplicas; i++) {  
        circle.put(hashFunction.hash(node.toString() + i), node);  
      }  
    }  
   
    public void remove(T node) {  
      for (int i = 0; i < numberOfReplicas; i++) {  
        circle.remove(hashFunction.hash(node.toString() + i));  
      }  
    }  
   
    public T get(Object key) {  
      if (circle.isEmpty()) {  
        return null;  
      }  
      int hash = hashFunction.hash(key);  
      if (!circle.containsKey(hash)) {  
        SortedMap<Integer, T> tailMap = circle.tailMap(hash);  
        hash = tailMap.isEmpty() ? circle.firstKey() : tailMap.firstKey();  
      }  
      return circle.get(hash);  
    }  
   } 

4. 目标：

   1. 可扩展，快速添加，删除结点
   2. 平衡性，对数据分布（尤其是一个结点被删除后，如何快速把这个空结点分配）
   3. 虚拟结点：虚拟结点分布在两个真实结点之间，加速查询，所有落在虚拟结点上的，会直接指向真实结点

---

排序

1. 左出序：记录Ri的关键字值为Ki，Ri是左出序当且仅当Ki < max{Kj}(0<=j<i)，既这个关键字左边的值至少有一个比它大。有几个比它大叫做几个左出序。

2. 插入排序，时间为O((k+1)*n)，k为左出序记录个数，故左出序越少性能越好

3. 冒泡排序，每次交换消除一对逆序，算法平均O(n^2)

4. 希尔排序，在插入排序基础上，将总记录划分为多个子记录，每个记录相隔incr个元素。算法交换非相邻元素，故可能一次交换消除多对逆序，鉴于非相邻交换时消除逆序对数量随机，在统计上计算，可知算法复杂度在O(n^1.2 ~ n^2)之间（唯一一个无法纯理论计算出复杂度的排序算法）

5. 希尔排序改进，数学归纳法:1) 定义hk = 2^k -1,若hk 已经排序，则h(k-1)也排序，不会打乱之前的排序（不创造新逆序，只消除逆序），可最终导致h(1)排序。 2) 如果hk 和 h(k-1)已经排序，则可知h(k)和h(k-1)的公倍数序列也排序，则h(k-2)排序的时候不用考虑该序列 3)使用递归

6. 快速排序改进了希尔排序，将基准记录放在一个位置，分为左右两个记录表，左边所有元素都小于右边的最小的，然后递归地对两个左右记录表进行排序（这个过程可以独立），最终合并。相对稳定，平均O(nlogn)，最差O(n^2)

7. 归并排序需要辅助空间O(n-l+1)，对左右任意分配的（一般是长度相同或者-1）的两表直接归并（站队归并），可以通过循环或者递归归并来进行排序。也是O(nlogn)，稳定排序

8. 堆排序：利用最大堆，通过插入和删除操作，得出排序序列。为了优化构建最大堆的效率，可以采用优化的adjust方法来使堆成为最大堆。

9. 基数排序：在关键字值为0到n-1的整数范围内饰，可以直接装箱。箱子个数取决于排序元素，对于数字可以2进制的2个箱子，也可以10进制10个箱子，对于字母可以26个箱子。比如说用十进制为基数排序，按照个位，十位，百位……依次构成链表的节点（即每层链表10个节点），然后存储所有满足位数的元素。
   每次扫描时，首先从个位开始，按照0-9的顺序排过去，结果链表保留下来，进行下一轮。下一轮从十位开始，从结果链表选出，用十位排序，更新结果链表…………直到最终扫描结束（扫描次数就是关键字长度，比如0-999就是3次）
   效率为O(n)，缺点是占用空间较大

---

查找

1. 二叉查找树

   1. 定义：（1）是二叉树 （2）关键字不重 （3）左孩子小于根节点，右孩子大于根节点（如果有的话）（4）左右子树也为二叉查找树（如果有的话）
   2. 查找：与根节点比较，小于走左，大于走右，等于返回，找不到null
   3. 插入：先查找，如果有重合的返回false，如果不重，在搜索的结束位置加入新的节点
   4. 删除：先查找，找到就删除，找不到返回。

2. AVL树：见书上，理解4种旋转。

3. 红黑树：

   1. 定义：
      1. 节点是红色或黑色。
      2. 根是黑色。
      3. 所有叶子都是黑色（叶子是NIL节点）。
      4. 每个红色节点必须有两个黑色的子节点。(从每个叶子到根的所有路径上不能有两个连续的红色节点。)
      5. 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。
   2. 查找：因为红黑树也是二叉查找树，因此红黑树上的查找操作与普通二叉查找树上的查找操作相同。即递归下去比较，等于根节点返回，小于向左走，大于向右走。
   3. 插入：(1) 查找要插入的位置，时间复杂度为：O(N) (2) 将新节点的color赋为红色 (3) 自下而上重新调整该树为红黑树
   4. 删除：(1) 查找要删除位置，时间复杂度为：O(N) (2) 用删除节点后继或者节点替换该节点（只进行数据替换即可，不必调整指针，后继节点是中序遍历中紧挨着该节点的节点，即：右孩子的最左孩子节点） (3) 如果删除节点的替换节点为黑色，则需重新调整该树为红黑树
   5. 旋转：复杂，保证规则不变的情况下，在插入和删除下各有3种情况
   6. 应用：快速搜索，字典
   7. 图片：

4. Splay树：见书，每次插入删除可能不平衡，会造成旋转。4种旋转LL,RR,LR,RL，只需要2类旋转函数即可。

5. B-树：

   1. 定义： B-树结构特性：一棵m阶B-树，或为空树，或为满足下列特性的m叉树：(m≥3)
      1. 根结点只有1个，关键字字数的范围[1,m-1]，分支数量范围[2,m]；
      2. 除根以外的非叶结点，每个结点包含分支数范围[[m/2],m]，即关键字字数的范围是[[m/2]-1,m-1]，其中[m/2]表示取大于等于m/2的最小整数；
      3. 叶结点是由非叶结点分裂而来的，所以叶结点关键字个数也满足[[m/2]-1,m-1]；
      4. 所有的非终端结点包含信息：(n，A0，K1，A1，K2，A2，……，Kn，An)，其中Ki为关键字，Ai为指向子树根结点的指针，并且Ai-1所指子树中的关键字均小于Ki，而Ai所指的关键字均大于Ki（i=1，2，……，n）。n+1表示B-树的阶，n表示关键字个数；
      5. 所有叶子结点都在同一层，并且指针域为空，具有如下性质： 根据B树定义，第一层为根有一个结点，至少两个分支，第二层至少2个结点，i≥3时，每一层至少有2乘以([m/2])的i-2次方个结点([m/2]表示取大于m/2的最小整数)。若m阶树中共有N个结点，那么可以推导出N必然满足N≥2*(([m/2])的h-1次方)-1 (h≥1)，因此若查找成功，则高度h≤1+log[m/2](N+1)/2，h也是磁盘访问次数(h≥1)，保证了查找算法的高效率。
   2. 查找：首先从根结点开始重复如下过程： 若比结点的第一个关键字小，则查找在该结点第一个指针指向的结点进行；若等于结点中某个关键字，则查找成功；若在两个关键字之间，则查找在它们之间的指针指向的结点进行；若比该结点所有关键字大，则查找在该结点最后一个指针指向的结点进行；若查找已经到达某个叶结点，则说明给定值对应的数据记录不存在，查找失败。
   3. 插入：
      1. B-树的生成从空树开始，逐个插入关键字而得。关键字的个数必须至少为[m/2]-1，每次插入总在最底层某个终端结点添加一个关键字，如果该结点关键字个数小于m-1则直接插入，如果发现新插入关键字后，关键字总数超过m-1个则结点需要分裂，做法如下：
      2. 假设结点p中已经含有m-1个关键字，再插入一个关键字之后(插入总要保持关键字数组的大小有序，从小到大排好序)，可以将p分裂为p和p’，其中p含有的信息为[m/2]-1([m]表示大于m的最小整数)，p’含有的信息为m-[m/2] ([m]表示大于m的最小整数)。然后将关键字K[m/2]和指向p’的指针则一起插入到p的双亲结点中去。
      3. 检查双亲结点，如果双亲结点出现(a)的情况，则回到步骤a继续执行。直到插入满足条件为止，树的深度增加过程是随着插入而自下而上生长的过程。
   4. 删除：
      1. B-树删除算法分析，分以下5种情况讨论：
      2. 被删除关键字所在的结点为叶结点，关键字数目大于或等于[m/2]，则只需要直接删去Ai和Ki即可；
      3. 被删除关键字所在的结点为叶结点，关键字数目等于[m/2]-1，相邻的左右兄弟关键字数目至少有一方大于或者等于[m/2]，此时，如果右兄弟关键字数目大于或者等于[m/2]，则将右兄弟中最小的关键字上移到双亲结点中，然后将其中紧靠在上移关键字左边的一个关键字移动到被删除关键字所在的结点的最右边；否则，如果左兄弟的关键字数目大于或者等于[m/2]，则左兄弟中最大的关键字上移到双亲结点中，将紧靠在该上移关键字右边的一个关键字移动到被删除关键字所在的结点的最左边。这些做法类似于减法的借位运算。
      • 被删除关键字所在的结点为叶结点，关键字数目等于[m/2]-1，相邻的左右兄弟关键字数目均等于[m/2]-1，则从双亲借关键字补充，然后算法进入非叶结点的删除判断；
      • 被删除关键字所在的结点为非叶结点，并且关键字数目大于或等于[m/2]，则删去Ai和Ki后，原来关键字的左右孩子进行合并，若合并后的结点的关键字数目满足B-树性质，则结束，而对于关键字数目大于m-1，则进行一次分裂，将其中一个结点移到当前结点中。
      • 被删除关键字所在的结点为非叶结点，关键字数目等于[m/2]-1，相邻的左右兄弟关键字数目均等于[m/2]-1，则删除该关键字之后优先判断能否从被删除的关键字的左右孩子中寻找关键字补充，如果左右孩子的关键字数目均为[m/2]-1，如果此结点已经是树的根，则直接将被删除关键字的左右孩子结点合并即可，如果不是树的根，则从自己的双亲补充关键字，然后重复上述判断算法(d)或者(e)。
      • 应用：数据库搜索
      • 图片：

6. B+树：

   1. 定义： B+树是应文件系统所需而出的一种B-树的变型树。一棵m阶的B+树和m阶的B-树的差异在于：
      1. 有n棵子树的结点中含有n个关键字，每个关键字不保存数据，只用来索引，所有数据都保存在叶子节点。
      2. 所有的叶子结点中包含了全部关键字的信息，及指向含这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接。
      3. 所有的非终端结点可以看成是索引部分，结点中仅含其子树（根结点）中的最大（或最小）关键字。 通常在B+树上有两个头指针，一个指向根结点，一个指向关键字最小的叶子结点。
   2. 查找：
      1. 从最小关键字起顺序查找；
      2. 从根结点开始，进行随机查找。 在查找时，若非终端结点上的关键值等于给定值，并不终止，而是继续向下直到叶子结点。因此，在B+树中，不管查找成功与否，每次查找都是走了一条从根到叶子结点的路径。其余同B-树的查找类似。
   3. 插入： m阶B树的插入操作在叶子结点上进行，假设要插入关键值a，找到叶子结点后插入a，做如下算法判别：
      1. 如果当前结点是根结点并且插入后结点关键字数目小于等于m，则算法结束；
      2. 如果当前结点是非根结点并且插入后结点关键字数目小于等于m，则判断若a是新索引值时转步骤④后结束，若a不是新索引值则直接结束；
      3. 如果插入后关键字数目大于m(阶数)，则结点先分裂成两个结点X和Y，并且他们各自所含的关键字个数分别为：u=大于(m+1)/2的最小整数，v=小于(m+1)/2的最大整数； 由于索引值位于结点的最左端或者最右端，不妨假设索引值位于结点最右端，有如下操作： 如果当前分裂成的X和Y结点原来所属的结点是根结点，则从X和Y中取出索引的关键字，将这两个关键字组成新的根结点，并且这个根结点指向X和Y，算法结束； 如果当前分裂成的X和Y结点原来所属的结点是非根结点，依据假设条件判断，如果a成为Y的新索引值，则转步骤④得到Y的双亲结点P，如果a不是Y结点的新索引值，则求出X和Y结点的双亲结点P；然后提取X结点中的新索引值a’，在P中插入关键字a’，从P开始，继续进行插入算法；
      4. 提取结点原来的索引值b，自顶向下，先判断根是否含有b，是则需要先将b替换为a，然后从根结点开始，记录结点地址P，判断P的孩子是否含有索引值b而不含有索引值a，是则先将孩子结点中的b替换为a，然后将P的孩子的地址赋值给P，继续搜索，直到发现P的孩子中已经含有a值时，停止搜索，返回地址P。
   4. 删除：B+树的删除也仅在叶子结点进行，当叶子结点中的最大关键字被删除时，其在非终端结点中的值可以作为一个“分界关键字”存在。若因删除而使结点中关键字的个数少于m/2 （m/2结果取上界，如5/2结果为3）时，其和兄弟结点的合并过程亦和B-树类似。
   5. 应用：文件系统
   6. 图片：

7. R树：多维空间中的搜索树

   1. 定义：
      1. 除非它是根结点之外，所有叶子结点包含有m至M个记录索引（条目）。作为根结点的叶子结点所具有的记录个数可以少于m。通常，m=M/2。
      2. 对于所有在叶子中存储的记录（条目），I是最小的可以在空间中完全覆盖这些记录所代表的点的矩形（注意：此处所说的“矩形”是可以扩展到高维空间的）。
      3. 每一个非叶子结点拥有m至M个孩子结点，除非它是根结点。
      4. 对于在非叶子结点上的每一个条目，i是最小的可以在空间上完全覆盖这些条目所代表的店的矩形（同性质2）。
      5. 所有叶子结点都位于同一层，因此R树为平衡树。
   2. 搜索：R树的插入操作也同B树的插入操作类似。当新的数据记录需要被添加入叶子结点时，若叶子结点溢出，那么我们需要对叶子结点进行分裂操作。显然，叶子结点的插入操作会比搜索操作要复杂。插入操作需要一些辅助方法才能够完成。
   3. 插入：R树的插入操作也同B树的插入操作类似。当新的数据记录需要被添加入叶子结点时，若叶子结点溢出，那么我们需要对叶子结点进行分裂操作。显然，叶子结点的插入操作会比搜索操作要复杂。插入操作需要一些辅助方法才能够完成。
   4. 删除：R树的删除操作与B树的删除操作会有所不同，不过同B树一样，会涉及到压缩等操作。相信读者看完以下的伪代码之后会有所体会。R树的删除同样是比较复杂的，需要用到一些辅助函数来完成整个操作。
   5. 应用：空间搜索，地图定位，图片查找
   6. 图片：

---

时间/空间复杂度表

常用算法和数据结构的复杂度速查表

搜索

    <th>
      数据结构
    </th>
    
    <th colspan="2">
      时间复杂度
    </th>
    
    <th colspan="3">
      空间复杂度
    </th>
  </tr>
  
  <tr>
    <th>
    </th>
    
    <th>
    </th>
    
    <th>
      平均
    </th>
    
    <th>
      最差
    </th>
    
    <th>
      最差
    </th>
  </tr>
</thead>

<tbody>
  <tr>
    <td>
      <a href="http://en.wikipedia.org/wiki/Depth-first_search">深度优先搜索 (DFS)</a>
    </td>
    
    <td>
      Graph of |V| vertices and |E| edges
    </td>
    
    <td>
      <code>-</code>
    </td>
    
    <td>
      <code>O(|E| + |V|)</code>
    </td>
    
    <td>
      <code>O(|V|)</code>
    </td>
  </tr>
  
  <tr>
    <td>
      <a href="http://en.wikipedia.org/wiki/Breadth-first_search">广度优先搜索 (BFS)</a>
    </td>
    
    <td>
      Graph of |V| vertices and |E| edges
    </td>
    
    <td>
      <code>-</code>
    </td>
    
    <td>
      <code>O(|E| + |V|)</code>
    </td>
    
    <td>
      <code>O(|V|)</code>
    </td>
  </tr>
  
  <tr>
    <td>
      <a href="http://en.wikipedia.org/wiki/Binary_search_algorithm">二分查找</a>
    </td>
    
    <td>
      Sorted array of n elements
    </td>
    
    <td>
      <code>O(log(n))</code>
    </td>
    
    <td>
      <code>O(log(n))</code>
    </td>
    
    <td>
      <code>O(1)</code>
    </td>
  </tr>
  
  <tr>
    <td>
      <a href="http://en.wikipedia.org/wiki/Brute-force_search">穷举</a>查找
    </td>
    
    <td>
      Array
    </td>
    
    <td>
      <code>O(n)</code>
    </td>
    
    <td>
      <code>O(n)</code>
    </td>
    
    <td>
      <code>O(1)</code>
    </td>
  </tr>
  
  <tr>
    <td>
      <a href="http://en.wikipedia.org/wiki/Dijkstra's_algorithm">最短路径-Dijkstra，用小根堆作为优先队列</a>
    </td>
    
    <td>
      Graph with |V| vertices and |E| edges
    </td>
    
    <td>
      <code>O((|V| + |E|) log |V|)</code>
    </td>
    
    <td>
      <code>O((|V| + |E|) log |V|)</code>
    </td>
    
    <td>
      <code>O(|V|)</code>
    </td>
  </tr>
  
  <tr>
    <td>
      <a href="http://en.wikipedia.org/wiki/Dijkstra's_algorithm">最短路径-Dijkstra，用无序数组作为优先队列</a>
    </td>
    
    <td>
      Graph with |V| vertices and |E| edges
    </td>
    
    <td>
      <code>O(|V|^2)</code>
    </td>
    
    <td>
      <code>O(|V|^2)</code>
    </td>
    
    <td>
      <code>O(|V|)</code>
    </td>
  </tr>
  
  <tr>
    <td>
      <a href="http://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm">最短路径-Bellman-Ford</a>
    </td>
    
    <td>
      Graph with |V| vertices and |E| edges
    </td>
    
    <td>
      <code>O(|V||E|)</code>
    </td>
    
    <td>
      <code>O(|V||E|)</code>
    </td>
    
    <td>
      <code>O(|V|)</code>
    </td>
  </tr>
</tbody>

算法

排序

    <th>
      数据结构
    </th>
    
    <th colspan="3">
      时间复杂度
    </th>
    
    <th colspan="3">
      最坏情况下的辅助空间复杂度
    </th>
  </tr>
  
  <tr>
    <th>
    </th>
    
    <th>
    </th>
    
    <th>
      最佳
    </th>
    
    <th>
      平均
    </th>
    
    <th>
      最差
    </th>
    
    <th>
      最差
    </th>
  </tr>
</thead>

<tbody>
  <tr>
    <td>
      <a href="http://en.wikipedia.org/wiki/Quicksort">快速排序</a>
    </td>
    
    <td>
      数组
    </td>
    
    <td>
      <code>O(n log(n))</code>
    </td>
    
    <td>
      <code>O(n log(n))</code>
    </td>
    
    <td>
      <code>O(n^2)</code>
    </td>
    
    <td>
      <code>O(n)</code>
    </td>
  </tr>
  
  <tr>
    <td>
      <a href="http://en.wikipedia.org/wiki/Merge_sort">归并排序</a>
    </td>
    
    <td>
      数组
    </td>
    
    <td>
      <code>O(n log(n))</code>
    </td>
    
    <td>
      <code>O(n log(n))</code>
    </td>
    
    <td>
      <code>O(n log(n))</code>
    </td>
    
    <td>
      <code>O(n)</code>
    </td>
  </tr>
  
  <tr>
    <td>
      <a href="http://en.wikipedia.org/wiki/Heapsort">堆排序</a>
    </td>
    
    <td>
      数组
    </td>
    
    <td>
      <code>O(n log(n))</code>
    </td>
    
    <td>
      <code>O(n log(n))</code>
    </td>
    
    <td>
      <code>O(n log(n))</code>
    </td>
    
    <td>
      <code>O(1)</code>
    </td>
  </tr>
  
  <tr>
    <td>
      <a href="http://en.wikipedia.org/wiki/Bubble_sort">冒泡排序</a>
    </td>
    
    <td>
      数组
    </td>
    
    <td>
      <code>O(n)</code>
    </td>
    
    <td>
      <code>O(n^2)</code>
    </td>
    
    <td>
      <code>O(n^2)</code>
    </td>
    
    <td>
      <code>O(1)</code>
    </td>
  </tr>
  
  <tr>
    <td>
      <a href="http://en.wikipedia.org/wiki/Insertion_sort">插入排序</a>
    </td>
    
    <td>
      数组
    </td>
    
    <td>
      <code>O(n)</code>
    </td>
    
    <td>
      <code>O(n^2)</code>
    </td>
    
    <td>
      <code>O(n^2)</code>
    </td>
    
    <td>
      <code>O(1)</code>
    </td>
  </tr>
  
  <tr>
    <td>
      <a href="http://en.wikipedia.org/wiki/Selection_sort">选择排序</a>
    </td>
    
    <td>
      数组
    </td>
    
    <td>
      <code>O(n^2)</code>
    </td>
    
    <td>
      <code>O(n^2)</code>
    </td>
    
    <td>
      <code>O(n^2)</code>
    </td>
    
    <td>
      <code>O(1)</code>
    </td>
  </tr>
  
  <tr>
    <td>
      <a href="http://en.wikipedia.org/wiki/Bucket_sort" rel="tooltip" data-original-title="Only for integers with range k">桶排序</a>
    </td>
    
    <td>
      数组
    </td>
    
    <td>
      <code>O(n+k)</code>
    </td>
    
    <td>
      <code>O(n+k)</code>
    </td>
    
    <td>
      <code>O(n^2)</code>
    </td>
    
    <td>
      <code>O(nk)</code>
    </td>
  </tr>
  
  <tr>
    <td>
      <a href="http://en.wikipedia.org/wiki/Radix_sort" rel="tooltip" data-original-title="Constant number of digits 'k'">基数排序</a>
    </td>
    
    <td>
      数组
    </td>
    
    <td>
      <code>O(nk)</code>
    </td>
    
    <td>
      <code>O(nk)</code>
    </td>
    
    <td>
      <code>O(nk)</code>
    </td>
    
    <td>
      <code>O(n+k)</code>
    </td>
  </tr>
</tbody>

算法

数据结构

    <th colspan="8">
      时间复杂度
    </th>
    
    <th>
      空间复杂度
    </th>
  </tr>
  
  <tr>
    <th>
    </th>
    
    <th colspan="4">
      平均
    </th>
    
    <th colspan="4">
      最差
    </th>
    
    <th>
      最差
    </th>
  </tr>
  
  <tr>
    <th>
    </th>
    
    <th>
      索引
    </th>
    
    <th>
      查找
    </th>
    
    <th>
      插入
    </th>
    
    <th>
      删除
    </th>
    
    <th>
      索引
    </th>
    
    <th>
      查找
    </th>
    
    <th>
      插入
    </th>
    
    <th>
      删除
    </th>
    
    <th>
    </th>
  </tr>
</thead>

<tbody>
  <tr>
    <td>
      <a href="http://en.wikipedia.org/wiki/Array_data_structure">基本数组</a>
    </td>
    
    <td>
      <code>O(1)</code>
    </td>
    
    <td>
      <code>O(n)</code>
    </td>
    
    <td>
      <code>-</code>
    </td>
    
    <td>
      <code>-</code>
    </td>
    
    <td>
      <code>O(1)</code>
    </td>
    
    <td>
      <code>O(n)</code>
    </td>
    
    <td>
      <code>-</code>
    </td>
    
    <td>
      <code>-</code>
    </td>
    
    <td>
      <code>O(n)</code>
    </td>
  </tr>
  
  <tr>
    <td>
      <a href="http://en.wikipedia.org/wiki/Dynamic_array">动态数组</a>
    </td>
    
    <td>
      <code>O(1)</code>
    </td>
    
    <td>
      <code>O(n)</code>
    </td>
    
    <td>
      <code>O(n)</code>
    </td>
    
    <td>
      <code>O(n)</code>
    </td>
    
    <td>
      <code>O(1)</code>
    </td>
    
    <td>
      <code>O(n)</code>
    </td>
    
    <td>
      <code>O(n)</code>
    </td>
    
    <td>
      <code>O(n)</code>
    </td>
    
    <td>
      <code>O(n)</code>
    </td>
  </tr>
  
  <tr>
    <td>
      <a href="http://en.wikipedia.org/wiki/Singly_linked_list#Singly_linked_lists">单链表</a>
    </td>
    
    <td>
      <code>O(n)</code>
    </td>
    
    <td>
      <code>O(n)</code>
    </td>
    
    <td>
      <code>O(1)</code>
    </td>
    
    <td>
      <code>O(1)</code>
    </td>
    
    <td>
      <code>O(n)</code>
    </td>
    
    <td>
      <code>O(n)</code>
    </td>
    
    <td>
      <code>O(1)</code>
    </td>
    
    <td>
      <code>O(1)</code>
    </td>
    
    <td>
      <code>O(n)</code>
    </td>
  </tr>
  
  <tr>
    <td>
      <a href="http://en.wikipedia.org/wiki/Doubly_linked_list">双链表</a>
    </td>
    
    <td>
      <code>O(n)</code>
    </td>
    
    <td>
      <code>O(n)</code>
    </td>
    
    <td>
      <code>O(1)</code>
    </td>
    
    <td>
      <code>O(1)</code>
    </td>
    
    <td>
      <code>O(n)</code>
    </td>
    
    <td>
      <code>O(n)</code>
    </td>
    
    <td>
      <code>O(1)</code>
    </td>
    
    <td>
      <code>O(1)</code>
    </td>
    
    <td>
      <code>O(n)</code>
    </td>
  </tr>
  
  <tr>
    <td>
      <a href="http://en.wikipedia.org/wiki/Skip_list">跳表</a>
    </td>
    
    <td>
      <code>O(log(n))</code>
    </td>
    
    <td>
      <code>O(log(n))</code>
    </td>
    
    <td>
      <code>O(log(n))</code>
    </td>
    
    <td>
      <code>O(log(n))</code>
    </td>
    
    <td>
      <code>O(n)</code>
    </td>
    
    <td>
      <code>O(n)</code>
    </td>
    
    <td>
      <code>O(n)</code>
    </td>
    
    <td>
      <code>O(n)</code>
    </td>
    
    <td>
      <code>O(n log(n))</code>
    </td>
  </tr>
  
  <tr>
    <td>
      <a href="http://en.wikipedia.org/wiki/Hash_table">哈希表</a>
    </td>
    
    <td>
      <code>-</code>
    </td>
    
    <td>
      <code>O(1)</code>
    </td>
    
    <td>
      <code>O(1)</code>
    </td>
    
    <td>
      <code>O(1)</code>
    </td>
    
    <td>
      <code>-</code>
    </td>
    
    <td>
      <code>O(n)</code>
    </td>
    
    <td>
      <code>O(n)</code>
    </td>
    
    <td>
      <code>O(n)</code>
    </td>
    
    <td>
      <code>O(n)</code>
    </td>
  </tr>
  
  <tr>
    <td>
      <a href="http://en.wikipedia.org/wiki/Binary_search_tree">二叉搜索树</a>
    </td>
    
    <td>
      <code>O(log(n))</code>
    </td>
    
    <td>
      <code>O(log(n))</code>
    </td>
    
    <td>
      <code>O(log(n))</code>
    </td>
    
    <td>
      <code>O(log(n))</code>
    </td>
    
    <td>
      <code>O(n)</code>
    </td>
    
    <td>
      <code>O(n)</code>
    </td>
    
    <td>
      <code>O(n)</code>
    </td>
    
    <td>
      <code>O(n)</code>
    </td>
    
    <td>
      <code>O(n)</code>
    </td>
  </tr>
  
  <tr>
    <td>
      <a href="https://en.wikipedia.org/wiki/Cartesian_tree">笛卡尔树</a>
    </td>
    
    <td>
      <code>-</code>
    </td>
    
    <td>
      <code>O(log(n))</code>
    </td>
    
    <td>
      <code>O(log(n))</code>
    </td>
    
    <td>
      <code>O(log(n))</code>
    </td>
    
    <td>
      <code>-</code>
    </td>
    
    <td>
      <code>O(n)</code>
    </td>
    
    <td>
      <code>O(n)</code>
    </td>
    
    <td>
      <code>O(n)</code>
    </td>
    
    <td>
      <code>O(n)</code>
    </td>
  </tr>
  
  <tr>
    <td>
      <a href="http://en.wikipedia.org/wiki/B_tree">B-树</a>
    </td>
    
    <td>
      <code>O(log(n))</code>
    </td>
    
    <td>
      <code>O(log(n))</code>
    </td>
    
    <td>
      <code>O(log(n))</code>
    </td>
    
    <td>
      <code>O(log(n))</code>
    </td>
    
    <td>
      <code>O(log(n))</code>
    </td>
    
    <td>
      <code>O(log(n))</code>
    </td>
    
    <td>
      <code>O(log(n))</code>
    </td>
    
    <td>
      <code>O(log(n))</code>
    </td>
    
    <td>
      <code>O(n)</code>
    </td>
  </tr>
  
  <tr>
    <td>
      <a href="http://en.wikipedia.org/wiki/Red-black_tree">红黑树</a>
    </td>
    
    <td>
      <code>O(log(n))</code>
    </td>
    
    <td>
      <code>O(log(n))</code>
    </td>
    
    <td>
      <code>O(log(n))</code>
    </td>
    
    <td>
      <code>O(log(n))</code>
    </td>
    
    <td>
      <code>O(log(n))</code>
    </td>
    
    <td>
      <code>O(log(n))</code>
    </td>
    
    <td>
      <code>O(log(n))</code>
    </td>
    
    <td>
      <code>O(log(n))</code>
    </td>
    
    <td>
      <code>O(n)</code>
    </td>
  </tr>
  
  <tr>
    <td>
      <a href="https://en.wikipedia.org/wiki/Splay_tree">伸展树</a>
    </td>
    
    <td>
      <code>-</code>
    </td>
    
    <td>
      <code>O(log(n))</code>
    </td>
    
    <td>
      <code>O(log(n))</code>
    </td>
    
    <td>
      <code>O(log(n))</code>
    </td>
    
    <td>
      <code>-</code>
    </td>
    
    <td>
      <code>O(log(n))</code>
    </td>
    
    <td>
      <code>O(log(n))</code>
    </td>
    
    <td>
      <code>O(log(n))</code>
    </td>
    
    <td>
      <code>O(n)</code>
    </td>
  </tr>
  
  <tr>
    <td>
      <a href="http://en.wikipedia.org/wiki/AVL_tree">AVL 树</a>
    </td>
    
    <td>
      <code>O(log(n))</code>
    </td>
    
    <td>
      <code>O(log(n))</code>
    </td>
    
    <td>
      <code>O(log(n))</code>
    </td>
    
    <td>
      <code>O(log(n))</code>
    </td>
    
    <td>
      <code>O(log(n))</code>
    </td>
    
    <td>
      <code>O(log(n))</code>
    </td>
    
    <td>
      <code>O(log(n))</code>
    </td>
    
    <td>
      <code>O(log(n))</code>
    </td>
    
    <td>
      <code>O(n)</code>
    </td>
  </tr>
</tbody>

数据结构

堆

    <th colspan="7">
      时间复杂度
    </th>
  </tr>
  
  <tr>
    <th>
    </th>
    
    <th>
      建堆
    </th>
    
    <th>
      查找最大值
    </th>
    
    <th>
      提取最大值
    </th>
    
    <th>
      Increase Key
    </th>
    
    <th>
      插入
    </th>
    
    <th>
      删除
    </th>
    
    <th>
      合并
    </th>
    
    <th>
    </th>
  </tr>
</thead>

<tbody>
  <tr>
    <td>
      <a href="http://en.wikipedia.org/wiki/Linked_list">链表（已排序）</a>
    </td>
    
    <td>
      <code>-</code>
    </td>
    
    <td>
      <code>O(1)</code>
    </td>
    
    <td>
      <code>O(1)</code>
    </td>
    
    <td>
      <code>O(n)</code>
    </td>
    
    <td>
      <code>O(n)</code>
    </td>
    
    <td>
      <code>O(1)</code>
    </td>
    
    <td>
      <code>O(m+n)</code>
    </td>
  </tr>
  
  <tr>
    <td>
      <a href="http://en.wikipedia.org/wiki/Linked_list">链表（未排序）</a>
    </td>
    
    <td>
      <code>-</code>
    </td>
    
    <td>
      <code>O(n)</code>
    </td>
    
    <td>
      <code>O(n)</code>
    </td>
    
    <td>
      <code>O(1)</code>
    </td>
    
    <td>
      <code>O(1)</code>
    </td>
    
    <td>
      <code>O(1)</code>
    </td>
    
    <td>
      <code>O(1)</code>
    </td>
  </tr>
  
  <tr>
    <td>
      <a href="http://en.wikipedia.org/wiki/Binary_heap">二叉堆</a>
    </td>
    
    <td>
      <code>O(n)</code>
    </td>
    
    <td>
      <code>O(1)</code>
    </td>
    
    <td>
      <code>O(log(n))</code>
    </td>
    
    <td>
      <code>O(log(n))</code>
    </td>
    
    <td>
      <code>O(log(n))</code>
    </td>
    
    <td>
      <code>O(log(n))</code>
    </td>
    
    <td>
      <code>O(m+n)</code>
    </td>
  </tr>
  
  <tr>
    <td>
      <a href="http://en.wikipedia.org/wiki/Binomial_heap">二项堆</a>
    </td>
    
    <td>
      <code>-</code>
    </td>
    
    <td>
      <code>O(log(n))</code>
    </td>
    
    <td>
      <code>O(log(n))</code>
    </td>
    
    <td>
      <code>O(log(n))</code>
    </td>
    
    <td>
      <code>O(log(n))</code>
    </td>
    
    <td>
      <code>O(log(n))</code>
    </td>
    
    <td>
      <code>O(log(n))</code>
    </td>
  </tr>
  
  <tr>
    <td>
      <a href="http://en.wikipedia.org/wiki/Fibonacci_heap">斐波那契堆</a>
    </td>
    
    <td>
      <code>-</code>
    </td>
    
    <td>
      <code>O(1)</code>
    </td>
    
    <td>
      <code data-original-title="Amortized">O(log(n))*</code>
    </td>
    
    <td>
      <code data-original-title="Amortized">O(1)*</code>
    </td>
    
    <td>
      <code>O(1)</code>
    </td>
    
    <td>
      <code data-original-title="Amortized">O(log(n))*</code>
    </td>
    
    <td>
      <code>O(1)</code>
    </td>
  </tr>
</tbody>

Heaps

图

    <th>
      Storage
    </th>
    
    <th>
      Add Vertex
    </th>
    
    <th>
      Add Edge
    </th>
    
    <th>
      Remove Vertex
    </th>
    
    <th>
      Remove Edge
    </th>
    
    <th>
      Query
    </th>
  </tr>
  
  <tr>
    <td>
      <a href="http://en.wikipedia.org/wiki/Adjacency_list">邻接表</a>
    </td>
    
    <td>
      <code>O(|V|+|E|)</code>
    </td>
    
    <td>
      <code>O(1)</code>
    </td>
    
    <td>
      <code>O(1)</code>
    </td>
    
    <td>
      <code>O(|V| + |E|)</code>
    </td>
    
    <td>
      <code>O(|E|)</code>
    </td>
    
    <td>
      <code>O(|V|)</code>
    </td>
  </tr>
  
  <tr>
    <td>
      <a href="http://en.wikipedia.org/wiki/Incidence_list">关联表</a>
    </td>
    
    <td>
      <code>O(|V|+|E|)</code>
    </td>
    
    <td>
      <code>O(1)</code>
    </td>
    
    <td>
      <code>O(1)</code>
    </td>
    
    <td>
      <code>O(|E|)</code>
    </td>
    
    <td>
      <code>O(|E|)</code>
    </td>
    
    <td>
      <code>O(|E|)</code>
    </td>
  </tr>
  
  <tr>
    <td>
      <a href="http://en.wikipedia.org/wiki/Adjacency_matrix">邻接矩阵</a>
    </td>
    
    <td>
      <code>O(|V|^2)</code>
    </td>
    
    <td>
      <code>O(|V|^2)</code>
    </td>
    
    <td>
      <code>O(1)</code>
    </td>
    
    <td>
      <code>O(|V|^2)</code>
    </td>
    
    <td>
      <code>O(1)</code>
    </td>
    
    <td>
      <code>O(1)</code>
    </td>
  </tr>
  
  <tr>
    <td>
      <a href="http://en.wikipedia.org/wiki/Incidence_matrix">关联矩阵</a>
    </td>
    
    <td>
      <code>O(|V| ⋅ |E|)</code>
    </td>
    
    <td>
      <code>O(|V| ⋅ |E|)</code>
    </td>
    
    <td>
      <code>O(|V| ⋅ |E|)</code>
    </td>
    
    <td>
      <code>O(|V| ⋅ |E|)</code>
    </td>
    
    <td>
      <code>O(|V| ⋅ |E|)</code>
    </td>
    
    <td>
      <code>O(|E|)</code>
    </td>
  </tr>
</tbody>

节点 / 边 管理

应用（转自博客）：

BST树

<p style="margin:10px auto; padding-top:0px; padding-bottom:0px; color:rgb(57,57,57); font-family:verdana,'ms song',Arial,Helvetica,sans-serif; font-size:14.3999996185303px; line-height:16.7999992370605px">
  <span style="background-color:rgb(255,255,255)"><span style="margin:0px; padding:0px">       </span><span style="margin:0px; padding:0px; font-family:宋体">即二叉搜索树：</span></span>
</p>

<p style="margin:10px auto; padding-top:0px; padding-bottom:0px; color:rgb(57,57,57); font-family:verdana,'ms song',Arial,Helvetica,sans-serif; font-size:14.3999996185303px; line-height:16.7999992370605px">
  <span style="background-color:rgb(255,255,255)"><span style="margin:0px; padding:0px">       1.</span><span style="margin:0px; padding:0px; font-family:宋体">所有非叶子结点至多拥有两个儿子（</span>Left<span style="margin:0px; padding:0px; font-family:宋体">和</span>Right<span style="margin:0px; padding:0px; font-family:宋体">）；</span></span>
</p>

<p style="margin:10px auto; padding-top:0px; padding-bottom:0px; color:rgb(57,57,57); font-family:verdana,'ms song',Arial,Helvetica,sans-serif; font-size:14.3999996185303px; line-height:16.7999992370605px">
  <span style="background-color:rgb(255,255,255)"><span style="margin:0px; padding:0px">       2.</span><span style="margin:0px; padding:0px; font-family:宋体">所有结点存储一个关键字；</span></span>
</p>

<p style="margin:10px auto; padding-top:0px; padding-bottom:0px; color:rgb(57,57,57); font-family:verdana,'ms song',Arial,Helvetica,sans-serif; font-size:14.3999996185303px; line-height:16.7999992370605px">
  <span style="margin:0px; padding:0px; background-color:rgb(255,255,255)">       3.</span><span style="margin:0px; padding:0px; font-family:宋体; background-color:rgb(255,255,255)">非叶子结点的左指针指向小于其关键字的子树，右指针指向大于其关键字的子树；</span>
</p>

<p style="margin:10px auto; padding-top:0px; padding-bottom:0px; color:rgb(57,57,57); font-family:verdana,'ms song',Arial,Helvetica,sans-serif; font-size:14.3999996185303px; line-height:16.7999992370605px">
  <span style="background-color:rgb(255,255,255)"><span style="margin:0px; padding:0px">       </span><span style="margin:0px; padding:0px; font-family:宋体">如：</span></span>
</p>

<p style="margin:10px auto; padding-top:0px; padding-bottom:0px; color:rgb(57,57,57); font-family:verdana,'ms song',Arial,Helvetica,sans-serif; font-size:14.3999996185303px; line-height:16.7999992370605px">
  <span style="background-color:rgb(255,255,255)">       </span>
</p>

<p align="center" style="margin:10px auto; padding-top:0px; padding-bottom:0px; color:rgb(57,57,57); font-family:verdana,'ms song',Arial,Helvetica,sans-serif; font-size:14.3999996185303px; line-height:16.7999992370605px">
  <span style="background-color:rgb(255,255,255)"><img alt="" src="http://p.blog.csdn.net/images/p_blog_csdn_net/manesking/1.JPG" style="margin:0px; padding:0px; border:0px" /></span>
</p>

<p style="margin:10px auto; padding-top:0px; padding-bottom:0px; color:rgb(57,57,57); font-family:verdana,'ms song',Arial,Helvetica,sans-serif; font-size:14.3999996185303px; line-height:16.7999992370605px">
  <span style="background-color:rgb(255,255,255)">       <span style="color:rgb(57,57,57); font-family:verdana,'ms song',Arial,Helvetica,sans-serif; font-size:14px; line-height:16.7999992370605px"> BST</span><span style="margin:0px; padding:0px; font-family:宋体">树的搜索，从根结点开始，如果查询的关键字与结点的关键字相等，那么就命中；</span></span>
</p>

<p style="margin:10px auto; padding-top:0px; padding-bottom:0px; color:rgb(57,57,57); font-family:verdana,'ms song',Arial,Helvetica,sans-serif; font-size:14.3999996185303px; line-height:16.7999992370605px">
  <span style="margin:0px; padding:0px; font-family:宋体; background-color:rgb(255,255,255)">否则，如果查询关键字比结点关键字小，就进入左儿子；如果比结点关键字大，就进入</span>
</p>

<p style="margin:10px auto; padding-top:0px; padding-bottom:0px; color:rgb(57,57,57); font-family:verdana,'ms song',Arial,Helvetica,sans-serif; font-size:14.3999996185303px; line-height:16.7999992370605px">
  <span style="margin:0px; padding:0px; font-family:宋体; background-color:rgb(255,255,255)">右儿子；如果左儿子或右儿子的指针为空，则报告找不到相应的关键字；</span>
</p>

<p style="margin:10px auto; padding-top:0px; padding-bottom:0px; color:rgb(57,57,57); font-family:verdana,'ms song',Arial,Helvetica,sans-serif; font-size:14.3999996185303px; line-height:16.7999992370605px">
  <span style="background-color:rgb(255,255,255)"><span style="margin:0px; padding:0px">       </span><span style="margin:0px; padding:0px; font-family:宋体">如果</span><span style="color:rgb(57,57,57); font-family:verdana,'ms song',Arial,Helvetica,sans-serif; font-size:14px; line-height:16.7999992370605px">BST</span><span style="margin:0px; padding:0px; font-family:宋体">树的所有非叶子结点的左右子树的结点数目均保持差不多（平衡），那么</span>B<span style="margin:0px; padding:0px; font-family:宋体">树</span></span>
</p>

<p style="margin:10px auto; padding-top:0px; padding-bottom:0px; color:rgb(57,57,57); font-family:verdana,'ms song',Arial,Helvetica,sans-serif; font-size:14.3999996185303px; line-height:16.7999992370605px">
  <span style="background-color:rgb(255,255,255)"><span style="margin:0px; padding:0px; font-family:宋体">的搜索性能逼近二分查找；但它比连续内存空间的二分查找的优点是，改变</span><span style="color:rgb(57,57,57); font-family:verdana,'ms song',Arial,Helvetica,sans-serif; font-size:14px; line-height:16.7999992370605px">BST</span><span style="margin:0px; padding:0px; font-family:宋体">树结构</span></span>
</p>

<p style="margin:10px auto; padding-top:0px; padding-bottom:0px; color:rgb(57,57,57); font-family:verdana,'ms song',Arial,Helvetica,sans-serif; font-size:14.3999996185303px; line-height:16.7999992370605px">
  <span style="margin:0px; padding:0px; font-family:宋体; background-color:rgb(255,255,255)">（</span><span style="margin:0px; padding:0px; font-family:宋体; background-color:rgb(255,255,255)">插入与删除结点）不需要移动大段的内存数据，甚至通常是常数开销；</span>
</p>

<p style="margin:10px auto; padding-top:0px; padding-bottom:0px; color:rgb(57,57,57); font-family:verdana,'ms song',Arial,Helvetica,sans-serif; font-size:14.3999996185303px; line-height:16.7999992370605px">
  <span style="background-color:rgb(255,255,255)"><span style="margin:0px; padding:0px">       </span><span style="margin:0px; padding:0px; font-family:宋体">如：</span></span>
</p>

<p style="margin:10px auto; padding-top:0px; padding-bottom:0px; color:rgb(57,57,57); font-family:verdana,'ms song',Arial,Helvetica,sans-serif; font-size:14.3999996185303px; line-height:16.7999992370605px">
  <span style="margin:0px; padding:0px; background-color:rgb(255,255,255)">      </span>
</p>

<p align="center" style="margin:10px auto; padding-top:0px; padding-bottom:0px; color:rgb(57,57,57); font-family:verdana,'ms song',Arial,Helvetica,sans-serif; font-size:14.3999996185303px; line-height:16.7999992370605px">
  <span style="background-color:rgb(255,255,255)"><img alt="" src="http://p.blog.csdn.net/images/p_blog_csdn_net/manesking/2.JPG" style="margin:0px; padding:0px; border:0px" /></span>
</p>

<p style="margin:10px auto; padding-top:0px; padding-bottom:0px; color:rgb(57,57,57); font-family:verdana,'ms song',Arial,Helvetica,sans-serif; font-size:14.3999996185303px; line-height:16.7999992370605px">
  <span style="margin:0px; padding:0px; font-family:宋体"><span style="background-color:rgb(250,247,239)">   </span><span style="background-color:rgb(255,255,255)">但</span></span><span style="background-color:rgb(255,255,255)"><span style="color:rgb(57,57,57); font-family:verdana,'ms song',Arial,Helvetica,sans-serif; font-size:14px; line-height:16.7999992370605px">BST</span><span style="margin:0px; padding:0px; font-family:宋体">树在经过多次插入与删除后，有可能导致不同的结构：</span></span>
</p>

<p align="center" style="margin:10px auto; padding-top:0px; padding-bottom:0px; color:rgb(57,57,57); font-family:verdana,'ms song',Arial,Helvetica,sans-serif; font-size:14.3999996185303px; line-height:16.7999992370605px">
  <span style="margin:0px; padding:0px; font-family:宋体; background-color:rgb(255,255,255)"><img alt="" src="http://p.blog.csdn.net/images/p_blog_csdn_net/manesking/31.JPG" style="margin:0px; padding:0px; border:0px" /></span>
</p>

<span style="margin:0px; padding:0px; color:rgb(57,57,57); font-family:verdana,'ms song',Arial,Helvetica,sans-serif; font-size:14.3999996185303px; line-height:16.7999992370605px; background-color:rgb(255,255,255)"></span> <p align="left" style="margin:10px auto; padding-top:0px; padding-bottom:0px">
</p>

<p align="left" style="margin:10px auto; padding-top:0px; padding-bottom:0px">
  <span style="margin:0px; padding:0px; font-family:宋体; background-color:rgb(255,255,255)">   右边也是一个BST<span style="margin:0px; padding:0px">树，但它的搜索性能已经是线性的了；同样的关键字集合有可能导致不同的</span></span>
</p>

<p align="left" style="margin:10px auto; padding-top:0px; padding-bottom:0px">
  <span style="margin:0px; padding:0px; font-family:宋体; background-color:rgb(255,255,255)"><span style="margin:0px; padding:0px">树结构索引；所以，使用</span>BST<span style="margin:0px; padding:0px">树还要考虑尽可能让</span>BST<span style="margin:0px; padding:0px">树保持左图的结构，和避免右图的结构，也就</span></span>
</p>

<p align="left" style="margin:10px auto; padding-top:0px; padding-bottom:0px">
  <span style="margin:0px; padding:0px; font-family:宋体; background-color:rgb(255,255,255)"><span style="margin:0px; padding:0px">是所谓的“平衡”问题；</span>      </span>
</p>

<p align="left" style="margin:10px auto; padding-top:0px; padding-bottom:0px">
  <span style="margin:0px; padding:0px"><span style="background-color:rgb(255,255,255)">       </span><br /> <strong><span style="font-size:14px">AVL平衡二叉搜索树</span></strong><br /> 定义：平衡二叉树或为空树,或为如下性质的二叉排序树:<br />   （1）左右子树深度之差的绝对值不超过1;<br />   （2）左右子树仍然为平衡二叉树.<br /> 平衡因子BF=左子树深度－右子树深度.<br /> 平衡二叉树每个结点的平衡因子只能是1，0，-1。若其绝对值超过1，则该二叉排序树就是不平衡的。<br /> 如图所示为平衡树和非平衡树示意图：</span>
</p>

<p align="left" style="margin:10px auto; padding-top:0px; padding-bottom:0px">
  <span style="margin:0px; padding:0px"><img src="" alt="" /><br /> </span>
</p>

<p align="left" style="margin:10px auto; padding-top:0px; padding-bottom:0px">
  <span style="margin:0px; padding:0px"><img src="http://images.cnitblog.com/blog/695961/201412/132035360718832.png" alt="" /><br /> </span>
</p>

<p style="margin:10px auto; padding-top:0px; padding-bottom:0px">
   <img src="" alt="" />
</p>

<p style="margin:10px auto; padding-top:0px; padding-bottom:0px">
  <strong><span style="font-size:14px">RBT 红黑树</span></strong>
</p>

<p style="margin:10px auto; padding-top:0px; padding-bottom:0px">
  AVL是严格平衡树，因此在增加或者删除节点的时候，根据不同情况，旋转的次数比红黑树要多；<br /> 红黑是弱平衡的，用非严格的平衡来换取增删节点时候旋转次数的降低；<br /> 所以简单说，搜索的次数远远大于插入和删除，那么选择AVL树，如果搜索，插入删除次数几乎差不多，应该选择RB树。
</p>

<p style="margin:10px auto; padding-top:0px; padding-bottom:0px">
  红黑树上每个结点内含五个域，color，key，left，right，p。如果相应的指针域没有，则设为NIL。<br /> 一般的，红黑树，满足以下性质，即只有满足以下全部性质的树，我们才称之为红黑树：<br /> 1）每个结点要么是红的，要么是黑的。<br /> 2）根结点是黑的。<br /> 3）每个叶结点，即空结点（NIL）是黑的。<br /> 4）如果一个结点是红的，那么它的俩个儿子都是黑的。<br /> 5）对每个结点，从该结点到其子孙结点的所有路径上包含相同数目的黑结点。<br /> 下图所示，即是一颗红黑树：
</p>

<p style="margin:10px auto; padding-top:0px; padding-bottom:0px">
  <br /> <br /> <img src="http://hi.csdn.net/attachment/201012/29/8394323_1293613306CGzE.jpg" alt="" width="835" height="242" style="word-wrap:break-word; border:none; color:rgb(51,51,51); font-family:Arial; font-size:17px; line-height:37px" /><br />
</p>

<p style="margin:10px auto; padding-top:0px; padding-bottom:0px">
  <br />
</p>

<p style="margin:10px auto; padding-top:0px; padding-bottom:0px">
  <br />
</p>

<p style="margin:10px auto; padding-top:0px; padding-bottom:0px">
   
</p>

<p style="margin:10px auto; padding-top:0px; padding-bottom:0px">
  <span style="margin:0px; padding:0px"><span style="font-size:14px"><strong>B-<span style="margin:0px; padding:0px; font-family:宋体">树</span></strong></span></span>
</p>

<p style="margin:10px auto; padding-top:0px; padding-bottom:0px">
  <span style="margin:0px; padding:0px">       </span><span style="margin:0px; padding:0px; font-family:宋体">是一种平衡多路搜索树（并不是二叉的）：</span>
</p>

<p style="margin:10px auto; padding-top:0px; padding-bottom:0px">
  <span style="margin:0px; padding:0px">       1.</span><span style="margin:0px; padding:0px; font-family:宋体">定义任意非叶子结点最多只有</span>M<span style="margin:0px; padding:0px; font-family:宋体">个儿子；且</span>M>2<span style="margin:0px; padding:0px; font-family:宋体">；</span>
</p>

<p style="margin:10px auto; padding-top:0px; padding-bottom:0px">
  <span style="margin:0px; padding:0px">       2.</span><span style="margin:0px; padding:0px; font-family:宋体">根结点的儿子数为</span>[2, M]<span style="margin:0px; padding:0px; font-family:宋体">；</span>
</p>

<p style="margin:10px auto; padding-top:0px; padding-bottom:0px">
  <span style="margin:0px; padding:0px">       3.</span><span style="margin:0px; padding:0px; font-family:宋体">除根结点以外的非叶子结点的儿子数为</span>[M/2, M]<span style="margin:0px; padding:0px; font-family:宋体">；</span>
</p>

<p style="margin:10px auto; padding-top:0px; padding-bottom:0px">
  <span style="margin:0px; padding:0px">       4.</span><span style="margin:0px; padding:0px; font-family:宋体">每个结点存放至少</span>M/2-1<span style="margin:0px; padding:0px; font-family:宋体">（取上整）和至多</span>M-1<span style="margin:0px; padding:0px; font-family:宋体">个关键字；（至少</span>2<span style="margin:0px; padding:0px; font-family:宋体">个关键字）</span>
</p>

<p style="margin:10px auto; padding-top:0px; padding-bottom:0px">
  <span style="margin:0px; padding:0px">       5.</span><span style="margin:0px; padding:0px; font-family:宋体">非叶子结点的关键字个数</span>=<span style="margin:0px; padding:0px; font-family:宋体">指向儿子的指针个数</span>-1<span style="margin:0px; padding:0px; font-family:宋体">；</span>
</p>

<p style="margin:10px auto; padding-top:0px; padding-bottom:0px">
  <span style="margin:0px; padding:0px">       6.</span><span style="margin:0px; padding:0px; font-family:宋体">非叶子结点的关键字：</span>K[1], K[2], …, K[M-1]<span style="margin:0px; padding:0px; font-family:宋体">；且</span>K[i] < K[i+1]<span style="margin:0px; padding:0px; font-family:宋体">；</span>
</p>

<p style="margin:10px auto; padding-top:0px; padding-bottom:0px">
  <span style="margin:0px; padding:0px">       7.</span><span style="margin:0px; padding:0px; font-family:宋体">非叶子结点的指针：</span>P[1], P[2], …, P[M]<span style="margin:0px; padding:0px; font-family:宋体">；其中</span>P[1]<span style="margin:0px; padding:0px; font-family:宋体">指向关键字小于</span>K[1]<span style="margin:0px; padding:0px; font-family:宋体">的</span>
</p>

<p style="margin:10px auto; padding-top:0px; padding-bottom:0px">
  <span style="margin:0px; padding:0px; font-family:宋体">子树，</span>P[M]<span style="margin:0px; padding:0px; font-family:宋体">指向关键字大于</span>K[M-1]<span style="margin:0px; padding:0px; font-family:宋体">的子树，其它</span>P[i]<span style="margin:0px; padding:0px; font-family:宋体">指向关键字属于</span>(K[i-1], K[i])<span style="margin:0px; padding:0px; font-family:宋体">的子树；</span>
</p>

<p style="margin:10px auto; padding-top:0px; padding-bottom:0px">
  <span style="margin:0px; padding:0px">       8.</span><span style="margin:0px; padding:0px; font-family:宋体">所有叶子结点位于同一层；</span>
</p>

<p style="margin:10px auto; padding-top:0px; padding-bottom:0px">
  <span style="margin:0px; padding:0px">       </span><span style="margin:0px; padding:0px; font-family:宋体">如：（</span><strong>M=3</strong><span style="margin:0px; padding:0px; font-family:宋体">）</span>
</p>

<p align="center" style="margin:10px auto; padding-top:0px; padding-bottom:0px">
  <span style="margin:0px; padding:0px; font-family:宋体"><img alt="" src="http://p.blog.csdn.net/images/p_blog_csdn_net/manesking/4.JPG" style="margin:0px; padding:0px; border:0px" /></span>
</p>

<p align="left" style="margin:10px auto; padding-top:0px; padding-bottom:0px">
  <span style="margin:0px; padding:0px">       B-<span style="margin:0px; padding:0px; font-family:宋体">树的搜索，从根结点开始，对结点内的关键字（有序）序列进行二分查找，如果</span></span>
</p>

<p align="left" style="margin:10px auto; padding-top:0px; padding-bottom:0px">
  <span style="margin:0px; padding:0px; font-family:宋体">命中则结束，否则进入查询关键字所属范围的儿子结点；重复，直到所对应的儿子指针为</span>
</p>

<p align="left" style="margin:10px auto; padding-top:0px; padding-bottom:0px">
  <span style="margin:0px; padding:0px; font-family:宋体">空，或已经是叶子结点；</span>
</p>

<p style="margin:10px auto; padding-top:0px; padding-bottom:0px; text-indent:21pt">
  B-<span style="margin:0px; padding:0px; font-family:宋体">树的特性：</span>
</p>

<p style="margin:10px auto; padding-top:0px; padding-bottom:0px">
  <span style="margin:0px; padding:0px">       1.</span><span style="margin:0px; padding:0px; font-family:宋体">关键字集合分布在整颗树中；</span>
</p>

<p style="margin:10px auto; padding-top:0px; padding-bottom:0px">
  <span style="margin:0px; padding:0px">       2.</span><span style="margin:0px; padding:0px; font-family:宋体">任何一个关键字出现且只出现在一个结点中；</span>
</p>

<p style="margin:10px auto; padding-top:0px; padding-bottom:0px">
  <span style="margin:0px; padding:0px">       3.</span><span style="margin:0px; padding:0px; font-family:宋体">搜索有可能在非叶子结点结束；</span>
</p>

<p style="margin:10px auto; padding-top:0px; padding-bottom:0px">
  <span style="margin:0px; padding:0px">       4.</span><span style="margin:0px; padding:0px; font-family:宋体">其搜索性能等价于在关键字全集内做一次二分查找；</span>
</p>

<p style="margin:10px auto; padding-top:0px; padding-bottom:0px">
  <span style="margin:0px; padding:0px">       5.</span><span style="margin:0px; padding:0px; font-family:宋体">自动层次控制；</span>
</p>

<p style="margin:10px auto; padding-top:0px; padding-bottom:0px">
  <span style="margin:0px; padding:0px">       </span><span style="margin:0px; padding:0px; font-family:宋体">由于限制了除根结点以外的非叶子结点，至少含有</span>M/2<span style="margin:0px; padding:0px; font-family:宋体">个儿子，确保了结点的至少</span>
</p>

<p style="margin:10px auto; padding-top:0px; padding-bottom:0px">
  <span style="margin:0px; padding:0px; font-family:宋体">利用率，其最底搜索性能为：</span>
</p>

<p align="center" style="margin:10px auto; padding-top:0px; padding-bottom:0px">
  <span style="margin:0px; padding:0px"><img alt="" src="http://p.blog.csdn.net/images/p_blog_csdn_net/manesking/0.JPG" style="margin:0px; padding:0px; border:0px" /></span>
</p>

<p style="margin:10px auto; padding-top:0px; padding-bottom:0px">
      
</p>

<p style="margin:10px auto; padding-top:0px; padding-bottom:0px">
  <span style="margin:0px; padding:0px">       </span><span style="margin:0px; padding:0px; font-family:宋体">其中，</span>M<span style="margin:0px; padding:0px; font-family:宋体">为设定的非叶子结点最多子树个数，</span>N<span style="margin:0px; padding:0px; font-family:宋体">为关键字总数；</span>
</p>

<p style="margin:10px auto; padding-top:0px; padding-bottom:0px">
  <span style="margin:0px; padding:0px">       </span><span style="margin:0px; padding:0px; font-family:宋体">所以</span>B-<span style="margin:0px; padding:0px; font-family:宋体">树的性能总是等价于二分查找（与</span>M<span style="margin:0px; padding:0px; font-family:宋体">值无关），也就没有</span>B<span style="margin:0px; padding:0px; font-family:宋体">树平衡的问题；</span>
</p>

<p style="margin:10px auto; padding-top:0px; padding-bottom:0px">
  <span style="margin:0px; padding:0px">       </span><span style="margin:0px; padding:0px; font-family:宋体">由于</span>M/2<span style="margin:0px; padding:0px; font-family:宋体">的限制，在插入结点时，如果结点已满，需要将结点分裂为两个各占</span>
</p>

<p style="margin:10px auto; padding-top:0px; padding-bottom:0px">
  <span style="margin:0px; padding:0px; font-family:宋体"></span>M/2<span style="margin:0px; padding:0px; font-family:宋体">的结点；删除结点时，需将两个不足</span>M/2<span style="margin:0px; padding:0px; font-family:宋体">的兄弟结点合并；</span>
</p>

<p style="margin:10px auto; padding-top:0px; padding-bottom:0px">
   
</p>

<p style="margin:10px auto; padding-top:0px; padding-bottom:0px">
   
</p>

<p style="margin:10px auto; padding-top:0px; padding-bottom:0px">
  <span style="margin:0px; padding:0px"><strong><span style="font-size:14px">B+<span style="margin:0px; padding:0px; font-family:宋体">树</span></span></strong></span>
</p>

<p style="margin:10px auto; padding-top:0px; padding-bottom:0px">
  <span style="margin:0px; padding:0px">       B+</span><span style="margin:0px; padding:0px; font-family:宋体">树是</span>B-<span style="margin:0px; padding:0px; font-family:宋体">树的变体，也是一种多路搜索树：</span>
</p>

<p style="margin:10px auto; padding-top:0px; padding-bottom:0px">
  <span style="margin:0px; padding:0px">       1.</span><span style="margin:0px; padding:0px; font-family:宋体">其定义基本与</span>B-<span style="margin:0px; padding:0px; font-family:宋体">树同，除了：</span>
</p>

<p style="margin:10px auto; padding-top:0px; padding-bottom:0px">
  <span style="margin:0px; padding:0px">       2.</span><span style="margin:0px; padding:0px; font-family:宋体">非叶子结点的子树指针与关键字个数相同；</span>
</p>

<p style="margin:10px auto; padding-top:0px; padding-bottom:0px">
  <span style="margin:0px; padding:0px">       3.</span><span style="margin:0px; padding:0px; font-family:宋体">非叶子结点的子树指针</span>P[i]<span style="margin:0px; padding:0px; font-family:宋体">，指向关键字值属于</span>[K[i], K[i+1])<span style="margin:0px; padding:0px; font-family:宋体">的子树</span>
</p>

<p style="margin:10px auto; padding-top:0px; padding-bottom:0px">
  <span style="margin:0px; padding:0px; font-family:宋体">（</span>B-<span style="margin:0px; padding:0px; font-family:宋体">树是开区间）；</span>
</p>

<p style="margin:10px auto; padding-top:0px; padding-bottom:0px">
  <span style="margin:0px; padding:0px">       5.</span><span style="margin:0px; padding:0px; font-family:宋体">为所有叶子结点增加一个链指针；</span>
</p>

<p style="margin:10px auto; padding-top:0px; padding-bottom:0px">
  <span style="margin:0px; padding:0px">       6.</span><span style="margin:0px; padding:0px; font-family:宋体">所有关键字都在叶子结点出现；</span>
</p>

<p style="margin:10px auto; padding-top:0px; padding-bottom:0px">
  <span style="margin:0px; padding:0px">       </span><span style="margin:0px; padding:0px; font-family:宋体">如：（</span>M=3<span style="margin:0px; padding:0px; font-family:宋体">）</span>
</p>

<p align="center" style="margin:10px auto; padding-top:0px; padding-bottom:0px">
  <span style="margin:0px; padding:0px; font-family:宋体"><img alt="" src="http://p.blog.csdn.net/images/p_blog_csdn_net/manesking/5.JPG" style="margin:0px; padding:0px; border:0px" /></span>
</p>

<p style="margin:10px auto; padding-top:0px; padding-bottom:0px">
  <span style="margin:0px; padding:0px; font-family:宋体">   </span>B+<span style="margin:0px; padding:0px; font-family:宋体">的搜索与</span>B-<span style="margin:0px; padding:0px; font-family:宋体">树也基本相同，区别是</span>B+<span style="margin:0px; padding:0px; font-family:宋体">树只有达到叶子结点才命中（</span>B-<span style="margin:0px; padding:0px; font-family:宋体">树可以在</span>
</p>

<p style="margin:10px auto; padding-top:0px; padding-bottom:0px">
  <span style="margin:0px; padding:0px; font-family:宋体">非叶子结点命中），其性能也等价于在关键字全集做一次二分查找；</span>
</p>

<p style="margin:10px auto; padding-top:0px; padding-bottom:0px">
  <span style="margin:0px; padding:0px">       B+</span><span style="margin:0px; padding:0px; font-family:宋体">的特性：</span>
</p>

<p style="margin:10px auto; padding-top:0px; padding-bottom:0px">
  <span style="margin:0px; padding:0px">       1.</span><span style="margin:0px; padding:0px; font-family:宋体">所有关键字都出现在叶子结点的链表中（稠密索引），且链表中的关键字恰好</span>
</p>

<p style="margin:10px auto; padding-top:0px; padding-bottom:0px">
  <span style="margin:0px; padding:0px; font-family:宋体">是有序的；</span>
</p>

<p style="margin:10px auto; padding-top:0px; padding-bottom:0px">
  <span style="margin:0px; padding:0px">       2.</span><span style="margin:0px; padding:0px; font-family:宋体">不可能在非叶子结点命中；</span>
</p>

<p style="margin:10px auto; padding-top:0px; padding-bottom:0px">
  <span style="margin:0px; padding:0px">       3.</span><span style="margin:0px; padding:0px; font-family:宋体">非叶子结点相当于是叶子结点的索引（稀疏索引），叶子结点相当于是存储</span>
</p>

<p style="margin:10px auto; padding-top:0px; padding-bottom:0px">
  <span style="margin:0px; padding:0px; font-family:宋体">（关键字）数据的数据层；</span>
</p>

<p style="margin:10px auto; padding-top:0px; padding-bottom:0px">
  <span style="margin:0px; padding:0px">       4.</span><span style="margin:0px; padding:0px; font-family:宋体">更适合文件索引系统；比如对已经建立索引的数据库记录，查找10<=id<=20，那么只要通过根节点搜索到id=10的叶节点，之后只要根据叶节点的链表找到第一个大于20的就行了，比B-树在查找10到20内的每一个时每次都从根节点出发查找提高了不少效率。</span>
</p>

<p style="margin:10px auto; padding-top:0px; padding-bottom:0px">
    
</p>

<p style="margin:10px auto; padding-top:0px; padding-bottom:0px">
  <span style="margin:0px; padding:0px"><strong><span style="font-size:14px">B*<span style="margin:0px; padding:0px; font-family:宋体">树</span></span></strong></span>
</p>

<p style="margin:10px auto; padding-top:0px; padding-bottom:0px">
  <span style="margin:0px; padding:0px">       </span><span style="margin:0px; padding:0px; font-family:宋体">是</span>B+<span style="margin:0px; padding:0px; font-family:宋体">树的变体，在</span>B+<span style="margin:0px; padding:0px; font-family:宋体">树的非根和非叶子结点再增加指向兄弟的指针；</span>
</p>

<p align="center" style="margin:10px auto; padding-top:0px; padding-bottom:0px">
  <span style="margin:0px; padding:0px; font-family:宋体"><img alt="" src="http://p.blog.csdn.net/images/p_blog_csdn_net/manesking/6.JPG" style="margin:0px; padding:0px; border:0px" /></span>
</p>

<p style="margin:10px auto; padding-top:0px; padding-bottom:0px">
  <span style="margin:0px; padding:0px; font-family:宋体">   </span>B*<span style="margin:0px; padding:0px; font-family:宋体">树定义了非叶子结点关键字个数至少为</span>(2/3)xM<span style="margin:0px; padding:0px; font-family:宋体">，即块的最低使用率为</span>2/3
</p>

<p style="margin:10px auto; padding-top:0px; padding-bottom:0px">
  <span style="margin:0px; padding:0px; font-family:宋体">（代替</span>B+<span style="margin:0px; padding:0px; font-family:宋体">树的</span>1/2<span style="margin:0px; padding:0px; font-family:宋体">）；</span>
</p>

<p style="margin:10px auto; padding-top:0px; padding-bottom:0px">
  <span style="margin:0px; padding:0px">       B+</span><span style="margin:0px; padding:0px; font-family:宋体">树的分裂：当一个结点满时，分配一个新的结点，并将原结点中</span>1/2<span style="margin:0px; padding:0px; font-family:宋体">的数据</span>
</p>

<p style="margin:10px auto; padding-top:0px; padding-bottom:0px">
  <span style="margin:0px; padding:0px; font-family:宋体">复制到新结点，最后在父结点中增加新结点的指针；</span>B+<span style="margin:0px; padding:0px; font-family:宋体">树的分裂只影响原结点和父</span>
</p>

<p style="margin:10px auto; padding-top:0px; padding-bottom:0px">
  <span style="margin:0px; padding:0px; font-family:宋体">结点，而不会影响兄弟结点，所以它不需要指向兄弟的指针；</span>
</p>

<p style="margin:10px auto; padding-top:0px; padding-bottom:0px">
  <span style="margin:0px; padding:0px">       B*</span><span style="margin:0px; padding:0px; font-family:宋体">树的分裂：当一个结点满时，如果它的下一个兄弟结点未满，那么将一部分</span>
</p>

<p style="margin:10px auto; padding-top:0px; padding-bottom:0px">
  <span style="margin:0px; padding:0px; font-family:宋体">数据移到兄弟结点中，再在原结点插入关键字，最后修改父结点中兄弟结点的关键字</span>
</p>

<p style="margin:10px auto; padding-top:0px; padding-bottom:0px">
  <span style="margin:0px; padding:0px; font-family:宋体">（因为兄弟结点的关键字范围改变了）；如果兄弟也满了，则在原结点与兄弟结点之</span>
</p>

<p style="margin:10px auto; padding-top:0px; padding-bottom:0px">
  <span style="margin:0px; padding:0px; font-family:宋体">间增加新结点，并各复制</span>1/3<span style="margin:0px; padding:0px; font-family:宋体">的数据到新结点，最后在父结点增加新结点的指针；</span>
</p>

<p style="margin:10px auto; padding-top:0px; padding-bottom:0px">
  <span style="margin:0px; padding:0px">       </span><span style="margin:0px; padding:0px; font-family:宋体">所以，</span>B*<span style="margin:0px; padding:0px; font-family:宋体">树分配新结点的概率比</span>B+<span style="margin:0px; padding:0px; font-family:宋体">树要低，空间使用率更高；</span>
</p>

<p style="margin:10px auto; padding-top:0px; padding-bottom:0px">
    
</p>

<p style="margin:10px auto; padding-top:0px; padding-bottom:0px">
  <span style="margin:0px; padding:0px; font-family:宋体"><span style="margin:0px; padding:0px"><strong><span style="font-size:14px">小结</span></strong></span></span>
</p>

<p style="margin:10px auto; padding-top:0px; padding-bottom:0px">
  <span style="margin:0px; padding:0px">       B</span><span style="margin:0px; padding:0px; font-family:宋体">树：二叉树，每个结点只存储一个关键字，等于则命中，小于走左结点，大于</span>
</p>

<p style="margin:10px auto; padding-top:0px; padding-bottom:0px">
  <span style="margin:0px; padding:0px; font-family:宋体">走右结点；</span>
</p>

<p style="margin:10px auto; padding-top:0px; padding-bottom:0px">
  <span style="margin:0px; padding:0px">       B-</span><span style="margin:0px; padding:0px; font-family:宋体">树：多路搜索树，每个结点存储</span>M/2<span style="margin:0px; padding:0px; font-family:宋体">到</span>M<span style="margin:0px; padding:0px; font-family:宋体">个关键字，非叶子结点存储指向关键</span>
</p>

<p style="margin:10px auto; padding-top:0px; padding-bottom:0px">
  <span style="margin:0px; padding:0px; font-family:宋体">字范围的子结点；</span>
</p>

<p style="margin:10px auto; padding-top:0px; padding-bottom:0px">
  <span style="margin:0px; padding:0px">       </span><span style="margin:0px; padding:0px; font-family:宋体">所有关键字在整颗树中出现，且只出现一次，非叶子结点可以命中；</span>
</p>

<p style="margin:10px auto; padding-top:0px; padding-bottom:0px">
  <span style="margin:0px; padding:0px">       B+</span><span style="margin:0px; padding:0px; font-family:宋体">树：在</span>B-<span style="margin:0px; padding:0px; font-family:宋体">树基础上，为叶子结点增加链表指针，所有关键字都在叶子结点</span>
</p>

<p style="margin:10px auto; padding-top:0px; padding-bottom:0px">
  <span style="margin:0px; padding:0px; font-family:宋体">中出现，非叶子结点作为叶子结点的索引；</span>B+<span style="margin:0px; padding:0px; font-family:宋体">树总是到叶子结点才命中；</span>
</p>

<p style="margin:10px auto; padding-top:0px; padding-bottom:0px">
  <span style="margin:0px; padding:0px">       B*</span><span style="margin:0px; padding:0px; font-family:宋体">树：在</span>B+<span style="margin:0px; padding:0px; font-family:宋体">树基础上，为非叶子结点也增加链表指针，将结点的最低利用率</span>
</p>

<p style="margin:10px auto; padding-top:0px; padding-bottom:0px">
  <span style="margin:0px; padding:0px; font-family:宋体">从</span>1/2<span style="margin:0px; padding:0px; font-family:宋体">提高到</span>2/3<span style="margin:0px; padding:0px; font-family:宋体">；</span>
</p>

<p style="margin:10px auto; padding-top:0px; padding-bottom:0px">
  <span style="margin:0px; padding:0px; font-family:宋体"><br /> </span>
</p>

<p style="margin:10px auto; padding-top:0px; padding-bottom:0px">
  <span style="margin:0px; padding:0px; font-family:宋体"><strong><span style="font-size:14px">B+/B*<span style="color:rgb(51,51,51); font-family:Arial; font-size:14px; line-height:26px">Tree</span>应用</span></strong></span>
</p>

<p style="margin:10px auto; padding-top:0px; padding-bottom:0px">
  <span style="margin:0px; padding:0px; font-family:宋体"></span>
</p>

<p style="color:rgb(51,51,51); font-family:Arial; font-size:14.3999996185303px; line-height:26px">
  数据库索引--<span style="color:rgb(51,51,51); font-family:Arial; font-size:14px; line-height:26px">索引文件和数据文件是分离的，索引文件仅保存数据记录的地址。</span>
</p>

<p style="color:rgb(51,51,51); font-family:Arial; font-size:14.3999996185303px; line-height:26px">
  <span style="color:rgb(51,51,51); font-family:Arial; font-size:14px; line-height:26px">数据库索引--</span><span style="color:rgb(51,51,51); font-family:Arial; font-size:14px; line-height:26px"><span style="color:rgb(51,51,51); font-family:Arial; font-size:14px; line-height:26px">表数据文件本身就是按B+Tree组织的一个索引结构，这棵树的叶节点data域保存了完整的数据记录。这个索引的key是数据表的主键。</span></span><br />
</p>

<p style="color:rgb(51,51,51); font-family:Arial; font-size:14.3999996185303px; line-height:26px">
  倒排索引--也可以由<span style="color:rgb(51,51,51); font-family:Arial; font-size:14px; line-height:26px">B树及其变种实现但</span>不一定非要<span style="color:rgb(51,51,51); font-family:Arial; font-size:14px; line-height:26px">B树及其变种实现</span>，如<span style="font-family:verdana; font-size:14.3999996185303px; line-height:17.9200000762939px">lucene没有使用B树结构，因此lucene可以用二分搜索算法快速定位关键词</span><span style="font-family:verdana; font-size:14.3999996185303px; line-height:17.9200000762939px">。</span><span style="font-family:verdana; font-size:14.3999996185303px; line-height:17.9200000762939px">实现时，lucene将下面三列分别作为词典文件（Term Dictionary）、频率文件(frequencies)、位置文件 (positions)保存。其中词典文件不仅保存有每个关键词，还保留了指向频率文件和位置文件的指针，通过指针可以找到该关键字的频率信息和位置信息。 　　</span>
</p>

<p style="color:rgb(51,51,51); font-family:Arial; font-size:14.3999996185303px; line-height:26px">
</p>