最小生成树：Prim 与 Kruskal
最小生成树：Prim 与 Kruskal 在带权无向图里，有一类非常经典的问题： 如果要把所有顶点连起来，同时总代价尽可能小，应该怎么选边？ 这类问题在现实里非常常见。比如： 修建通信网络，希望总布线成本最低； 铺设道路、电网，希望连接所有...
拓扑排序：有向无环图中的依赖关系处理
拓扑排序：有向无环图中的依赖关系处理 很多现实问题里，我们真正关心的不是“两个点连不连”，而是“谁必须先于谁发生”。例如： 课程学习中，某门课要先修另一门课； 构建系统里，某个模块要先编译依赖模块； 工作流中，某个任务必须等前置任务完成； ...
图的遍历：DFS、BFS 与连通分量
图的遍历：DFS、BFS 与连通分量 学完图的基本概念和存储方式之后，第一件真正要做的事，通常就是遍历。因为一张图只靠“画出来”是没有意义的，真正要解决问题时，你总要从某个顶点出发，沿着边把可达区域探索出来。图的遍历，正是在回答这样一个问题...
图的基本概念与存储方式
图的基本概念与存储方式 如果说树让我们从“线性结构”进入了“层级结构”，那么图则进一步把数据结构带进了“任意关系结构”的世界。在树里，关系仍然比较克制： 有根； 有层次； 通常没有回路； 节点之间路径关系较为受限。 但现实问题往往更复杂。社...
Trie 字典树：前缀匹配与字符串检索
Trie 字典树：前缀匹配与字符串检索 前面学字符串时，我们已经知道：文本处理里最常见的不只是“是否相等”，还包括前缀匹配、词典查询、自动补全、多模式检索这些问题。如果每次都把所有字符串放进数组或普通哈希表里，再靠逐个比较去判断前缀关系，很...
B 树与 B+ 树：面向磁盘与数据库索引的结构
B 树与 B+ 树：面向磁盘与数据库索引的结构 前面我们已经学过 BST、AVL、红黑树，它们都在解决一个核心问题：如何在内存中保持有序查找结构，并尽量让树高不要失控。但如果场景从“内存里的几万几百万条数据”，切换到“磁盘上的海量数据索引”...
哈夫曼树与哈夫曼编码：贪心思想的典型应用
哈夫曼树与哈夫曼编码：贪心思想的典型应用 树结构学到这里，我们已经见过很多围绕“查找效率”“结构平衡”“最值维护”展开的模型。但哈夫曼树很特别，它关心的不是查找某个键值，也不是维持集合关系，而是另一个非常现实的问题： 如果不同符号出现频率不...
并查集：连通性问题的高效解法
并查集：连通性问题的高效解法 数据结构学到这里，你会慢慢发现：并不是所有问题都在问“怎么查找某个值”“怎么维护顺序”“怎么取最小最大”。还有一类问题问得非常直接，也非常高频：两个元素是不是属于同一组？一堆对象之间是否连通？加入一条边之后，哪...
堆与优先队列：Top K 问题的经典工具
堆与优先队列：Top K 问题的经典工具 学到树结构这里，很多人会自然把注意力放在“有序查找树”上，例如 BST、AVL、红黑树。但树的价值并不只体现在查找。还有一类非常高频的问题，并不关心“整体有序”，也不要求中序遍历得到完整顺序，而是只...
红黑树：工程中常见的平衡查找树
红黑树：工程中常见的平衡查找树 在 AVL 树里，我们已经看到：如果想让 BST 长期保持高效，就必须额外控制树的形状。AVL 通过非常严格的平衡条件，把树高稳定压在较低水平，但代价是插入删除时维护成本不低。工程世界里，人们往往更希望找到一...