大话数据结构12-查找2
接着上一篇介绍的二叉排序树，这一篇我们首先介绍几种基于二叉排序树的优化树型查找法。接着，介绍了一种更加高效的寻找特定唯一元素的查找方法：散列表查找法。
I. 平衡二叉树（AVL 树）
平衡二叉树（Self-Balancing Binary Search Tree 或者 Height-Balanced Binary Search Tree，或叫 AVL tree, AVL是它的几个发明人的名字的缩写）是一种二叉排序树，其中每一个结点的左子树和右子树的高度（深度）差至多等于1。
我们将二叉树上结点的左子树深度减去右子树的深度值称为平衡因子BF（Balance Factor），由上述定义可知，这个值for AVL tree 只可能是 -1, 0 or 1。
距离插入结点最近的，且 平衡因子的绝对值大于1的结点 为根的子树，我们称为最小不平衡子树。
实现平衡二叉树的基本思想是在构建二叉树的时候，每当插入一个结点，就先检查一下是否因为插入而破坏了树的平衡性，若是，则找出最小不平衡子树，并在保证二叉排序树特性的前提下，调整 最小不平衡子树 中结点链接的方式，进行旋转等操作使之成为新的平衡子树。
需要注意的是，上面那步的调整是针对 最小不平衡子树 进行，而不是对整棵树进行。这样的好处是可以尽量减小调整所需的工作量。
总结来说，旋转操作处理子树不平衡大概可以分为以下几类：
- 最小不平衡子树的根结点的平衡因子 BF 大于 1， 右旋；
- 最小不平衡子树的根结点的平衡因子 BF 小于 -1， 左旋；
- 插入节点后，最小不平衡子树的 BF 与它的子树的 BF 的符号相反，就需要先对子树进行一次旋转将符号变为相同之后，在对最小不平衡子树进行旋转。
除 AVL 之外，二叉排序还有另外的平衡算法，如 红黑树（Red Black Tree）等，他们与二叉平衡树相比各有优势。
II. 多路查找树（B树）
对于大数据量的数据，我们通常将其存储在外部存储设备例如硬盘上，这时，数据的读取、存取次数会极大的影响程序的效率。为提升这一效率，我们希望一次读取可以获得更多的数据，从而设计了如下的多路查找树方案。
多路查找树（Multi-way Search Tree）,其每个结点的孩子数可以多于两个，且 每个结点处可以存储多个元素。
这里，我们讲解它的四种特殊形式，2-3树 和 2-3-4树，以及 B树 和 B+树。
a. 2-3树 和 2-3-4树
2-3树 是这样的一棵多路查找树：它的每个结点都具有两个孩子（2结点）或3个孩子（3结点）。
一个 2结点 包含一个元素和两个孩子（或没有孩子）。且与二叉排序树类似，左子树包含的元素小于该元素，右子树包含的元素大于该元素。但不同的是，2结点要不有2个孩子，要不没有孩子，不存在只有1个孩子的情况。
一个 3结点 包含 一小一大两个元素 和 3个孩子（或没有孩子），同 2结点 一样，3结点也是要不有3个孩子，要不没有孩子。3结点 的左子树包含 小于较小元素（根结点中） 的元素，右子树包含 大于较大元素 的元素，中间子树包含介于结点中两个元素大小之间的元素。
需要注意的是，2-3树 的所有叶子结点都在同一层次上，一个例子如下图所示：Figure link
与传统的二叉排序树不同的是，为满足2-3树的结构要求，2-3树的数据插入过程可能会对其余的结点产生连锁反应。
整体上，插入元素可以分为向2结点中插入和向3结点中插入。向2结点插入时可以直接将该2结点变为3结点；向3结点插入时较为复杂，需要将部分元素上移到上一层的根结点中。类似的，删除操作也需要分多种情况进行讨论。
2-3-4树 实际上是 2-3树 的扩展，它在 2-3树 的基础上增加了一个 4结点，4结点包含小中大三个元素和四个孩子（或没有孩子），如果有孩子，四个孩子分布在三个元素形成的4个区间中。
b. B树 and B+树
B树 （B-tree） 是一种平衡多路查找树，2-3树，2-3-4树都是 B树的 特例。结点最大的孩子数目称为 B树的阶（order）, 因此，2-3树是3阶B树，2-3-4树是4阶B树。
一个 m阶的B树 具有如下属性：
- 如果根结点不是叶结点，则至少有两棵子树。
- 每个结点都有 k-1 个元素，$\lceil m/2\rceil \leq k \leq m$,若是分支结点（非叶子结点），则有 k 个孩子。
- 所有叶子结点都位于同一层次。
- 所有分支结点包含下列信息 $(n,A_0,K_1,A_1,K_2,A_2…,K_n,A_n)$。其中 n 为结点包含的元素（关键字）的个数，$K_i$ 为结点中元素值（所存储的关键字），且 $K_i \leq K_{i+1}$。$A_i$ 为指向子树根结点的指针，且 $A_i$ 所指向的子树的关键字大小 均位于 $K_i$ 和 $K_{i+1}$ 之间(note: special case for $A_0$ and $A_n$)。
通过 B树 的方式，我们可以在有限内存的情况下，每一次访问磁盘都访问我们可以获得的最大量数据，从而尽可能的减少硬盘读取的次数，最终提升性能。因此，B树的数据结构，非常适合用于内外存的数据交互工作。
B+树 是 B树 的一种变形，目的是提升树的遍历效率 （因为如果要遍历 B树，需要访问所有外存页，as每个结点代表一个外存页）。具体的，在 B+ 树中，
- 分支结点中对应的元素会在他们的中序后继的叶子结点中再次出现 （所以分支结点实际上只作为索引用，数据都在叶子结点中。）
- 叶子结点间添加链接指针，依关键字顺序自小到大顺序链接。
因此，对于 B+树，遍历时只需要从最左侧的叶子结点开始，顺序读取即可，大大提升了遍历效率。
III. 散列表查找与散列函数的构造
散列表的核心思想是将数据的存储位置与数据的关键字联系起来，即 $Storing_place = f(Key)$， 从而我们可以直接通过关键字查找到记录的位置，而不需要通过排序等方法进行查找。
这里，我们将上面的对应关系 $f$ 称为 散列函数，又称为 哈希函数（Hash）。采用散列技术将记录存储在一块连续的存储空间中，这块连续的存储空间称为 散列表 或 哈希表（Hash Table），关键字对应的记录存储位置称为 散列地址。
散列技术最适合处理的问题是查找与给定值相等的记录，可以大大提升查找效率。但它也有很大局限性，例如它不适合处理一个关键字对应很多记录的情况。
散列表存储/查找 的核心是设计一个好的散列函数，使得从关键字得到的 散列地址，尽量均匀、不重复的存储在存储空间中。
一个好的散列函数应当具有2个特点：计算简单和散列地址分布均匀。下面，我们介绍一些常见的散列函数构造方法。
a. 直接定地址法
通常线性函数具有较好的平均分布特性，因此我们设计 $f(key) = a* key + b$ (a,b 为常数)，即使用线性函数来生成散列地址。
但使用该方法需要事先知道关键字的分布情况，适合查找表较小且连续的情况。因而在实际中很少使用。
b. 数字分析法
我们首先通过分析关键字寻找到关键字中具有特征的部分，将该部分 抽取 出来用来计算散列存储位置。
例如手机号，同一运营商，同一地区的人的手机号前7位非常容易重复，因此我们可以选择最后4位作为散列地址。
c. 平方取中法
将关键字求平方，然后取中间的几位数字作为散列地址。
例如，关键字1234，平方为 1522756，抽取它的中间三位 227 作为散列地址。
这种方法适合不清楚关键字分布，且关键字位数不是很大 的情况。
d. 折叠法
折叠法是将关键字从左到右分割为位数相等的几部分（最后一部分位数不足可以短一些），然后将它们叠加求和，并按照散列表表长，取最后几位作为散列表的地址。
折叠法适合处理不知道关键字分布且关键字位数较多的情况。
e. 除留余数法
散列表的长度为 m， 该方法的 散列函数为：$f(key) = key\ mod \ p, \ (p\leq m)$。mod 是取模的意思。此外，除留余数法不仅可以直接处理关键字，也可以折叠、平方取中后再取模。
此方法是较为常见的构造散列表的方法。方法的关键是选取合适的 p 值。通常的，对于长度为 m 的散列表，通常 p 为小于或等于表长（最好接近 m）的质数 或 不包含小于 20 质因子的合数。
f. 随机数法
以 key 为 sead 生成一个随机数作为散列地址。$f(key) = random(key)$, 这里的 random 是随机函数。
当关键字的长度变化较大时，这一方法比较适合。
IV. 处理散列冲突的方法
如果两个关键字不相同，$key1 \neq key2$, 但是却有 $f(key1) = f(key2)$，这种现象称为 冲突(collision)，并且，我们称 $key1$ 和 $key2$ 为这个散列的 同义词(synonym)。
为处理散列冲突，这里列举如下几种处理方案。
a. 开放定址法
所谓的开放定址法就是一旦发生了冲突，就去寻找下一个空的散列地址，我们知道，只要散列表足够大，空的散列地址总能够找到。
它的公式是： $f_i(key) = (f(key) + d_i)\ MOD \ m, \ (d_i = 1,2,3,…m-1)$。
也就是说，当余数重复时，我们将对应重复的余数加 1 后再取余（实际上就是紧接着的下一个数字的余数），如果仍然重复，就再加1，直到找到空位为止。上述 $d_i$ 是从1开始逐渐递加，我们因此也称它为 线性探测法。
但是这一方法对于 空位在 重复地址 的前面 的情况效率很低，我们因此设计如下的 二次探针法：$f_i(key) = (f(key) + d_i)\ MOD \ m, \ (d_i = 1^2,-1^2,2^2,-2^2,…q^2,-q^2: q<(m/2))$. 可以注意到，二次探针法的 $d_i$ 值是一正一负交替出现，从而避免了单方向寻找空位。此外，该方法还使用了平方运算，目的是让关键字不要都聚集在一块区域，从而减少 堆积 现象的发生，同样可以提高效率。
最后，我们还可以设置位移量 $d_i$ 为一个随机函数计算得到的值，我们称为 随机探针法。
b. 再散列函数法
除去在重复时微调我们的散列函数，我们还可以选取几个完全不同的散列函数作为备选，当使用一个散列函数得到相同的 hash 值时，我们就针对这一 key 值使用下一个散列函数，即: $f_i(key) = RH_i(key), (i = 1,2,…,k)$. 这里的 $RH_i$ 就是不同的散列函数。例如，前面的除留余数、折叠法、平方取中等。
这一方法的好处是当发生散列地址冲突时，直接更换一个散列函数，散列值的位置可以相对分散，但是也相应的增加了计算成本。
c. 链地址法
链地址法则不同于上面冲突了就换地址的思想，而是通过链表的形式解决冲突。具体的，对于链地址法，关键字为同义词（即关键字的散列函数计算值相等）的记录存储在一个单链表中， 散列表中则存储所有同义词链表的头指针。这样，当遇到冲突时，我们仅需要给单链表增加节点即可。
链地址法对于冲突非常多的散列函数来说是一个极佳的处理方法。但是，该方法在查找时的性能损耗可能也更大（需要遍历链表）。
d. 公共溢出区法
这一方法更加粗暴，直接将重复的关键值对应的元素存放到一个公共的存储区域，从而避免了前面开放定址法需要逐次向后寻找空的存储空间的问题。这一方法对于冲突较少的情况存储、查找效率很高。
e. 总结
最后，我们总结一下影响散列表的查找性能的因素：
- 散列函数是否均匀；
- 处理冲突的方法；
- 散列表的装填因子：$\alpha =$ 填入表中的记录的个数/散列表的长度，标志着散列表的装满的程度。当 $\alpha$ 越大时，产生冲突的可能性就越大。