用 TodoWrite 做任务分解：把大任务拆成可追踪、可验证的步骤，并接入 TaoToken 统一 Key
2026/10/3 6:32:34
2-3树 (2-3 Tree) — 5W1H故事与需求定义
0642-3树：支撑我们数字世界的无名巨人
Who（谁）
发明者：John Hopcroft 于1970年提出（有时与 Aho、Ullman 合著的相关工作并列引用）。
推广者：Donald E. Knuth 在 TAOCP 第3卷第6.2.4节中详细讨论了多路搜索树（Multiway Trees）的理论，2-3树是其最简形式。
继承者：2-3树是 B 树（B-Tree）的特例（阶数为3），也是2-3-4树和红黑树的理论前身——Guibas/Sedgewick证明2-3-4树与红黑树等价。
使用者：数据库系统、文件系统（B+树的概念来源），以及计算机科学教育中讲授平衡树的经典素材。
What（什么）
2-3树是一种完全高度平衡的多路搜索树，节点有两种类型：
| 节点类型 | 键数 | 子节点数 | 排序关系 |
|---|---|---|---|
| 2-节点 | 1（key） | 2（左、右） | 左子 < key ≤ 右子 |
| 3-节点 | 2（k1 < k2） | 3（左、中、右） | 左子 < k1；中子在 [k1, k2)；右子 ≥ k2 |
核心性质：所有叶子节点处于同一层——树是完全高度平衡的，无需存储平衡因子或颜色信息。
插入分裂：若插入导致节点溢出（临时变为4-节点），则将中间键上升到父节点，节点一分为二；若根溢出，则树高增加1。
When（何时）
- 需要教学/理解B树和红黑树的概念原型时，2-3树是最清晰的入门模型。
- 需要完全高度平衡（而非"近似"平衡）的有序数据结构时。
- 在磁盘IO密集型应用中，多路节点减少树高，降低磁盘访问次数（B树的动机）。
Where（何处）
- 教育领域：算法教材（Sedgewick《算法》、Knuth TAOCP）将2-3树作为B树和左倾红黑树的教学基础。
- 数据库/文件系统：B+树（MySQL InnoDB、PostgreSQL、NTFS、ext4）是2-3树推广到更大阶数的工业实现。
- 函数式语言：Haskell 等语言的有序映射（Data.Map）底层使用平衡树，理论原型即为2-3树或其变体。
Why（为何）
- AVL/红黑树的旋转复杂：2-3树通过节点分裂（而非旋转）保持平衡，逻辑直观，易于证明正确性。
- 完美平衡：所有叶子在同一深度，查找路径长度严格等于
⌊log₂(n+1)⌋到⌈log₃(n+1)⌉之间，无最坏情况退化。 - 理论优雅：插入算法纯粹通过"分裂上溢"实现，不需要旋转，结构变化局部且可预测。
- B树桥梁：理解2-3树的分裂机制，直接迁移到B树（阶数为任意t），是学习存储引擎设计的最短路径。
How（如何）
核心操作
| 操作 | 时间复杂度 | 说明 |
|---|---|---|
| 搜索 | O(log n) | 每层最多比较2次键，决定进入哪个子树 |
| 插入 | O(log n) | 找到叶节点 → 插入 → 向上分裂（若溢出） |
| 中序遍历 | O(n) | 递归中序，3-节点需访问两个键和三个子树 |
插入分裂流程
插入 key 到叶节点： 若叶是 2-节点：直接变为 3-节点，完成。 若叶是 3-节点： 临时构造 4-节点（3个键，4个子），取中间键 m → 左半变为 2-节点，右半为新 2-节点 → 将 m 上升到父节点，递归处理父节点 → 若根节点溢出：创建新根（树高 +1）节点结构（本实现）
typedefstructTTNode{intkeys[2];/* 最多 2 个键 */intn_keys;/* 1 或 2 */structTTNode*child[3];/* 最多 3 个子节点 */}TTNode;需求定义
功能需求
| ID | 需求描述 |
|---|---|
| F1 | tt_insert(t, key)：将整数 key 插入2-3树，忽略重复键，必要时向上分裂 |
| F2 | tt_search(t, key)：搜索 key，找到返回 1，否则返回 0 |
| F3 | tt_inorder(t, &size)：中序遍历，返回有序整数数组（调用者释放） |
| F4 | tt_all_leaves_same_depth(t)：验证所有叶子在同一深度，满足返回 1 |
| F5 | tt_create()/tt_destroy(t)：创建和释放树 |
性质约束
| ID | 约束描述 |
|---|---|
| P1 | 所有叶子始终在同一深度（完全高度平衡） |
| P2 | 每个内部节点有 2 或 3 个子节点（对应 1 或 2 个键） |
| P3 | 键的排序关系满足 BST 性质 |
| P4 | 插入后树仍然保持以上所有性质 |
非功能需求
- 所有操作时间复杂度 O(log n)
- 内存无泄漏：
tt_destroy释放所有节点 - C99 标准，
gcc -std=c99 -Wall无警告编译
验收标准
| 测试编号 | 测试描述 | 预期结果 |
|---|---|---|
| TC1 | 插入[3,7,1,5,9,2,6,8,4]后执行中序遍历 | 输出有序序列[1,2,3,4,5,6,7,8,9]，共9个元素 |
| TC2a | 对上述树搜索已存在的键（1-9每个） | 全部返回 1 |
| TC2b | 搜索不存在的键（0, 10, 100） | 全部返回 0 |
| TC3 | 每次插入一个键后立即调用tt_all_leaves_same_depth | 每次插入后均返回 1（始终完全平衡） |
| TC4 | 插入20个不同键（乱序），搜索全部键并验证平衡 | 20个键全部可搜索到，且tt_all_leaves_same_depth返回1 |