共计 857 个字符,预计需要花费 3 分钟才能阅读完成。
一. 查找算法的评估规范
ASL: 查找关键字的均匀次数
二. 程序查找
如名,一个个查找,不限数据排序规定和存储格局
优化:
(1)将查找表的数据有序排放(递增或者递加)
(2)查找断定树
(3)当关键字的概率不同
可按被查概率降序排列,查找胜利时 ASL 变小
三. 折半查找
(1)应用条件:仅实用于有序的程序表(因为程序表有随机拜访特效)
(2)代码实现:(/ 代表取整)
(3)查找断定树
关键字:左小于中小于右;且失败节点为胜利节点的空域数量,即 n +1
如果 mid 是向上取整的话,则右边比左边多一个
须要留神的是,查找判断树肯定是均衡二叉树,且最上面一层是不满的,所以树高为 log2(n+1)向上取整
四. 分块查找
(1)用折半查找查索引,如果最终索引表停在 low>high,则在 low 所在分块中查找,如果 low 超出索引表范畴,则查找失败。索引表的查找可用程序或者折半,但索 = 索引内进行程序查找
(2)查找效率剖析
五. 二叉排序树
(1)结构与查找
代码有两种模式,另一种为递归实现,但递归实现会使空间复杂度变为 O(n)
(2)二叉排序树的插入
(3)二叉排序树的删除
1. 如果 z 只有左子树或者右子树,则让 z 的子树成为父节点的子树,代替 z 的地位
2. 若 z 有左右两颗子树,则让 z 的间接后继代替 z,而后删去这个后继,从而转化为第一种状况
(4)工夫复杂度
最好的 O(log2n), 最坏的 O(n)
六. 均衡二叉树
(1)插入
最重要的为插入后的调整,间接看书
(2)删除
能看懂最好,看不懂间接看书或者看视频
七. 红黑树
(1)呈现的起因
(2)定义
左根右,根叶黑,不红红,黑路同(从一个节点登程,到所有叶子节点通过的黑节点数量雷同)
黑高:从某一节点登程到任一空叶节点的门路上黑节点的总数
推论:黑高为 n 的树,节点树起码为多少?
起码状况:共 n 层黑节点的满树状况,起码 2 的 n 次方减一个
(3)性质
1. 从根节点到叶子节点的最长门路不大于最短门路的两倍
2. 有 n 个节点的高度 h 不大于 2log2(n+1)
(4)插入
看书或者视频,不过考的概率不大
八.b 树,b+ 树和散列查找
看书,内容不多,但比拟琐碎,多练多做