第七章 查找技术
第七章 查找技术
一、基本术语
在问题中查找数据元素时被称为记录；通过标识一个记录中的某个数据项来确定其关键码；具有唯一标识一个记录的关键码被称为主关键码
2.查找：在具有同类型记录的集合中找出给定条件的记录
3.静态查找：不涉及插入和删除操作的查找
4.动态查找：设计插入和删除操作的查找
5.查找结构：专门为查找操作设计的数据结构
(1)线性表：适用静态查找，主要采用顺序查找技术、折半查找技术
(2)树表：适用动态查找，主要采用二叉排序树查找技术
(3)散列表：适用静态查找和动态查找，主要采用散列技术
6.查找算法的时间性能：用平均查找长度来度量(关键码比较次数的期望)
在查找成功的场景中, 平均查找长度等于涉及该节点的关键码比较次数, 并且等于所有节点的关键码比较次数总和除以节点的数量
在进行查找操作而未找到目标时，在算法中定义了平均查找长度（ASL）。ASL等于因查找不成功而导致的关键码比较次数与所有外部节点上进行的关键字比较总和的比例。
二、线性表的查找技术
1.顺序查找：应用于顺序存储和链式存储，平均查找长度为O(n)
二分查找法要求待查元素按关键字有序排列且以顺序方式存储
3.折半查找判定树
判定树表示折半查找过程的二叉树；每个节点对应一个记录；而节点值则指示该记录在其列表中的具体位置。
(2)判定树的构造方法：
第一步：确定结点值的区间：若有序表长度为n，则结点值的区间为[1,n]
第二步：确定根结点的值：mid=(1+n)/2；
第三步：确定左子树的区间：[1,mid-1]，和右子树的区间：[mid+1,n]；
第四步：确定左、右子树根结点的值：左mid=(1+mid-1)/2；右mid=(mid+1+n)/2；返回第三步
(3)判定树的性质：
①判定树是二叉排序树，且结点个数相同的判定树一样
②任意两个叶子所处层数最多差1，n个结点的判定树的深度为[long2n]+1
(4)判定树的平均查找长度
结点的比较次数=该结点所在层数
外节点：在各节点的空指针字段中引入一个虚拟存在的节点，在此操作下会导致长度为n的一个有序表生成总共n+1个外部节点
外结点的比较次数=外结点的根结点所在层数
①查找成功时的平均查找长度=所有结点的比较次数之和/有序表的长度
②查找失败时的平均查找长度=所有外结点的比较次数之和/外结点的个数
4.示例：详细说明如何绘制长度为10个元素的折半查找判定树，并对等概率情况下成功与失败情况下的平均查找长度进行分析
三、树表的查找技术
1.二叉排序树：左子树结点值比根结点小，右子树结点值比根结点大
2.二叉排序树的构造方法：
第一步：以空树为基础建立一棵二叉排序树，并将第一个关键码放置于根节点位置。
第二步：依次插入结点，满足左比根小、右比根大的规则
3.二叉排序树中删除结点的方法：
第一步：确定一个比待删除结点大或小的数值位置s
第二步：用结点s替换待删除结点
第三步：删除结点s
4.平衡二叉树
(1)平衡二叉树：二叉排序树中所有结点的左右子树深度最多相差1
结点的平衡因子：该结点的左子树深度-右子树深度
最小失衡子树：以其为根的子树，并其到新插入的节点的距离最近者。
(2)构造平衡二叉树的方法
第一步：插入一个结点，计算此时所有结点的平衡因子，
若不存在绝对值大于1，则没有失去平衡，返回第一步；
若发现某结点的平衡因子绝对值大于1，进入第二步；
第二步：确定最小不平衡子树的根节点A之后，在分析新插入节点与该根节点A之间的平衡关系的基础上作出相应的平衡修正
当新增节点位于某个节点A的左孩子的左子树上时，在这种情况下需要对最小不平衡子树进行一次顺时针方向旋转以恢复平衡状态，并相应地重新配置该子树的支撑点以确保整体结构平衡
RR型：新增节点位于A节点右孩子右侧的子树中----将最小不平衡子树作为支干进行顺时针方向上的调整，并优化其支撑结构
LR型：当新插入节点位于节点A的左子节点右子树位置时，则需依次执行以下操作：首先对节点A的左子节点进行逆时针方向旋转以重新定位其支撑结构；接着对包含该节点的最小不平衡子树进行顺时针方向旋转以完成平衡处理
新插入节点位于A节点右子树左子树的位置----随后进行一次顺时针方向的旋转操作以平衡结构；接着对最小不平衡子树执行逆时针方向的旋转以恢复平衡状态
第三步：计算此时所有结点的平衡因子，
若不存在绝对值大于1，则调整成功，返回第一步；
若发现某结点的平衡因子绝对值大于1，返回第二步，继续调整；
四、散列表的查找技术
-
哈希表是一种用于实现快速数据访问的数据结构，在其核心思想中，在数据存储的位置与键值之间建立了一一对应的关系函数h（·），从而实现了对任意键值都可以直接定位到其对应的存储位置
-
该函数h（·）的作用就是将一系列可能存在的所有键值映射到一组固定大小的目标地址集合中
-
当需要根据某个特定的关键字来访问相应数据时（即输入参数为某个特定的关键字），系统会利用h（·）函数计算出该关键字对应的地址
-
这种基于计算的方法被称为哈希方法或哈希查找技巧
-
散列表：利用散列技术将数据存储在一组有序的空间区域内，这一组有序的空间区域被称为哈希表
-
散列函数：将关键码合理分配到散列表中的相应位置所使用的计算方法称为哈希算法（或称开 addressing），这些关键码对应的存储位置则被称作哈希地址（或称开放定址法）。
-
散列过程：在数据处理中，哈希表主要作为一种基于查找的数据存储方式，在这种技术下利用哈希函数实现了从一组关键码到对应地址集的一一对应关系
在进行存储操作时，首先利用散列函数计算出记录对应的散列地址；然后按照该散列地址将记录进行存储。
在线查询时，在使用相同的哈希函数确定该记录的位置后进行访问。
- 碰撞：在散列函数计算的结果下，在同一存储位置中可能会出现两个不同的记录被错误地映射的情况，则这种情况被称为碰撞现象；其中这两个不同的记录所具有的关键码则被称为同义词键。
6.散列技术的两个主要问题：散列函数的设计+冲突的处理
7.散列函数的设计
直接定址技术：当已知关键字在存储空间中的分布情况时，并且要求关键字集合规模不大且具有一定的连续性。
(2)取余法：简便且广泛应用的一种散列函数构造方法，在该方法中无需预先掌握关键码的分布情况。
数字分析技术：适合于在已知关键码的分布情况且这些关键码具有多位较为均匀的状态时应用
平方取中法：用于处理未知其分布情况的关键码，并且这些关键码的位数较少的情况
折叠策略：适用于关键码的位长较长且每一位在分布上都不均匀的情况
8.处理冲突的方法
8.1 开放定址法
(1)开散列法：当关键码计算出的散列地址发生冲突时，则依次寻找后续可用的空间。
(2)闭散列表：用开放定址法处理冲突构造的散列表
(3)寻找下一个空散列地址的方法
该方法采用线性探测策略实现冲突解决，在闭散列表中设定总容量为m的情况下（即表长为m），当发生碰撞时通过计算确定下一个可用位置的公式为：Hi=(H(key)+i) mod m。（其中i取值范围为1至m-1）
在二次探测法中：假设闭散列表的大小设为m。当发生碰撞时，计算空散列位置的公式如下所示：Hi=(H(key)+i)%m; 其中i=1,2,…,q²。
采用随机探测法时,假定闭散列表的大小为m.当发生碰撞时,则会通过计算出下一个可用散列位置来实现存储.其具体公式为Hi=(H(key)+i)%m;其中i取值于区间[1, m−1]内的随机整数
8.2 拉链法--不会产生堆积
(1)拉链法：将所有散列地址相同的记录存储在一个单链表中----同义词子表
(2)开散列表：用拉链法处理冲突构造的散列表
9.应用1：使用线性探测策略来解决冲突问题，并构建闭散列表以计算成功查找的平均探测次数
10.应用2：使用二次探测技术来处理冲突，并构建闭散列表以评估成功查找的平均搜索长度
应用3：通过拉链法来处理冲突，在构建开放散列表时计算成功查找的平均搜索长度
12.散列表的装填因子
散列表的装填因子等于其内部元素数量除以其长度，在这种情况下（当值增大时）会产生越高的冲突率；给定装填因子及元素数量即可计算出对应的表长
(2)散列表的平均查找长度是装填因子a的函数
13.开散列表与闭散列表的比较
(1)开散列表：
优点：该系统采用关联式存储技术以实现同义词的高效存储，在避免出现堆积问题的同时支持高效的动态查询功能，并且增删操作的实现较为简单。该系统设计使得平均搜索长度较低，并且无需预先确定数据表的容量。
缺点：附加指针域增加了存储开销
(2)闭散列表:
优点：无须附加指针，存储效率较高，必须事先估计表容量
缺点：易产生堆积现象使得查找效率较低，删除操作需要做标记较麻烦