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