查找算法
二叉查找树（BST）
对于任何节点
若其左子树存在，则其左子树中每个节点的值都不大于该节点值； 左子节点小
若其右子树存在，则其右子树中每个节点的值都不小于该节点值。 右子节点大
二叉排序树中序遍历可输出从小到大的排序数列
https://www.jianshu.com/p/ff4b93b088eb
操作：查找、插入、删除
查询节点过程：比较元素值是否相等，相等则返回，不相等则判断大小情况，迭代查询左、右子树，直到找到相等的元素，或子节点为空，返回节点不存在。最好O(nlogn)（AVL），最差O(n)
插入节点的过程：比较元素值是否相等，相等则返回，表示已存在，不相等则判断大小情况，迭代查询左、右子树，直到找到相等的元素，或子节点为空，则将节点插入该空节点位置。易错：插入必能插到一个新的空位置上去！（如果没重复）
删除节点过程：1.查找出左子树中的最大值节点 $Node_{max}$
2.替换待删除节点 $Node$ 的值为$Node_{max}$的值
3.删除 $Node_{max}$节点
因为 $Node_{max}$ 作为左子树的最大值节点，所以节点的度一定是 0 或 1，所以删除节点的情况就转移为以上两种情况。
平衡二叉树（AVL）
二叉查找树+每一个结点的左子树和右子树的高度差最多为1
（可以规避BST的最坏情况）
https://www.jianshu.com/p/3a6650269d39
插入：先按照BST的插入方法插入，然后再进行旋转操作
旋转操作-4种情况：
在根结点的左孩子的左子树上插入，对根结点进行右旋转。
在根结点的右孩子的右子树上插入，对根结点进行左旋转。
在根结点的左孩子的右子树上插入，先对根结点的左孩子进行左旋转，再对根结点进行右旋转。
在根结点的右孩子的左子树上插入，先对根结点的右孩子进行右旋转，再对根结点进行左旋转。
插入之后还要调整每个结点的平衡因子
B树
即多路平衡查找树，一个结点有多个分叉。
B树相比AVL树高度更低，查询耗时更少
B+树
B+树相比于B树：叶子节点有序且串成一串
InnoDB底层数据结构
红黑树
红黑树也是二叉树，基于AVL改进，它对平衡的要求没那么严格，使得增删结点旋转次数降低减少开销(红黑树最多需要3次旋转就能回复红黑树平衡），但是不平衡导致高度增加，使得查询次数相比AVL增加。
红黑树是一种对时间和性能的折中，实际使用中，如果搜索次数远大于插入和删除次数，那么选AVL；如果差不多，则旋转RB
红黑树的性质：①每个结点要么黑，要么白②根节点黑③每个叶子节点（null）为黑④每个红色结点的两个子节点一定都黑⑤任意一结点到每个叶子结点的路径都包含数量相同的黑色结点
哈夫曼树
哈夫曼树使得带权路径长度最小（一个结点=深度×结点权重）
那么就要将权值最小的结点放最底层（因为底层深度大，所以应该尽量将权值小的放到长路径上）
于是就在所有结点中找到最小的作为叶子节点，然后合并作为中间结点，开始层层向上
哈夫曼树结构固定
哈夫曼编码即是先求出各个字母出现的频率，频率即为结点权值，尽量放深层
Hash算法
hash函数
①直接定址法：$H(key)=a×key+b$
②除留余数法：$H(key)=key\%p$
③数字分析法
④平方取中法
⑤折叠法
冲突处理方法
①开放定址法：$H_i=(H(key)+d_i)\%m$，$d_i$为增量序列，$m$为散列表表长
增量序列的取法：线性探测法$d_i=0,1,2,\cdots,m$、平方探测法$d_i=0^2,1^2,-1^2,2^2,\cdots,k^2,-k^2$、再散列法（双散列法）$d_i=Hash_2(key)$、伪随机序列法$d_i=random(m)$
②拉链法
java中hashmap的处理方法，后来冲突链改为红黑树了（当冲突链比较长的时候）
KMP【】
略
图的应用
最小生成树
最小生成树：树中所有边权值和最小
Prim算法：以点为中心
从顶点开始扩展生成树，生成树不断壮大，加入跟多的节点
设$N=(V,E)$是连通网
初始空集合$G$，点集合$V$，先将任一结点加入集合$G$
然后选择与集合$G$中相连的点中最短的那一条，连线，将该结点加入集合$G$（一次循环加入一个点）
不断重复上述
时间复杂度$O(|V|^2)$，不依赖于边，所以适合稠密图
伪代码：
void Prim(G,T)
{
T=∅;
U={w};
while((V-U)!=∅)
{
设(u,v)是使u∈U与v∈(V-U)，且权值最小的边 //这里要用一个内存循环去找
T=T∪{(u,v)};
U=U∪{v};
}
}Kruskal算法：以边为中心
按权值的递增次序选择合适的边来构造最小生成树
设$N=(V,E)$是连通网
每一轮循环不断选取当前未被选取的，边集中权值最小的边（不需要像Prime一样必须是已加入集合的结点的邻边），最终没有连通分量为1时候，表明已经生成一棵树
时间复杂度：$O(|E|\log|E|)$（用堆来存放边集，否则$O(|E|^2)$，适合边稀疏的图
伪代码：
void Kruskal(V,T)
{
T=V;
numS=n; //连通分量数
while(numS>1)
{
从E中取出权值最小的边(v,u) //一个内存循环
if(v和u属于T中不同的连通分量) //注意这里判断【】
{
T=T∪{(v,u)};
numS--;
}
}
}最短路径
基本思想：如果要让任意两点（例如从顶点a点到顶点b）之间的路程变短，只能引入第三个点（顶点k），并通过这个顶点k中转即a->k->b，才【可能】缩短原来从顶点a点到顶点b的路程
Dijkstra算法【1】
思想：广度优先搜索+贪心算法，每轮找最优解，局部最优最后达到全局最优
【数学原理：一条最短路径上的任意结点到原点的距离都是最短的】。（证明略）
核心步骤：广度优先遍历，每轮找到距离最小的那条路，计算出来比原来不走这条路小则更新；每一层遍历选择出距离最小的走法那个结点，再次进行下一层广度优先遍历。
实现需要：①邻接矩阵 ②$S$数组（储存已访问节点）③$dist$数组（储存起点到目标节点的当前最短路径；可以直接将邻接矩阵第一行作为dist数组）④$path$数组（path[i]表示源点到结点$i$的最短路径的前驱结点，可用此追溯路径）
时间复杂度：$O(|V|^2)$
如果是找某点到特定终点的最短路径，那就只能先计算所有点到该终点的最短路径，再找最短的，需要$O(|V|^3)$
Dijkstra 算法不能处理带有负权边的图，有负边就不能保证局部最优可以使得全局最优了。
伪代码与理解：
1~4：初始化，起点加入已访问数组，当前结点为源结点，记录第一跳的最短路径dict值（这里源结点的dict初始化可以放在下面的循环里）（当前结点指当前访问的结点）
5：当还有结点未被访问，继续循环
——6：从最短路径$dist$中找到当前结点到其它结点最短路径对应的结点$j$（且未被访问）
——7：结点$j$加入已访问数组，当前结点变为结点$j$（我们判断要不要经过这个点，这就是最开始那个原理）
——8~10：将经过当前结点$j$到各结点的距离更短的距离值更新进dict，更长的不更新；同时更新path也是同理，如果途径当前结点距离更短了，则前驱结点变为当前结点，否则不更新
（然后注意，循环到下一层的6中，是在所有最短路径dist里找最短，有可能未更新的是最短的，所以下一轮依然会从未更新的结点继续选择，上一个当前结点访问后没有加入路径！
注意一个误区：从源点到某个结点的最短距离并不一定需要包含所有结点！最短路径问题并不是要求把所有结点串起来成一条路径求最短！
代码实现【】：https://blog.csdn.net/u011638883/article/details/17200869
Floyd算法【2】
基于开头的基本思想：如果要让任意两点（例如从顶点a点到顶点b）之间的路程变短，只能引入第三个点（顶点k），并通过这个顶点k中转即a->k->b，才可能缩短原来从顶点a点到顶点b的路程
那我们直接一个个去试不就好了？
三个for
for(k=1;k<=n;k++) //k设定为途径结点
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(e[i][j]>e[i][k]+e[k][j] )
e[i][j]=e[i][k]+e[k][j]; 理解：https://www.cnblogs.com/wangyuliang/p/9216365.html
不允许负权值(带有“负权回路”的图没有最短路)
拓扑排序
定义：
由一个有向无环图（DAG）的顶点组成的序列，当且仅当满足下列条件时，称为该图的一个拓扑排序：
①每个顶点出现且只出现一次
②若顶点A排在顶点B前面，则在图中不存在从顶点B到顶点A的路径
拓扑排序算法：
①从DAG图中选择一个没有前驱结点的顶点输出
②从图中删除该顶点和所有以它为起点的有向边
③重复①②直到当前的DAG图为空（输出成功）或不存在无前驱的结点（无拓扑排序，必存在环）为止
代码实现：（使用栈实现）
①将所有入度为0的顶点入栈
②若栈非空，顶点出栈，将所有该顶点指向的顶点入度-1，并将入度减为0的顶点压入栈中
③如此循环直到结束，检查是否输出所有顶点，是则ok，不是则无拓扑排序
拓扑排序的应用：关键路径
在带权有向图中，顶点表示事件，边表示活动，边的权值表示完成事件的开销=>AOE网（用边表示活动的网络）
①只有某顶点所代表的事件发生后，从该顶点出发的各有向边才能开始活动
②只有在进某一顶点的各有向边所代表的活动都已结束时，该顶点所代表的事件才能发生
完成整个工程的最短时间就是关键路径的长度
AOE网中仅一个入度为0的顶点：开始顶点（源点）
仅一个出度为0的顶点：结束顶点（汇点）
此类题的解决办法：拓扑排序
【】
