数据结构基础第7讲 查找
考点一:查找的基本概念
1.概念
-
静态查找
-
动态查找
-
分类
2.查找性能计算
-
平均查找长度:
考点二:顺序查找
1.顺序查找
2.优劣
考点三:折半查找(二分搜索)
1.概念
2.过程
3.构建为判定树
-
构建
向上取整:左少右多向右偏
向下取整:左多右少向做左偏
-
结论
查找比较次数=层次高度
查找路径是一条从根到该点的参次路径,该路径有且仅有一条
-
查找成功平均比较次数
查找成功平均比较次数:拿层高乘以每层结点个数累加再除以元素个数
-
查找不成功平均比较次数
顺序查找及折半查找均为静态查找手段
考点四:二叉排序树
1.二叉排序树定义
注意:二叉排序树中没有相同关键字的结点
2.二叉排序树的查找
查找过程:
查找过程永远是一条层次路径的形态
3.二叉排序树的插入
插入过程:
4.二叉排序树的删除
4种情形:
-
删除叶子
-
删除结点只有右子树
-
被删除的结点只有左子树
-
被删除同时具有左右子树
用中序直接前驱或中序直接后继代替
-
二叉排序树的构造
依次作为叶子结点插入
元素相同顺序不同,构成的二叉排序树也不同
6.二叉排序树的性能分析
相同结点,树形结构不同,也会导致平均比较次数不同
考点五:平衡二叉树
1.平衡二叉树概念
-
AVL树引入
-
平衡因子
-
最小不平衡子树
以距离插入结点最近的,且失衡的结点为根的子树
2.平衡二叉树的旋转及实现
-
导致不平衡原因
插入与删除可能导致失衡
-
插入结点:
插入只会改变它所在层次路径的平衡因子
-
删除结点:
删除可能会改变父亲所在层次路径的平衡因子
插入看自己,删除看兄弟(父亲)
删除改变的一定是兄弟子树因此从兄弟往上找
-
-
不平衡的4种情况
-
不平衡情况判断
插入:
从自己开始向上查找,找到不平衡那个点,以那个点的层次路径即为最小不平衡子树
删除:
从兄弟向上去找,找到第一个不平衡点;
从该点开始画层次路径,层次路径可能有多个;
当层次路径高相同时都可以,不同时谁高看谁
-
如何调整
全把落单的当叶子结点重新插进去
以最小不平衡子树根节点开始,向下子节点位置命名
-
LL
落单的拿出来,剩下的按平衡二叉树规则变形。
重新把R当叶子结点插入回去
R比10大比11小,插入11左边
-
LR
先把10放到中间构成LL
接着掰弯
当有左右子树时
把L,R落单,剩余按平衡二叉树规则处理。
再把L,R当作叶子结点插回去
L比9大比10小,插入到9左边
R比10大比11小,插入到11右边
-
RR
10有左子树
L比10小,比9大,插入到9左边
-
RL
有L,R情况
L比9大,比10小,放9左边
R比10大,比11小,放11右边
-
考点七:索引查找
1.B-树的定义和性质
用关键字分割子树
-
索引查找引入
-
B树的定义
性质总结:
2.B-树的查找
-
查找过程
-
B-插入
-
B-删除
m为B树阶数
-
删除非叶子中的key
任意非叶子都有左子树
用中序直接前驱或中序直接后继代替之。
即用左子树最大值或右子树最小值代替。
删除看下界
不够找兄弟借,借左兄弟最大值,或右兄弟最小值,把父亲拽下来把兄弟升上去。
都不够
将自己父亲左兄弟合并,或自己有兄弟合并
总结:
ex:
-
3.B+树的定义与性质
用关键字引导子树
考点八:散列查找
1.散列查找的基本思想
-
设计散列函数
-
直接地址法
-
平方取中法
-
(\(\bigstar\))除留余数法
-
2.处理哈希冲突
-
开放定址法
凡是空白空间均可使用。
线性探查法:
计算成功/失败的平均查找次数
失败标志,从算出哈希位置向后找到空
-
二次探查法
左右横跳,越跳越长
-
拉链法
将余数相同的所有元素放入单链表中
成功查找平均次数:
失败查找平均次数:
-
装填因子
-
复杂度