查找基本概念
顺序表查找
树表的查找
- 二叉排序树
- 平衡二叉树
  - 平衡二叉树的定义
  - 失衡二叉排序树的分析与调整
散列表的查找

查找基本概念

问题：在哪里找？

在查找表中进行查找，查找表是由同一类型的数据元素(或记录)构成的集合。由于”集合”中的数据元素之间存在着松散的关系，因此查找表是一种应用灵便的结构。

问题：怎么查找？

根据给定的某个值，在查表表中确定一个其关键字等于给定值的数据元素或记录。

关键字：用来标识一个数据元素(或记录)的某个数据项的值

主关键字：可唯一标识某一个记录的关键字是主关键字。
次关键字：与上面相反，可以识别多个记录的关键字是次关键字。

问题：如何判断查找是否成功？

若查找表中存在这样一个记录，则称”查找成功”，返回结果为整个记录的信息，或指示该记录在查找表中的位置。

否则称为”查找不成功”，返回结果为空记录或空指针。

问题：查找目的是什么？

对查找表经常进行的操作：

查询某个特定的数据元素是否在查找表中。
检索某个特定的数据元素的各种属性。
在查找表中插入一个数据元素。
删除查找表中的某个数据元素。

问题：查找表怎么分类？

查找表可分为两类：

静态查找表：仅左查询或减少操作的查找表。

动态查找表：找到指定位置后，进行插入和删除操作的查找表。

问题：如何评价查找算法？

查找算法的评价指标：

关键字的平均比较次数，也称平均查找长度

查找 - 图1

问题：查找过程中我们要研究什么？

查找的方法取决去查找表的结构，即表中数据元素是以何种关系组织在一起的。由于对查找表来说，在集合中查询或检索一个特定的数据元素时，若无规律可循，只能对集合中的元素一一加以辨认直到找到位置。

而这样的查询或检索式任何计算机应用系统中使用平度都很高的操作，因此设法提高查找表的查找效率，就是本章讨论问题的出发点。为提高查找效率，一个办法就是在构造查找表时，在集合中的数据元素之间人为的加上某种确定的约束关系。

顺序表查找

本章主要学习以下顺序查找算法：

顺序查找(线性查找)
折半查找(二分查找)
分块查找

顺序查找

顺序查找可以使用顺序表或线性链表表示的静态查找，是最基本的查找技术，它的查找过程是，最表的第一个(或是最后一个)位置开始，逐个记录和指定的关键字进行比较，如果能查找到，则查找成功，反之则查找失败。

顺序查找算法：

// arr:顺序表  len:表长  key:查找关键字
int sq_search(int* arr,int len,int key) {
    int i;
    for (i = 1; i <= len; i++) {
        if (arr[i] == key) {
            return i;
        }
    }
    return 0;
}

这段代码特别简单，就是依据简单的遍历方法判断记录是否和关键字相等(注意元素值从下标1开始)。

但是其实这段代码还有改进的空间，因为这段代码每次循环都要至少比较两次，一次是判断 i 是否越界，二是比较元素是否和关键值相等。我们可以把待查的关键字 key 存入表头，称为”哨兵”或”监视哨”，然后从表尾开始向前比较，就可以免去每一步都要检测是否查找完毕，加快速度。

int sq_search2(int* arr, int len, int key) {
    int i;
    arr[0] = key;
    for (i = len; arr[i] != key; i--);
    return i;
}

在这个算法中，从表尾开始遍历表，当查找到关键字直接返回索引位置，如果匹配到表头则会和设置的”哨兵”匹配成功，返回的便是0，表示匹配失败。当然，哨兵也不一定就要数组开始，也可以在数组末端。

那么这个算法的时间复杂度是多少呢？我们可以发现，查找第 i 个元素，需要比较 n - i + 1次。若查找失败，则需要比较 n + 1 次。

可以算出时间复杂度为：O(n)

而我们多使用了一个辅助空间用来存放”哨兵”，所以空间复杂度为 O(1)。

顺序查找的性能分析

优先：算法简单，逻辑次序无要求，且不同的存储结构均使用。

缺点：ASL太长，时间效率太低。

折半查找(二分查找)

前面使用顺序查找法可以实现查找，但是查找的效率不高。如果在元素之间按照顺序排列，并不是随机排列，我们可以采用折半查找法。

什么是折半查找呢？

假设我们遇到不认识的单词，去牛津词典查找，在假设我们不翻看目录的情况下，如何最快的方式查找出一个单词呢？假设我们查找”search”这个单词在词典中的翻译。

我们可以先打开词典大致中间的页数，然后发现页数中是 N 的开头的字母，可以很明显的发现我们还需要往后翻页，因为 S 开头的单词在 N 后面，那么此时，N 字母所在页前面的所有页数都被我们排除掉了。

然后我们从 N 的后一个字母页数往后翻一半的页数，发现翻到字母 U 开头的字母，发现 U 字母已经在 S 后面了，说明翻过头了，我们又会往前翻，那么 U 字母后面的页数也被排除掉了。

依据这种方法进行查找，直到找到目标单词为止，这就是折半查找的精神。

折半查找：每次将待查记录所在区间缩小一半。

折半查找循环算法实现：

int binary_search(int* arr, int len, int key) {
    int low, high, mid;
    low = 1, high = len;
    while (low <= high) {    
        mid = (low + high) >> 1;
        if (arr[mid] > key)
            high = mid - 1;
        else if (arr[mid] < key)    
            low = mid + 1;    
        else  
            return mid;
    }
    return 0;
}

折半查找递归算法实现：

int binary_search2(int* arr, int low, int high, int key) {
    int mid;
    if (low > high) return 0;
    mid = (low + high) >> 1;
    if (arr[mid] > key)
        return binary_search2(arr, low, mid - 1, key);
    else if (arr[mid] < key)
        return binary_search2(arr, mid + 1, high, key);
    else
        return mid;
}

折半查找性能分析 —— 判定树

如果我们把折半查找法当成一棵二叉树来看，只需查找一次的结点作为树的根，查找两次的结点作为根的两个分支，查找三次的结点作为根分支的分支，依次类推…

那么如下的数组就可以得到如下一棵判定树，我们前面在树的章节已经直到完全二叉树的深度为 log2 n+1。所以比较的次数一定小于等于树的深度，也就是log2 n+1。

查找 - 图2

那么假设每个元素的查找概率相等，求查找成功时的平均查找长度是多少呢？

如上图的判定树的查找长度如下：

查找 - 图3

平均查找长度ASL(成功时)：

设表长 n=2h-1，则 h=log2 (n+1) (此时，判定树的深度为=h的满二叉树)，且表中的每个记录的查找概率相等：Pi=1/n。

查找 - 图4

折半查找的性能分析

折半查找优点：效率比顺序查找高。

折半查找缺点：只适用于有序表，且限于顺序存储结构(对线性链表无效)。

分块查找

还是以词典为例，可以发现词典是把每个单词的首字母作为一部分的区块，我们可以使用二分查找的方法找到这个区块，但是找到了区块之后，我们还可以根据顺序的方式或者折半(需有序)的方式再次进行查找。这就是分块查找的精神。

分块查找的方式：

将表分成几块，且表或者有序，或者分块有序。若 i < j，则第 j 块中所有记录的关键字均大于第 i 块中的最大关键字。
建立索引表，每个结点含有最大关键字域和指向本块第一个结点的指针，且按关键字有序。

查找过程：先确定带查找记录所在块(顺序或折半查找)，然后在块内查找(顺序或折半查找)。

查找 - 图5

树表的查找

前面学习了几种排序算法，其中，二分查找的效率比较高。但是当表插入、删除操作频繁时，为维护表的有序性，需要移动表中很多记录。所以我们可以改用动态查找表 —— 几种特殊的树：二叉排序树、平衡二叉树、红黑树、b - 树、b + 树、键树。

这种动态查找表的特点是表结构在查找过程中动态生成，对于给定值key，若表中存在，则成功返回。否则插入关键字等于key的记录。

二叉排序树

二叉排序树，又称为二叉搜索树，二叉查找树。

二叉排序树或是空树，或是满足如下性质的二叉树：

若其左子树非空，则左子树上所有结点的值均小于根节点的值。
若其右子树非空，则右子树上所有结点的值均大于等于根结点的值。
其左右子树本身又各是一棵二叉排序树。

如图所示即为二叉排序树
查找 - 图6

那么中序遍历二叉排序树，可以得到什么规律呢？如上图所示的二叉排序树中序遍历后可以得到这样的结果：3 - 12 - 24 - 37 - 45 - 53 - 61 - 78 - 90 - 100。

二叉排序树的性质：中序遍历非空的二叉排序树所得到的数据元素序列是一个按关键字排列的递增有序序列。

二叉排序树查找操作

算法思想：

若查找的关键字等于根结点，则查找成功。
若查找的关键字小于根结点，则查找左子树。
若查找的关键字大于根节点，则查找右子树。
在其左右子树中重复上述操作。

算法实现：

BiTree searchBST(BiTree T, KeyType key) {
    // 如果查找的树为空或者data域的值key，就返回T，不再查找
    if (!T || T->data == key) return T;
    // 如果data域的值比key大，说明需要到右子树中查找，反之去左子树查找
    if (T->data > key) {
        return searchBST(T->lchild, key);
    }
    else {
        return searchBST(T->rchild, key);
    }
}

二叉排序树查找分析

二叉排序树上查找某关键字等于给定值的结点过程，其实就是走了一条从根到该结点的路径，故比较的关键字次数=此结点所在层次数。最多的比较次数=树的深度。

二叉排序树的平均查找长度

含有n个结点的二叉排序树的平均查找长度和树的形态有关，如图所示：

查找 - 图7

查找 - 图8

那么如何提高形态不均衡的二叉排序树的查找效率？

解决这个问题的办法就是做”平衡化”处理，即尽量让二叉树的形状均衡。那么这样的二叉树就是平衡二叉树，关于平衡二叉树的概念在后面会学习到。

二叉排序树创建和插入操作

在学习创建操作之前，我们需要先了解二叉排序树是怎么进行插入操作的。

插入操作算法思想：

若二叉排序树为空，则插入结点作为根结点插入到空树中
若二叉排序树不空，则继续查找其左右子树
- 若树中已有和插入结点相同的结点，则不再插入
- 若树中没有找到和插入结点相同的结点，则查找至某个结点的左子树或右子树为空位置，则插入结点应为该结点的左孩子或右孩子。

查找 - 图9

不过我们需要实现插入算法，那我们需要提前修改以下查找算法，这是因为前面我们未查找到结果是返回NULL指针，但是这里我们需要获取到的是插入结点的父结点，这样，我们才可以把新结点插入。如上图，原来我们需要找40关键字所在的位置，如果没找到是返回NULL，而现在我们需要找到37，然后37和40比较大小，决定插入的右子树还是左子树。

插入算法实现：

/*
    改进查找算法
    BiTree T：树的根结点
    KeyType key：需要查找的关键字
    BiTree f：子节点的父节点，如果查找失败则返回f
    BiTree* p：查找成功返回的结点
*/
Status searchBST2(BiTree T, KeyType key, BiTree f, BiTree* p) {
    if (!T) {
        *p = f;
        return FALSE;
    }
    else if(T->data == key) {
        *p = T;
        return TRUE;
    }
    else if (T->data > key) {
        searchBST2(T->lchild, key, T, p);
    }
    else {
        searchBST2(T->rchild, key, T, p);
    }
}
// 插入算法
Status insertBST(BiTree* T, KeyType key) {
    BiTree R, S;
    // 根据查找算法的返回值进行判断，如果能查找到值，则取消插入
    if (!(searchBST2(*T,key,NULL,&R))) {
        // 无法查找到值，说明需要插入新结点，创建新的空间
        S = (BiTree)malloc(sizeof(BTNode));
        S->data = key;    // 赋值
        S->lchild = S->rchild = NULL;
        // 第一次创建结点，根为空，直接把新结点作为根结点
        if (R==NULL) {
            *T = S;
        }    // 之后依据大小判断左右子树
        else if (R->data > key) {
            R->lchild = S;
        }
        else {
            R->rchild = S;
        }
        return TRUE;
    }
    else {
        return FALSE;
    }
}

学习完插入算法之后，创建一张二叉排序表就简单了，我们只需要将需要插入的数据都执行一次插入操作，那么最后就可以生成二叉排序树了。

int main() {
    // 声明根结点，初始值为空
    BiTree T = NULL;
    // 需要插入的数据，此处为字符，也可以是数值等
    char ch_arr[8] = { 'e','c','a','d','k','f','m','l' };
    // 根据数组创建二叉排序树
    for (int i = 0; i < 8; i++) {
        insertBST(&T, ch_arr[i]);
    }
    // 查找操作
    BiTree p;
    searchBST2(T, 'k', NULL, &p);
    printf("result: %c", p->data);
    return 0;
}

右上面的操作可以发现，其实二叉排序树的创建过程，就是将一个无序序列构造成一个有序序列的过程。那么将无序序列构造成二叉排序树，其实也可以看成是一个排序的过程。

由于插入的结点均为叶子结点，故无需移动其他结点，相当于在有序序列上插入记录而无需移动其他记录。

但是，根据关键字的输入顺序不同，建立的二叉排序树也不同。如下图所示：

查找 - 图10

二叉排序树的删除操作

从二叉排序树中删除一个结点，不能把以该结点为根的子树都删除，只能删除该结点，并且还应该保证删除后所得的二叉树仍然满足二叉排序树的性质。

如果需要满足二叉排序树的性质，那么删除结点就有以下情况：

被删除结点是叶子结点，那么我们可以直接删去，不会影响到其他结点。
被删除的结点只有左子树或者只有右子树，那么我们直接用其左子树或右子树替换被删除的结点即可。
被删除的既有左子树，也有右子树。这是最麻烦的情况。由于二叉排序树是中序遍历，按照递增排序的。所以我们有两种方式处理这种情况。
- 找到被删除结点的(中序遍历下)前驱结点，也就是所有左子树的最大结点。我们用此结点替换被删除结点。如果替换的结点有其他子树，根据上面的情况进行同样的处理。
- 找到被删除结点的(中序遍历下)后继结点，也就是所有右子树的最大结点。和上面找到前驱结点一样的处理方式，下图右三就是使用这种方式进行处理。

查找 - 图11

平衡二叉树

前面学习过，如果生成二叉树的数据本身就是递增有序的，可能会造成生成的二叉排序树只有单分支，从而并没有达到提升效率的目的。所以基于这个问题的解决办法，就是把二叉排序树做平衡化处理，即尽量让二叉树的形态均衡，这就是平衡二叉树。

平衡二叉树的定义

平衡二叉树又称为 AVL 树，一棵平衡二叉树或者是空树，或者是具有下列性质的二叉排序树：

左子树与右子树的高度之差的绝对值小于等于1。
左子树和右子树也是平衡二叉排序树。

为了方便起见，给每个结点附加一个数字，给出该结点所有左子树与所有右子树的高度差，这个数字称为结点的平衡因子(BF)。

平衡因子 = 结点左子树高度 - 结点右子树高度

更具上面平衡二叉树的两点定义，平衡二叉树上所有结点的平衡因子只能是-1、0或1。

查找 - 图12

失衡二叉排序树的分析与调整

当我们在一个平衡二叉排序树上插入一个结点时，有可能导致失衡，即出现的平衡因子绝对值大于1的结点，如：2、-2。

查找 - 图13

如果在一棵AVL树中插入一个新结点后造成失衡，则必须重新调整树的结构，使之恢复平衡。其中失衡的结点可能不止一个，插入一个新结点后可能造成多个结点的失衡，但是我们先处理最小失衡子树的根结点。

那么失衡的结点大致分为以下四种类型：

查找 - 图14

所以我们的需求就是把如上的失衡结点调整为平衡结点，如下图：

查找 - 图15

调整原则：降低高度并且保持二叉排序树的性质

那么我们怎么实现如上图中的转换呢？

LL型调整

查找 - 图16

步骤：

先将中间结点 4 带着左子树上升。
结点 5 修改为结点 4 的右孩子。
如果结点 4 还有右孩子，就作为结点 5 的左孩子。

RR型调整

查找 - 图17

步骤：

先将中间结点 6 带着右子树上升。
结点 4 修改为结点 6 的左孩子。
如果结点 6 还有左孩子，就作为结点 4 的右孩子。

LR型调整

查找 - 图18

步骤：

先将中间结点 7 上升，不带其左孩子以及右孩子。
结点 3 成为结点 7 的左孩子，结点 16 成为结点 7 的右孩子。
如果结点 7 有左右孩子，结点 7 的左孩子成为结点 3 的右孩子，结点 7 的右孩子成为结点 16 的左孩子。

RL型调整

查找 - 图19

步骤：

先将中间结点 9 上升，不带其左孩子以及右孩子。
结点 7 成为结点 9 的左孩子，结点 11 成为结点 9 的右孩子。
如果结点 9 有左右孩子，结点 9 的左孩子成为结点 7 的右孩子，结点 9 的右孩子成为结点 11 的左孩子。

散列表的查找

基本概念

基本思想：记录的存储位置与关键字之间存在对应关系。对应关系可以由 hash 函数求得：Loc(i) = H(keyi)。所以散列表又被称为哈希(Hash)表。

范例

查找 - 图20

如图上面的存储方式中，使用的存储方式不是直接按顺序存储或者是链式存储，而是根据后两位数字作为索引，将信息存入对应的索引位。

这种方式，如果我们向查找学号为 “200101180211” 的学生是否存在，只需要查找 11 位单元是否有信息，如果没有信息则返回一个特殊值，如空指针或空记录，返回的是此特殊值则表示该学生不存在。

这种查找方式可以的有点就是查找效率极高，但是空间效率却很低。

散列表的若干术语

散列方法(杂凑法)

使用某个函数，依该关键字计算元素的存储位置，并按此位置存放。

查找时，由同一个函数对给定值 k 计算地址，将 k 与地址单元中元素关键码进行对比，确定查找是否成功。

散列函数(杂凑函数)：散列方法中使用的转换函数。

散列表(杂凑表)：按上述思想构造的表

冲突：不同的关键码映射到同一个散列地址，key1 != key2，但是hash(key1) == hash(key2)

查找 - 图21

同义词：具体相同函数值的多个关键字，如上图中的25、11。

散列函数的构造

前面说过，散列表中元素的插入需要求使用散列函数计算存储位置，同时，如果散列函数计算出的索引位置已经有元素，则会产生冲突。在散列查找函数中，冲突是不可避免的，只能尽可能减少。

故使用散列表要尽量解决号两个问题：

构造号的散列函数
- 所选函数尽可能简单，以便提高转换速度。
- 所选函数对关键码计算出的地址，应在散列地址集中致均匀分布，以减少空间。
指定一个好的解决冲突的方法
- 虽然冲突无法避免，但是我们应该尽量避免冲突。如果有多个冲突的关键字，我们应该怎么处理这些关键字。

根据元素集合的特性构造

要求一：n个数据源仅占用n个地址，虽然散列查找以空间换时间，但仍希望散列的地址空间尽量小。
要求二：无论用什么方法存储，目的都是尽量均匀的存放元素，以避免冲突。

依据上面的特性，主流的散列函数大致分为以下几种构造方式：直接定址法、数字分析法、平方取中法、折叠法、除留取余法、随机数法。

直接定址法：

查找 - 图22

优点：以关键码key的某个线性函数值作为散列地址，不会产生冲突。

缺点：要占用连续地址空间，空间效率低。

查找 - 图23

除留余数法：

查找 - 图24

关于p的取值，设表长为m，则 p 取 p<= m 且为质数。

查找 - 图25

处理冲突的方法：

开放地址法
链地址法
再散列法
建立公共溢出区域

开放地址法

基本思想：有冲突时就去寻找下一个空的散列地址，只要散列表足够大，空的散列地址总能找到，并将数据元素存入。

查找 - 图26

线性探测法

 Hi=(Hash(key) + di) mod m

其中：m为散列表长度，di为增练序列(1,2,3,….)，且di=i。一旦有冲突，就找下一个地址，直到找到空地址存入。

查找 - 图27

二次探测法

 Hi = (Hash(key) + di) mod m

其中：m为散列表长度，di为增练序列12, -12, 22, -22 …, q2。

伪随机探测法

 Hi = (Hash(key) + di) mod m        (1

其中：m为散列表长度，di为伪随机数。

但是如果使用随机数来作为递增序列的化，下次怎么查找元素呢？注意，这里是伪随机数，我们只要设置相同的随机种子，通过不断调用随机函数，就会得到一个随机不会重复的序列，但是下次使用这个随机种子，得到的随机数还是相同的。

链地址法

基本思想：相同散列地址的记录链成一单链表，m 个散列地址就设 m 个单链表，然后用一个数组将 m 个单链表的表头指针存储起来，形成一个动态的结构。

查找 - 图28

链地址法建立散列表步骤：

取出数据元素的关键字key，计算其散列函数值(地址)。若该地址对应的链表为空，则将该元素插入此链表，否则采用第2步的方式解决冲突。
根据选择的冲突处理方法，计算关键字key的下一个存储地址，若该地址对应的链表不为空，则利用链表的前插法或后插法将元素插入此链表。

链地址法的优点：

非同义词不会冲突，无”聚集”现象。
链表上结点空间动态申请，更适合于表长不确定的情况。

散列表的查找：

查找 - 图29

散列表的查找效率分析

如果问散列表的平均查找长度ASL能达到O(1)吗？这答案很显然是不能的，从前面的例子可以看到，如果通过计算后得到的索引可以直接取得元素，那么只需要查找一次，但是如果有多个同义词，不管是使用开地址法还是链地址法，显然某些同义词不能一次查找成功。

如图所示的散列表，如1、27、79等元素，都无法一次查找到元素：

查找 - 图30

那么怎么计算散列表的ASL呢？散列表的ASL取决于：

散列函数
处理冲突的方法
散列表的装填因子

装填因子 = 表中填入的记录数 / 哈希表长度

装填因子越大，表中记录数越多，说明表装的越慢，发生冲突的可能性就越大，查找时比较次数就越多。

故ASL与装填因子有关，既不是严格的O(1)，也不是O(n)。

查找 - 图31

总结

散列表技术具有很好的平均性能，优于一些传统的技术。
链地址法优于开地址法。
除留余数法做散列函数由于其他函数。

本章完。