一些概念及算法题
1. 一些数据结构
1.1 线性表
线性表中数据元素之间的关系是一对一的关系，即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的（注意，这句话只适用大部分线性表，而不是全部。 我们说“线性”和“非线性”，只在逻辑层次上讨论，而不考虑存储层次，所以双向链表和循环链表依旧是线性表。
特征：
- 1．集合中必存在唯一的一个“第一元素”。
- 2．集合中必存在唯一的一个 “最后元素” 。
- 3．除最后一个元素之外，均有 唯一的后继(后件)。
- 4．除第一个元素之外，均有 唯一的前驱(前件)。
我们常见的链表，数组，字符串，栈，队列等都是线性表。
1.2 平衡二叉树
平衡二叉树是基于二分法的策略提高数据的查找速度的二叉树的数据结构。
平衡二叉树是采用二分法思维把数据按规则组装成一个树形结构的数据，用这个树形结构的数据减少无关数据的检索，大大的提升了数据检索的速度；
平衡二叉树的数据结构组装过程有以下规则：非叶子节点只能允许最多两个子节点存在，每一个非叶子节点数据分布规则为左边的子节点小当前节点的值，右边的子节点大于当前节点的值(这里值是基于自己的算法规则而定的，比如hash值)；
平衡树的层级结构：因为平衡二叉树查询性能和树的层级（h高度）成正比、为了保证树的结构左右两端数据大致平衡降低二叉树的查询难度一般会采用一种算法机制实现节点数据结构的平衡，实现了这种算法的有比如AVL、Treap、红黑树，使用平衡二叉树能保证数据的左右两边的节点层级相差不会大于1，通过这样避免树形结构由于删除增加变成线性链表影响查询效率，保证数据平衡的情况下查找数据的速度近于二分法查找。
特点：
- 1.非叶子节点最多拥有两个子节点；
- 2.非叶子节值大于左边子节点、小于右边子节点；
- 3.树的左右两边的层级数相差不会大于1;
- 4.没有值相等重复的节点;
其插入和调整都比较复杂，需要进行旋转操作。
1.3 B/B-树
B树和B-树实际上是同一种树据结构。
B树和平衡二叉树稍有不同的是B树属于多叉树又名平衡多路查找树（查找路径不只两个），数据库索引技术里大量使用者B树和B+树的数据结构。
其构建规则如下：
（1）树中的每个节点最多拥有m个子节点且m>=2,空树除外（注：m阶代表一个树节点最多有多少个查找路径，m阶=m路,当m=2则是2叉树,m=3则是3叉）；意思就是这个树是一个m叉树。
（2）除根节点外每个节点的关键字数量大于等于ceil(m/2)-1个小于等于m-1个，非根节点关键字数必须>=2;（注：ceil()是个朝正无穷方向取整的函数 如ceil(1.1)结果为2)
（3）所有叶子节点均在同一层、叶子节点除了包含了关键字和关键字记录的指针外也有指向其子节点的指针只不过其指针地址都为null对应下图最后一层节点的空格子
（4）如果一个非叶节点有N个子节点，则该节点的关键字数等于N-1;
（5）所有节点关键字是按递增次序排列，并遵循左小右大原则；
查询流程：
如上图我要从上图中找到E字母，查找流程如下
（1）获取根节点的关键字进行比较，当前根节点关键字为M，E要小于M（26个字母顺序），所以往找到指向左边的子节点（二分法规则，左小右大，左边放小于当前节点值的子节点、右边放大于当前节点值的子节点）；
（2）拿到关键字D和G，D<E<G 所以直接找到D和G中间的节点；
（3）拿到E和F，因为E=E 所以直接返回关键字和指针信息（如果树结构里面没有包含所要查找的节点则返回null）；
插入节点流程：
定义一个5阶树（平衡5路查找树;），现在我们要把3、8、31、11、23、29、50、28 这些数字构建出一个5阶树出来;
遵循规则：
（1）当前是要组成一个5路查找树，那么此时m=5,关键字数必须大于等于cei(5/2)小于等于5-1（关键字数小于cei(5/2) -1就要进行节点合并，大于5-1就要进行节点拆分,非根节点关键字数>=2）；
（2）满足节点本身比左边节点大，比右边节点小的排序规则;
删除:
（1）当前是要组成一个5路查找树，那么此时m=5,关键字数必须大于等于cei(5/2)-1，小于等于5-1，非根节点关键字数大于2；
（2）满足节点本身比左边节点大，比右边节点小的排序规则;
（3）关键字数小于二时先从子节点取，子节点没有符合条件时就向向父节点取，取中间值往父节点放；
特点：
B树相对于平衡二叉树的不同是，每个节点包含的关键字增多了，特别是在B树应用到数据库中的时候，数据库充分利用了磁盘块的原理（磁盘数据存储是采用块的形式存储的，每个块的大小为4K，每次IO进行数据读取时，同一个磁盘块的数据可以一次性读取出来）把节点大小限制和充分使用在磁盘快大小范围；把树的节点关键字增多后树的层级比原来的二叉树少了，减少数据查找的次数和复杂度;
1.4 B+树
B+树是B树的一个升级版，相对于B树来说B+树更充分的利用了节点的空间，让查询速度更加稳定，其速度完全接近于二分法查找。为什么说B+树查找的效率要比B树更高、更稳定；
两者的区别
（1）B+跟B树不同B+树的非叶子节点不保存关键字记录的指针，这样使得B+树每个节点所能保存的关键字大大增加；
（2）B+树叶子节点保存了父节点的所有关键字和关键字记录的指针，每个叶子节点的关键字从小到大链接；
（3）B+树的根节点关键字数量和其子节点个数相等;
（4）B+的非叶子节点只进行数据索引，不会存实际的关键字记录的指针，所有数据地址必须要到叶子节点才能获取到，所以每次数据查询的次数都一样；
1.5 哈夫曼树
给定n个权值作为n个叶子结点，构造一棵二叉树，若带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。
相近概念：哈夫曼编码
哈夫曼树（霍夫曼树）又称为最优树.
1、路径和路径长度 在一棵树中，从一个结点往下可以达到的孩子或孙子结点之间的通路，称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为1，则从根结点到第L层结点的路径长度为L-1。
2、结点的权及带权路径长度 若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。结点的带权路径长度为：从根结点到该结点之间的路径长度与该结点的权的乘积。
3、树的带权路径长度 树的带权路径长度规定为所有叶子结点的带权路径长度之和，记为WPL。
构造哈夫曼树：
设有n个权值，则构造出的哈夫曼树有n个叶子结点。 n个权值分别设为 w1、w2、…、wn，则哈夫曼树的构造规则为：
(1) 将w1、w2、…，wn看成是有n 棵树的森林(每棵树仅有一个结点)；
(2) 在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；
(3)从森林中删除选取的两棵树，并将新树加入森林；
(4)重复(2)、(3)步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树。
1.6 哈希表
散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。
给定表M，存在函数f(key)，对任意给定的关键字值key，代入函数后若能得到包含该关键字的记录在表中的地址，则称表M为哈希(Hash）表，函数f(key)为哈希(Hash) 函数。
哈希表是一种通过哈希函数将特定的键映射到特定值的一种数据结构，他维护者键和值之间一一对应关系。
- 键(key)：又称为关键字。唯一的标示要存储的数据，可以是数据本身或者数据的一部分。
- 槽(slot/bucket)：哈希表中用于保存数据的一个单元，也就是数据真正存放的容器。
- 哈希函数(hash function)：将键(key)映射(map)到数据应该存放的槽(slot)所在位置的函数。
- 哈希冲突(hash collision)：哈希函数将两个不同的键映射到同一个索引的情况。
哈希冲突就是指不同的键值k1,k2在哈希函数h(x)映射下到了相同的slot自然，有冲突就会有解决方案。
Open Hashing 拉链法
h(x) = x mod 10是一个哈希函数，可见代入x=91和x=1的时候都会到映射到键值为1的slot，那么这样就会引发冲突，在拉链法中，用链表延展去存储同键值的数据。
优点： 拉链法处理冲突简单，且无堆积现象，即非同义词决不会发生冲突，因此平均查找长度较短； 在用拉链法构造的散列表中，删除结点的操作易于实现
缺点： 在对链表进行存储空间分配的时候，会降低整个程序的运行速率
2. 树的遍历方法比较
二叉树的遍历主要有5种，前序、中序、后序、深度优先、广度优先
遍历的实现方式主要是：递归和非递归
递归遍历的实现非常容易，非递归的实现需要用到栈，难度系数要高一点。
前序遍历：先访问根节点，再访问左子树，最后访问右子树 用递归或者堆栈实现。
中序遍历：先访问左子树，再访问根节点，最后访问右子树 用递归或者堆栈实现。
后序遍历：先访问左子树，再访问右子树，最后访问根节点 用递归或者堆栈实现。
广度优先：每一层从左到右访问每一个节点。 用队列实现
深度优先：先访问根节点，然后访问完左子树再访问右子树。 用递归或者堆栈实现。实际上，前序、中序、后序都可以认为是深度优先的特例，特别是前序遍历。
- 使用栈来实现。相关算法实现总结为：
（1） 将初始节点压栈。
（2） While(栈非空) {
（3） 取出栈顶点，暂时存储这个节点node_t信息。
（4） 访问该节点，并且标示已访问。
（5） 将栈顶元素出栈。
（6） For(遍历node_t的相邻的未访问过的节点){
（7） 将其入栈。
（8） }
（9） }
注意事项：一定要先将该访问节点出栈后，再将其邻接的未访问的节点入栈。切记不要，之前我的经历，如果没有邻接点就出栈，否则就不出栈，但是标记了该节点为访问节点的。
- 使用递归来实现。相关算法实现总结为：
（1） DFS（初始节点）
（2） Function DFS(一个节点) {
（3） 访问该节点，并且标示已访问。
（4） For(遍历该节点的相邻的未访问过的节点) {
（5） DFS（这个邻接节点）。
（6） }
（7） }
3. 逆波兰式
逆波兰表示法（Reverse Polish notation，RPN，或逆波兰记法），是一种是由波兰数学家扬·武卡谢维奇1920年引入的数学表达式方式，在逆波兰记法中，所有操作符置于操作数的后面，因此也被称为后缀表示法。逆波兰记法不需要括号来标识操作符的优先级。
逆波兰记法广泛地被用于台式计算器，因此也在普通公众（工程、商业和金融领域）中使用。
以一个表达式 2 * 3 + 1为例。
以顺序方式输入这个表达式，计算机首先需要解析这个表达式，然后递归的求值。
比如从左起进行顺序解析，得到一个符号树：
+
/ \
* 1
/ \
2 3
计算机会递归的从叶子开始求值，最后回到根，得出结果。
所以对于一个比较复杂的表达式，树可能会很深，而且递归的过程将会消耗大量的内存，由于有解析和运算两个过程，时间开销也不理想。
如果将上式改为逆波兰表达式： 3 2 * 1 + 那么就能实现 “在线处理”。在线处理必须是这类问题在计算机中最快的算法。
创建过程:
先按照算式，构造符号树; 逆波兰式：对树进行后序遍历； 波兰式：对树进行先序遍历；
References
[1] 平衡二叉树、B树、B+树、B*树 理解其中一种你就都明白了 https://zhuanlan.zhihu.com/p/27700617 [2] 全面剖析树的各类遍历方法 https://blog.csdn.net/terence1212/article/details/52182836 [3] 逆波兰式到底是什么鬼 ？ https://www.zhihu.com/question/41103160 [4] 逆波兰表示法 https://zh.wikipedia.org/wiki/%E9%80%86%E6%B3%A2%E5%85%B0%E8%A1%A8%E7%A4%BA%E6%B3%95