四、串与 KMP 核心
1. 朴素匹配 vs KMP
朴素(BF)：主串指针 i 回溯，最坏 O(n·m)
KMP：主串 i 不回溯，靠 next[] 移动模式串，O(n+m)
2. next / nextval 数组
next[j] = 模式串 P[0..j−1] 的最长相等真前后缀长度（失配时模式串右移位数）
next[0] = −1；next[j] = k（使 P[0..k−1]==P[j−k..j−1] 的最大 k）
nextval[j] = (P[j]==P[next[j]]) ? nextval[next[j]] : next[j] （再压缩）
📌 手算 next：对每个 j，找"前缀==后缀"的最大长度；next[j] 等于该长度值（j=0 特判 −1）。nextval 是 next 的优化版，避免连续相同字符重复比较。
3. 数组地址（行/列优先）
行优先：Loc(i,j) = base + (i·n + j)·w （m行n列，起始(i,j)=(0,0)）
列优先：Loc(i,j) = base + (j·m + i)·w
三维/特殊矩阵（对称、三角、稀疏）按压缩存储规律换算一维下标。
五、树与二叉树 核心
1. 二叉树五大性质 必背
① 第 i 层最多 2ⁱ⁻¹ 个节点（i≥1）
② 深度为 k 的二叉树最多 2ᵏ − 1 个节点
③ 任意二叉树 n₀ = n₂ + 1（叶子=度为2节点+1）
④ 完全二叉树节点数 n，深度 ⌊log₂n⌋ + 1
⑤ 编号 i（从1）：父⌊i/2⌋，左子2i，右子2i+1；从0编号则父⌊(i−1)/2⌋
2. 遍历
先序 DLR / 中序 LDR / 后序 LRD；层次遍历用队列
📌 中序+先序 或 中序+后序 可唯一确定二叉树；先序+后序不能（仅能定根，不能确定左右）。
3. 线索二叉树
n节点二叉树有 n+1 个空指针 → 用作线索（指向前驱/后继）
ltag=0指向左孩、=1指向前驱；rtag=0指向右孩、=1指向后继。中序线索化可实现 O(1) 找前驱后继。
4. 哈夫曼树（最优二叉树）
WPL = Σ wᵢ · lᵢ （w权重，l路径长度）；哈夫曼树使 WPL 最小
构造：每次取权最小的两棵合并，新权=二者之和，反复至单树。没有度为1的节点（n₂=n₀−1）。
5. 二叉排序树 BST / 平衡树 AVL
BST：左子树 < 根 < 右子树；查找/插入/删除平均 O(log n)（退化链表 O(n)）
AVL：任意节点 |h_L − h_R| ≤ 1；失衡后 LL/LR/RL/RR 旋转调整
⚠ 平衡因子 = 左高 − 右高 ∈ {−1,0,1}。插入后从插入点向上更新，第一个失衡点为旋转根。
6. B 树 / B+ 树 必背
m阶B树：根[1, m−1]关键字；非根[⌈m/2⌉−1, m−1]；孩子数 = 关键字数+1
高度(含叶) h：满足 ⌈m/2⌉^(h−1) ≤ n+1 ≤ m^h（n为关键字总数）
B+树：所有关键字在叶子层且链表相连，非叶只作索引；更适合范围查询与数据库索引。
六、图 核心
1. 图的基本概念
无向完全图边数 = n(n−1)/2；有向完全图 = n(n−1)
生成树边数 = n − 1；连通分量、强连通分量
邻接矩阵 O(n²)、适合稠密图；邻接表 O(n+e)、适合稀疏图。有向图入度/出度分别统计。
2. 最小生成树 MST
- Prim：从一点起，每次加连接已选集的最小边；O(n²)，适合稠密
- Kruskal：边按权排序，按不形成环依次加入；O(e log e)，适合稀疏
3. 最短路径
Dijkstra（单源，非负权）：每轮选距离最小未访问点，松弛其邻边；O(n²)/O((n+e)log n)
Floyd（多源）：DP， Dᵏ[i][j] = min(Dᵏ⁻¹[i][j], Dᵏ⁻¹[i][k]+Dᵏ⁻¹[k][j])；O(n³)
⚠ Dijkstra 不能处理负权边（会出错）；有负权用 Bellman-Ford / SPFA。
4. 拓扑排序 / 关键路径
拓扑：每次删入度0点；有环则无法完成全部排序
关键路径：ve(最早)=max(前驱ve+权)；vl(最晚)=min(后继vl−权)
活动最早 e=ve(弧尾)，最晚 l=vl(弧头)−权；e == l 的活动为关键活动
📌 关键路径长度是工程最短总工期；缩短非关键活动不影响总工期。