数据结构
（1）线性表
1）数组
2）链表：单向链表、双向链表、循环链表、双向循环链表、静态链表。
3）栈：顺序栈、链式栈
4）队列：普通队列、双向队列、阻塞队列、并发队列、阻塞并发队列。
（2）散列表
1）散列函数
2）冲突解决：链表法、开放地址、其他
3）动态扩容
4）位图
（3）树
1）二叉树：平衡二叉树、二叉查找树、平衡二叉树（AVL树、红黑树）、完全二叉树、满二叉树。
2）多路查找树：B树、B+树、2-3树、2-3-4树。
3）堆：小顶堆、大顶堆、优先级队列、契波那契堆、二项堆、可并堆。
4）其他： 树状数组、线段树、字典树、后缀树。
（4）图
1）图的存储：临接矩阵、临接表。
2）拓扑排序
3）最短路径
4）关键路径
5）最小生成树
6）二分图
7）最大流
8）最短路、最小生成树、网络流建模、最近公共祖先、并查集。
树
二叉树：树中每个节点至多有两个子节点
二叉搜索树：对于树中任何节点，如果其左子节点不为空，那么该节点的value值永远 >= 其左子节点；如果其右子节点不为空，那么该节点的value值永远 <= 其右子节点
满二叉树：树中除了叶子节点，每个节点都有两个子节点
完全二叉树：在满足满二叉树的性质后，最后一层的叶子节点均需在最左边
完美二叉树：满足完全二叉树性质，树的叶子节点均在最后一层（也就是形成了一个完美的三角形）
满二叉树、完全二叉树、完美二叉树的定义是越来越严格的
AVL 树
AVL树本质上还是一个二叉搜索树，不过比二叉搜索树多了一个平衡条件：每个节点的左右子树的高度差不大于1。
二叉树的应用是为了弥补链表的查询效率问题，但是极端情况下，二叉搜索树会无限接近于链表，这种时候就无法体现二叉搜索树在查询时的高效率，而最初出现的解决方式就是AVL树。
因为二查搜索树的要求，所以遵循vale从小到大：左-> 中 ->右， 搜索的时候效率很高。
红黑树，因为只是满足平衡二叉树的左右两个子树高度差只有1的差距，所以插入和删除的效率更高，搜索的效率角度。
LSM
LSM 树
LSM（Log-Structured Merge-Trees）和 B+ 树相比，是牺牲了部分读的性能来换取写的性能(通过批量写入)，实现读写之间的。 Hbase、LevelDB、Tair（Long DB）、nessDB 采用 LSM 树的结构。LSM可以快速建立索引。
B+ 树读性能好，但由于需要有序结构，当key比较分散时，磁盘寻道频繁，造成写性能。
LSM 是将一个大树拆分成N棵小树，先写到内存（无寻道问题，性能高），在内存中构建一颗有序小树（有序树），随着小树越来越大，内存的小树会flush到磁盘上。当读时，由于不知道数据在哪棵小树上，因此必须遍历（二分查找）所有的小树，但在每颗小树内部数据是有序的。
《LSM树（Log-Structured Merge Tree）存储引擎》
极端的说，基于LSM树实现的HBase的写性能比MySQL高了一个数量级，读性能低了一个数量级。
优化方式：Bloom filter 替代二分查找；compact 小数位大树，提高查询性能。
Hbase 中，内存中达到一定阈值后，整体flush到磁盘上、形成一个文件（B+数），HDFS不支持update操作，所以Hbase做整体flush而不是merge update。flush到磁盘上的小树，定期会合并成一个大树。
二叉树
主要语义
- 普通平衡树的广度遍历和深度遍历和链表相比，相同的是存在不稳定性。不同的是最好的性能是logN, 最坏是n。
2. 二叉查找树最大特性是，左子树关键字 < 根节点关键字 < 柚子树关键字。这样能保证查找的时候是稳定的logN。 但是为了保存二叉树的特征，在插入和删除的时候，需要做必要的旋转。
AVL是强平衡二叉查找树， 查找的性能最稳定，数的高度也最低，但是插入和删除的时候，旋转太耗时。
红黑树是弱平衡树， 插入和删除的时候只需要达到红黑相间隔以及二叉树特性，故相对性能较好。 同时红黑的特征了也优化了查找路径，增加了约束，避免二叉树旋转N次后成为极端的线性链。
b树和b+树是多路查找树，也是平衡树。相当于在之前的二叉树增加一级索引：每一层允许关键字M，允许出现[2,M]个子节点，允许非叶子节点有关键字和指向子节点的指针，插入的时候不一定需要通过旋转来实现。 这样在非常复杂和庞大的基数数据中，可以极大的降低树的高度，增加查询和插入的性能。缺点就是单节点的计算边复杂了，如果cpu的计算能力很强的情况下，这点可以忽略。
6. b+数和b树的区别是b+树在b树的基础上优化了索引，使索引和关键字分开，且关键字只存在于叶子节点，简化了每一个节点的计算，当m变大的时候，优化程度越大；并且在增加和删除关键字的直接和存储卷功能相关，因为文件系统中是按页和块存储的， b树的数据变更存在跨多个页和块，而b+树是存在于树的叶子节点是，可以是连续存储空间，增加和删除都是性能很高的。 b+树在叶子节点增加了链指针，可以指向关键字代表的行记录或块记录。
旋转
b++插入和删除时涉及到叶子节点和索引节点的拆分、合并，索引下沉问题。在兄弟节点有富余，但是索引节点满的情况下还会 产生旋转。
https://blog.csdn.net/sunshine_lyn/article/details/82747596
二叉查找树
简介
二叉查找树也称为有序二叉查找树,满足二叉查找树的一般性质,是指一棵空树具有如下性质:
任意节点左子树不为空,则左子树的值均小于根节点的值.*
任意节点右子树不为空,则右子树的值均大于于根节点的值.*
任意节点的左右子树也分别是二叉查找树.*
没有键值相等的节点.*
参考：
https://www.cnblogs.com/feng9exe/p/8920738.html
B树特性
B树的性质
定义任意非叶子结点最多只有M个儿子；且M>2；
根结点的儿子数为[2, M]；
除根结点以外的非叶子结点的儿子数为[M/2, M]；
每个结点存放至少M/2-1（取上整）和至多M-1个关键字；（至少2个关键字）
非叶子结点的关键字个数=指向儿子的指针个数-1；
非叶子结点的关键字：K[1], K[2], …, K[M-1]；且K[i] < K[i+1]；
非叶子结点的指针：P[1], P[2], …, P[M]；其中P[1]指向关键字小于K[1]的子树，P[M]指向关键字大于K[M-1]的子树，其它P[i]指向关键字属于(K[i-1], K[i])的子树；
所有叶子结点位于同一层；
B+树特性
B+树的性质(下面提到的都是和B树不相同的性质)
非叶子节点的子树指针与关键字个数相同;
非叶子节点的子树指针p[i],指向关键字值属于[k[i],k[i+1]]的子树.(B树是开区间,也就是说B树不允许关键字重复,B+树允许重复)；
为所有叶子节点增加一个链指针.
所有关键字都在叶子节点出现(稠密索引). (且链表中的关键字恰好是有序的);
非叶子节点相当于是叶子节点的索引(稀疏索引),叶子节点相当于是存储(关键字)数据的数据层.
更适合于文件系统;
B-树是一种平衡的多路查找(又称排序)树，在文件系统中有所应用。主要用作文件的索引。其中的B就表示平衡(Balance)
B+树有一个最大的好处，方便扫库，B树必须用中序遍历的方法按序扫库，而B+树直接从叶子结点挨个扫一遍就完了。
B+树支持range-query(区间查询)非常方便，而B树不支持。这是数据库选用B+树的最主要原因。
比如要查 5-10之间的，B+树一把到5这个标记，再一把到10，然后串起来就行了，B树就非常麻烦。B树的好处，就是成功查询特别有利，因为树的高度总体要比B+树矮。不成功的情况下，B树也比B+树稍稍占一点点便宜。B树的优势是当你要查找的值恰好处在一个非叶子节点时，查找到该节点就会成功并结束查询，而B+树由于非叶节点只是索引部分，这些节点中只含有其子树中的最大(或最小)关键字，当非终端节点上的关键字等于给点值时，查找并不终止，而是继续向下直到叶子节点。因此在B+树中，无论查找成功与否，都是走了一条从根到叶子节点的路径。mysql底层存储是用B+树实现的，因为内存中B+树是没有优势的，但是一到磁盘，B+树的威力就出来了。
B*树
是B+树的变体，在B+树的非根和非叶子结点再增加指向兄弟的指针；B树定义了非叶子结点关键字个数至少为(2/3)M，即块的最低使用率为2/3（代替B+树的1/2）；
B+树的分裂：当一个结点满时，分配一个新的结点，并将原结点中1/2的数据复制到新结点，最后在父结点中增加新结点的指针；B+树的分裂只影响原结点和父结点，而不会影响兄弟结点，所以它不需要指向兄弟的指针；
B*树的分裂：当一个结点满时，如果它的下一个兄弟结点未满，那么将一部分数据移到兄弟结点中，再在原结点插入关键字，最后修改父结点中兄弟结点的关键字（因为兄弟结点的关键字范围改变了）；如果兄弟也满了，则在原结点与兄弟结点之间增加新结点，并各复制1/3的数据到新结点，最后在父结点增加新结点的指针；
所以，B树分配新结点的概率比B+树要低，空间使用率更高；*
B-树
1970年，R.Bayer和E.mccreight提出了一种适用于外查找的树，它是一种平衡的多叉树，称为B树（或B-树、B_树）。
一棵m阶B树(balanced tree of order m)是一棵平衡的m路搜索树。它或者是空树，或者是满足下列性质的树：
1、根结点至少有两个子女；
2、每个非根节点所包含的关键字个数 j 满足：┌m/2┐ - 1 <= j <= m - 1；
3、除根结点以外的所有结点（不包括叶子结点）的度数正好是关键字总数加1，故内部子树个数 k 满足：┌m/2┐ <= k <= m ；
4、所有的叶子结点都位于同一层。
是一种多路搜索树（并不是二叉的）：
1.定义任意非叶子结点最多只有M个儿子；且M>2；
2.根结点的儿子数为[2, M]；
3.除根结点以外的非叶子结点的儿子数为[M/2, M]；
4.每个结点存放至少M/2-1（取上整）和至多M-1个关键字；（至少2个关键字）
5.非叶子结点的关键字个数=指向儿子的指针个数-1；
6.非叶子结点的关键字：K[1], K[2], …, K[M-1]；且K[i] < K[i+1]；
7.非叶子结点的指针：P[1], P[2], …, P[M]；其中P[1]指向关键字小于K[1]的
子树，P[M]指向关键字大于K[M-1]的子树，其它P[i]指向关键字属于(K[i-1], K[i])的子树；
8.所有叶子结点位于同一层；
算法
算法分析
（1）复杂度分析
1）空间复杂度
2）时间复杂度：最好、最坏、平均、均摊。
（2）基本算法思想：贪心算法、分治算法、动态规划、回溯算法、枚举算法、倍增、二分。
算法实现
（1）排序
1）O(n^2)：冒泡、插入、选择、希尔。
2）O(NlogN)：归并、快速、堆
3）O(n)：计数、基数、桶。
（2）搜索：深度优先搜索、广度优先搜索、A*启发式搜索。
（3）查找：线性表查找、树结果查找、散列表查找。
（4）字符串匹配：朴素、KMP、Robin-Karp、Boyer-Moore、AC自动机、Trie、后缀数组。
（5）其他：数论、计算几何、概率分析、并查集、拓扑网络、矩阵运算、线性规划。
回溯算法
https://segmentfault.com/a/1190000018319044?utm_source=tag-newest
前缀树
https://www.cnblogs.com/luosongchao/p/3239521.html
深度优先和广度优先
https://www.cnblogs.com/whywhy/p/4888632.html
动态规划
动态规划的解题核心主要分为两步：
第一步：状态的定义
第二步：状态转移方程的定义
在这里，我们为了避免混淆用“状态”这个词来替代“问题”这个词。“问题”表示的含义类似：题目、要求解的内容、题干中的疑问句这样的概念。状态表示我们在求解问题之中对问题的分析转化。
第一步：状态的定义
有的问题过于抽象，或者过于啰嗦干扰我们解题的思路，我们要做的就是将题干中的问题进行转化（换一种说法，含义不变）。转化成一系列同类问题的某个解的情况，比如说：
题目：求一个数列中最大连续子序列的和。
我们要将这个原问题转化为：
状态定义：Fk是第k项前的最大序列和，求F1～FN中最大值。
通过换一种表述方式，我们清晰的发现了解决问题的思路，如何求出F1～FN中的最大值是解决原问题的关键部分。上述将原问题转化成另一种表述方式的过程叫做：状态的定义。这样的状态定义给出了一种类似通解的思路，把一个原来毫无头绪的问题转换成了可以求解的问题。
第二步：状态转移方程的定义
在进行了状态的定义后，自然而然的想到去求解F1～FN中最大值。这也是状态定义的作用，让我们把一个总体的问题转化成一系列问题，而第二步：状态转移方程的定义则告诉我们如何去求解一个问题，对于上述已经转换成一系列问题我们要关注的点就在于：如何能够用前一项或者前几项的信息得到下一项，这种从最优子状态转换为下一个最优状态的思路就是动态规划的核心。
对于上面的例子题目来说，状态转移方程的定义应该是：
Fk=max{Fk-1+Ak,Ak}
Fk是前k项的和，Ak是第k项的值
仔细思考一番，我们能够得到这样的结论，对于前k个项的最大子序列和是前k-1项的最大子序列和Fk与第k项的和、或者第k项两者中较大的。如果大家还是不能理解这个原理建议用演算纸自己计算一番，这里就不过多赘述了。这种状态转移的思路就是DP的核心。
动态规划
动态规划（英语：Dynamic programming，简称 DP）是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。
动态规划常常适用于有重叠子问题和最优子结构性质的问题，动态规划方法所耗时间往往远少于朴素解法。
动态规划背后的基本思想非常简单。大致上，若要解一个给定问题，我们需要解其不同部分（即子问题），再根据子问题的解以得出原问题的解。动态规划往往用于优化递归问题，例如斐波那契数列，如果运用递归的方式来求解会重复计算很多相同的子问题，利用动态规划的思想可以减少计算量。
通常许多子问题非常相似，为此动态规划法试图仅仅解决每个子问题一次，具有天然剪枝的功能，从而减少计算量：一旦某个给定子问题的解已经算出，则将其记忆化存储，以便下次需要同一个子问题解之时直接查表。这种做法在重复子问题的数目关于输入的规模呈指数增长时特别有用
贪心算法
记录中间状态，拆解子问题、子状态，当前决策是否影响后续的决策。寻求最优解。
如何拆解子问题
按串行任务分
时间串行的任务，按子任务来分解，即每一步都是在前一步的基础上再选择当前的最优解。
按规模递减分
规模较大的复杂问题，可以借助递归思想（见第2课），分解成一个规模小一点点的问题，循环解决，当最后一步的求解完成后就得到了所谓的“全局最优解”。
按并行任务分
这种问题的任务不分先后，可能是并行的，可以分别求解后，再按一定的规则（比如某种配比公式）将其组合后得到最终解。
动态规划和贪心
动态规划可以用到回溯， 也可以用记忆法来优化重复计算。
动态规划是一种自顶向下的方法。
贪心法是一种自底向上的方法，避免回溯。也就是从解向起始条件靠近
KMP算法
https://www.cnblogs.com/ZuoAndFutureGirl/p/9028287.html
