数据查找思维脑图思维导图
折半查找，分块查找，顺序查找等内容讲解
树图思维导图提供 数据查找思维脑图 在线思维导图免费制作，点击“编辑”按钮，可对 数据查找思维脑图 进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：b78a2e7eb278526a8dc004b55ffcf1b8
思维导图大纲
查找思维导图模板大纲
查找基本概念
查找表
用于查找的数据结构，由同一类型数据元素组成
关键字
数据元素中唯一标识该元素的某个数据项的值，使用基于关键字的查找，结果应该是唯一的
常见操作
静态查找表
只需要查找
动态查找表
既要查找
又要插入删除
评价指标
平均查找长度ASL
通常考虑查找成功和失败两种情况下的ASL
公式
折半查找
适用范围
有序顺序表
思想、代码
折半查找三种代码形式不会写你可以去死了
判定树
构造
二叉排序树
一定满足：右子树结点数 - 左子树结点数 = 0 or 1
当然了，如果你是⌈(low+high)/2⌉，就是左比右多
特性
平衡的二叉排序树
只有最下面一层不满，n+1个空链域（失败节点）
树高 = ⌈log(n+1)⌉ or ⌊logn⌋ + 1
树高也是折半查找（不）成功比较次数最多值
折半查找的判定树对每棵子树都满足左子树（结点数） - 右子树 = 0 or 1 或者是 右子树 - 左子树 = 0 or 1，只能满足一种！
时间复杂度O(logn)
分块查找
又称索引顺序查找，满足块内无序、块间有序
算法思想
索引表中记录每个分块的最大关键字、分块的区间
先查索引表，再对分块内顺序查找
分块查找表
ASL
ASL = 查索引表长度 + 查分块内长度
设n个记录，均匀分成b块，每块s个记录
顺序查索引表
ASL = (b+1)/2 + (s+1)/2
当s=根号下n时，ASLmin = 根号下n + 1
折半查找索引表
ASL = ⌈log(b+1)⌉ +(s+1)/2
折半查找索引表不包含目标关键字时，最终必有low > high，在low分块中查找
特点
查动态查找表效率高
如果是动态查找表，可以使用链表形式
顺序查找
算法实现
从头到尾或从尾到头一个一个查
适用于顺序表、链表，有序无序都可以
三行代码
也可在0号位置存放哨兵，从尾到头查
优点：不用判断下标是否越界
效率分析
ASL成功 = (1+2+……+n) / n =（n+1）/2
ASL失败 = n+1
如果ASL成功和ASL失败可能相同，则ASL等于二者相加/2 = 3(n+1)/4
时间复杂度O(n)
优化
有序
优点：ASL失败更低
查找判定树
ASL及计算
n+1个失败节点 ： n+1种查找失败情况
失败节点查找长度 = 父节点所在层数
n个成功结点查找长度 = 自身所在层数
各关键字被查概率不等
按概率降序排列
ASL成功更低
相关思维导图模板
树图思维导图提供 地热勘查技术思维脑图 在线思维导图免费制作，点击“编辑”按钮，可对 地热勘查技术思维脑图 进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：40766191388459a07ce8e9efe75edc71
树图思维导图提供 木炭的制取思维脑图 在线思维导图免费制作，点击“编辑”按钮，可对 木炭的制取思维脑图 进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：7715ddf3610acba40dd05386a789a966
沪公网安备 31011502019485号
上海工商