数据结构拾遗

绪论

时间复杂度 $T(n)$ 时指算法中所有语句的频度（执行次数）之和。

渐进时间复杂度是当 $n$ 趋于无穷时 $T(n)$ 的数量级，而非 $T(n)$ 的准确大小，因此以 T(n) 的数量级来表征时间复杂度。

加法规则：

乘法规则：

时间复杂度的大小关系：

空间复杂度 $S(n)$ 是指算法运行过程中所使用的辅助空间的大小。

算法原地工作是指算法所需的辅助空间是常量，空间复杂度是 $O(1)$。

影响辅助空间大小的两个方面：

• 算法运行过程中的各个变量所占的空间，如：辅助数组
• 递归工作栈带来的空间复杂度

线性表

• 顺序表：顺序存储，逻辑上相邻的物理上也相邻
• 链表：链式存储，逻辑上相邻的物理上可以不相邻，用指针描述逻辑上的前驱后继关系。

栈和队列

当 $n$ 个元素以某种顺序进栈，并且可在任意时刻出栈，所获得的元素排列的数目 $N$ 恰好满足卡特兰数 Catalan() 的计算：

树与二叉树

• 结点的度：树中一个结点的子结点的个数。
• 树的度：树中结点的最大度数
• 分支结点：度大于0的结点
• 叶子结点：度等于0的结点
• 结点的深度：从根结点开始自顶向下逐层累加
• 树的高度或深度：树种结点的最大层数
• 路径：树中两个结点之间经过的结点序列
• 路径长度：路径上所经过的边的条数

• 单分支结点数 + 双分支结点数 $\times$ 2 = 所有结点的分支数
• 总结点数 - 1 = 总分支数
• 非空二叉树上 叶子结点数 = 双分支结点数 + $1$
• 树上 叶子结点数 $L =\displaystyle\sum_{i=2}^m (i-1) * n_i + 1$

• $i$ 分支结点的度，$n_i$ 为对应结点的个数

• 二叉树的第 $i$ 层上最多有 $2^{i-1} (i \geqslant 1)$ 个结点

• 高度为 $k$ 的二叉树最多有 $2^k - 1 (k \geqslant 1)$ 个结点

• 有 $n$ 个结点的 完全二叉树，对各结点从上到下、从左到右依次编号，编号范围为 $1 \sim n$，若 $i$ 为某结点 $a$ 的编号，则结点之间有如下关系：

• 如果 $i \neq 1$，则 $a$ 双亲结点的编号为 $\lfloor i/2 \rfloor$；
• 如果 $2i \leqslant n$，则 $a$ 左孩子的编号为 $2i$；如果 $2i > n$，则 $a$ 无左孩子；

• 如果 $2i + 1 \leqslant n$，则 $a$ 右孩子的编号为 $2i+1$；如果 $2i + 1 > n$，则 $a$ 无右孩子；

• 给定 $n$ 个结点，能构成 Catalan(n) 种不同的二叉树，卡特兰函数见上；

• 具有 $n(n\geqslant 1)$ 个结点的完全二叉树的高度为 $h= \lfloor \log_2n\rfloor + 1 = \lceil \log_2(n + 1) \rceil$

• 树的后序遍历 等同于该树对应 二叉树的中序遍历

哈夫曼树

从树根结点到任意结点的路径长度（经过的边数）与该结点上权值的乘积成为该结点的带权路径长度。树中 所有叶子结点 的 带权路径长度之和 称为该树的 带权路径长度：

其中 $w_i$ 是第 $i$ 个叶子结点所带的权值；$l_i$ 是该叶子结点到根结点的路径长度。

在含有 $N$ 个带权叶子结点的二叉树中，其中带权路径长度最小的二叉树称为 哈夫曼树。

哈夫曼树的特点：

• 每个初始结点最终都称为叶子结点，并且权值越小的结点到根结点的路径长度越大
• 构造过程中共新建了 $N-1$ 个双分支结点，因此哈夫曼树中的结点总数为 $2N-1$
• 每次构造都选择 2 棵树作为新结点的孩子，因此哈夫曼树中不存在度为 1 的结点
• 用 $n$ 个叶子结点构造的哈夫曼树形态可能不唯一，但带权路径长度唯一

哈夫曼编码：

如果没有一个编码是另一个编码的前缀，则这样的编码称为 前缀编码。利用哈夫曼树可以设计出总长度最短的二进制前缀编码。

哈夫曼编码形成过程：

• 将每个待编码元素当作一个独立的结点，构造出哈夫曼树
• 从根至该字符的路径的边上标记的序列，其中边标记为 0 的表示 转向左孩子，标记为 1 的表示 转向右孩子
• 从根结点到待编码元素结点的路径形成 0、1 序列就是哈夫曼编码

构造度为 $m$ 的哈夫曼树时，每次把 $m$ 个叶子结点合并成为一个父结点，每次合并减少 $m-1$ 个结点。

图

图的概念

图的存储

• 邻接矩阵法：比较适合稠密图
• 有向图顶点 出度 为顶点 行 中有效数目
• 有向图顶点 入读 为顶点 列 中有效数目
• 邻接表法：比较适合稀疏图

图的遍历

广度(BFS)有限遍历：

• 需要一个辅助队列，空间复杂度为 $O(n)$
• 邻接矩阵表示时，算法总的时间复杂度为 $O(|V|^2)$
• 邻接表表示时，算法总的时间复杂度为 $O(|V| + |E|)$

最小生成树 MST(Minimum Spanning Tree)

• Prim 算法：不断地加如点，保证代价最小。时间复杂度为 $O(|V|^2)$，不依赖于 $|E|$，适用于 边稠密 的图。

• Kruskal 算法：不断地加代价最小的边，时间复杂度为 $O(|E|\cdot\log_2|E|)$，适用于 边稀疏 而 顶点较多 的图。

• 最小生成树不是唯一的，可能有多个最小生成树

• 当图 $G$ 中的各边权值不同时，$G$ 的最小生成树唯一
• 最小生成树所对应的边的权值之和总是唯一的，而且时最小的。

最短路径

在带权图中，边上的权值表示路径长度；从一个顶点到另一个顶点的路径长度是路径上各边的权值之和。

• 单元最短路径问题：求从给定源点到其他各个顶点的最短路径长度。(Dijkstra) 不断地加如点，保证路径最小，时间复杂度 $O(|V|^2)$
• 点对点最短路径问题：求每一对顶点之前的最短路径长度 (Floyd) 不断地更新代价最小的边，时间复杂度 $O(|V|^3)$，允许图中带有负权值的边，不允许负权值的回路。
• 最短路径回路：旅行商问题 TSP(Travelling salesman problem)，属于NP完全问题。

拓扑排序

拓扑排序的性质：

• 每个顶点出现且只出现一次
• 若顶点 $A$ 在序列中排在顶点 $B$ 的前面，则图中不存在 顶点 $B$ 到顶点 $A$ 的路径
• 每个有向无环图都有一个或多个拓扑排序

拓扑排序的算法：

1. 从有向无环图中选择一个没有前驱的顶点并输出
2. 从图中删除该顶点和所有以它为起点的有向边
3. 重复 1. 和 2. 直到当前的图为空或当前图中不存在无前驱的顶点为止
4. 若图中不存在无前驱的顶点，则说明有向图中必然存在环

• 若基于 邻接表，则拓扑排序的时间复杂度为 $O(|V| + |E|)$
• 若基于 邻接矩阵，则拓扑排序的时间复杂度为 $O(|V|^2)$

关键路径

带权有向图以顶点表示事件，有向边表示活动，边上的权值表示完成该活动的开销，则称为 AOE(Activity On Edge Network)网，AOE 网中从源点到汇点的所有路径中 长度最长的路径 称为 关键路径，关键路径长度是整个工程所需的最短工期，关键路径上的活动称为 关键活动。

关键路径的性质：

• 可以通过加快关键活动，来缩短整个工程的工期。并非关键活动缩短多少工期就缩短多少，因为缩短到一定的程度，该关键活动可能就变成非关键活动了
• 关键路径不唯一，对于有几条关键路径的网，只提高一条关键路径上的关键活动速度并不能缩短整个工程的工期，只有加快那些包括在所有关键路径上的关键活动才能达到缩短工期的目的。

查找

顺序查找法

逐个比较查找表中的元素，直到找到目标元素或达到查找表的尽头为止，时间复杂度为 $O(n)$；

查找成功时，在等概率的条件下，平均查找长度为：

查找不成功时，平均查找长度为：

折半查找法

又称为二分查找发，它仅适用于 有序的顺序表。

1. 若顺序表为空，查找失败：否则转到 2
2. 将 key 与顺序表中间位置元素的关键字比较，若相等，查找成功；
3. 若 key 小于（大于）顺序表中间位置的关键字，则以中间元素的前半部分（后半部分）作为新的查找表。执行 1.

描述折半查找过程中的二叉树称为判定树，判定树的树高 $h=\lceil\log_2(n + 2)\rceil$，表的中间结点时二叉树的根，左子表相当于左子树，右子表相当于右子树。

这般查找的判定树为完全二叉树。

B树与B+树

B-树 就是 B树，出现 B-树的原因可能是早期引进技术的人，误把 B-Tree 中的连词号当成了减号；实际上是不正确的😂😂😂。

B+ 树适合用来做数据库 聚簇索引，所以在外部存储的查找中应用广泛。

一颗 $m$ 阶 $B$ 树或为空树，或为满足下列特征的 $m$ 叉树：

• 若根结点不是终端结点，则至少有两颗子树，至多有 $m$ 棵子树
• 除根结点外的所有非叶子结点至少有 $\displaystyle\lceil\frac{m}{2}\rceil$ 棵子树，至多有 $m$ 棵子树。
• 所有的叶子结点都出现在同一层次上，并且不带信息（可看成是失败结点）

一颗 $m$ 阶 $B+$ 树满足下列条件：

• 每个分支结点最多有 $m$ 棵子树
• 非叶根结点至少有两颗子树，其他每个分支结点至少有 $\displaystyle\lceil\frac{m}{2}\rceil$ 棵子树
• 结点的子树个数与关键字个数相等
• 所有的叶子结点包含全部关键字及指向相应记录的指针，而且叶子结点中将关键字大小顺序排列，并且 相邻叶子节点按大小顺序相互链接起来
• 所有分支结点（可看成是索引的索引）中仅包含它的各个子节点（下一级的索引块）中关键字最大值及指向其子节点的指针。

B 树和 B+ 树的区别：

• 对于含有 $n$ 个关键字的 B树 的查找，磁盘 I/O 次数也就是树的高度 $h$ (不包含叶子结点)，满足：$\displaystyle h \leqslant \log_{\lceil\frac{m}{2}\rceil}(\frac{n + 1}{2}) + 1$

B树的插入过程如下：

• 查找：利用查找算法，找出插入该关键字的最底层中某个非叶子结点
• 插入：当插入后的结点关键字个数小于 $m$，则可以直接插入；如果等于 $m$，则必须对结点进行分裂，分裂当前结点，把中间的元素提到父结点，如果父结点关键字等于 $m$，然后递归的分裂上提，直到结点关键字个数小于 $m$。

B树的删除过程如下：

为使删除后的结点关键字个数 $n_k \geqslant \lceil\frac{m}{2}\rceil - 1$，将设计结点的合并问题。

• 当被删除的关键字 $k$ 不在非叶终端结点中时：
  • 如果小于（大于）$k$ 的子树中关键字个数 $> \lceil\frac{m}{2}\rceil - 1$，则找出 $k$ 的前驱（后继）值 $k'$，并且用 $k'$ 来取代 $k$，再递归地按此方法删除 $k'$
  • 如果前后两个子树中关键字个数均为$\lceil\frac{m}{2}\rceil - 1$，则将两个子节点合并，直接删除 $k$
• 当被删除的关键字 $k$ 在非叶终端结点中时：
  • 若该结点的关键字个数 $> \lceil\frac{m}{2}\rceil - 1$，直接删除该关键字
  • 若该结点的关键字个数 $=\lceil\frac{m}{2}\rceil - 1$，且与此结点相邻的右（左）兄弟结点的关键字个数$\geqslant \lceil\frac{m}{2}\rceil$，需要调整该结点、右（左）兄弟结点以及其双亲结点（父子换位法），以达到新的平衡
  • 若该结点的关键字个数 $=\lceil\frac{m}{2}\rceil - 1$，且与此结点相邻的右（左）兄弟结点的关键字个数$= \lceil\frac{m}{2}\rceil - 1$，则将关键字删除后与右（左）兄弟结点及其双亲结点中的关键字进行合并
  • 在合并的过程中，若此时导致其父结点的关键字个数也不满足B树的定义，则继续进行这种合并操作
  • 若最终使得根结点被合并，B树的高度减一

散列表

相关基本概念

散列函数的构造方法

最常用的是 除留余数法：假设散列表表长度为 $m$，取一个不大于 $m$ 但最接近或等于 $m$ 的素数 $p$，散列函数为：

冲突处理方法：

平均查找长度：

• $P_i$ 是查找第 $i$ 个数据元素的概率
• $C_i$ 是找到第 $i$ 个数据元素所需的比较次数

排序

排序算法的性能

堆排序建堆的过程：

• 长度为 $n$ 的序列，对应 $n$ 个结点的完全二叉树（最后一个叶子结点是第 $\lfloor\frac{n}{2}\rfloor$ 个结点的孩子）
• 以此对第 $\lfloor\frac{n}{2}\rfloor, \lfloor\frac{n}{2}\rfloor - 1, \cdots, 1$ 个结点为根的子树调用堆的调整操作，使其成为堆，建堆的时间复杂度为 $O(n)$。
• 从后往前按顺序检查所有分支结点，若要建立大根堆，则让小元素不断 递归下坠。
• 交换根结点和最后一个结点，然后重新调整根结点，使堆成为大根堆。

外部排序

归并过程中的磁盘 I/O 次数 = 归并树的 WPL $\times$ 2

外部排序的优化方法：

• 增加归并路数
• 减少归并段数量，即增加初始归并段长度（置换-选择排序）
• 减少各归并段在内存中的关键字比较次数（败者树）

重点与难点

• 后缀表达式
• KMP算法
• AVL树
• 二叉树、树、森林