软件设计师考试 | 第三章 数据结构 | 查找
（一）查找的基本概念
1.基本概念
查找是一种常用的基本运算。
查找表是指由同一类型的数据元素（或记录）构成的集合。
查找表是一种非常灵活的数据结构。
对查找表经常进行的两种操作（静态查找表）：
- 查询某个特定的数据元素；
- 检索某个特定的数据元素的各种属性。
对查找表经常要进行的另外两种操作（动态查找表）：
- 插入一个数据元素；
- 删除一个数据元素。
关键字是数据元素（或记录）的某个数据项的值，用它来标识这个数据元素。
主关键字是指能为一标识一个数据元素的关键字；次关键字是指能标识多个数据元素的关键字。
2.平均查找长度
通常以“其关键字和给定的值进行比较的记录个数的期望值”作为衡量查找算法好坏的依据。
定义：为确定记录在查找表中的位置，需和给定的关键字进行比较的次数多期望值称为查找算法在查找成功时的平均查找长度。
（二）静态查找表的查找方法
1.顺序查找
基本思想：从表的一端开始，逐个将记录的关键字和给定值比较，若找到一个记录的关键字与给定值相等，则查找成功；若整个表中的记录均比较过，仍未找到关键字等于给定的记录，则查找失败。
顺序查找的方法对于顺序存储方式和链式存储方式的查找表都适用。
顺序查找成功的平均查找长度为：(n+1)/2，即查找的平均比较次数约为表长的一半。
顺序查找方法的优缺点：
- 缺点：与其他查找方法相比，顺序查找方法在
n值较大时，其平均查找长度较大，查找效率较低； - 优点：算法简单并且适应面广，对查找表的结构没有要求，无论记录是否按关键字有序排列均可应用。
2.折半查找
基本思想：一维数组中，元素已经按关键字递增方式排列。首先将查找元素的关键字值与表中间位置上记录的关键字进行比较，若相等，则查找成功；若关键字值比表中间位置上关键字值大，则说明待查记录只能在后半段的半个子表中，下一步应在后半个子表中进行查找；反之，则说明待查记录只能在前半个子表中，下一步应在前半个子表中进行查找，这样逐步缩小范围，直到查找成功或子表为空时失败为止。
折半查找的平均查找长度为：log2(n+1)-1。
折半查找方法的优缺点：
- 缺点：该方法要求查找表进行顺序排序存储，并且按关键字有序排列，当对表进行插入或删除操作时，需要移动大量的元素，所以折半查找适用于表不易变动，且又经常进行查找的情况；
- 优点：查找效率比顺序查找的效率要高。
3.分块查找
分块查找又称为索引顺序查找，是对顺序查找方法的一种改进，其效率介于顺序查找与折半查找之间。
基本思想：首先将表分为若干块，每一块的关键字不一定有序，但块之间是有序的，即后一块中所有记录的关键字均大雨前一个块中最大的关键字。此外，还建立一个“索引表”，索引表按关键字有序排列。然后剩下的部分分为两步：一是在索引表汇总确定待查记录所在的块，二是在块内顺序查找。
分块查找的平均查找长度为：两次查找的平均查找长度（索引查找和块内查找）之和，即(n/s+s)/2+1，其中s为每块中的元素个数。
（三）动态查找表
动态查找表的特点是表结构本身是在查找过程中动态生成的。
1.二叉排序树
定义：又称为二叉查找树。它或者是一棵空树，或者是具有以下性质的二叉树：
- 若它的左子树非空，则左子树上所有结点的值均小于结节点的值；
- 若它的右子树非空，则右子树上所有结点的值均大于根节点的值；
- 左、右子树本身是二叉排序树。
查找过程：二叉排序树非空时，将给定值与根结点的关键字值相比较，若相等，则查找成功；若不相等，则当根结点的关键字大于给定值时，下一步到根的左子树中进行查找，否则到根的右子树中进行查找。若查找成功，则查找过程是走了一条从树根到所找到结点的路径；否则，查找过程终止于一棵空的子树。
插入结点：每读入一个元素，建立一个新结点。若二叉排序树非空，则将新结点的值与根结点的值相比较，如果小于根节点的值，则插入到左子树中，否则插入到右子树中；若二叉排序树为空，则新结点作为二叉排序树的根结点。
二叉排序树插入结点
删除结点：删除结点可分为三种情况：删除的是叶子结点，删除的结点只有左子树或只有右子树，被删除结点的左子树、右子树均存在。
- 删除的是叶子结点。只需更改双亲结点的相应指针即可。
- 删除的结点只有左子树或只有右子树。将被删除结点的左子树或右子树接成其双亲结点的左子树（或右子树）。
- 被删除结点的左、右子树均存在。应将其左、右子树连接到适当的位置，并保持二叉排序树的特性。
二叉排序树删除结点
从二叉排序树的定义可知，中序遍历二叉排序树可得到一个关键字有序的序列，构造二叉排序树的过程就是对无序序列进行排序的过程。
2.平衡二叉树
定义：又称为AVL树，它或者是一棵空树，或者是具有以下性质的二叉树：
- 左子树和右子树都是平衡二叉树；
- 左子树和右子树的高度之差的绝对值不超过
1。
平衡因子（BF）为该结点左子树的高度减去其右子树的高度，则平衡二叉树上所有结点的平衡因子只可能是-1,0,1。
分析二叉树的查找过程可知，只有在树的形态比较均匀的情况下，查找效率才能达到最佳。
使二叉树保持平衡的基本思想是：每当在二叉排序树中插入一个结点时，首先检查是否因插入破坏了平衡。若是，则找出其中的最小不平衡二叉树，在保持二叉排序树特性的情况下，调整最小不平衡子树中结点之间的关系，以达到新的平衡。
最小不平衡子树：指离插入结点最近且以平衡因子的绝对值大于1的结点作为根的子树。
插入操作：假设由于在二叉排序树上插入结点而失去平衡的最小子树根结点的指针为a，也就是说，a所指结点是离插入结点最近且平衡因子的绝对值超过1的祖先结点，那么，失去平衡后进行调整的规律可归结为以下四种情况：
-
LL型单向右旋平衡处理；
LL型单向右旋平衡处理
-
RR型单向左旋平衡处理；
RR型单向左旋平衡处理
-
LR型先左后右双向旋转平衡处理；
LR型先左后右双向旋转平衡处理
-
RL型先有后左双向旋转平衡处理。
RL型先有后左双向旋转平衡处理
删除操作：若待删除结点的两个子树都不为空，就用该结点左子树上的中序遍历的最后一个结点（或其右子树上的第一个结点）替换该结点，将情况转化为待删除的结点只有一个子树后再进行处理。当一个结点被删除后，从被删除结点到树根到路径上所有结点的平衡因此都需要更新。
3.B_树
定义：一棵m阶的B_树，或为空树，或为满足下列特性的m叉树：
- 树中每个结点最多有
m棵子树； - 若根结点不是叶子结点，则最少有两棵子树；
- 除根之外的所有非终端结点最少有
m/2（向上取整）棵子树； - 所有的非终端结点中包含下列数据信息：
(n,A0,A1,...,Kn,An)，其中，Ki(I=1,2,...,n)为关键字，且Ki<Ki+1(I=1,2,...,n-1)；
Ai(i=0,1,...,n)为指向子树根结点的指针，且指针Ai-1所指子树中所有结点的关键字均小于Ki(I=1,2,...,n)，An所指子树中所有结点的关键字均大于Kn，n为结点中关键字的个数。
- 所有的叶子结点都出现在同一层次上，并且不带信息。
查找过程：首先在根结点所包含的关键字中查找给定的关键字，若找到则成功返回；否则确定待查找的关键字所在地子树并继续进行查找，直到查找成功或查找失败为止。
插入操作：插入一个关键字，不是在树中增加一个叶子结点，而是首先在低层的某个非终端结点中添加一个关键字，若该结点中关键字的个数不超过m-1，则完成插入；否则，要进行结点的“分裂”处理。分裂，就是把结点中处于中间位置上的关键字取出来插入到其父结点中，并以该关键字为分界线，把原结点分成两个结点。分裂的过程可能会一直持续到树根。
删除操作：首先找到关键字所在的结点，若该结点在含有信息的最后一层，且其中关键字的数目不少于m/2（向上取整）-1，则完成删除；否则需进行结点的“合并”运算。若待删除的关键字所在的结点不在含有信息的最后一层，则将该关键字用其在B_树中的后继替代，然后删除其后继元素，即将需要处理的情况统一转化为在含有信息的最后一层再进行删除运算。
（四）哈希表
1.哈希表的定义
哈希表通过计算一个以记录的关键字为自变量的函数（哈希函数）来得到该记录的存储地址。
在进行查找操作时，用同一哈希函数计算得到待查记录的存储地址，然后到相应的存储单元中去获得有关信息在判定是否查找成功。
定义：根据设定的哈希函数和处理冲突的方法，将一组关键字映射到一个有限的连续的地址集上，并以关键字在地址集中的“像”作为记录在表中的存储位置，这种表称为哈希表，这一映射过程称为哈希造表或散列，所得的存储位置称为哈希地址或散列地址。对于某个哈希函数和两个关键字，如果关键字不相等，而哈希函数值相等，则称为冲突。具有相同哈希函数值的关键字对该哈希函数来说称为同义词。
2.哈希函数的构造方法
常用的哈希函数构造方法有直接定址法、数字分析法、平方取中法、折叠法、随机数法、除留余数法等。
对于哈希函数的构造，应解决好两个主要问题：
- 哈希函数应是一个压缩映像函数，它应具有较大的压缩性，以节省存储空间；
- 哈希函数应具有较好的散列性，虽然冲突是不可避免的，但应尽量减少。
3.处理冲突的方法
解决冲突的关键就是为出现冲突的关键字找到另一个“空”的哈希地址。
常见的处理冲突的方法有以下几种：
- 开放定址法
- 链地址法
- 再哈希法
- 建立一个公共溢出区
4.哈希表的查找
在查找操作时，用与存入元素时相同的哈希函数和冲突处理方法计算得到待查记录的存储地址，然后到相应的存储单元获得有关信息再判定查找是否成功。
特点：
- 虽然哈希表在关键字与记录的存储位置之间建立了直接映像，但由于“冲突”的产生，使得哈希表的查找过程仍然是一个给定值和关键字进行比较的过程。因此，仍需要以平均查找长度衡量哈希表的查找效率。
- 在查找过程中需要和给定值进行比较的关键字的个数取决于下列三个因素：哈希函数、处理冲突的方法、哈希表的填装因子。
