数据结构-查找-06
目录
第六章 查找① 线性表上的查找【一】顺序查找（线性查找）【二】折半查找（二分或对分查找）【三】分块查找（索引顺序查找）折半查找成功
② 树表的查找【三】二叉排序树的查找（二叉查找树）【四】平衡二叉树！【五】B-树！（王卓没讲）【六】B+树！（王卓没讲）
散列表（哈希表）【八】散列表的基本概念【九】处理冲突的方法！1、开放地址法a.线性探测法b.平方探测法（二次探测法）c. 伪随机探测法
2. 链地址法散列表的查找
B树的基本操作B树的特性B+树KMP算法
第六章 查找
① 线性表上的查找
【一】顺序查找（线性查找）
【二】折半查找（二分或对分查找）
折半查找｛每次将待查记录所在区间缩小一半｝要求线性表必须采用顺序存储结构，而且表中元素按关键字排列。
查找成功里的是查找的层数
查找不成功里的是查找的次数
【三】分块查找（索引顺序查找）
性能介于顺序查找和折半查找之间的一种查找方法。
折半查找成功
② 树表的查找
【三】二叉排序树的查找（二叉查找树）
二叉排序树的一个重要性质：中序遍历一棵二叉树时可以得到一个结点值递增的有序序列。
最好情况：
最坏情况：
二叉排序树查找算法的性能取决于二叉树的结构，而二叉排序树的形状则取决于其数据集。
如果数据呈有序排列，则二叉排序树是线性的，查找的时间复杂度为O(n)；
反之，如果二叉排序树的结构合理，则查找速度较快，查找的时间复杂度为O(log2n)。
事实上，树的高度越小，查找速度越快。因此，希望二叉树的高度尽可能小
【四】平衡二叉树！
调整方法是：找到离插入结点最近且平衡因子绝对值超过1的祖先结点，以该结点为根的子树称为最小不平衡子树，可将重新平衡的范围局限于这棵子树。
【五】B-树！（王卓没讲）
1．B-树的定义一棵m阶的B-树，或为空树，或为满足下列特性的m叉树：
（1）树中每个结点至多有m棵子树；
（2）若根结点不是叶子结点，则至少有两棵子树；
（3）除根之外的所有非终端结点至少有）棵子树；
（4）所有的叶子结点都出现在同一层次上，并且不带信息，通常称为失败结点（失败结点并不存在，指向这些结点的指针为空。引入失败结点是为了便于分析B-树的查找性能）；
（5）所有的非终端结点最多有m−1个关键字，结点的结构如图7.21所示。
【六】B+树！（王卓没讲）
1．B+树和B-树的差异一棵m阶的B+树和m阶的B-树的差异在于：（1）有n棵子树的结点中含有n个关键字；（2）所有的叶子结点中包含了全部关键字的信息，以及指向含这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接；（3）所有的非终端结点可以看成是索引部分，结点中仅含有其子树（根结点）中的最大（或最小）关键字。
散列表（哈希表）
【八】散列表的基本概念
一个有限连续的地址空间，用以存储按散列函数计算得到相应散列地址的数据记录。通常散列表的存储空间是一个一维数组，散列地址是数组的下标。
冲突：
构造方法：
【九】处理冲突的方法！
1、开放地址法
发现冲突，就去寻找下一个空的散列地址，只要散列表足够大，空的散列地址就能找到，并将元素存入。
a.线性探测法
答案：A
b.平方探测法（二次探测法）
c. 伪随机探测法
2. 链地址法
散列表的查找
B树的基本操作
B树删除不是叶子的情况：
B树删除是叶子的情况：
B树的特性
B+树
KMP算法
2024最新激活全家桶教程，稳定运行到2099年，请移步至置顶文章：https://sigusoft.com/99576.html
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。 文章由激活谷谷主-小谷整理,转载请注明出处：https://sigusoft.com/94992.html
