一. 查找算法的评估规范
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+ 树和散列查找
看书，内容不多，但比拟琐碎，多练多做