数据结构思维导图--查找.pdf
需积分: 14 23 浏览量
2022-08-21
20:09:52
上传
评论
收藏 1.04MB PDF 举报
查找
基本概念
静态
不修改删除表元素，
顺序查找、折半查找、散列查找
动态
动态插入或删除的查找表叫动态查找表
二叉排序树的查找（二叉平衡树、b树）、散列查找
平均查找长度ASL
线性结构
顺序查找
一般线性
ASL(成功)=1+2+3+...+n=(n+1)/2
ASL(不成功)=n+1
缺点：n较大时，平均查找长度较大，效率低；
优点：对数据元素的存储没要求，链式顺序都可；对
有序性业务要求；
链表只能进行顺序查找；
逻辑
逻辑：0号位存放关键字信息，称哨兵，从后往前查
找元素，不必判断数组越界。查找失败return 0号
位；
代码
typedef struct{
ElemType *elem;//泛型定义数组，需要动态分配存
储空间，0号位不存放任何元素，
int TableLen;
}SSTable;//定义查找表的数据结构
int Search_Seq(SSTable ST,ELemType key){
ST.elem[0]=key;//关键字的值赋给哨兵
for(i=ST.TableLen;ST.elem[i]!=key;--i);//从后往
前遍历查找
return i;//跳出循环后的i值
}
有序表
ASL(成功)=(n+1)/2
ASL(失败)=(1+2+...+n+n)/(n+1)=n/2+n/(n+1)
折半查找(二分查找)
ASL(成功)=(1*1+2*2+...+h*2^(h-1))=log2(n+1)-1,
ASL判定树是一颗平衡二叉树，需要具体计算成功和
失败ASL
逻辑
有序的顺序表。关键字与表中间元素比较，相等返
回，不等判断大小与前半部分还是后半部分的中间元
素再次比较，重复直到查找成功或失败。
代码
int Binary_Search(SeqList L,ElemType key){//序
列L和关键字
int low=0,high=L.TableLen-1,mid;
while(low<=high){
mid=(low+high)/2;
if(L.elem[mid]==key){
return mid;//查找成功
}else if(L.elem[mid]>key){
high=mid-1;//前半部分
}else{
low=mid+1;//后半部分
}
}
return -1;
}
分块查找(索引顺序查找)
逻辑：查找表分为n个子块，块内无序，子块之间有
序，建立有序的索引表，存放每个子块的最大关键字
和子块起始位置；①索引表中查询所在的块，顺序/
折半查找②块内顺序查找
ASL(成功)=索引的ASL+块内查找表的ASL
树形结构
二叉排序树(二叉查找树)BST
性质：左结点<根结点<右结点，中序遍历得到递增序
列。子树也是二叉排序树
插入
逻辑
树空直接插入，不空与结点进行比较，比结点大右
走，比结点小左走。插入的一定是叶子结点且是查找
失败路径上最后一个结点的左孩子或右孩子。
代码
//递归插入新结点
int BST_Insert(BiTree &T,KeyType k){
if(T==NULL){//子树为空。插入结点。
T=(BiTree)malloc(sizeof(BSTNode));
T->data=k;
T->lchild=T->rchild=NULL;
return 1;
}else if(k==T->data){
return 0;
}else if(k<T->data){//左子树
return BST_Insert(T->lchild,k);
}else if(k>T->data){//右子树
return BST_Insert(T->rchild,k);
}
}
查找
//非递归查找
BSTNode *BST_Search(BiTree T,ElemType key){
while(T!=NULL&&key!=T->data){//不为空且根节
点也不是
if(key<T->data){//继续左找
T=T->lchild;
}else{
T=T->rchild;//继续右找
}
}
//T为NULL或者T的根节点就是关键字
return T;
}
删除
①删除的是叶子结点，直接删除
②删除的结点有左子树或者右子树，直接把子树上移
到该位置
③删除的结点两个子树都不为空，找右子树的中序遍
历的第一个结点，先把此节点移到此位置，右子树相
当于又删除了一个结点，按照步骤123再次进行删除
操作即可。
查找效率
取决于树的形状，与二分查找类似，可能是平衡二叉
树也可能是单支树。
不同
当有序表是静态查找表时，存储结构是顺序表，使用
二分查找；是动态查找表时，存储结构是二叉排序
树，用二叉排序查找。
顺序表使用二分查找时，如有修改结点操作，时间复
杂度O(n);使用二叉排序时，只需移动删除指针，时
间复杂度为O(log2(n));
平衡二叉树AVL
平衡因子 左子树高度减去右子树高度
定义
为提高二叉排序树的性能，左右子树高度差最多为
1，
插入
①找到距离插入结点最近的平衡因子不是-1，1，0的
结点，以它为根结点的子树为最小不平衡子树，
②LL(A的左子树B的左子树插入新结点)。A平衡因子
变为2，将A作为B的右子树，原B的右子树挂到A的左
子树上。
③RR(A的右子树B的右子树插入新结点)。A平衡因子
变为-2，将A作为B的左子树，原B的左子树挂到A的
右子树上。
④LR(A的左子树B的右子树C插入新结点)。A平衡因
子变为2，B修改为C的左子树，原C的左子树为B的
右子树，将A修改为C的右子树，原C的右子树为A的
左子树。
⑤RL(A的右子树B的左子树C插入新结点)。A平衡因
子为-2，B修改为C的右子树，原C的右子树为B的左
子树，A修改为C的左子树，原C的左子树为A的右子
树。
总结：最小不平衡子树找到之后，看子树根结点往下
不到三层的结点的平衡因子，两侧树高差距大，则把
根结点往左下右下移动，哪边矮补哪边，相当于扒了
树状结构的顶层单侧的皮下移；中间和两侧的树高相
比差距大，则把根结点往下移动之后，去除根结点之
后的左或右子树，再次把左右子树下移和根结点不同
的方向，相当于再扒了树状结构顶层两侧的皮下移。
删除
按照二叉排序树的方式先删除，从底层向上调整平衡
二叉树的树高。
B树、B+树
B-多路平衡查找树
最大的分支数为b树的阶，
特点
平衡因子都是0的多路平衡查找树
每个结点最多有m个分支，最多有m-1个关键字。
根结点如果不为空则至少有两个子树
非根结点至少有[m/2]（向上取整）个分支
关键字与分支有序
所有叶子结点都在最底层，不带任何信息，可以视为
空
总关键字为n，叶子结点为n+1，叶子结点相当于查
找不成功，即n个关键字排序的缝隙有n+1个；
操作
树高
不包含不带信息的叶子节点，即有关键字的结点高
度。
一、树高h尽量小，即分支m越多，则总关键字n越
多，关系为：n<=(m-1)*(1+m+m^2+...+m^(h-1))=
m^h-1，又得出树高最矮时：logm(n+1)<=h。
二、树高h尽量大，即分支数越小，每个结点的关键
字尽量少：第一层至少一个根结点，第二次至少两
个（根结点至少两个子树），第三层开始至少2*[m/
2](向上取整)个结点。第h+1即叶子结点处至少有2*[
m/2]^(h-1)（向上取整）个结点，叶子结点数为n+
1，则n+1>=2*[m/2]^(h-1)（向上取整），则h<=
log[m/2]((n+1)/2)+1（向上取整）
查找
①从b树中找结点②结点中找关键字
①是在磁盘中进行，用二叉查找树的思路查找结点②
读取结点信息到内存中，用顺序or折半查找
插入
定位：先查找到关键字所在位置，即最底层的非叶子
结点，
插入：如果关键字个数再插入后满足([m/2]-1~~m-
1)，可以直接插入，否则关键字个数过多需要分裂
成，取[m/2]（向上取整）位置的关键字向上插入（
向上插入过程中如果关键字个数过多，重读分裂过
程），左右形成两个新结点。
删除
要使删除后关键字满足[m/2]-1（向上取整）
①当删除的关键字在终端结点，即最底层的关键字。
兄弟结点够借，需要把父结点的关键字下移一位，则
取兄弟关键字上移，父子换位法；
兄弟结点不够借，父结点关键字下移，与兄弟结点合
并；
B+的基本概念
① 每个分支结点最多有m个子树，最少有[m/2]（向
上取整）个子树，关键字与子树数量一致，
②非叶根结点至少有2个关键字和子树
③叶子结点存储关键字记录存储地址，每个叶子结点
由pnext指针链接起来，有序。
④所有分支结点只存储各个子树对应的指针和最大关
键字。
对比 差异
一、b树中n个关键字有n+1个子树，b+树中n个关键
字有n个子树。
二、B树中结点关键字的范围[m/2]-1~~m-1,根结
点（1~~m-1）；b+树中关键字范围[m/2]~~m,根
结点(2~~m)。
三、b+中，所有非叶子结点只保存指向下一个子树
指针和最大关键字是什么，不存储关键字地址，只起
到索引的作用，叶子结点包含所有关键字；b树中，
关键字分布在非最底层叶子结点的所有结点上。
四、同h层的b树和b+树，b+树结点关键字更多，更
加矮胖，同样多的结点元素，b+要更矮。查找效率
要高于b树，b+对于磁盘的io操作更少，相对比于b
树需要中序遍历，b+单链表遍历叶子结点即可。
红黑树(大纲无)
散列结构
散列表
基本概念
线性表和树表关键字与存储地址之间没有确定关系，
分配的，查找效率基于比较的次数。
散列函数：Hash(key)=Addr(可以是数组下标，索引
或者内存地址)。
理想情况，散列查找时间复杂度为O(1)。
构造方法
注意
一、定义域应包含全部关键字，值域依赖散列结构的
大小或地址范围。
二、散列函数计算应尽可能的快和简单。
三、散列结构中关键字应尽量均匀分布在全部地址范
围内，减少冲突的发生。
方法
直接定址法
取关于关键字的线性函数为散列函数。
Hash(key)=a*key+b
适用于关键字分布连续的情况，否则会造成空间的浪
费。
除留余数法
Hash(key)=key%p
最常见最常用的一种。重在p的选取，需要把关键字
尽量等概率的分布在地址空间上。
数字分析法
关键字是r进制数时，r个数出现在关键字的每个位置
上的频率不太相同，如果有几个数码经常出现，分析
数码规律，使关键字均匀的分布在地址空间即可。应
用于已知关键字时，换关键字需要重新构造函数
平方取中法
取关键字平方值的中间几位。位数过大前面补零。取
值随机，和关键字每一位都有关系。
适用于关键字怎么取都不均匀，所以随机一下，或者
为了符合散列地址所需的位数。
所有方法没有优劣之分，之后根据关键字来看合适与
否，目的都是要减少冲突的发生，均匀分布在地址空
间中。
冲突处理
开放定址
定义：空闲地址向同义词开放又向非同义词开放，即
向函数值开放，又向非函数值开放。
线性探测法
Hi(key)=(h(key)+di)%m
m为表长，di取0,1,...,m-1。
散列表未满的话。遍历该散列表总能找到位置，冲突
过多有些随意存放的意思了，查找不便。元素堆积聚
集。
平方探测法
二次探测法
Hi(key)=(h(key)+di)%m
di取0^2,1^2,...,k^2,k<=m/2。m必须为4k+3的素
数。
较好的解决冲突方法，缺点是不能探测全部空间。可
以探测一半的地址空间。避免堆积，因为有平方啊肯
定不挨着。
双散列法
Hi(key)=(h(key)+i*h2(key))%m
i是冲突的次数。i*h2计算增量序列di。
伪随机序列法
Hi(key)=(h(key)+di)%m
di=伪随机数序列。
拉链法
把所有同义词放在一个线性链表里，线性链表由散列
函数确定的唯一地址标识。即hash(key)=函数值，
每个函数值对应一个线性列表。
拉链法适用于经常删除插入的情况
同义词 相同函数值的关键字为同义词
性能分析
步骤
根据Hash(key)=Addr,在hash表中查找对应元素，查
找元素为空，则查找失败。查找元素不为空且等于关
键字，则查找成功，不为空且不相等，转到冲突处
理，处理后继续查找；
多次进行冲突处理的函数得到散列地址进行对比，直
到找到相同位置，冲突处理走了一轮了，就是查找失
败。
ASL衡量散列查找的效率
计算出查找各个关键字需要的比较次数，算出平均查
找长度ASL。具体序列和关键字具体分析。
影响因素
散列函数
处理冲突的方法
装填因子
α=关键字数量n/表长m，α越大，表越满，产生冲突
的可能越大，越难处理。
效率指标
平均查找长度
查找成功
查找失败
查找算法的分析与应用
拓展
题目
一个数组中，一个元素出现的次数大于数组长度的1/
2。找出这个元素。
资源评论
