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