DS-7-查找
2021-07-27 21:30:22 0 举报AI智能生成
数据结构 第七章 查找 知识点总结
作者其他创作
大纲/内容
散列查找
(HASH查找)
(HASH查找)
通过关键字直接计算出存储地址：哈希函数(4)
H(key)=key%p，设表长为m，p取不大于m的最大质数：除留取余法
H(key)=a*key+b：直接定址法
无冲突，但是有浪费
关键字分布不连续
以数码分布相对均匀的若干位作为散列地址：数字分析法
取关键字平方值的中间几位作为散列地址：平方取中法
注意选取
几位要考
虑表长的
实际需求
几位要考
虑表长的
实际需求
不同关键字通过散列函数映射到同一地址：同义词
通过散列函数确定的位置已经存放了其他元素：冲突
冲突解决
用链表存储同义词：链地址法
用空闲地址既向同义词开放，
又向非同义词开放：开放定址法
m为表长，为增量序列，
i为第i次冲突，H=(H(key)+)%m
又向非同义词开放：开放定址法
m为表长，为增量序列，
i为第i次冲突，H=(H(key)+)%m
冲突就顺延：线性探测法
冲突处理值域可以大于哈希函数值域，但是不超过m
一直顺延直到匹配或为空：查找
直接删除元素会导致查找出现假失败，可以用一个
bool做标记表示逻辑上元素已被删除：逻辑删除
bool做标记表示逻辑上元素已被删除：逻辑删除
造成大量堆积
同义词进行排序可以略微提高查找时的效率
令：平方探测法
只有当m是可以表示为4j+3的素数
才能探测到所有位置
才能探测到所有位置
：伪随机序列法
再散列法
再哈希法
再哈希法
用备用散列函数，逐个计算地址直到不冲突为止
表中记录数/表长：装填因子
越大，冲突越多，性能越差
性能
ASL=1~n：成功
ASL=0~n：失败
NOTE:当位置是指针为空时无需对比关键字，ASL=0
但部分学校标准可能不同。注意参考真题
但部分学校标准可能不同。注意参考真题
空间换时间
B树
多路平衡查找树
多路平衡查找树
构造：m叉树
m称为B树的阶
m称为B树的阶
m叉树中，除了根结点外，任何结点至少有个分叉，即至少要有关键字
数据域data[m-1]（必须有序）+指针域ptr[m]：结点结构
对任何一个结点，其子树的高度必须相同
比AVL树更平衡
若根结点非终端结点(并非叶子结点，叶子结点是查找失败结点)，则根必至少有两棵子树
成员
B树的结点数
n个关键字的B树必然有n+1个叶子结点
n个数将数域分割为n+1个区间
B树高度
最小高度
尽可能填满
最大高度
每个结点分叉尽可能少
根结点2分叉，其他结点
高度不包括叶子结点(失败结点)
方法
查找
查找成功可能发生在非终端结点
插入
直接的元素插入一定发生在终端结点
元素插入过程中的调整引起的元素插入不一定发生在终端结点
目标结点有空
直接插入
目标结点无空
目标结点是根结点
目标结点的中间位置(ceil(m/2))元素不变，
左右元素各形成一组子结点
左右元素各形成一组子结点
目标结点不是根结点
父结点未满
父结点新增元素在两端
目标结点的中间位置元素插入到父结点，
本节点左/右元素形成一个新结点
连接到上述元素左/右侧的分叉
本节点左/右元素形成一个新结点
连接到上述元素左/右侧的分叉
父结点新增元素在中间
目标结点的中间位置元素插入到父结点，
本节点左/右元素形成一个新结点
连接到上述元素左/右侧的分叉
并调整指针的顺序
本节点左/右元素形成一个新结点
连接到上述元素左/右侧的分叉
并调整指针的顺序
父结点满
父结点有父结点
父结点无父结点
新建一个父结点，将父结点中间元素插入其中
其左右元素各形成一个新结点连接之。
目标结点的中间位置元素插入到父结点，
本节点左/右元素形成一个新结点
连接到上述元素左/右侧的分叉
注意调整指针的顺序
其左右元素各形成一个新结点连接之。
目标结点的中间位置元素插入到父结点，
本节点左/右元素形成一个新结点
连接到上述元素左/右侧的分叉
注意调整指针的顺序
删除
非终端结点
使用原来元素的直接前驱/后继替代之
并删除直接前驱/后继
并删除直接前驱/后继
终端结点
删除后结点关键字
直接删除
删除后结点关键字
左右不够借
父结点中对应指针左/右元素拉入该结点
，并删除其关键字。合并左/右结点
，并删除其关键字。合并左/右结点
左/右兄弟元素可以借一个
父结点对应指针左/右关键字拉入该结点，并删除其关键字
结点左/右元素的前驱之前驱/后继之后继顶替父结点中对应的位置
结点左/右元素的前驱之前驱/后继之后继顶替父结点中对应的位置
根结点删除后空
删除根结点
B+树
构造
B+树的叶子结点包含了所有关键字
m阶B+树每个非叶子结点最多有m棵子树
根结点最少两棵子树，其他结点至少有棵子树
结点子树数=关键字数
叶结点结构
全部关键字 : 指向相应记录的ptr
指向下一个叶结点的ptr
索引是多层树结构，每个结点指向子结点中最大的元素
类似分块查找原理
方法
查找
必须走到叶层才能确定查找成功与否
B+树也支持直接对叶结点内的数据顺序查找
vs B树
应用
非叶子结点很小，可以用于在很小的块中包含更多关键字，从而使B+树的阶更大，树高更矮，用于读磁盘加速
基本概念
查找
在数据集合中寻找满足某些条件的数据元素
查找表
用于查找的数据结构，由同一类型的数据元素组成
关键字
数据元素中唯一标识该元素的某个数据项的值。结果应该是唯一的
基本操作
查找
只进行查找的查找表是静态查找表
插入
删除
性能分析
ASL平均查找长度
查找长度需要对比关键字的次数
默认查找每个数据都是等可能的
区分查找成功、查找失败，两者不一样
查找操作的数量级反映了时间复杂度
顺序查找
(线性查找)
(线性查找)
适用于线性表（顺序表、链表）
逐个比对，成功返回，不成功下一个
注意越界问题
性能分析
时间复杂度：O(n)
优化：哨兵法
数据从1号开始存，用0号存储目标元素
倒序查找
成功返回对应index，失败返回0
可以少n次越界判断
性能分析
ASL(成功)：(n+1)/2
ASL(失败)：n+1
ASL(失败)：n+1
优化：对有序表：可以结合数据单调性进行优化
查找判定树
成功结点的SL=结点所在层数
失败结点SL=父结点所在层数
ASL(失败)：n/2+n/(n+1)
优化：被查概率不等：概率降序排列
查找失败时ASL很大
折半查找
(二分查找)
(二分查找)
只使用于有序顺序表
不可用于链表
实现
双指针指向区间始末。初始时区间为0~len-1
mid=floor((low+high)/2)
while low<=high
比较mid指针与待查数据
成功？退出
不成功，减半区间
元素在mid哪一侧，就将另一侧指针替换为
替换为mid+1/mid-1中与元素同侧的一个，
并重新计算mid
替换为mid+1/mid-1中与元素同侧的一个，
并重新计算mid
NOTE：*mid已经对比过，不要再纳入区间
NOTE：*low/*high仍要纳入区间
NOTE: low=high也可能导致该元素未被查找，故low>high时停止
查找判定树
性质
奇数元素：左右子树元素相等
偶数元素：左子树比右子树少一个元素
必是平衡二叉树
树高与查找性能直接相关
树高不考虑失败结点
其实是二叉排序树
例
1
2
3
4
5(失败)
如图：ASL成功：
如图：ASL失败：
NOTE：一个失败区间结点看做一个元素
失败结点=成功结点的空链域数
性能
时间复杂度
分块查找
查找表分为不同的区间，用索引表保存每个分块的最大关键字和分块的存储区间
实现“块内无序，块间有序”
实现“块内无序，块间有序”
索引表中用顺序或折半查找当*mid>key，
在块内顺序查找，超出分块范围则认为失败
索引表中low指针为0则直接失败
在块内顺序查找，超出分块范围则认为失败
索引表中low指针为0则直接失败
NOTE：直接根据关键字在索引表中查找可能失败，应改变成功条件
边界条件改为：若low>high，仍要在*low分块中进行查找
边界条件改为：若low>high，仍要在*low分块中进行查找
ASL
成功:
失败
TIP:一般不怎么考
有规律的情况下的效率分析：
顺序查找Index：
考虑n=sb，,时
考虑n=sb，,时
折半查找Index：
改进：动态查找表：链式存储，方便增删改
职业：暂无
0 条评论
下一页
