数据结构与算法

Lomuto 与 Hoare 两种划分方案、最坏与最好情况的递归式、随机化快排期望 O(n log n) 的指示随机变量证明、为什么「常数比例分割」就足够、三路划分处理重复元素，以及 Go 的 pdqsort 做了哪些工程加固。

决策树模型下 Ω(n log n) 下界的完整证明、下界成立的前提是什么、突破下界的三种线性排序（计数、基数、桶）及其各自的额外假设与适用条件。

第 k 小元素问题：随机化快速选择的期望线性时间证明、中位数的中位数（BFPRT）为什么保证最坏线性、递归式 T(n)=T(n/5)+T(7n/10)+O(n) 的求解，以及为什么组大小必须取 5。

被公认最容易写错的算法：三种边界写法的循环不变式、溢出与死循环的成因、lower_bound/upper_bound 的统一模型、旋转数组与峰值等变体，以及「二分答案」这一把最优化问题转成判定问题的通用技巧。

有序字典 ADT 与 BST 性质、四种遍历、查找/前驱/后继/最值的实现、删除的三种情形与「两个孩子」的标准处理、随机构建 BST 期望高度 O(log n) 的证明，以及为什么真实工作负载下必须平衡。

旋转是所有平衡树的共同原语：它为什么保持 BST 性质。AVL 的平衡因子不变式、高度上界 1.44 log n 的斐波那契证明、插入的四种失衡情形与修复、删除为什么可能需要 O(log n) 次旋转。

先讲 2-3-4 树的分裂与合并，再把红黑树理解为它的二叉表示——五条不变式因此不再是天书。含黑高定理 h ≤ 2log(n+1) 的证明、插入的三种修复情形、左倾红黑树的简化实现，以及删除为什么只需 O(1) 次旋转。

外存模型：为什么当访问代价是块传输时，二叉树是错的结构。B 树的定义与高度分析、分裂与合并、B+ 树为什么成为所有数据库索引的标准，以及 LSM 树对写密集负载的不同答案。

不靠旋转规则、靠随机数维持平衡的两种结构：跳表的多级索引与期望 O(log n) 证明、Treap 的堆序优先级与「随机 BST 等价」定理、split/merge 这对强大的原语，以及为什么 Redis 和 LevelDB 选择跳表。

增强方法论的四个步骤与「可维护性定理」、顺序统计树（Rank/Select）、区间树的重叠查询与正确性证明、前缀和结构（树状数组与线段树）的对比，以及按大小 split 的平衡树序列。