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