《算法与数据结构基础》学习笔记07——查找算法_线性表、树表、散列表的查找 声明 本文章只是本人个人学习笔记，如有错误，欢迎批评指正 以下是本人自学的视频数据结构与算法基础（青岛大学-王卓）_哔哩哔哩_bilibili 概要： 查找算法：对不同的数据结构有不同的查找算法线性表的查找算法：顺序查找：最简单的查找算法，效率最低二分查找：无链式结构，要求数组素有序，效率最高分块查找：利用索引表分块，再查每块，利于动态规划操作（插入、删除），效率居中树表的查找算法：二叉排序树、平衡二叉树、红黑树、B-树、B+树、键树……二叉排序树：类似于线性表的二分查找，中序遍历二叉排序树可以得到递增序列，时间复杂度介于
与 之间平横二叉树AVL：左右子树高度差不超过1的二叉排序树，ASL为 量集散列表的查找算法：记录的存储位置与关键字之间满足函数对应关系散列表的查找是拿空间换时间的算法构造散列表一般用除留余数法作散列函数H处理冲突一般用链地址法（散列表一般平均性能更好） 7.1 查找算法简介 1.查找：根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据素 2.关键字：用来标识一个数据素的某个数据项的值主关键字：该关键字找出的记录唯一次关键字：该关键字找出的记录不唯一 3.查找成功：给出整个记录的信息 4.查找不成功：给出 “空记录” or “空指针” 5.查找表的分类：静态查找表——仅作 “查询” 操作的查找表动态查找表——作 “插入” 和 “删除” 操作的查找表 6.平均查找长度ASL（Average Search Length 关键字的平均比较次数） ——记录个数； ——找茬第 个记录的概率（一般 ） ——找到第 个记录所需要的比较次数 7.2 线性表的查找 7.2.1 顺序查找 1.顺序查找：一个方向查找顺序表or线性链表的静态查找表表内素之间无序 2.【顺序表结构定义】： 注意！！！：数组第0号素不用 3.顺序查找案例： 在顺序表中查找值尾key的数据素，返回素下标，从最后一个素开始查找
基础算法： 改进算法（省时间）：数据第0号素的关键字值存储为查找的关键字——添加监视哨平均时间复杂度 查找成功的平均查找长度 空间复杂度 7.2.2 二分查找（折半查找） 1.二分查找：每次将待查找区间折半表内之间素有序（升序or降序）只适合顺序结构，对线性链表无效 2.二分查找的思路：建立low、high、mid记录素上界、下界、中点下标每次比较中点下标素的值，若不对，则改变low、high的值重复上一步，直到找到，或者 low>high时，查找失败 3.二分查找算法： 4.二分查找的效率时间复杂度 成功时的平均查找长度 ————记录最大查找次数（判定树的深度） ————第 层的每个结点的比较次数 ————第 层结点数
7.2.3 分块查找（索引顺序表查找） 1.分块查找：将表分成若干块，块间有序块内可以无序，也可以有序建立索引表（类似于目录，如查一个单词，索引表为单词首字母） 2.查找过程：先确定待查记录所在块：顺序查找or二分查找再在每个块中找，无序只能用顺序查找；有序可以用二分查找（一般块内是无序的，因为这样插入新素的时候可以随便查）
3.分块查找的效率 令 个素， 每块内部记录为 个，共分成 块成功时的平均查找长度 ————对索引表查找的ASL ————对块内查找的ASL 7.2.4 顺序、二分、分块查找的比较 
7.3 树表的查找 动态查找表——几种特殊的树（表结构再查找过程中动态生成） 树表的查找有：二叉排序树、平衡二叉树、红黑树、B-树、B+树、键树…… 7.3.1 二叉排序树（Binary Sort Tree） 1.二叉排序树的性质：可以为空树左子树所有结点值都 小于 根结点值，or为空右子树所有结点值都 大于等于 根结点值，or为空左右子树又是一棵二叉排序树
2.二叉排序树的中序遍历（左根右）————得到递增序列
3.二叉排序树的操作——查找 查找方式：类似于二分查找关键字与根节点值相比，若关键字较小，则往左子树找；若关键字大，则往右子树找之后重复上一步（递归），直到找到or没找到 存储结构：链式存储结构 【二叉排序树的查找算法】 二叉排序树找找算法_效率分析： 含有n个结点的二叉排序树的平均查找长度ASL和树的形态有关最好情况（树较平衡） 时间复杂度 最坏情况（单支树） 时间复杂度
4.二叉排序树的操作——插入 插入方式：若二叉排序树为空，则插入根结点若二叉排序树非空，则根据查找方式在左右子树上查找，直到子树的根结点为空（插入的结点一定为叶子结点：无孩子）
5.二叉排序树的操作——生成 生成二叉树方式：给n个素，从空二叉树开始，依次插入这些素（插入方式见上4） <<<不同的插入次序，生成不同形态的二叉树：
6.二叉排序树的操作——删除 3种删除：删除叶子结点——直接删除删除结点只有一个孩子——将孩子替换成它删除的结点有两个孩子——2种方式以中序前驱结点替换之，按照上述方式删除中序前驱结点（递归）（中序前驱结点也是左子树中最大结点）以中序后继结点替换之，按照上述方式删除中序后继结点（递归）（中序后继结点也是右子树中最小结点）
7.3.2 平衡二叉树（AVL树） 1.平衡二叉树（又称AVL树）的性质：是二叉排序树“平衡因子BF”=左右子树的高度差（左-右）；要求平衡因子的绝对值小于等于1左右子树也是平衡二叉树（n个结点的平衡二叉树，其高度为 ，ASL保持 量级
2.失衡二叉排序树调整为平衡二叉树 4种基本类型平衡调整：
调整原则：降低高度、保持二叉排序树的性质（找ABC的大小关系）
例题：构造平衡二叉树：边构造边调整
7.4 散列表的查找 7.4.1 散列表的基本概念 1.散列表（杂凑表）的基本思想：记录的存储位置与关键字之间满足函数对应关系下标 Loc(i) = H(key_i)其中 H—— hash哈希函数（散列函数） 2.散列表的查找特点：时间效率高，空间效率低
3.散列表的几个术语冲突：不同关键字映射到同一个散列地址，即 key1 key2，但 H(key1) = H(key2)同义词：具有相同函数值的多个关键字 7.4.2 构造散列表 1.散列表解决的问题所选函数尽量简单——提高转换速度，减少空间浪费制定好的解决冲突的方案，存放尽可能均匀 2.散列函数的构造方法： 2.1 直接定址法——线性函数：Hash(key) = a·key + b优点：线性函数无冲突缺点：空间效率低 2.2 除留余数法——Hash(key) = key mod p p m(表长)，且为质数
7.4.3 处理冲突的方法 1.开放地址法——有冲突时寻找下一个空的散列地址 如除留余法 为增量序列，注意这里是mod m线性探测法—— 为线性序列1，2，…，m-1
二次探测法—— 为二次序列
伪随机探测法—— 为随机数 2.链地址法——相同散列地址的记录（冲突记录）链成单链表 m个散列地址，就有m个单链表，用数组存储表头指针，形成动态结构
链地址法建立散列步骤：无冲突，直接插入链表有冲突，用前插法or尾插法插入素 链地址法的优点：无非同义次不会冲突空间动态申请 7.4.4 散列表的查找 1.查找过程：
2.散列表的平均查找长度ASL取决于散列函数H处理冲突的方法散列表的装填因子 ， 大，说明表中记录多，冲突发生概率大 3.各冲突处理方法的ASL拉链法—— 线性探测法—— 随机探测法—— 7.4.5 散列表的几点结论 散列表具有更好的平均性能链地址法优于开地址法除留余数法作H散列函数优于其他类型函数
2024最新激活全家桶教程，稳定运行到2099年，请移步至置顶文章：https://sigusoft.com/99576.html
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。 文章由激活谷谷主-小谷整理,转载请注明出处：https://sigusoft.com/87532.html
