亿图脑图MindMaster查找
导图社区 查找
- 相似推荐
- 大纲
查找
基本概念
查找
动态查找表
动态查找表
关键字
唯一标志数据元素的关键项
关键字可以唯一地标志一个记录，则称此关键字为主关键字 不同的记录，主关键字不相同，关键字所在的数据项称为主关键码。
查找算法的效率评价
查找成功的ASL
查找失败的ASL
静态查找
顺序查找
算法思想
从表中一端开始往另一端查，值相等，查找成功
算法实现
基本算法
int sequential search(int a[ ],int n, int key) { int i; for(i=1;i<=n;i++) {if(a[i]==key) return i; } return 0; }
局限，每一次查找结束都要判断i是否越界。
哨兵顺序法
int sequcesearch(int a[ ] ,int key,int n) { int i; a[0]=key; i=n; while(a[i]!=key) i--; return i; //返回0则说明查找失败 }
改善了查找过程中每一次比较厚都要判断是否越界，总数据多的时候提高效率
时间复杂度O(n)
ASL
查找成功
成功asl

查找失败
n+1
优化：有序表的顺序查找
元素查找概率相同，改善查找失败的ASL

为什么分母变成n+1
n个元素有n个查找不成功的情况
为什么还要加个n
最后一层情况有两种情况
元素查找概率不相同，改善查找成功的ASL
查找失败，就无优化效果
ASL=p*层数
折半查找
前提：线性表元素有序！
实现代码
int brinary search( int a[ ],int n,int key)//a[ ]的元素从a[1]开始存储 {int mid,low,high; low=1; high=n; while(low<=high) // { mid=(low+high)/2; //这里mid是向下取整 if(a[mid]>key) low=mid+1; else if(a[mid]<key) high=mid-1; else return mid; //可以在这里加一个计数器，看查找了几次 }//while return 0;//查找失败 }
时间复杂度
n对2取对数，向下取整。然后这个整体+1
logn
并不意味着折半查找在任何时候都比顺序查找快，考虑查找的元素就是第一个元素
2016年真题考的就是什么情况下顺序查找比折半查找更快
画折半查找子树
很容易误解这是一颗排序二叉树 但折半查找的判定树是一棵平衡二叉树。 由折半查找的定义，每次把一个数组从中间结点分割时，总是把数组分为结点数相差不超过1的两个子数组，从而使判定树的两棵子树的高度差绝对值不超过1，对应平衡二叉树
通过根节点看向下取整还是向上取整
向上取整

左边结点比右边多
向下取整

右边结点比左边多
判断符不符合向上取整和向下取整的统一性
向上取整，即让较大的数优先被查到，或者说处于树的更高层，地位更高 向下取整，让较小的数优先被查到，处于树的更高层
左右结点一样多的时候，有分叉直接排除
不合理情况
1

2

3

合理情况
1统一向上取整

2向下取整

左右结点不一样多，则整个树取整方式要统一
合理情况

左边节点多，向上取整
整棵树都是向上取整的形状
不合理情况

右边结点多，向下取整
整棵树却是向下取整的形状
迭代就是AVL的插入
ASL
必须画出判定树才能求解
局限
顺序存储作用，链式存储不作用
静态的已排好的有序表比较适合，但是动态的维持有序的成本有点高
补充
插值查找
插值公式
不适用于数据分布不均匀的数组
斐波那契数列查找
分块查找
分块
数据集分成若干块
块内无序
块间有序
每块有一个索引
最大关键码
块中记录的个数
用于指向首快数据元素的指针
查找
1先找关键字所在的块
很容易通过折半查找
2.再找块间元素
顺序查找
查找长度
分为索引查找和块内查找的平均查找长度之和

链式存储

方便删除和插入
无法进行折半查找
动态查找表
二叉排序树
定义
左子树值<根节点<右子树结点值
中序遍历可以得到一个递增的序列
左右子树也是一个二叉排序树
查找
BstNode *BST-search(BiTree T,ElemType key) { while(T!=Null&&key!=T->data) { if(key>T->data) T=T->rchild; else T=T->Lchild;} return T; }
查找序列

只用标出拐点的数值，且是从右向左的拐点的值，然后从上到下比较，满足大到小即可
查找某个数，查找次数等于这个结点所在的深度
插入
插入的结点只能是叶子结点
是查找失败时访问的最后一个结点的左（右）孩子
插入顺序不同，得到不同的二叉树
什么时候相同
第二层相同
删除
不能全部直接删除，先把被删除结点从存储二叉排序树的链表中摘下，将因删除结点而断开的二叉链表重新连接，同时保证二叉树的性质
一般做法：还原中序序列，找到被删除的结点前后两个结点，连接起来并且还原回排序二叉树
可以利用BST性质简化的情况
被删除的结点是叶子结点
直接删除
被删除的结点只有右子树
用右子树补
被删除的结点只有左子树
用左子树补
删除后某结点后又插入，序列不变，但是树的结构发生变化，不再是原来的树
中序序列对应的树不唯一
查找效率分析
比平衡二叉树慢
与二分查找的比较
二分查找对应的判断树是平衡二叉树，一般比排序树查找效率高
二分查找对应的顺序存储结构，而平衡二叉树增删比二分查找效率高
比单支树快
平衡二叉树
与二叉排序树的关系
是一种特殊的二叉排序树
左右子树高度差不超过1
优化，限制排序树高度增长过快
定义
排序树基本且满足左右高度差不超过1
一定是折半查找的判定树
平衡树的插入
插入思想，每插入一个结点都要考虑这个操作是否导致不平衡
不平衡，则调整结点所在的最小不平衡子树
调整的对象是不包括插入结点在内的最小不平衡子树
沿着插入路径找到中间大的数作为新的根节点，调整树
调整完树以后再插入新值
可能会有断链和新的连接关系
调整的本质
调整只是让插入后的树满足中序遍历后递增
平衡二叉树的删除
与调整的本质类似
查找
公式Nh=Nh-1+Nh-2+1

这是深度为h的AVL树含有的最少结点数
查找过程中，与key的比较次数不超过树的深度
应用
解决给定结点数的平衡二叉树的查找所需的最多比较次数Nh
基本算数题
含有20个结点的AVL至少有（）个结点
具有5层结点的AVL至少有（）个结点
平衡二叉树的构建
要拒绝一个一个插入然后调整，直接通过中序遍历从上往下构造树（选填）

大题要求依次构建只能迭代
B/B+树
B树
m阶b树
b树中所有结点孩子个数最大的那个值称为b树的阶
阶是被子树的个数，例如5阶b树一定是区域被四个点化成了五个区域
B树的性质
1.结点的孩子个数等于关键字个数+1
和B树是几阶的无关
结点的孩子是被划分的区间
关键字是点坐标
2.根结点
至少两棵子树，如果有关键字
3.分支节点
子树数目
最少：m/2向上取整
最多：m
关键字个数
最少：m/2向上取整-1
最多：m-1
4.所有叶结点都在一层，表示查找失败，不算入树的高度
5.B树的高度
查找效率与B树的高度密切相关 b树中的大部分操作所需的磁盘存储次数与b树的高度成正比
需要明确地信息，关键字的个数n，b树的阶数m，和所求的高度h
最小高度
类似于满二叉树
最大高度
第一层一个关键字
第二层m/2课子树
第三层2*（m/2）课子树
B树的查找
在B树中查找结点
在磁盘中进行
在结点中查找关键字
在内存中进行
找到目标结点后，将结点信息读入内存，再在内存中才有顺序查找法和折半查找
B树的插入|构建

1.新关键字插入的结点都是最后一层
2.当结点中关键字数小于m-1时，直接插入该结点
3，需要向上溢出，必然导致局部的分裂
因为上层的关键字增多，子树增多
若3,中父节点也超出上限，则对父节点进行分裂操作，传递到根节点，
在根节点发生分裂的情况下，树高+1
B树的删除
1. 删除的本质
关键字的删除导致的是权利的下降，变局过大时，会有权利的上升
2. 删除能简化
删除的节点是叶子结点
叶子结点中关键字数量大于1
直接删
叶子结点只有一个关键字
双亲结点和左右兄弟结点中关键字都大于1
从中借
删完后不能借
只能让父节点关建字-1，让最小或者最大那个下降合并
！！！删完之后导致不平衡

整颗b树整体结构都要改变
1.将中序遍历写出来
2.可以直接划掉底层的结构，因为删除不可能导致叶子结点上移
4.选择对整体改变小的关键字作为根节点
删除的结点是中间结点
找中序前驱（后驱）
替换被删除的点
删除的结点时跟结点
1.将中序遍历写出来
2.可以直接划掉底层的结构，确定根节点
3，左右子树分别找可能的根节点，划分范围
212,112，211,
23,24
B树的局限和与B+树的发展
B树不方便遍历，需要频繁切换上下级，而切换上下级的实质是切换硬盘的页面和将读取，开销很大
B+树应该能满足方便地遍历B树中的元素，适合带有范围的查找
B+树
+的是多层索引和head指针遍历叶子结点
1.关键字和孩子是一一对应的关系
孩子通常是活动记录
n颗子树有n个关键字
2.叶子结点有全部关键字的信息，并且在最后一层有序排列
还包括指向记录活动的指针，相邻叶结点还有指针链接起来
3.分支结点仅起索引作用，每个索引项只含有指向对应子树的指针和此子树的最大关键字，但不包含关键字指向的活动记录地址
会导致B+树中有重复的关键字
散列表（哈希表）
避免了动态查找表和静态查找表相当多的比较 但不是完全避免
概念
散列函数
散列表地址和关键字值key的映射
冲突
不同的关键字经过一个散列函数映射到同一个地址，会发生地址冲突
散列函数应该减少冲突
设计好处理冲突的办法
同义词
发生冲突的不同关键字
散列函数
指定原则
类别
直接定址法
取关键字的某个线性地址值为散列地址
不会产生冲突
适合关键字的分布基本连续的情况
分布不连续会导致空位较多，空间浪费
除留余数法
H(key)=key%p
p应该为最接近散列表表长m的一个质数
会形成环
数字分析法
平方去中法
处理冲突的方法
任何散列函数都不能绝对地避免冲突
开放定址法
指可存放新表项的空闲地址既可以向它的同义词表项开放，也可以向非同义词表项开放 Hi=（H（key)+di)%m
di是递增序列，di的不同导致了处理方法的不同
线性探测法
di取0,1,2,...,k
会导致聚集（堆积）问题
多个不同哈希函数值的记录争抢同一地址
探测表尾元素的时候下一个探测地址是表头首地址0，直到找到空位查找失败
查找到空闲地址或者查遍全表回到原处，查找失败
平方探测法
di=k的平方
散列表长度必须是4k+3的素数
可以避免“堆积问题”
不能探索所有单元
至少一半单元
双散列法
di=hash2（key）
伪随机序列法
不能随便物理删除表中元素，会阻断其他具有相同的散列地址的元素的查找
逻辑删除，但是副作用明显
散列表看起来很满，但是很多地方未利用
拉链法
为了避免非同义词发生冲突
适用于经常发生删除和插入的情况
散列表的查找
查找失败
理解
查找失败时针对mod n而言的，所以查找失败的ASL分母一定是n，他说的是0-n-1的每一个位置都可以遇到查找失败的情况，所以上面就是每一个位置到最近空位（查找失败）的距离之和
情况
1
[0,n-1]内有空格
表内循环找即可
2
[0，n-1]无空格
此时散列表长度m必然大于n，找离n最近的空格即可
3
[0，n-1]之外有值
不参与查找的计算，只对空格位置有影响
查找成功
理解
查找成功是针对散列表中已经有的关键字而言的，它的ASL分子是每个关键字的查找次数之和，分母是散列表中已经有的关键字的个数；
查找效率
散列函数，处理冲突的方法和装填因子
装填因子
衡量表的装满程度， 越满，越容易发生冲突 越近，越