中序遍历(LDR)是顺序的。

插入k若k小于根节点，则左子树；若k大于根节点，则右子树。
删除k如果k有左右子树，则以右子树中序遍历的第一个结点为根节点。

搜索效率取决于树的高度
计算平均搜索长度=($\sum$层*该层的结点数)/总结点数。

扩展问题:已知前序、中序、后序遍历、构造二叉树的问题

前序：DLR，中序：LDR，后序：LRD
其中 前 中 或者 中 后 一棵树可以唯一确定
前 第一个序列是根结点，左子树和右子树是根据节点在序列中的位置找到的。重复这一步以获得二叉树。
后 中间:后序的最后一个是根节点，其他是同上的。

1.在二叉排序树上找到的序列要求
a,b,c,d,e,f,g：a大于/小于 bcdefg，b大于/小于 cdefg

子树高度差不超过1
平均搜索长度为O(logn)

1.高度为hAVL，至少结点数：$f(h)=f(h?1)f(h?2)1$
2.非空AVL T1，删除v形成AVL T2，将v插入T2得到AVL T3，则：
若v是T叶节点1，是的T1和T3可能不同
若v不是T叶节点1，是的T1和T3可能不同

哈夫曼树(最佳二叉树):带权路径长度(WPL)最小的二叉树
WPL计算方式：$\sum$权值*路径长度。

1.n有2棵哈夫曼树叶结点n-1个结点。
2.哈夫曼树对应一组权值，一般不是唯一的。

空间复杂度:最坏情况:$O(V)$ （队列）
时间复杂度：邻接表：$O(V+E)$
邻接矩阵：$O(V^2)$

空间复杂度：$O(V)$ （递归工作栈）
时间复杂度：邻接表：$O(V+E)$
邻接矩阵：$O(V^2)$

Prim：$O(V^2)$ 顶点较少边稠密的图
Kruskal: $O(ElogE)$ 边稀疏而顶点较多的图
其中使用到了并查集，并查集的两个优化方法：路径压缩+按秩合并

Dijkstral ： $O(VlogE)$ 负边权不适用
Bellman-Ford：$O(VE)$
是通过循环 n 次，每次循环都遍历每条边，进而更新结点的距离
假如当前迭代次数为k次，d[]数组的含义为源点s到每个点的不超过k条边的最短距离
SPFA：可以处理负边权，判断负环，本质是广度优先算法。
平均时间复杂度是$O(E)$，最坏时间复杂度是$O(VE)$，其中m是图的边数。

1. 二分图最大匹配：匈牙利算法
2. 二分图最小点覆盖=二分图最大匹配 ：证明
3. 二分图最少边覆盖=V-二分图最大匹配：证明
4. 二分图最大独立集=V-二分图最小点覆盖：证明
5. 最小路径覆盖：算法描述

一开始每个点都是独立的为一条路径，总共有n条不相交路径。我们每次在二分图里找一条匹配边就相当于把两条路径合成了一条路径，也就相当于路径数减少了1。所以找到了几条匹配边，路径数就减少了多少。所以有最小路径覆盖=原图的结点数-新图的最大匹配数。

Tarjan算法：$O(V+E)$

（1）正拓扑
（2）逆拓扑
（3）判断正逆值是否相等，相等则该弧为关键路径

直接插入排序
对于第$i$个元素，$[1,i-1]$为有序序列，将$i$插入前方序列
比较次数和移动次数与初始序列有关。
最好情况下：比较n次，移动0次
最坏情况下：比较次数$\frac{n\times (n-1)}{2}$ ，移动次数${\sum }_{i=2}^{n}i+1$
稳定

折半插入排序
对于第$i$个元素，$[1,i-1]$为有序序列，将$i$插入前方序列
插入时，使用折半查找寻找插入位置。
比较次数和移动次数与初始序列有关。
比直接插入排序比较次数少。
稳定

希尔排序
对于距离为$d_i$的记录放在同一组，组内插入排序
一般来说$d_1=n/2,d_{i+1}=d_i/2$
最坏时间复杂度为$O(n^2)$，平均约为$O(n^{1.3})$
不稳定

冒泡排序
每次将最小的元素移到序列头上（或者最大的元素放在尾上）
比较次数和移动次数与初始序列有关。
最好情况下：比较n-1次，移动0次，只需要
最坏情况下：比较次数$\frac{n(n-1)}{2}$ ，移动次数$\frac{3n(n-1)}{2}$

快速排序
基于分治法，选择枢轴元素，每趟让枢轴元素在正确的位置上，左侧为小于枢轴元素的数，右侧为大于枢轴元素的数字。
空间效率：递归实现，平均情况下$O(logn)$，最大递归深度为$O(n)$，最小递归深度为$O(logn)$

递归次数与排列顺序有关，若每次划分后，分区比较平衡，则递归次数少。

时间效率：最坏情况下$O(n^2)$，最好情况下$O(nlogn)$
不稳定
快速排序 是所有 内部排序算法 中 平均性能最优 的算法

简单选择排序
对于第$i$个元素，$[1,i-1]$已为最终有序序列，从i至n选择当前最小作为第i个元素。
与冒泡排序不同在于，选择排序为从i到n选择最小元素，而冒泡是通过从后往前两两比较和移动来实现最小元素到第i个位置。
时间效率：移动操作 最多$3(n-1)$ 次，最少0次。但比较次数与序列初始状态无关，始终为$\frac{n(n-1)}{2}$次

堆排序
建立大根堆或者小根堆，是一个完全二叉树，可顺序存储，其中第$i$个元素，左儿子$2i$，右儿子$2i+1$
时间效率：建堆$O(n)$，每次调整$O(h)$，故时间复杂度$O(nlogn)$
不稳定

归并排序
性能与元素序列无关，排序的趟数为$lo{g}_{2}n$，每趟排序复杂度为$O(n)$
缺点在于需要$O(n)$的额外存储空间
多路归并排序为外部排序

基数排序
在n很大，且记录的关键字位数较少且可分解的情况下。
基于关键字大小排序
空间复杂度$O(r)$
时间效率为$O(d(n+r))$，与序列的初始无关。总共d趟，一趟分配需要$O(n)$，一趟收集需要$O(r)$
其中$d$为$a_i$的最多位数，r=10[0,1,2,3…9]总共10个队列