B 树和 B+ 树适用于频繁的 I/O 操作，广泛应用于文件存储系统以及数据库系统中。 转载自 https://www.jianshu.com/p/cf7dba86c391 B 树 定义 B 树（B-tree）是一种平衡的多路查找树，结点最大的孩子数目称为 B 树的阶（Order）。 多路查找 ...

**红黑树（Red Black Tree）**是一种自平衡二叉查找树。 在 1972 年由 Rudolf Bayer 发明的，当时被称为平衡二叉B树（symmetric binary B-trees）。后来，在1978年被 Leo J. Guibas 和 Robert Sedgewick 修改为如 ...

树状数组 树状数组 又名 二叉索引树（Binary Indexed Tree，BIT）：多用于高效计算数列的 前缀和， 区间和，可以用于 在线查询。 最早由 Peter M. Fenwick 于 1994 年提出，又以其发明者命名为Fenwick树 lowbit 运算 lowbit(x) = ...

今天，重拾《数据结构》中学到的 KMP 算法，印象中 KMP 是《数据结构》中最难的一个点。 KMP 解决的是否 字符串的匹配问题：如果给出两个字符串 text 和 pattern，需要判断字符串 pattern 是否是 text 的子串。 暴力解法时间复杂度为 O(nm)O(nm)O(nm)，而 ...

AOV 和 AOE 顶点活动（Activity On Vector，AOV）网 是指 顶点表示活动，而 边集表示活动间优先关系 的 有向图。AOV 显然不能存在环，否则会逻辑错误。 边活动（Activity On Edge，AOE）网 是指用 带权边集表示活动，而 顶点表示事件 的 有向图，其中边 ...

**最小生成树（Minimum Spanning Tree，MST） **是在一个给定的 无向图 G(V, E) 中求一棵树，使得这棵树拥有 G 的所有顶点，且所有的边都来自 G，并且满足整棵树的 边权和最小。 最小生成树的性质： MST 是棵树，因此 E = V - 1，且不存在环 MST 不唯 ...

之前在算法课的学习就总结了一下最短路径与最小生成树的区别，顺便提了一下思路，不过那时的最短路径只有常见的 Dijkstra 算法，现在对最短路径几种常见的算法进行补充。 最短路径：对任意给出的图 G(V, E) 和起点 S、终点 T，如何求出从 S → T 的最短路径。 本文具体介绍的算法有：Dij ...

图的定义 图(Graph) 由 顶点(Vertex) 和 边(Edge) 组成，每条边的两端都必须是两个顶点。 二元组定义 图 G 是一个 有序二元组 (V, E)，其中 V 称为 顶集 (Vertices Set)，E 成为 边集 (Edges Set)，E 与 V 不相交。 E 的元素都是二 ...

扩展欧几里得算法 扩展欧几里得算法 (Extended Euclidean algorithm) 是欧几里得算法（辗转相除法）的扩展。 给定两个 非零整数 a 与 b，必存在有 整数 x 与 y，使得 ax+by=gcd(a,b)ax + by = gcd(a, b)ax+by=gcd(a,b) ...

头文件 algorithm 定义一个函数集合，特别设计用于元素范围，主要应用于 STL 的 Containers。 引入 algorithm ，需在 std 命名空间中。 max()、min()、abs() 返回最大值、最小值、绝对值（整数） 浮点型的绝对值使用 math.h 里的 fabs ...