二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查 找元素相当于在顺序表中搜索元素，效率低下。因此，两位俄罗斯的数学家G.M.Adelson-Velskii 和E.M.Landis在1962年 发明了一种解决上述问题的方法：当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均

在上一篇中我们实现了二叉树的顺序结构——堆的实现,这次实现链式结构,若对堆不了解,可以观看。

顺序结构以及平衡树中，元素关键码与其存储位置之间没有对应的关系，因此在查找一个元素 时，必须要经过关键码的多次比较。顺序查找时间复杂度为O(N)，平衡树中为树的高度，即 O(log2N)，搜索的效率取决于搜索过程中元素的比较次数理想的搜索方法：可以不经过任何比较，一次直接从表中得到要搜索的元素。 如果构造一种存储结构，通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立 一一映

红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或 Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的

给两个文件，分别有100亿个整数，我们只有1G内存，如何找到两个文件交集？方案1:将其中一个文件1的整数映射到一个位图中，读取另外一个文件2中的整数，判断在不在位图，在就是交集。消耗500M内存方案2:将文件1的整数映射到位图1中，将文件2的整数映射到位图2中，然后将两个位图中的数按位与。与之后为1的位就是交集。消耗内存1G

1970年，R.Bayer和E.mccreight提出了一种适合外查找的树，它是一种平衡的多叉树，称为B树 (后面有一个B的改进版本B+树，然后有些地方的B树写的的是B-树，注意不要误读成"B减树")。一 棵m阶(m>2)的B树，是一棵平衡的M路平衡搜索树，可以是空树或者满足以下性质：