数据结构考研笔记

栈

$$
{C^2_{2n}/(n+1)}\
这个东西可能还有一个问法，比如说他说先序序列为a,b,c,d的二叉树的个数，其实就是问你四个的进栈顺序有多少个
$$

中缀转后缀表达式

正常方式（利用栈的方式）（考试可能会问你符号栈有多少个元素）

遇到数字，直接加入后缀表达式

遇到操作符：

1. 左括号：直接入栈
2. 右括号：将符号栈依次弹出，直到遇到一个左括号为止，把遇到的左括号删除而不是弹出
3. 其他：栈空、栈顶为左括号或者比当前符号优先级低的符号就直接入栈，否则就以此弹出直到遇到前面三种情况再入栈。

一个取巧的方式

1)先按照运算符的优先级对中缀表达式加括号，变成( ( a+(b * c) ) + ( ((d*e)+f) *g ) )

2)将运算符移到括号的后面，变成((a(bc) * )+(((de) * f)+g)*)+

3)去掉括号，得到abc*+def+g+

KMP模式匹配

其实只要会算next数组就可以啦

平衡二叉树

定义

任意节点的左右子树高度绝对值不大于1，左子树与右子树的高度差称为平衡因子

平衡方法

当插入新节点时，先检查有无破坏性质，若破坏了，找到离插入节点最近的平衡因子绝对值大于1的节点，让他作为根，设为A，来调整他的子树，然后会有以下四种情况，这四种情况名字很好记和对应不平衡的原因联系起来记比价好记，具体的操作直接看名字就能记忆，结合例子懂得更深。

LL，即A的左孩子的左子树插入了导致不平衡（下面的都同理就不写了），用一个右旋即可

RR，用一个左旋

LR，先左旋再右旋，这个左旋是子树的旋，后面右旋是A的旋

RL，先右旋再左旋

线索二叉树

相当的easy啊，就是写出序列然后直接前后少了就填对应的就可以了，这就叫线索化啊

哈夫曼树

定义

哈夫曼树可以解决如下问题：给定N个带权值的叶子节点，如何构造出一个带权路径长度（WPL）最小的二叉树，带权路径即从根节点到叶子节点经历的边的数量乘叶子节点的权值。此外，这种二叉树也就是哈夫曼树的定义。

构建

构建其实很简单，下面以二叉哈夫曼树为例 给n个点，每个点都有权值，构造一棵哈夫曼树。每次选剩下的两棵根权值最小的树合并成一棵新树，新树的根权值等于两棵合并前树的根权值和。（一开始一个点也看成一棵树，只不过这棵树没有孩子节点）

哈夫曼树中只有度为0和度为2的节点，且n0=n2+1（这个的证明很简单，因为度为1的节点不会产生新的叶节点，一个度为2的产生一个叶子节点，再加上原本的根节点就得到这个公式了，然后哈夫曼树是最优二叉树所以没有度为1的节点）

哈夫曼编码

一篇电文，原文为：AMCADEDDMCCAD。现在要把原文转换成01串发送给对方。为了节省资源，我们当然希望翻译好的01串长度尽量的短。怎么办？

分析，我们当然希望用的最多编码的串更短，并且不能出现歧义（这时候就要用前缀码了，即没有一个编码是其他编码前缀的编码），这样的话正好就可以用哈夫曼树了，将出现次数视为权值，然后来做

树、森林和二叉树互换

有时候我一直很困惑树和森林的区别是什么，其实森林就是m棵互不相交的树的集合，树删掉了根节点就变成了森林。

树转换为二叉树

左兄弟右孩子，所以转换出来的二叉树没有右子树

森林转换为二叉树

把每一个树转换为二叉树，然后再根据左孩子右兄弟来转换（根视为兄弟），这个逆过程也得会，稍微思考一下就懂了。

二叉树转换为森林

将右孩子断了，然后将，再对断了的右子树递归进行此操作直到没有右子树为止。然后再对每一个树转换为二叉树。

树的先序遍历与其转换的相应的二叉树的先序遍历的结果序列相同；树的后序遍历与其转换的二叉树的中序遍历的结果序列相同；树的层序遍历与其转换的二叉树的后序遍历的结果序列相同。由森林与二叉树的转换关系以及森林与二叉树的遍历定义可知，森林的先序遍历和中序遍历与所转换得到的二叉树的先序遍历和中序遍历的结果序列相同

堆排序（其实也是二叉树的应用）

堆一般是一种完全二叉树，分为最大堆和最小堆，最大堆即每个父节点都大于子节点，最小堆同理。

堆排序顺序，创建堆，调整堆，堆排序。

主要是后两部，调整堆即把一个堆变成最大/最小堆，堆排序即将排好的堆的根以此输出（交换元素），并且要维持堆的性质不变。

调整堆

这个调整是一切的基础，以最大堆距离，简单来说是一个迭代的过程，从最后一个元素往前开始，要是此元素小于左右子树的最大值，就把根与该值交换，不断重复直到完全满足要求。

堆排序（交换元素）

将根与最后一个没排序好的元素交换，此中要一直保持堆的性质不变

插入元素

插入先插入末尾，然后向上执行调整操作

B+树B-树

B树和B+树是一种查找的手段，主要解决磁盘读取慢的问题

n阶B树至少要关键词达到n个才分裂

m阶B树的性质：

1. 每个结点最多有m个子树，即最多m-1个关键字
2. 除根节点外的非叶节点至少得有m/2（向上取整）个子树，即最少要有m/2（向上取整）-1个关键字
3. 若根节点不是终端结点，则至少有两颗子树
4. 所有叶节点在同一层次上，且不带信息（表示查找过程）

m阶B+树的性质：

1. 每个分支阶段最多有m棵子树
2. 除根节点外的非叶节点至少得有m/2（向上取整）个子树，即最少要有m/2（向上取整）-1个关键字

区别：

1. B+树具有n个关键字的结点只有n棵子树，但是B树有n+1棵（所以他们结点数量的最大最小值也不一样嗷）
2. B+树叶结点包含信息，B树中

图的应用

图的一堆杂七杂八的概念

完全图：对于无向图，边的最大值是n * (n-1)/2，取得最大值的无向图叫完全图，对于有向图同理，但是有向图最大值为n * (n-1)

连通：若从顶点v到顶点w有路径存在，则称v和w是连通的

连通图：任意两个顶点都是连通的

连通分量：无向图中的极大连通子图成为连通分量

强连通：有向图中，若两个顶点互相都有路径则叫强联通

强联通图：任何一对顶点都是强联通的

强联通分量：极大强联通子图

关键路径是AOE网从起点到终点的最长路径

一个边对应两个度，一些计算题可以这样算

存储方法

1. 连接矩阵：就是一个n阶方阵，要注意如果是有向图那么(i,j)代表顶点i到顶点j有边

2. 邻接表法：每个点一个链表，链表里的值代表和该点相连的点

3. 十字链表：

拓扑排序

可以先修课程，即没修某门课不能上一门课

生成方法：1.选择一个没有前驱的顶点并输出2.删除该顶点和所有以它为起点的边，然后重复以上过程

做题数有几个拓扑排序可以采用树的方法，这样比较清晰，不多谈，你应该懂得。

记住拓扑排序必须要包括全部的元素

最小生成树&最短路径

搞清楚递归过程和结束条件

最小生成树

Prim算法

任取一点加入点集，然后找与现在点相连的边中最小的边（且不能是已经有的点）将该点加入点集，直到全部点都选完

这个适合边多点少的图

Kruskal算法

先把边按照权值大小排列好，把点都打散（这样每个点自成一个连通分量）然后依次选择，如果这个边连接了不同的连通分量，就加入，否则选下一个，以此直到都连通。

这个适合边少点多的图

最短路径

Dijkstra（是找一个点到全部点的最短路径）

从某一点出发，寻找该点最小的边，然后加入，然后也把这个点的边加入进来考虑最小，直到所有的点都有最短路径。

Floyd算法

其实就是一个动态规划，理解这个状态转移方程即可
$$
dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j])
$$

排序

归并排序

m路平衡归并：就是讲m个有序表组合成一个新的有序表，经过一趟后剩下的记录数是原来的1/m，所以要求最少的几趟n就是用记录数x/m^n向上取整求最小的，但是也不能太大，太大可能不用那么多。

败者树高度为ceil(log2k)+1所以比较次数为个数*高度

基数排序

总结

选择排序无论如何都是O（n方）的复杂度

索引表查找

这个我个人觉得可以理解为二维的二分查找，懂了这个之后就很容易推了，假设一共有n个元素，那么就分成n^1/2组，每组n^1/2个元素，先对组进行查找，再在组内进行查找。

折半查找最多次数为log2N（向下取整）+1

AVL：二叉查找树（Adelson-Velsky-Landis Tree）:是带有平衡条件的BST

BST：二叉排序树（Binary Search Tree）：左子树值<=根值<=右子树

散列表查找

构造方法

处理冲突方法

开放定址法

Hi=(H(key)+di)%m（下面的方法就是d的取法不同）

线性探测法

d取0,1,2……其实就是遇到冲突逐个往后找空闲的位置放下，但这样会造成同义词的堆叠

平方探测法

d取0^2,1^2,-1^2……不会堆叠，但最多只能查找一半的长度

再散列法

di=i*H2(key)

伪随机序列法

d=伪随机序列

拉链法

把所有的同义词都放在同一地址，用线性链表存储，适合经常进行插入和删除的序列

怎么算成功平均查找长度和失败平均查找长度

成功平均长度很容易算，就算每一个value要用给定的构造函数和处理方法算几遍才能得到就可以

失败怎么理解呢？首先你这个数只有可能落在0-p-1的范围内，那你怎么才能知道自己不成功呢？就是一直往后找（这个往后找的意思是用冲突处理的办法来不断往后）遇到一个空的时候就说明肯定没有了呀，就说明你这个元素不在表里，然后把这个结果记录下来，再取平均。

查找概率

很长一段时间不太懂这个词到底什么意思，其实就是查的这个词在不在这一堆记录的概率，用来算平均查找长度的话就是查找概率 * 成功平均查找长度 + （1 - 查找概率） * 失败平均查找长度

装填因子表示一个表装满的程度，当然越满越容易发生冲突

新考点

并查集

红黑树

平衡二叉树插入删除很容易破坏平衡特性，破坏了需计算平衡因子，找最小不平衡子树

而红黑树无需频繁调整树的形态，调整也可以常数时间内完成。

所以，平衡二叉树适用于查为主，红黑树适用于频繁删除插入

可能考定义、性质，手绘插入

定义

1. 左<根<右

2. 每个结点要么是红色要么是黑色

3. 根节点和叶节点（外部结点，NULL结点，失败结点，不包含关键字）都是黑色的

4. 不存在两个相邻的红结点（即一个红结点的父亲和儿子都不能是红结点，兄弟不算连续）（即查找路径不能连续两个红结点）

5. 任一结点到它下面的任一叶节点经历的路径的黑结点数量必须都一样

结点的黑高：从某结点出发（不含该结点）到达任一空叶节点的路径上的黑结点总数

性质

1. 从根节点到叶节点的最长路劲不大于最短路径的2倍
2. 有n个内部结点的高度h<2log2(n+1)（所以查找操作复杂度O(log2n)

插入

插入为根：染成黑色

插入非根：染成红色（因为不会改变黑结点的个数，这样就不会改变顺序）

如果满足定义，则插入结束

如果不满足（只用看是否不满足不红红，因为不会改变黑色节点数量），则需要调整（看叔叔的脸色，即父亲结点的兄弟的颜色）

叔叔为黑色：旋转+染色

• LL：右单旋，父换爷+染色
• RR：左单旋，父换爷+染色
• LR：左、右双旋，儿换爷+染色
• RL：右、左双旋，儿换爷+染色

叔叔为红色：染色+变新

• 叔父爷染色，爷变为新结点