07查找

顺序查找和折半查找

平均查找长度 ASL (Average Search Length)
计算公式

为第 个元素发生的概率, 若是等概率的情况,
为找到第 个元素需比较的次数

查找与存储结构 (顺序存储/链式存储)

• 顺序查找
  {顺序表和链表都可以}
• 折半查找
  {只能是顺序存储结构}
  一定是有序
• 树形查找法
  {顺序表和链表都可以}
• 散列查找法
  {顺序表和链表都可以}

顺序查找

• 优点:
  通用性好,
  对数据存储结构没有要求
  对数据是否有序, 也没有要求
• 缺点:
  效率低

折半查找
当元素个数为 的时候
折半查找树树高={}
时间复杂度={}

Q: 折半查找查找成功和查找失败的最多次数
A: 成功: 次
失败: 次
都等与折半查找树的树高

分块查找的性质

若 , 则平均查找长度取最小值 .

查找方法	等概率情况下, 计算公式
无序查找表, 顺序查找
- ASL 成功	{c1: }
- ASL 失败	{c1: }
有序查找表, 顺序查找
- ASL 成功	{c2: }
- ASL 失败	{c2: }
有序查找表, 折半查找
- ASL	具体问题具体分析,{c3: 先应根据题目给出的结点个数 n 来画出相应的折半查找判定树, 再根据判定树来计算 ASL.}
有序查找表, 分块查找 均匀地分为 b 块, 每块有 s 个记录 在块内和索引表中均采用顺序查找
- ASL	{c4: }

Q: 一个长度为 n 的顺序表, 其元素按关键字有序排列, 若采用折半查找算法查找一
个不存在的元素, 则比较的次数至少是 ( ), 至多是 ( ).
A: 至多=
至少=

Q: 对于同样的数据, 直接顺序查找与排序后, 顺序查找
查找失败与查找成功的 ASL 相同吗
A: - 成功: ASL 相同, 都是

• 失败: ASL 不相同,
  直接顺序查找
  排序后, 顺序查找
  显然排序之后, 再顺序查找, ASL 更低

Q: 如何判断某棵树是否是折半查找判定树?
A: 折半查找判定树是一棵平衡二叉树
利用平衡二叉树的性质
所有左子树的度>=右子树, 或者所有左子树的度⇐右子树
折半查找判定树有这样的性质
左右子树高度差最多为 1
由 mid 指针的取法 (向上取或者向下取), 决定了
还是
折半查找判定树是递归定义的
存在一个左子树的高>=右子树
意味着, 所有的左子树的高>=右子树
一但出现冲突, 就不可能是棵折半查找判定树

树形查找

二叉排序树是一种{非线性}(线性/非线性) 的结构

Q: 二叉排序树的中序遍历得到的是一个怎样的序列?
A: 有序序列
符合严格定义的二叉排序树 (左<根<右), 得到一个升序序列
左>根>右, 得到的则是一个降序序列

二叉排序树不是为了排序,
而是为了
方便查找, 插入和删除关键字等操作

Q: 什么是二叉排序树?
A: 进行中序遍历, 得到一个有序序列的二叉树
常见为左<中<右, 中序遍历结果为一个单增序列

二叉排序树的查找时间复杂度
最好:{c1: } 即二叉树为{c1: 平衡二叉树}
最坏:{c2: }

唯一性
折半查找判定树{c1: 唯一}
二叉排序树{c1: 不唯一}

Q: 折半查找判定树是平衡二叉树, 是非线性的结构
所以, 折半查找是树形查找?
A: 不是
折半查找判定树是描述查找的过程, 确实是一个平衡二叉树
但, 折半查找本身不是树形查找
树形查找的操作对象为一个树形的数据结构
而折半查找的操作对象为有序线性数组

折半查找与二叉排序树
时间复杂度比较
查找
两种差不多
插入和删除操作
折半查找
二叉排序树

使用折半查找还是使用二叉排序树
主要是看
查找表是{静态还是动态}
有序表是静态查找表时, 用折半查找实现, 存储使用顺序存储
若有序表是动态查找表, 用二叉排序树实现, 存储使用链式存储

平衡二叉树
判断旋转类型
平衡因子旋转类型
2 1 {c1: LL, 根右旋}
2 -1 {c1: LR, 子树左旋, 根右旋}
-2 1 {c1: RL, 子树右旋, 根左旋}
-2 -1 {c1: RR 根左旋}

平衡二叉树删除与插入操作比较
插入之后的旋转操作只需要进行一次
而删除之后的旋转操作可能需要多次
第一次旋转之后, 还需要向上回溯, 判断上方的结点是否出现不平衡的情况

平衡二叉树
此平均查找效率为

Q: 二叉排序树和二叉查找树有区别吗?
A: 没区别
A binary search tree (BST), also called an ordered or sorted binary tree

Q: 个不同结点构造的二叉排序树的形态共有 ( ) 种
A: 二叉排序树的中序是确定的
那就变成了有一个固定的中序遍历
会有多少种不同的输入序列
根据卡特兰数的计算公式可知
有 种输入序列
对应 种二叉查找树的形态

Q: 平衡二叉树深度为 h, 最少结点数为?
A:

红黑树

Q: 平衡二叉树有哪些缺点?
A: 平衡二叉树的平衡策略极其严格, 进行插入或者删除操作, 往往会带来整个树拓扑结构的大量变化

Q: 为什么会有红黑树这种数据结构? 相较于 AVL 树
A: AVL 树的插入与删除代价较高
红黑树放宽了平衡策略, 在查找代价提高较少的情况下, 降低插入和删除操作的代价

Q: 红黑树与 AVL 都是是递归定义的吗?
A: 红黑树不是递归定义的
而 AVL 是递归定义的

Q: AVL 树的子树一定是 AVL 树吗?
红黑树的子树一定是红黑树吗?
A: AVL 是递归定义的
所以 AVL 树的子树一定也是 AVL 树
而红黑树不是递归定义的
意味着红黑树的子树不一定是红黑树

红黑树的定义

1. 左根右: 二叉排序树, 左子树<根结点<右子树
2. 根叶黑: 根结点和叶子结点都是黑色的
3. 不红红: 不存在连续的红色结点
4. 黑路同: 所有到叶子结点的路径上, 黑色结点的数量相同

红黑树中的叶子结点指的是{虚构的外部结点}

红黑树的性质
任意一个结点左右子树的高度, 相差不超过 2 倍
有 个内部结点的红黑树的高度 .

Q: 红黑树与 AVL 树的查找、插入、删除的时间复杂度,效率比较
A: 时间复杂度相同, 都是一样的量级
但是效率不同
各自优势
红黑: 插入, 删除
AVL: 查找

红黑树插入 结点操作流程图

• 父结点=black
  • 不做调整
• 父结点=red
  • 是根结点
    • 变为黑色
  • 不是根结点
    • 叔结点=black
      • 按照平衡二叉树的插入操作来进行旋转
      • 之后再对旋转点和中心点变色
    • 叔结点=red
      • 父结点与叔结点变为黑色
      • 爷结点变为红色
      • 再判断爷结点是否需要调整

B 树和 B+树

M 路 B 树

• 至多:
  每个结点至多有{c1: m}棵子树 ({c1: m-1}个关键字)
• 至少:
  • 非叶根节点: 至少有{c2:2}棵子树 ({c2:1}个关键字)
  • 非根内部结点: 至少有{c3: }棵子树 ({c3: }个关键字)

B 树的高度
则对任意一棵包含 n 个关键字, 高度为 h, 阶数为 m 的 B 树:
{c1: } {c1: }

B 树插入关键字 的流程图

• 在叶子结点找到位置插入
• 上溢判断
  • 无上溢
    • 结束
  • 有上溢
    • 将第 个元素上移, 左右分裂
    • 再判断是否有上溢

B 树删除关键字 的流程图

• 转化为删除叶节点, 用直接前驱或者直接后继替换
• 下溢判断
  • 无下溢
    • 结束
  • 有下溢
    • 兄弟够借
      • 父下来, 兄上去
    • 兄弟不够借 (需要检查父节点)
      • 右并
        • 父下移到左, 右并过来
      • 左并
        • 父下移到右, 左并过来

Q: 为什么 B 树删除关键字 , 有下溢,
兄弟不够借, 在合并之后, 需要检查父结点
而兄弟够借, 不需要检查父结点
A: 兄弟够借, 父结点关键字中的数据虽然发生了变化, 但是关键字数量是没有变的
而兄弟不够借, 父结点的关键字数量-1, 就可能出现父结点也下溢, 需要再次判断

B+树是应{数据库需求}出现的, B 树的变形树

M 路 B+ 树

• 至多:
  每个结点至多有{c1: m}棵子树 ({c1: m}个关键字)
• 至少:
  • 非叶根节点: 至少有{c2:2}棵子树 ({c2:2}个关键字)
  • 非根内部结点: 至少有{c3: }棵子树 ({c3: }个关键字)

Q: 为什么 AVL, 红黑, B 树都不支持顺序查找, 只支持随机查找
而 B+ 树支持顺序查找与随机查找
A: B+ 树所有的叶子结点之间都有着指针连接
能够实现顺序查找

具有 n 个关键字的 m 阶 B 树, 应有{n+1}个叶结点

Q: 为什么
具有 n 个关键字的 m 阶 B 树, 应有 n+1 个叶结点
A: n 个关键字对应了 n 种查找成功的情况
也对应了 n+1 种查找失败的情况
例如一个 B 树的关键字为 1,2,3
对应查找成功为 1,2,3 三种情况
查找失败为 (-oo, 1), (1,2), (2,3), (3,+oo) 四种情况
而叶子结点的个数=查找失败区间的个数=4 个

Q: B 树的叶子结点之间是否有指针连接?
A: 没有
指针连接是 B+树的特点

Q: 为什么 B 树和 B+树都被称为绝对平衡树或高度平衡树?
A: 它们的所有叶子结点都在同一层

散列

Q: 关键字表, 哈希函数, 散列表之间的关系
A: 关键字表经过哈希函数处理得到散列表

常见的哈希函数 (散列函数)

• 直接定址法
  {c1: 哈希函数为一个线性函数, 直接映射到连续的空间}
• 除留余数法
  {c1: 取一个不大于 m 但最接近或等于 m 的质数 p 把关键字转换成散列地址}
• 数字分析法
  {c1: 取数码分布较为均匀的若干位作为散列地址, 例如电话号码的后四位}
• 平方取中法
  {c1: 取关键字的平方值的中间几位作为散列地址}

Q: 什么是聚集 (堆积) 现象?
A: 大量元素在相邻的散列地址上聚集 (或堆积) 起来

Q: 为什么会出现聚集 (堆积) 现象?
A: 选择的冲突处理方式不恰当
解决冲突办法-开放地址法-线性探测法-
会导致聚集 (堆积) 的发生

Q: 如何解决聚集 (堆积) 现象?
A: 使用解决冲突办法-开放地址法-平方探测法

产生堆积现象, 即产生了冲突
存储效率, 散列函数和装填因子{均不会有影响}
平均查找长度{会增大}(注意这里是存储效率, 而不是查找效率)

散列表装填因子的定义
表中记录数为 n ,散列表长度为 m
{}

散列表的查找效率取决于三个因素: {{c1::散列函数, 处理冲突的方法和装填因子}}
散列表的平均查找长度直接依赖于散列表的 {{c2::装填因子α}} , 而不直接依赖于 {{c2::表中记录数n 或 散列表长度m}}