CSCI2100
数据结构
链表、栈与队列、动态数组、哈希、优先队列、二叉搜索树、平衡搜索树与多路搜索树、Trie、不相交集合、排序、图算法及算法分析。
你的进度
0/ 30 节已标记完成
下一节: 不相交集合:划分、森林与并查集
完成记录保存在此浏览器中。
这门课在网上
CSCI2100 笔记里的内容
数字只算这门课 30 节公开笔记里写了什么,不是网上已记录的关系。目前其中 0 节已细致地记录到网上。
在网上定理卡 69 · 定义 41 · 反例 39 · 概念视角 20 · 证明透视 35
第 1 章 · 1 节
不相交集合
划分与并查集
- 1.1
不相交集合:划分、森林与并查集
用父指针森林表示逐步合并的群组,证明连接根与路径压缩的正确性,并分析按大小合并。
第 2 章 · 3 节
线性数据结构
队列不变量、摊还分析及链表环检测。
- 2.1
用两个栈建立先进先出队列
证明队列不变量,并计算偶尔昂贵的转移成本。
- 2.2
不使用访问集合检测链表中的环
追踪 Floyd 的指针,证明相遇原因,并定位及安全移除环。
- 2.3
双栈队列:不变量与摊还成本
追踪队首观察、转移循环与摊还成本。
第 3 章 · 2 节
优先队列
堆不变量、插入及移除最小值。
- 3.1
二叉最小堆与优先队列
证明二叉最小堆不变量,分析插入及移除最小值。
- 3.2
自底向上建立最小堆
证明下滤的正确性及原地建立堆的线性时间界。
第 4 章 · 2 节
搜索树的顺序统计量
维护子树大小并按排名选取键。
- 4.1
在搜索树中按排名选取
证明排名选取,并在插入、删除及旋转下维护子树计数。
- 4.2
选取最小的 k 个记录
以排名阈值选出恰好 k 个记录,明确订立平手、次序和成本。
第 5 章 · 2 节
哈希
拉链法与碰撞的期望成本。
- 5.1
拉链法与碰撞的期望成本
跟踪拉链查询,并在逐对碰撞假设下证明期望界。
- 5.2
线性探测与墓碑删除
追踪有界探测并证明删除与键唯一性的不变量。
第 6 章 · 1 节
概率式成员判定
布隆过滤器、保证及假阳性模型。
- 6.1
布隆过滤器与假阳性
区分确定性成员保证与理想化假阳性模型。
第 7 章 · 2 节
字符串 Trie
精确成员、前缀列举与安全剪枝。
- 7.1
Trie 前缀、终止标记与安全剪枝
维护精确字符串成员与前缀列举,并证明删除保留共用路径。
- 7.2
追踪精确查找与前缀补全
逐字追踪 trie 查询,区分到达节点与已存储键值。
第 8 章 · 1 节
多路搜索树
在插入时保持 B 树的占用和搜索不变量。
- 8.1
B 树:不变量、分裂与自顶向下插入
定义多路搜索树的规格,证明子节点分裂及插入正确,追踪二阶例子,并区分高度、比较及块访问成本。
第 9 章 · 1 节
自调整搜索树
伸展旋转与摊还访问证明。
- 9.1
伸展树:旋转与访问引理
追踪伸展操作并证明无权摊还访问界。
第 10 章 · 2 节
链表不变量
哨兵环、节点所属关系与拼接的代价。
- 10.1
哨兵链表与节点拼接
从局部链接推导整体成员关系,并计算查找与维护大小的代价。
- 10.2
递归删除与返回的表头
追踪节点所有权与元数据,证明递归删除的契约。
第 11 章 · 1 节
动态数组
几何扩缩容与摊还成本。
- 11.1
动态数组与摊还成本
追踪扩缩容并证明摊还更新界。
第 12 章 · 1 节
有序数组搜索
边界搜索与循环不变量。
- 12.1
二分查找:边界与循环不变量
证明上下界,处理重复值并分析访问成本。
第 13 章 · 2 节
图遍历
用队列和发现标记寻找无权图最短路径。
- 13.1
广度优先搜索:队列与最短路径
追踪入队标记,证明层次不变量并重建无权图最短路径。
- 13.2
图的表示与深度优先搜索
比较邻接矩阵与邻接表,并分析深度优先搜索:时间戳、边的分类、环检测与拓扑序。
第 14 章 · 2 节
图算法
最小生成森林与并查集。
- 14.1
Kruskal 算法:并查集与最小生成森林
证明森林不变量和贪心割交换,并追踪按大小合并。
- 14.2
加权图的前沿:Dijkstra 与 Prim
在同一加权图上追踪使用惰性堆的 Dijkstra 算法及 Prim 算法,并证明各自选取步骤的安全性。
第 15 章 · 2 节
平衡搜索树
AVL 树与红黑树:高度界及更新后的修复。
- 15.1
AVL 树:高度、旋转与删除
证明对数高度界,用旋转保持搜索顺序,并逐步分析插入和沿祖先路径传播的删除修复。
- 15.2
红黑树:黑高度与插入修复
从颜色不变量推导对数搜索深度,证明各种插入修复,并分清重新着色与旋转的代价。
第 16 章 · 1 节
哈希表与通用哈希
链地址法、期望链长与通用哈希族。
- 16.1
哈希表:链地址法、通用哈希与期望成本
在碰撞中保持映射,用指示变量证明期望链长,并用素数模运算构造通用哈希族。
第 17 章 · 1 节
二叉搜索树
普通二叉搜索树的次序不变量与删除。
- 17.1
二叉搜索树删除:后继、子树返回与节点身份
以后继节点替换法删除二叉搜索树的键,返回新的子树根,并检验次序不变量与代价。
第 18 章 · 2 节
排序
链表上的归并排序、数组归并排序、快速排序与比较排序下界。
- 18.1
链表上的归并排序:正确性也关乎链接
以破坏性且稳定的方式合并有序链表,用快慢指针分割链表,并分析链表上的归并排序。
- 18.2
比较排序:归并排序、快速排序与下界
用不变量与递推式分析数组上的归并排序和快速排序,并证明任何比较排序都需要约 n log n 次比较。
第 19 章 · 1 节
算法分析
代价模型与渐近记号。
- 19.1
渐近记号与代价模型
固定代价模型,以明确的常数定义 O、Omega 与 Theta,并推导简单循环代码的增长类别。