共计 4064 个字符，预计需要花费 11 分钟才能阅读完成。
二叉查找树 (Binary Search Tree)
概念
二叉查找树又称二叉搜索树，二叉排序树，特点如下:
左子树上所有结点值均小于根结点
右子树上所有结点值均大于根结点
结点的左右子树本身又是一颗二叉查找树
二叉查找树中序遍历得到结果是递增排序的结点序列。
BST 的操作代价分析：
查找代价：
任何一个数据的查找过程都需要从根结点出发，沿某一个路径朝叶子结点前进。因此查找中数据比较次数与树的形态密切相关。
当树中每个结点左右子树高度大致相同时，树高为 logN。则平均查找长度与 logN 成正比，查找的平均时间复杂度在 O(logN)数量级上。
当先后插入的关键字有序时，BST 退化成单支树结构。此时树高 n。平均查找长度为 (n+1)/2，查找的平均时间复杂度在 O(N) 数量级上。
插入代价：
新结点插入到树的叶子上，完全不需要改变树中原有结点的组织结构。插入一个结点的代价与查找一个不存在的数据的代价完全相同。
删除代价：
当删除一个结点 P，首先需要定位到这个结点 P，这个过程需要一个查找的代价。然后稍微改变一下树的形态。如果被删除结点的左、右子树只有一个存在，则改变形态的代价仅为 O(1)。如果被删除结点的左、右子树均存在，只需要将当 P 的左孩子的右孩子的右孩子的…的右叶子结点与 P 互换，在改变一些左右子树即可。因此删除操作的时间复杂度最大不会超过 O(logN)。
BST 效率总结 :
查找最好时间复杂度 O(logN)，最坏时间复杂度 O(N)。
插入删除操作算法简单，时间复杂度与查找差不多。
平衡二叉查找树 (Balanced Binary Search Tree)
二叉查找树在最差情况下竟然和顺序查找效率相当，这是无法仍受的。事实也证明，当存储数据足够大的时候，树的结构对某些关键字的查找效率影响很大。当然，造成这种情况的主要原因就是 BST 不够平衡(左右子树高度差太大)。既然如此，那么我们就需要通过一定的算法，将不平衡树改变成平衡树。因此，AVL 树就诞生了。
AVL 的操作代价分析：
查找代价：
AVL 是严格平衡的 BST（平衡因子不超过 1）。那么查找过程与 BST 一样，只是 AVL 不会出现最差情况的 BST(单支树)。因此查找效率最好，最坏情况都是 O(logN)数量级的。
插入代价：
AVL 必须要保证严格平衡 (|bf|<=1)，那么每一次插入数据使得 AVL 中某些结点的平衡因子超过 1 就必须进行旋转操作。事实上，AVL 的每一次插入结点操作最多只需要旋转 1 次(单旋转或双旋转)。因此，总体上插入操作的代价仍然在 O(logN) 级别上(插入结点需要首先查找插入的位置)。
删除代价：
AVL 删除结点的算法可以参见 BST 的删除结点，但是删除之后必须检查从删除结点开始到根结点路径上的所有结点的平衡因子。因此删除的代价稍微要大一些。每一次删除操作最多需要 O(logN)次旋转。因此，删除操作的时间复杂度为 O(logN)+O(logN)=O(2logN)
AVL 效率总结 :
查找的时间复杂度维持在 O(logN)，不会出现最差情况
AVL 树在执行每个插入操作时最多需要 1 次旋转，其时间复杂度在 O(logN)左右。
AVL 树在执行删除时代价稍大，执行每个删除操作的时间复杂度需要 O(2logN)。
红黑树 (Red-Black Tree)
二叉平衡树的严格平衡策略以牺牲建立查找结构 (插入，删除操作) 的代价，换来了稳定的 O(logN) 的查找时间复杂度。但是这样做是否值得呢？
能不能找一种折中策略，即不牺牲太大的建立查找结构的代价，也能保证稳定高效的查找效率呢？答案就是：红黑树。
RBT 的操作代价分析：
查找代价：
由于红黑树的性质 (最长路径长度不超过最短路径长度的 2 倍)，可以说明红黑树虽然不像 AVL 一样是严格平衡的，但平衡性能还是要比 BST 要好。其查找代价基本维持在 O(logN) 左右，但在最差情况下(最长路径是最短路径的 2 倍少 1)，比 AVL 要略逊色一点。
插入代价：
RBT 插入结点时，需要旋转操作和变色操作。但由于只需要保证 RBT 基本平衡就可以了。因此插入结点最多只需要 2 次旋转，这一点和 AVL 的插入操作一样。虽然变色操作需要 O(logN)，但是变色操作十分简单，代价很小。
删除代价：
RBT 的删除操作代价要比 AVL 要好的多，删除一个结点最多只需要 3 次旋转操作。
RBT 效率总结 :
查找 效率最好情况下时间复杂度为 O(logN)，但在最坏情况下比 AVL 要差一些，但也远远好于 BST。
插入和删除操作改变树的平衡性的概率要远远小于 AVL（RBT 不是高度平衡的）。因此需要的旋转操作的可能性要小，而且一旦需要旋转，插入一个结点最多只需要旋转 2 次，删除最多只需要旋转 3 次(小于 AVL 的删除操作所需要的旋转次数)。虽然变色操作的时间复杂度在 O(logN)，但是实际上，这种操作由于简单所需要的代价很小。
B~ 树 /B+ 树 (B-Tree)
对于在内存中的查找结构而言，红黑树的效率已经非常好了(实际上很多实际应用还对 RBT 进行了优化)。但是如果是数据量非常大的查找呢？将这些数据全部放入内存组织成 RBT 结构显然是不实际的。实际上，像 OS 中的文件目录存储，数据库中的文件索引结构的存储…. 都不可能在内存中建立查找结构。必须在磁盘中建立好这个结构。那么在这个背景下，RBT 还是一种好的选择吗？
在磁盘中组织查找结构，从任何一个结点指向其他结点都有可能读取一次磁盘数据，再将数据写入内存进行比较。大家都知道，频繁的磁盘 IO 操作，效率是很低下的(机械运动比电子运动要慢不知道多少)。显而易见，所有的二叉树的查找结构在磁盘中都是低效的。因此，B 树很好的解决了这一个问题。
B-Tree 的操作代价分析：
查找代价：
B-Tree 作为一个平衡多路查找树(m- 叉)。B 树的查找分成两种：一种是从一个结点查找另一结点的地址的时候，需要定位磁盘地址(查找地址)，查找代价极高。另一种是将结点中的有序关键字序列放入内存，进行优化查找(可以用折半)，相比查找代价极低。而 B 树的高度很小，因此在这一背景下，B 树比任何二叉结构查找树的效率都要高很多。而且 B + 树作为 B 树的变种，其查找效率更高。
插入代价：
B-Tree 的插入会发生结点的分裂操作。当插入操作引起了 s 个节点的分裂时，磁盘访问的次数为 h(读取搜索路径上的节点)+2s(回写两个分裂出的新节点)+1（回写新的根节点或插入后没有导致分裂的节点）。因此，所需要的磁盘访问次数是 h +2s+1，最多可达到 3h+1。因此插入的代价是很大的。
删除代价：
B-Tree 的删除会发生结点合并操作。最坏情况下磁盘访问次数是 3h=（找到包含被删除元素需要 h 次读访问）+（获取第 2 至 h 层的最相邻兄弟需要 h - 1 次读访问）+（在第 3 至 h 层的合并需要 h - 2 次写访问）+（对修改过的根节点和第 2 层的两个节点进行 3 次写访问）。
定义：
一颗 m 阶（m>=3，即一个结点包含的数据和子节点数），3 阶 B - 树有如下特点：
1. 根结点之多 3 颗子树
2. 定义：
define m 3 /*B 树的阶 */
typedef struct Node{
int keynum; /* 结点中关键码的个数，即结点的大小 */
int key[m]; /* 结点数据数组 */
struct Node *parent; /* 指向父节点的指针 */
Node*son[m]; /* 指向子结点的指针数组 */
};
B-Tree 效率总结：
由于考虑磁盘储存结构，B 树的查找、删除、插入的代价都远远要小于任何二叉结构树(读写磁盘次数的降低)。
动态查找树结构的对比：
平衡二叉树和红黑树 [AVL PK RBT]
AVL 和 RBT 都是二叉查找树的优化。其性能要远远好于二叉查找树。他们之间都有自己的优势，其应用上也有不同。
结构对比：AVL 的结构高度平衡，RBT 的结构基本平衡。平衡度 AVL > RBT.
查找对比：AVL 查找时间复杂度最好，最坏情况都是 O(logN)。RBT 查找时间复杂度最好为 O(logN)，最坏情况下比 AVL 略差。
插入删除对比：
1. AVL 的插入和删除结点很容易造成树结构的不平衡，而 RBT 的平衡度要求较低。因此在大量数据插入的情况下，RBT 需要通过旋转变色操作来重新达到平衡的频度要小于 AVL。
2. 如果需要平衡处理时，RBT 比 AVL 多一种变色操作，而且变色的时间复杂度在 O(logN)数量级上。但是由于操作简单，所以在实践中这种变色仍然是非常快速的。
3. 当插入一个结点都引起了树的不平衡，AVL 和 RBT 都最多需要 2 次旋转操作。但删除一个结点引起不平衡后，AVL 最多需要 logN 次旋转操作，而 RBT 最多只需要 3 次。因此两者插入一个结点的代价差不多，但删除一个结点的代价 RBT 要低一些。
4. AVL 和 RBT 的插入删除代价主要还是消耗在查找待操作的结点上。因此时间复杂度基本上都是与 O(logN) 成正比的。
总体评价：大量数据实践证明，RBT 的总体统计性能要好于平衡二叉树。
B- 树和 B + 树 [B-Tree PK B+Tree]
B+ 树是 B - 树的一种变体，在磁盘查找结构中，B+ 树更适合文件系统的磁盘存储结构。
结构对比：
B- 树是平衡多路查找树，所有结点中都包含了待查关键字的有效信息(比如文件磁盘指针)。每个结点若有 n 个关键字，则有 n + 1 个指向其他结点的指针。
B+ 树相比 B - 树的特点：
1. 数据只出现在叶子结点，B- 树每个结点都包含了数据；
2. 叶子结点之间用指针连接；
3. B+ 树的高度一般是 3；
查找对比：
1. 在相同数量的待查数据下，B+ 树查找过程中需要调用的磁盘 IO 操作要少于普通 B - 树。由于 B + 树所在的磁盘存储背景下，因此 B + 树的查找性能要好于 B - 树。
2. B+ 树的查找效率更加稳定，因为所有叶子结点都处于同一层中，而且查找所有关键字都必须走完从根结点到叶子结点的全部历程。因此同一颗 B + 树中，任何关键字的查找比较次数都是一样的。而 B 树就不一定了，可能查找到某一个非终结点就结束了。
插入删除对比：B+ 树与 B - 树在插入删除操作中的效率是差不多的。
总体评价：在应用背景下，特别是文件结构存储中。B+ 树的应用要更多，其效率也要比 B - 树好。
