1. 激活谷首页
  2. 激活谷笔记

二叉排序树的查找性能取决于_二叉排序树的查找性能与什么有关

• 激活谷笔记

二叉排序树的查找性能取决于_二叉排序树的查找性能与什么有关数据结构-查找-06目录 第六章 查找① 线性表上的查找【一】顺序查找（线性查找）【二】折半查找（二分或对分查找）【三】分块查找（索引顺序查找&#xff09

数据结构-查找-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

赞 (0)
0
上一篇 2024年 5月 25日 下午5:06
下一篇 2024年 5月 25日 下午5:16

相关推荐

关注微信