二叉排序树查找操作_二叉查找树的时间复杂度

2024年 8月 31日下午11:42 • 激活谷笔记

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

二叉排序树查找操作_二叉查找树的时间复杂度

相关推荐