Data structure review

数据结构总复习笔记

绪论

数据结构三元素：逻辑结构、存储结构、数据在运算上的实现。

逻辑结构：集合、线性、树、图

存储结构：顺序、链式、索引、散列

Note. 逻辑结构为树但存储结构可以为顺序，例如使用数组存储一棵完全二叉树。

向量与列表

二分查找

性质1：折半查找判定树是平衡二叉树，其高度差要么为 \(0,1\)，要么为 \(0,-1\)。

Prof. 当前序列为奇数个时，一定能保证两侧数量相同；当前序列为偶数个时，要么为 \(\left\lceil\dfrac{l+r}{2}\right\rceil\)，要么为 \(\left\lfloor\dfrac{l+r}{2}\right\rfloor\)，对应高度差为 \(1\) 和 \(-1\)，递归调用时一般不会更改中位数的选取，从而高度差要么非负、要么非正。

性质2：二分查找次数形成的树高为 \(\left\lceil\log _{2}(n+1)\right\rceil\)

Prof. \(2^0+\dots+2^{h-1}\leq n\leq2^0+\dots+2^{h}\Longrightarrow h\in[\log _2(n+1)-1,\log _{2}(n+1)]\)

栈与队列

（括号）匹配操作需要借助栈。

栈模拟队列

使用两个栈模拟队列，记“大小栈”容量为 \(M,N(M>N)\)，能够模拟的队列最大容量为 \(2N+1\)。

Prof. \(1,\cdots,N\) 入大栈，依次弹出进入小栈，大栈加入 \(N+1,\cdots,2N+1\)，因为还可以保留一个。输出队列时，小栈先依次弹出为 \(1,\cdots,N\)，大栈弹出 \(2N+1,\cdots N+2\) 进入小栈，剩下一个 \(N+1\)，先弹出 \(N+1\)，再弹出小栈中的元素，恰好形成一个队列。

表达式求值

前后缀表达式求值仅需维护一个数字栈。

后缀表达式：从左往右依次数字入栈，遇到操作符将栈顶的两个元素计算后结果入栈。

前缀表达式：从右往左依次数字入栈，遇到操作符将栈顶的两个元素计算后结果入栈。

Note. 如果有括号将内部计算均做完后左右括号出栈。

性质1：将表达式转换为二叉🌲，前缀、中缀、后缀表达式依次对应二叉树的前序、中序、后序遍历。

Note. 在构建时 \(\neg\neg P\) 前序为 \(\neg\neg P\)，后序则为 \(P\neg\neg\)。

树的结构

以下讨论皆规定根节点🌲高为 \(1\)，\(V\) 为🌲的节点个数，度为 \(i\) 的数目为 \(n_i\)，🌲的度 \(d\) 定义为所有节点度的最大值，度为 \(d\) 且有左右树之分的树称作 \(d\) 叉🌲，满足 \[ \begin{equation} V=\sum_{i=0}^{d} n_i \end{equation} \]

基本特性

对任何🌲 可以看成最小连通图，顶点的数目比度的总数多 \(1\)，即 \[ \begin{equation} 1+\sum_{i=1}^{d} in_i=V \end{equation} \] 给定一棵树的部分 \(n_i\)，使用公式 (1)(2) 可以获取许多信息。

二叉树

对一棵二叉树度为 \(2\) 的点有 \(n_2\) 个，叶节点（度为 \(0\)）的点有 \(n_0\)，则 \[ \begin{equation} n_0=n_2+1 \end{equation} \]

Prof. 二叉树代入公式(1) \(1+0\cdot n_0+1\cdot n_1+2\cdot n_2=n_0+n_1+n_2\) 即证。

具有 \(n\) 个节点的二叉树的最小深度为 \(\log_2(n+1)\)。

二叉树遍历方式

1. 广度优先遍历（层次遍历，使用队列模拟，记所有层中数量最大的为 \(F\)，队列最大容量为 \(F\) 中的节点数）

2. 深度优先遍历

   先序遍历 根左右（可以看成绕🌲外围一圈，图的深度优先遍历来源）

   

   中序遍历 左根右（可以看成顺次掉落，其为有序的，无论平衡与否）

   

   后序遍历 左右根（可以看成从左往右依次剪葡萄）

   

使用递推的方式遍历二叉树需要栈

性质1：完全确定二叉树至少需要中序遍历以及另外一种遍历，先序遍历和后序遍历不能完全确定一棵二叉树，除非保证每个节点的度为偶数。

Prof. 中序遍历为左根右，前序或者后序遍历能给出根节点，从而能够区分出左右子树节点集合，对左右子树递归操作，能构建完整树。而先序和后序当存在度为 \(1\) 的节点时叶节点可左可右，当每个节点的度为偶数时保证可重建二叉树。

性质2：若一棵二叉树的前序遍历和后序遍历相反，则该二叉树为链状。

Prof. 反证法，若有个节点有左右子树，则前序和后序遍历不互为逆序。

据此可求出已知前序遍历和后序遍历（记作 \(A\) 和 \(B\)）条件下构建二叉树的方法：\(A\) 的第一位和 \(B\) 的最后一位均为根节点，去掉这两位，判断剩下 \(A\) 首位和 \(B\) 的末尾是否相同，若相同，则该位与根节点形成“链表”，依此类推，若不同，则分别为左右子树的根节点，以两者的位置分别确定每棵子树的集合。剩下子树同样按照上述流程，同理，只要存在逆序字符串，该字符串对应的拓扑结构一定为链状。

性质3：若一个🍃为二叉树中序遍历最后一个节点，则该节点也为前序遍历最后一个节点，反之不成立。

Prof. 中序遍历为左根右，最后一个节点为🍃，则该叶子一定在右子树，依次递推下去，该叶子一定为若干个右子树最后的叶子，在前序遍历时一定作为最后一个节点。反之，若🍃节点为前序遍历最后一个节点，其可以为左子树的🍃，此时中序遍历最后一个节点可以为根节点，即反过来不成立。在🍃时成立中序最后 \(\Longrightarrow\) 前序最后。

子集树：\(n\) 个元素集合的子集可以看成是一颗叶子节点数为 \(2^{n}\) 的满二叉树，左和右分别代表选择或者不选。

二叉排序树：左子树所有元素值小于根节点，右子树所有元素值大于根节点。（二叉树不要求平衡）

性质4：二叉排序树插入节点的复杂度为 \(O(n)\)。

Prof. 最坏情况退化成链表，复杂度为 \(O(n)\)。

性质5：若排列组合随机，二叉树高度为 \(O(\log n)\)；若形状随机，高度则为 \(O(\sqrt{n})\)。

Prof. 前者证明参考算法导论二叉搜索树最后一节，后者证明参考论文，过于复杂，

完全二叉树

定义：除了最后一层外，其他各层全是满的， 并且最后一层的节点尽可能往左靠。

性质6：总点数为 \(n\) 的完全二叉树的非叶子节点如下 \[ \begin{equation} 完全二叉🌲,\sum _{叶子节点}1=\lceil \dfrac{n}{2}\rceil \end{equation} \]

Prof. 完全二叉树只有最后一层度为 \(1\) 的点为 \(0,1\)，即 \(n_1=0,1\)，代入 \(n_0=n_2+1,n=n_0+n_1+n_2\)，解得 \(n_0=\dfrac{n}{2},\dfrac{n+1}{2}=\lceil \dfrac{n}{2}\rceil\)。

性质7：🍃节点数为 \(n\) 的完全二叉树节点总数为 \(2n-1,2n\)，共 \(2\) 种。

Prof. 注意完全二叉树度为 \(1\) 的节点个数为 \(n_1=0,1\)，有两种情况。

完全二叉树的🍃可能在最后一层，可能在倒数第二层，对应两种情况。例如一棵高度为 \(h\) 的完全二叉树第 \(i\) 层有 \(x\) 个叶子，计算完全二叉树的节点数需要考虑该层为倒数第二层或者倒数第一层。

性质8：完全二叉树从 \(1\) 开始顺次标号，则标为 \(n\) 的节点左右节点为 \(2n\) 和 \(2n+1\)。

Note. 一般的二叉树没有这样的性质，其放在数组中有许多元素为空。

平衡二叉树

定义：\(\forall\ 节点,|h_{l}-h_{r}|\leq 1\)，即任意节点左右子树的高度差不大于 \(1\)。

性质9：令数列 \(\text{Fib}(n)\) 满足 \(\text{Fib(1)}=\text{Fib(2)}=1,\text{Fib(n+2)}=\text{Fib(n+1)}+\text{Fib(n)}\)，则总高度为 \(h\) 的平衡二叉树节点数量满足 \[ \begin{equation} V_h \in\left[\operatorname{Fib}(h+2)-1,2^h-1\right] \end{equation} \]

Prof. 对树高为 \(h\) 平衡二叉树，构造左右子树分别为 \(h-1\) 和 \(h-2\) 对应的最少平衡二叉树，满足平衡二叉树条件，且任意少一个节点要么让树高小于 \(h\)，要么不平衡，该构造为充分必要的，从而 \(V_{\min}(h)=V_{\min}(h-1)+V_{\min}(h-2)+1\)，则左边得证。右边为满二叉树情形 \(2^0+2^1+\cdots+2^{h-1}=2^h-1\)。

真二叉树

定义：所有节点的度为 \(0\) 或 \(2\) 的二叉树，如哈夫曼树。

树的应用

森林转换

有序树定义为兄弟节点有次序的树。

有序树转换为二叉树：先将每棵多叉树转换为二叉树，每个节点而言，“左孩子右兄弟” ，即初始左孩子仍为其左孩子，初始（右侧）兄弟转换为右孩子。

二叉树转换为有序树：作为上述过程的逆过程，将右孩子变为兄弟即可。

性质1：一棵森林中树的数目等于总节点数减去总边数。

性质2：有序树的遍历仅有前序和后序，分别等于转换后二叉树的前序和中序。

Prof. 构造基本有序树 \(\begin{gathered}b\ \newline/\quad \backslash\\a\quad\ \ c\end{gathered}\)，其转换为二叉树 \(\begin{gathered}b\ \\/\quad \newline a\longrightarrow c\end{gathered}\)，满足前者前序序列等于后者前序序列 \(bac\)，前者后序序列等于后者中序序列 \(acb\)。

性质3：给定有序树的前序和后序遍历能完全确定该有序树。

Prof. 由性质2和重构二叉树的性质即证。

森林转换为二叉树：先将每棵多叉树转换为二叉树，然后将所有二叉树根看成兄弟（假定有隐藏根节点），转换为一棵二叉树。

性质4：原森林中叶节点数量等于二叉树中无左孩子节点数量。

Prof. 原森林叶节点可能有兄弟导致在二叉树中有右孩子，但由于其没有孩子，其在二叉树中一定没有左孩子，两者一一映射，数量相同。

性质5：一棵树非🍃节点有 \(m\) 个，其转换为二叉树后无右孩子的节点有 \(m+1\) 个。

Prof. \(m\) 也为有孩子的节点数量，每个有孩子的节点，其有唯一的最右孩子，该孩子转换为二叉树之后无右孩子，其余孩子由于有右边的兄弟则有右孩子。还要加上根节点，其无兄弟，转换后无右孩子。

二叉树转换为森林：左孩子不变，把右孩子转换为自己的兄弟，然后从根节点开始，最长右孩子序列每个元素对应森林中每棵🌲的根。

哈夫曼树

哈夫曼树（也叫最优编码树）：每个🍃带权，使得带权路径长度最小的二叉树，构建方法：森林 \(F\) 初始化为 \(n\) 个权值的节点，重复下述操作直到 \(F\) 仅含一棵二叉🌲：

1. 在 \(F\) 中选取两棵根节点的权值最小的树作为左右子树构造一 个新的二叉树，且置新的二叉树的根节点的权值为左右子树上根节点的权值之和；
2. 在 \(F\) 中删除这两棵树，同时将新得到的二叉树加入 \(F\) 中。

对二叉🌲，每个🍃标定“路线”（例如：\(\{0110,10,1110,1111,110,00,0111,010\}\)），保证不是前缀码，为最优编码。

最小带权路径长度（WPL）：构建的哈夫曼树对每个🍃节点以及路径长度加权求和，满足等于使用二进制编码字符串的最小长度。

性质6： \(n\) 个节点的哈夫曼树对应 \(\dfrac{n+1}{2}\) 个叶子节点。

Prof. 由 \(n_0+n_2=n,n_0=n_2+1\) 即得。

性质7：出现次数最多和最少的字符哈夫曼编码中位数一定为最短和最长。

Prof. 使用反证法易证。

多叉树的带权最短路径：要求严格 \(m\) 叉树，通过 \(mn_{m}+1=n_0+n_{m}=n\) 补若干个 \(0\) （即不影响权的情况下适当增加 \(n\)）使得上述方程有整数解，之后仿造哈夫曼编码的方式，每次选择 \(m\) 棵树进行合并。

AVL 树

保证搜索树平衡，防止其退化为链式树。

选择 \(g, p, v\) ：\(g\) 为最小失衡子树根节点 ，\(p\) 和 \(v\) 分别为 \(g\) 和 \(p\) 孩子中的较高者。

调整：从左往右依次为 \(\text{zig-zig,zag-zag,zag-zig,zig-zag}\) 四种旋转方式。

例如顺次加入 \(7, 6, 4, 10, 8, 11\) 六个节点，形成的 AVL 树如下

性质8：AVL 🌲插入结点之后若不平衡，则调整之后与插入之前的🌲高相同。

Prof. 如果添加之后发生旋转，一定能让多出的一层通过旋转减少，AVL🌲仅有不旋转的时候“增高”。

删除：如果删除的节点 \(P\) 在根节点上，用 \(P\) 的中序直接前驱 \(O\) 替代，进而替代删除 \(O\)，由此进行递归删除

高级搜索树

B 树

\(m\) 阶B🌲又称 \(\left(\left\lceil \dfrac{m}{2}\right\rceil,m\right)\) 🌲，代表其分支数的取值范围，满足以下几种约束

1. 🍃的深度相同，根节点度数 \(\in[2,m]\)；

2. 非根节点度数 \(\in \left[\left\lceil \dfrac{m}{2}\right\rceil,m\right]\)；

3. 非🍃节点度数比关键码多 \(1\)。

性质1：B🌲下层与上层分支数之差等于本层关键码数，令 \(L_{h}\) 为第 \(h\) 层下层分支数，\(L_{h-1}\) 为第 \(h\) 层上层分支数，\(N_{h}\) 为第 \(h\) 层关键码数，则有 \[ \begin{equation} L_{h-1}+N_h=L_h \end{equation} \]

Prof. 对上一层的每个分支，假设关键码有 \(n_i\) 个，其下一层假设有 \(l_i\) 个分支，由约束(2)，可知 \(1+n_i=l_i\)，对上层每个分支求和即得。

该性质可以结合边界条件 \(L_{-1}=1\) 得 \[ \begin{equation} L_h=1+\sum_{i=1}^h N_i \end{equation} \] 性质2：\(m\) 阶 B🌲总高度满足 \[ \begin{equation} \log _m(N+1) \leq h \leq \log _{\left\lceil\frac{m}{2}\right\rceil}\left\lfloor\frac{N+1}{2}\right\rfloor+1 \end{equation} \]

Prof. 由约束(2)(3)可知度数满足条件 \(d_{i}\in\left[\lceil \dfrac{m}{2}\rceil,m\right]\)，🌲最矮的情况对应每个节点都填满 \(m-1\) 个值，有 \((m-1)\cdot (1+m+\cdots+m^{h-1})=m^{h}-1=N\)，左边得证；🌲最高的情况对应根节点度数为 \(2\)，每个节点填满 \(\lceil \dfrac{m}{2}\rceil-1\) 个值，第 \(i\) 层有 \(2\cdot \left( \left\lceil \dfrac{m}{2}\right\rceil\right)^{i}\) 组，\(1+\left(\lceil \dfrac{m}{2}\rceil-1\right)\cdot2\cdot\left[ \left( \left\lceil \dfrac{m}{2}\right\rceil\right)+\cdots+ \left( \left\lceil \dfrac{m}{2}\right\rceil\right)^{h-1}\right]=1+2\left[\left( \left\lceil \dfrac{m}{2}\right\rceil\right)^{h-1}-1\right]=N\)，右边得证。

另一种写法为，给定总高度 \(h\)，\(m\) 阶 B🌲总节点数的取值范围为 \[ \begin{equation} \left[2 \cdot\left(\left\lceil\frac{m}{2}\right\rceil\right)^{h-1}-1, m^h-1\right] \end{equation} \]

Note. B🌲总节点数和关键码数不同，后者可能不考虑叶子节点，对应 \(h\) 减 \(1\)。

插入节点：

① 根据性质查找插入的位置，如果overflow，就在中间关键码处split（这就是每节点的分支数大于 \(m/2\) 的原因），即：把中间关键码放到它的父亲节点中，并把它原本的左右键值看成它的左右孩子。（找 medieum 之后上溢）

② 如果父亲节点此时也 overflow，就不断分裂上溢。

③ 如果一直 split 到根节点，就为根节点创造一个新的 root。（允许根节点最少只有两个分支，仅有这种方法能长高，有爸求爸，没爸造爸）

删除节点：

① 找到要删的节点，如果不是叶子，交换其与后继的位置，转换为删除其后继，直到删除节点为叶子。

② 删除叶子之后如果 underflow，先看左右兄弟是否能“借”它一个节点。如果可以，就通过三角债的方式从父节点处 rotate。

③ 如果不可以，也就是说它和它的兄弟都恰好到下确界，就把它和它的右兄弟以及它们的父亲合并成一个孩子节点。这会导致父亲节点数-1. 如果这样，父亲需要重复上述操作。如果已经到了根节点，就意味着树的高度减 \(1\)。（对树高的改变，和 Insert一样，是很少出现的）

性质3：如果某个非🍃节点中所有关键码都存在直接后继，则这些后继都是🍃。

Prof. 观察下面这棵 B-树，第一层的关键码的直接后继需要迭代两层才能找到，仅有倒数第二层的关键码存在直接后继，后继均为🍃。

KD 树

对于搜索范围 \(R\) 的每条边，每个节点的 \(4\) 个孙子中不超过 \(2\) 个会与它相交，这意味着递归，如下图 (c) 中粗线最多只能交出 \(2\) 条线，则 \[ Q(n) = 2 + 2Q(n/4), Q(1) = O(1) \Longrightarrow Q(n) = O(\sqrt{n}) \]

卡特兰数

定义：\(n\) 个节点可构造的不同二叉树数目，显然其满足递推式 \[ \begin{equation} H_n=\sum_{i=0}^{n-1} H_i H_{n-i-1} \quad(n \geq 2) \end{equation} \]

Prof. \(n\) 个节点的二叉树根节点有 \(1\) 个，左右分别为 \(i\) 个和 \(n-i-1\) 个节点，两者相乘并求和为 \(H_n\)。

性质1：\(H_n=\dfrac{(2n)!}{n!(n+1)!}=\dfrac{\begin{pmatrix}2n\\n\end{pmatrix}}{n+1}=1,1,2,5,14,42\cdots\\\!\)其渐进于 \(\sim\dfrac{4^n}{\sqrt{\pi}n^{3/2}}\)

Prof. 令生成函数 \(H(x)=\displaystyle\sum_{n \geq 0} H_n x^n\)，由边界条件 \(H(0)=H(1)=1\)，由递推式\(H(x)=1+\displaystyle\sum_{n\geq 1}\sum_{i=0}^{n-1}H_{i}H_{n-i-1}x^n=1+x\sum_{n\geq 1}\sum_{i=0}^{n-1}H_ix^{i}H_{n-i-1}x^{n-i-1}\)，更换求和顺序，先对 \(i\) 求和有 \(\displaystyle\sum_{n\geq 1}\sum_{i=0}^{n-1}H_ix^{i}H_{n-i-1}x^{n-i-1}=\sum_{i=0}^{+\infty}H_ix^i\sum_{j=0}^{+\infty}H_{j}x^{j}=H(x)^2\)，则该函数满足方程 \(H(x)=1+xH(x)^2,H(0)=1\)，取极限下 \(H(x)=\dfrac{1- \sqrt{1-4x}}{2x}\)，由二项式定理 \(H(x)=\dfrac{1-\left(1+\displaystyle\sum_{n=1}^{+\infty}\begin{pmatrix}1/2\\n\end{pmatrix}(-4x)^{n}\right)}{2x},\begin{pmatrix}1/2\\n\end{pmatrix}=(-1)^{n-1}\dfrac{(2n-3)!!}{2^nn!}=\dfrac{(-1)^{n-1}(2n-2)!}{2^{2n-1}n!(n-1)!}\)代入得 \(H(x)=\dfrac{\displaystyle\sum_{n=1}^{+\infty}\dfrac{2(2n-2)!}{n!(n-1)!}x^n}{2x}=\displaystyle\sum_{n=1}^{\infty}\dfrac{(2n-2)!}{n!(n-1)!}x^{n-1}=\sum_{n=0}^{\infty}\dfrac{(2n)!}{n!(n+1)!}x^{n}\)，得证。

性质2：\(n\) 个元素的栈混洗个数有 \(H_n\) 个。

Prof. 考虑最后一个出栈元素，设其为 \(k\)，其必须满足前面 \(k-1\) 个元素入栈且出栈以及原序列中后面 \(n-k\) 个元素入栈且出栈，当两个过程全部完成 \(k\) 最后出栈，求和得\(\displaystyle \sum h(k-1)\cdot h(n-k)\)，不重不漏且满足递推式。

性质3：给定长度为 \(n\) 的前序遍历，中序遍历数量为 \(H_n\)。

Prof. 由性质1给出 \(H_n\) 种二叉树的形态，按照这些形态“输入”前序遍历获得完整的二叉树，每棵二叉树的中序遍历均不同，因为如果相同，由前序遍历和中序遍历完全确定一棵二叉树从而矛盾，故在前序遍历确定的情况下，每个二叉树形态与每个中序遍历一一对应。

性质4：一个凸 \(n+2\) 边形，用直线连接若干对顶点使之分成多个三角形，要求每条直线不能相交，共有 \(H_n\) 种划分方案。

Prof. 任意选取其中一条边以及连接中间第 \(k\) 和 \(k+1\) 个顶点，满足递推关系。

性质5：律师每天从 \(A\) 到 \(B\) 走 \(2n\) 个街区上班，要求不能穿越（但可以碰到）从家到办公室的对角线（只能经过绿色点），一共有 \(H_n\) 条可能路线。

Prof. 每一次向上走看作入栈，向左走看作出栈，则等价于 \(n\) 元素的栈混洗个数。

堆

堆排序

Floyd 堆合并算法，将所有非叶子节点下滤，由公式 (5)，筛选次数为 \(\sim\dfrac{n}{2}\)。

性质1：建堆时比较次数为 \(O(n)\)

Prof. 设高度为 \(h\)（ \(1\) 个节点高度为 \(0\)）相较之前的逐个插入法 \[ \sum _{i=0}^{h}i2^i\Longrightarrow\sum _{i=0}^{h}(h-i)2^i\\ (h-1)2^{h+1}+2=O(n\log n)\Longrightarrow2^{h+1}-h-2=n-\log _2(n+1)=O(n) \]

性质2：代码实现上从序列末尾开始向前遍历，比如从倒数第二层的最后一个节点开始上滤，但同层节点的下滤次序对算法的正确性和效率都没有影响，其互不相干。

性质3：合并两个一般堆与建堆的时间复杂度相同，时间为 \(O(n)\)。

Prof. 两个一般堆的合并使用 Floyd 算法目前为最快的 \(O(n)\)，使用左式堆可以降到 \(O(\log n)\)。

程序中的堆是自己生成自己回收，栈是操作系统来分配。

性质4：堆排序时间复杂度为 \(O(n\log n)\)，其中建堆次数共 \(n\) 次

Prof. 建堆时间 \(O(n)\)，之后每次移去最值并下滤，操作时间为 \(O(n\cdot \log n)\)。初始 \(1\) 次，之后仅用下滤并取极值 \(n-1\) 次，共 \(n\) 次。

图

基本性质

无向图中描述两顶点之间的关系可以用 (v1, v2) 来表示。

有向图中描述两顶点的单向关系用 <v1,v2> 来表示。

简单路径：经过的点互相不重复的路径。（回路不是简单路径）

连通分量：无向图中，若 \(v_i\) 到 \(v_j\) 有路径，则称 \(v_i\) 和 \(v_j\) 是连通的，无向图极大连通子图的集合为连通分量。

强连通分量：有向图中，若从 \(v_i\) 到 \(v_j\) 以及从 \(v_j\) 到 \(v_i\) 有路径，则称 \(v_i\) 和 \(v_j\) 是连通的，有向图极大强连通子图的集合为强连通分量。

平面图：可以画在平面上且不同的边互不交叠的图，判定 \(V-E+F=C+1\)，分别对应顶点、边、面、连通数目，满足 \(e \leq 3 \times v-6=O(v) \ll v^ 2\)。

有 \(e\) 条边的无向图，在邻接表中共有 \(n+e\cdot 2=n+2e\) 个节点（注意对称性）。

邻接表的空间复杂度为 \(O(n+e)\)，邻接矩阵的空间复杂度为 \(O(n^2)\)

性质1：无向图的邻接矩阵为对称矩阵 \(A=A^{T}\)，点为 \(i\) 的度为 \(\displaystyle \sum_{j=1}^n A[i, j]=\sum_{i=1}^n A[i, j]\)。

Prof. 对无向图中的一个点而言，其入度等于出度，

性质2：\(n\) 节点的连通无向图至少有 \(n-1\) 条边（邻接矩阵有 \(2(n-1)\) 个元素），连通有向图至少有 \(n\) 条边。

Prof. 对无向图而言，\(n-2\) 条边无法连接所有顶点，顺次连接 \(n\) 个点最少只需要 \(n-1\) 条边；对有向图形成一个大环为最少的边数。

性质3：要保证在任意连接方式下都能连通 \(n\) 个点，至少需要 \(\dfrac{n(n-1)}{2}+1\) 个点。

Prof. 最坏情况为 \(n-1\) 个点构成完全图，最后连接剩下 \(1\) 个点。

性质4：深度优先搜索生成的序列与图是否有向密切相关。

E.g. 对边集 \(E={<v_0,v_1>, <v_0,v_2>, <v_0,v_3>, <v_1,v_3>}\) 从 \(v_0\) 开始的深度优先搜索一共有 \(5\) 种，其中 \(v_0\rightarrow v_3\rightarrow v_2\rightarrow v_1\) 容易遗漏。

拓扑排序

步骤：每次选择入度为 \(0\) 的点入队，剪去出队元素的所有边，重复操作，出队序列为拓扑序列。（拓扑排序得到的序列不唯一）

性质5：如果一个有向图的邻接矩阵对角线以下的元素非 \(0\)，则该图存在拓扑排序。

Prof. 说明任意边 \(v_{i}\longrightarrow v_j\) 中 \(i<j\)，若存在环 \(v_i,v_j,v_k\)，则满足 \(i<j,j<k,k<i\)矛盾，从而该有向图无环，存在拓扑排序。

最小生成树算法

图的深度优先搜索能给出图的一棵支撑树，对应二叉树的先序遍历。

生成树：连通图 \(G\) 的某个子图是一颗包含 \(G\) 所有顶点的树。

Cayley 公式：\(n\) 个顶点的完全图的生成树总数为 \(n^{n-2}\)。

Prof. 设结果为 \(T(n)\)，考虑生成树序列的个数算两次，第一种计算方式为每棵树的排列为 \(T(n)\cdot n!\)，第二种方式为考虑第 \(k\) 次加入的边，当前有 \((n-k+1)\) 棵树，边的一端任选，另一端不能为前者所在的树，每次有 \(n\cdot (n-k+1-1)=n(n-k)\) 种选法，求积为 \(\displaystyle \prod_{k=1}^{n-1}n(n-k)=n^{n-1}\cdot (n-1)!\)，两者相等 \(T(n)n!=n^{n-1}\cdot (n-1)!\Longrightarrow T(n)=n^{n-2}\)。

性质1：\(n\) 个顶点、\(n\) 条边的连通图至少有 \(3\) 棵生成树。

Prof. 连通图一定有 \(n-1\) 条边的生成树，多一条边一定能通过其共同祖先形成环，该环至少有 \(3\) 条边，任一去掉一条边均为生成树，至少 \(3\) 棵生成树，

最小生成树（MST）：所有生成树中权值之和最小的树，最小生成树有两种算法。

Kruskal 算法

算法流程：按权值递增顺序依次选取 \(n-1\) 条边，始终保证不构成回路。

设图的边数量为 \(e\)，前者需要排序 \(O(e\log e)=O(e\log v)\) ，判断是否属于同一个树的时间为 \(O((v+e)\cdot \alpha(v))\)，其中 \(\alpha(v)\) 为阿克曼函数，对目前规模数据 \(\alpha(v)\leq 4\)，从而总的复杂度为 \(O(e\log v)\) ，适用于稀疏图。

Prim 算法

算法流程：重复加入当前节点与剩余节点距离最近的边，即一棵树以极短跨边生长。

使用优先级队列取出最小边以及加入当前可跨边进行下滤和上滤操作，判定边是否使用可以使用一组布尔变量 \(O(1)\) 时间内判定，则消耗时间 \(O(e+(v+e)\log v)=O(e\log v)\)。

可以看出，两种算法在渐进时间复杂度上是相同的。

Note. 上述两种算法更改选择方式可以得到“最大生成树”。

带权连通图的任意一个环中包含的边的权值均不相同时，其 MST是唯一的（充分条件）

最短路径算法

Dijkstra 算法

求解权值非负单源最短路径问题。

算法流程：每次考虑当前点集的最短路径对应点的邻边，对所有点集的最短路径更新最短路径以及前驱，层层遍历，得到所有最短路径。

算法共三组与顶点一一对应的数组，空间复杂度为 \(O(v)\)。

时间复杂度，时间主要消耗在寻找当前点集的最短路径，次数为 \(O(1+\cdots+(v-1)+e)\)，由于 \(O(e)=O(v^2)\)，则不加优化为 \(O(v^2)\)。

使用优先级队列在每次加入当前遇到的顶点时上滤，取出最小值之后下滤，每次操作 \(O(\log v)\)，共计 \(O(v+e)\) 次操作，故可以优化为 \(O((v+e)\log v)\)，可以看出对稀疏图较好，对稠密图反而不好。

Bellman-Ford 算法

求解权值任意单源最短路径问题

算法流程：设源点为 \(u\)，构造 \(\text{dist}^{k}[v]\) 代表源点最多经过 \(k\) 次到 \(v\) 点的最短路径，记遍历当前有效点的邻边求最小值更新 \(\text{dist}\) 数组为一次操作，重复操作 \(v\) 次。

Prof. 正确性，如果没有负环，每条最短路径最多只需要 \(n-1\) 次便能确定，前 \(n-1\) 次计算最短路径，最后一次如果还有更新，则代表有负环，不存在最短路径。

算法时间复杂度为 \(O(ve)\)，共进行 \(v\) 次循环，每次循坏最大可能遍历所有边。

Floyd-Warshall 算法

求解权值任意多源最短路径：标定 \(\text{dist}[u][v]\) 为从 \(u\) 到 \(v\) 的最短路径，对所有边进行初始化，对 \(k:0\to v\)，遍历 \(u\) 和 \(v\)，通过 \(\text{dist}[u][k]\) 和 \(\text{dist}[u][k]\) 对 \(\text{dist}[u][v]\) 松弛。

时间复杂度 \(O(v^3)\)，空间复杂度为 \(O(v^2)\)。

散列

评判一个散列函数的四个维度

1. 确定：同一关键码总是被映射到同一地址
2. 快速：计算时间复杂度为 \(O(1)\)
3. 满射：尽可能充分地覆盖整个散列空间
4. 均匀：映射到各位置的概率尽量接近，避免聚集

散列函数

1. 直接寻址法，直接取关键字的某个线性映射
2. MAD ( Multiply-Add-Divide ) 法，防止相邻关键码依然相邻

\[ \text{Hash}(\text {key})=(\mathbf{a} \times \mathbf{k e y}+\mathbf{b}) \% \mathbf{M} \]

2. 数字分析法，例如手机后四位

3. 平方取中法，例如 f(1234)=1522756=227

4. 折叠法，取若干位数相同的部分求和

5. 伪随机数法，\(\text{Rand(A)}\)

散列冲突解决方法

1. 多槽位法，预先几个槽

2. 独立链法，链表

3. 公共溢出法，冲突元素放置在单独一个地方

4. 线性试探法，冲突之后顺次放置，第 \(k\) 次试探地址 \(\left(\text{hash}(\text{key})+{k}\right) \% M\)，使用 lazyRemoval 防止删除之后断链

5. 平方试探法，第 \(k\) 次试探地址 \(\left(\text{hash}(\text{key})+{k^2}\right)\% M\)，能够更快地跳出聚集区

6. 双向平方试探法，第 \(k\) 次试探地址 \(\left(\text{hash}(\text{key})+{(-1)^{k-1}\left\lceil\dfrac{k}{2}\right\rceil^2}\right) \% M\)。

性质1：若表长为素数 \(p\equiv 3\pmod{4}\) ，使用双向平方试探法前 \(\text{p}\) 次试探能遍历所有桶。

Prof. 反证若两次试探 \(k_1,k_2\) 同时属于偶数、奇数集合 \(\{2,4,\cdots,p-1\},\{1,3,\cdots,p\}\)中的某个，则 \(k_1^2\equiv k_2^2\pmod{p},(k_1+k_2)(k_1-k_2)\equiv 0\pmod{p}\)\(\Longleftrightarrow p\mid k_1+k_2, k_1-k_2\)，后者均不能满足（之和为偶数）。则必须属于不同集合，此时 \(k_1^2+k_2^2\equiv 0\pmod{p}\)，而二平方和问题只能为 \(4k+1\) 型素数或者 \(2\)，这是因为 \(2\nmid x\Longrightarrow x\equiv 1\pmod{4}\)。则对任何情况均无解，不存在冲突，能够在 \(p\) 次试探中遍历所有桶。

Note. 当 \(M=2^s,s\in \mathbb{Z}\) ，第 \(k\) 次试探地址为 \(\left(\text{hash}(\text{key})+\dfrac{k(k+1)}{2}\right) \% M\) 时也能遍历所有桶。

线性探测失败和成功问题：成功查找次数等于线性探测加入 \(\text{Hash}\) 值时移动次数加 \(1\) 的累加。

性质2：在线性探测策略下，当插入节点的数量小于总数量时，对给定的节点序列，无论插入顺序如何，最后平均成功查找次数相同。

Prof.

组合索引：多个指标时“拼接”在一起计算哈希值。

串

KMP 算法

改进前：\(\text{Next}(P, j)=\{0 \leq t<j \mid P[0, t)=P[j-t, j)\}\)

改进后：\(\text{Next}(P, j)=\{0 \leq t<j \mid P[0, t)=P[j-t, j)\wedge P(t) \neq P(j)\}\)

算法复杂度为 \(O(m+n)\)，在最坏情况下依然是该复杂度。

排序

直接插入排序需要挪位置。

性质1：共 \(4\) 种不稳定排序，“快些选堆”（快速排序、希尔排序、选择排序、堆排序）

Prof. 快速排序轴点的选择影响相同值元素的先后顺序；希尔排序由于间隔的存在，相同值元素可能在不同间隔序列中打乱；选择排序将 \(\text{rank(i)}\) 的元素与第 \(i\) 个元素交换，交换的元素可能与后面某元素相同，顺序打乱；堆排序在不同分支的维护堆操作顺序可能发生改变。

基数排序

算法：关键码由多个字段组成，可按照优先级从低到高进行桶排序，低位字段优先策略 \[ \begin{array}{|c|c|c|c|c|c|c|c|} \hline \text { 输入序列 } & 441 & 276 & 320 & 214 & 698 & 280 & 112 \\ \hline \text { 以个位排序 } & 32{0} & 28{0} & 44{1} & 11{2} & 21{4} & 27{6} & 69{8} \\ \hline \text { 以十位排序 } & 1{1}2 & 2{1}4 & 3{2}0 & 4{4}1 & 2{7}6 & 2{8}0 & 6{9}8 \\ \hline \text { 以百位排序 } & {1}12 & {2}14 & {2}76 & {2}80 & {3}20 & {4}41 & {6}98 \\ \hline \end{array} \]

Prof. 正确性由数学归纳法给出，假设 \(i-1\) 趟后前 \(i-1\) 次序的数字排好序，第 \(i\) 趟如果第 \(i\) 优先级不同，则按照该优先级排序，如果相同，前面工作保证排好序，则总能排好序。

复杂度： 各字段取值范围 \(\left[0, M_i\right), i<=t\)，令 \(M=\max \left(M_i\right)\) \[ O\left(n+M_1\right)+O\left(n+M_2\right)+\cdots+O\left(n+M_t\right)=O\left(t\cdot(n+M)\right) \]

Note. 基数排序需要的操作次数为定值，桶排序可以看成是基数为 \(1\) 的基数排序。

快速排序

性质2：快速排序的平均时间复杂度为 \(O(1.386\cdot n\log n)\) \[ T(n)=(n-1)+\frac{1}{n} \cdot \sum_{k=0}^{n-1}[T(k)+T(n-k-1)]=(n-1)+\frac{2}{n} \cdot \sum_{k=0}^{n-1} T(k) \] \(\begin{cases} n \cdot T(n)-(n-1) \cdot T(n-1)=2 \cdot(n-1)+2 \times T(n-1) \\n \cdot T(n)-(n+1) \cdot T(n-1)=2 \cdot(n-1) \end{cases}\Longrightarrow\dfrac{T(n)}{n+1}-\dfrac{T(n-1)}{n}=\dfrac{4}{n+1}-\dfrac{2}{n}\)

解得 \(T(n)=(n+1)\cdot\left(2 \displaystyle \cdot \sum_{k=1}^{n+1} \frac{1}{k}+\frac{2}{n+1}-4\right)\approx 2\ln 2\cdot n\log n\)