没有网站可以做百度排名吗,怎么制作网站模板,互联网技术岗位校园招聘,黄页网站介绍前言
本文基础知识部分来自于b站#xff1a;分享笔记的好人儿的思维导图与王道考研课程#xff0c;感谢大佬的开源精神#xff0c;习题来自老师划的重点以及考研真题。此前我尝试了完全使用Python或是结合大语言模型对考研真题进行数据清洗与可视化分析#xff0c;本人技术…前言
本文基础知识部分来自于b站分享笔记的好人儿的思维导图与王道考研课程感谢大佬的开源精神习题来自老师划的重点以及考研真题。此前我尝试了完全使用Python或是结合大语言模型对考研真题进行数据清洗与可视化分析本人技术有限最终数据清洗结果不够理想相关CSDN文章便没有发出。
考研真题待更新 欢迎订阅专栏408直通车 请注意本文中的部分内容来自网络搜集和个人实践如有任何错误请随时向我们提出批评和指正。本文仅供学习和交流使用不涉及任何商业目的。如果因本文内容引发版权或侵权问题请通过私信告知我们我们将立即予以删除。 文章目录 前言第七章 查找查找的基本概念在哪里找什么是查找查找表咋么分类如何评价查找算法查找过程中研究什么 线性表的查找顺序查找线性查找折半查找二分/对分查找小结分块查找小结 比较 树表的查找当表插入、删除操作频繁时为维护表的有序性需要移动很多记录改用动态查找表几种特殊的树二叉排序树 BST小结 平衡二叉树 AVL练习小结删除AVL树删除操作―—例1AVL树删除操作―—例2AVL树删除操作―—例3AVL树删除操作―—例4AVL树删除操作―—例5AVL树删除操作―—例6 小结 红黑树B树小结小结 B树B树与B树的异同 散列表的查找散列表概述散列函数的构造方法冲突解决的方法散列的查找及性能分析 第七章 查找
查找的基本概念
在哪里找
查找表是由同一类型的数据元素或记录构成的集合数据元素之间关系松散应用灵活方便
什么是查找 查找根据给定值在查找表中确定一个其关键字等于给定值的数据元素或记录查找成功/查找不成功 关键字 用来标识一个数据元素或记录的某个数据项的值 主关键字可唯一标识一个记录的关键字 次关键字用以识别若干记录的关键字
查找表咋么分类 静态查找表仅作查询检索操作的查找表 查询某个“特定”数据元素是否在查找表中 检索某个“特定”数据元素的各种属性 动态查找表作插入和删除操作的查找表 在查找表中查找若查询结果不在查找表中则插入一个数据元素 从查找表中删除其查询结果在表中的某个数据元素
如何评价查找算法 平均查找长度ASL n记录个数pi查找第i个记录的概率通常为1/nci找到第i个记录所需的比较次数
查找过程中研究什么
研究查找表的各种组织方法及其查找过程的实施构造查找表时人为添加约束关系并设计与之匹配的查找方法从而提高查找表的查询效率
线性表的查找
顺序查找线性查找 概念 顺序查找顺序表或线性链表表示的静态查找表 表内元素无序 过程 从线性表的一端开始逐个检查关键字是否满足条件 若满足则查找成功返回元素位置 若已经查到表的另一端且还没有找到符合条件的元素则返回查找失败的信息 优化 哨兵 将待查关键字存入表头从后向前比较可免去查找过程中每步都要检查是否查找完毕效率可提高一倍 按查找频率高低存储 若无法测定按概率动态调整记录顺序访问频度域 顺序查找的优化(对有序表) 平均查找长度 成功Pi1/n 失败Pi1/n 折半查找二分/对分查找 概念 每次将待查记录所在区间缩小一半 有序的顺序表 在[low, high]之间找目标关键字将给定key值与表中中间位置mid比较若相等则查找成功 不等则根据mid所指元素与key值大小比较调整low或high缩小边界范围不断重复 若lowhigh则查找失败 判定树 圆形结点为记录值为关键字叶结点表示查找不成功的情况 特性 判定树是平衡的二叉排序树只有最下面一层不满 若查找表有n个关键字则失败结点有n1个 树高h ⌈log2(n1)⌉不包含失败结点 查找成功平均长度 ASL h 时间复杂度O(log2n) 仅适合于顺序存储结构不适合于链式存储结构且关键字有序
小结 分块查找 概念 又称索引顺序查找吸取了顺序查找和折半查找的优点既有动态结构若为动态查找表优先使用链式存储又适用于快速查找 过程 将查找表分为若干子块块内的元素可以无序但块间有序一个块的最大关键字小于下一个块中所有记录的关键字 再建立一个索引表索引表中的每个元素含有各块的最大关键字和各块中第一个元素的地址索引表按关键字排序 查找过程在索引表中确定记录所在块在块内顺序查找 查找成功长度 将长度为n的查找表均匀地分为b块每块有s个记录 ASL Lb对索引表查找的ASL Ls对块内查找的ASL 若块内和索引表都用顺序查找则按顺序查找公式 ASL Lb Ls (b1)/2 (s1)/2 可根据b和s的关系化简若用折半查找则用折半的公式替换h ⌈log2(n1)⌉
小结 比较
以下是按照您的要求创建的四行四列的Markdown表格
查找顺序查找折半查找分块查找ASL最大最小中间表结构有序/无序表有序表分块有序存储结构顺序/线性链表顺序表顺序/线性链表
树表的查找
当表插入、删除操作频繁时为维护表的有序性需要移动很多记录改用动态查找表几种特殊的树
二叉排序树 BST 二叉排序树的定义 特性 左子树结点值若左子树非空 根结点值 右子树结点值若右子树非空 其左右子树本树又各是一棵二叉排序树 性质 中序遍历非空的二叉排序树所得到的数据元素序列是一个按关键字排序的递增有序序列 二叉排序树的查找 从根结点开始沿某分支逐层向下比较的过程若二叉排序树非空先将给定值与根结点关键字比较 若相等则成功 若小于根结点关键字则在左子树上查找若大于根结点关键字则在右子树上查找可递归实现 二叉排序树的插入 过程 若关键字小于根结点值插入左子树 若关键字大于根结点值插入右子树 生成 按关键字序列依次插入 不同插入次序的序列生成不同形态的二叉排序树 二叉排序树的删除 若被删除的结点是叶结点直接删 若结点只有一棵左子树或右子树让子树成为该结点的父结点的子树代替该结点 若结点有左、右两棵子树 以其中序前驱值替换之值替换然后再删除该前驱结点前驱是左子树中最大的结点 也可以用其后继替换之然后再删除后继结点后继是右子树中最小的结点 二叉排序树的查找效率分析 查找成功的平均查找长度ASL (11 22 3*4 4 * 1) / 8 2.625 查找失败的平均查找长度ASL (37 42) / 9 3.22 查找效率主要取决于树的高度 若二叉排序树为平衡二叉树平均执行时间为O(log2n) 若二叉排序树只有左/右孩子单支树平均查找时间为O(n)
小结 平衡二叉树 AVL 概念 特性 是二叉排序树具有二叉排序树性质 左子树与右子树的高度之差的绝对值小于等于1 左子树和右子树也是平衡二叉排序树 平衡因子结点左子树的高度-结点右子树的高度 故平衡二叉树中平衡因子只能是 -1、01 平衡调整 当平衡二叉树插入删除一个结点时 首先检查其插入路径上的结点是否因此次操作导致不平衡 若不止一个失衡结点时从最小失衡子树的根结点开始平衡直到所有结点都满足平衡二叉树特性 LL 右单旋 RR 左单旋 LR 先左后右双旋转 RL 先右后左双旋转 如果记不住王道四种情况遵循以下两个原则代入到前四个情况理解一下可能就懂了 原则一降低高度 原则二保持二叉排序树性质 调整最小不平衡子树 平均查找长度O(log2n)
练习 小结 删除 AVL树删除操作―—例1 AVL树删除操作―—例2 AVL树删除操作―—例3 AVL树删除操作―—例4 AVL树删除操作―—例5 AVL树删除操作―—例6 小结 红黑树 红黑树的概念 定义 红黑树是二叉排序树左子树结点值 根结点值 右子树结点值 根结点是黑色的每个结点不是黑就是红 叶结点外部结点/NULL结点/失败结点均是黑色 不存在两个相邻的红结点即红结点的父结点和孩子结点均是黑色 对每个结点从该结点到任一叶结点的简单路径上所含黑结点的数目相同 口诀 左根右根叶黑不红红黑路同 性质 根到叶结点最长路径不大于最短路径全黑2倍 n个结点高度h2log2(n1) 黑高bh 从某结点出发不包含该结点到达任一空叶结点路径上黑色结点数 结论若根结点黑高为h内部结点数关键字最少有2^h-1个 红黑树的插入删除 https://www.cs.usfca.edu/~galles/visualization/RedBlack.html 红黑树的性能分析
B树 概述 概念 又称多路平衡查找树B树中所有结点的孩子个数的最大值称为B树的阶用m表示 特点 树中每个结点至多有m棵子树至多有m-1个关键字 关键字个数⌈m/2⌉-1nm-1根结点1nm-1 子树个数⌈m/2⌉ n m根结点2 n m 所有的叶结点都出现在同一层次上且不带信息 B树是所有结点的平衡因子均为0的多路平衡查找树 性质 结点的孩子个数 该结点关键字个数 1 对任一结点其所有子树高度都相同 关键字的值子树0关键字1子树1关键字2子树2…类比二叉排序树 左中右 B树的高度磁盘存取次数 - 对任意一颗包含n个关键字、高度为h、阶数为m的B树- h logm (n1)小结 B树的操作 查找 在B树上查找到某个结点后先在有序表中进行查找 若找到则查找成功否则按照对应的指针信息到所指的子树中去查找 查找到叶结点时对应指针为空指针则说明树中没有对应的关键字查找失败 插入 定位利用查找算法找出插入该关键字的最底层中的某个非叶结点 在插入后若结点关键字个数大于等于m则从中间位置⌈m/2⌉将关键字分为两部分 左部分留在原结点、右部分放到新的结点、中间位置⌈m/2⌉的结点插入原结点的父结点 删除 非终端结点关键字 用其直接前驱左子树“最右下”元素或直接后继右子树“最左下”元素替代其位置化为对“终端结点”的删除 终端结点关键字 删除后结点关键字个数未低于下限无需处理 低于下限 右兄弟够借则用当前结点的后继、后继的后继依次顶替空缺 左兄弟够借则用当前结点的前驱、前驱的前驱依次顶替空缺 左右兄弟都不够借需要将父结点内关键字、左右兄弟进行合并合并后导致父结点关键字数量-1可能需要继续合并
小结 B树 m阶B树 每个分支结点最多m棵子树 非叶根结点最少有2棵子树其他每个结点分支⌈m/2⌉ n m 结点的子树与关键字个数相等 所有叶结点包含全部关键字及指向相应记录的指针叶结点中将关键字按大小顺序排序并且相邻叶结点按大小顺序相互链接起来 所有分支结点可视为索引的索引中仅包含它的各个结点即下一级的索引块中关键字的最大值及指向其子结点的指针
B树与B树的异同 差异 m阶B树 关键字个数⌈m/2⌉-1nm-1根结点1nm-1n个关键字n1棵子树结点包含记录信息不支持顺序查找 查找成功可能在任何一层速度不稳定 m阶B树 关键字个数⌈m/2⌉ n m根结点1 n m n个关键字n棵子树 仅最下层叶子结点包含记录信息访问磁盘次数少 支持顺序查找 成功失败都在最后一层速度稳定 相同 任何结点子树一样高绝对平衡 散列表的查找 散列表概述 基本思想 记录的存储位置与关键字之间存在对应关系 对应关系------hash函数散列函数 概念 散列方法 选取某个函数依该函数按关键字计算元素的存储位置并按此存放 查找时由同一个函数对给定值k计算地址将k与地址单元中元素关键码进行比较确定查找是否成功 散列函数 把查找表中的关键字映射成该关键字对应的地址的函数记为Hash(key) Addr(这里的地址可以是数组下标索引或内存地址等) 散列表 根据关键字而直接进行访问的数据结构散列表建立了关键字和存储地址之间的一种直接映射关系 冲突 不同的关键码映射到同一个散列地址 key1 ! key2但H(key1) H(key2) 同义词 具有相同函数值的多个关键字 性能 查找效率高可达到 O(1) 、空间效率低 使用散列表要解决好两个问题 构造好散列函数 所选函数尽可能简单提高转换速度 所选函数对关键码计算出的地址应在散列地址集中致均匀分布以减少空间浪费 制定一个好的解决冲突的方案
散列函数的构造方法 考虑的因素 执行速度即计算散列函数所需时间、关键字的长度、散列表的大小、关键字的分布情况、查找频率 要求 n个数据仅占用n个地址虽然散列查找是以空间换时间但希望散列的地址空间尽量少 无论用什么方法存储目的都是尽量均匀地存放元素以避免冲突 散列函数 除留余数法 概述 假定散列表表长为m取一个不大于m但最接近或等于m的质数p利用以下公式把关键字转换为散列地址 散列函数 H(key) key % p 特点 关键在p的选取使得每个关键字通过该函数转换后等概率映射到散列空间的任一地址减少冲突 直接定址法 概述 直接取关键字的某个线性函数值为散列函数 散列函数 H(key) key 或 H(key) a*key ba和b为常数 特点 计算最简单不会产生冲突 适合关键字分布连续的情况若不连续则存储空间浪费很多 数字分析法 概述 设关键字是r进制数而r个数码在各位上出现的频率不一定相同可能在某些位上分布均匀某种数码出现机会均等。选取数码分布较为均匀的若干位作为散列地址 特点 适合于已知的关键字集合若更换了关键字则需要重新构造新的散列函数 平方取中法 概述 取关键字的平方值的中间几位作为散列地址 特点 适合于关键字的每位取值都不够均匀或均小于散列地址所需位数 冲突解决的方法 拉链法 概述 为了避免冲突把所有的同义词存储在一个线性链表由散列地址唯一标识中 优点 非同义词不会冲突无“聚集”现象 链表上结点空间动态申请更适合于表长不确定的情况经常插入删除 开放定址法 概念 指可存放新表项的空闲地址即向它的同义词开发又向其非同义词开发删除元素时用标记表示 数学递推公式 Hi (H(key) di) % m di即为增量序列 增量d的取值 线性探测法 di 0, 1, 2, … , m-1 发生冲突时顺序表查看表中下一个元素直到有空闲单元 会出现聚集现象降低查询效率 平方探测法 di 0² , 1² , -1² , 2² , -2² , … , k² , -k² 不会出现聚集现象不能探测所有单元但至少能探测一半 伪随机序列法 di 伪随机数序列 再散列法 公式变为Hi (H(key) i×Hash2(key)) % m diHash2(key)i为冲突次数作为公式中再散列系数别漏了
散列的查找及性能分析 查找过程 检测由散列函数形成的地址上是否有记录若无记录则失败 若有记录比较关键字值若相等则查找成功否则散列函数更新增量值重复执行 补充求查找失败的ASL时 失败位置也计数若H(key) k%7则失败要算0,1,2,3,4,5,6 散列表查找效率取决于三个因素 散列函数 处理冲突的方法 装填因子 装填因子为描述一个表装满程度越大越容易冲突 装填因子α 表中记录数n/散列表长度m 平均查找长度依赖于散列表的装填因子 补充 散列表技术具有很好的平均性能优于一些传统的技术 链地址法优于开放定址法 除留余数法作散列函数优于其它类型函数
