064 2-3树 (2-3 Tree)

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-节点1key2左、右左子 key ≤ 右子3-节点2k1 k23左、中、右左子 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₂(n1)⌋到⌈log₃(n1)⌉之间无最坏情况退化。理论优雅插入算法纯粹通过分裂上溢实现不需要旋转结构变化局部且可预测。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需求描述F1tt_insert(t, key)将整数 key 插入2-3树忽略重复键必要时向上分裂F2tt_search(t, key)搜索 key找到返回 1否则返回 0F3tt_inorder(t, size)中序遍历返回有序整数数组调用者释放F4tt_all_leaves_same_depth(t)验证所有叶子在同一深度满足返回 1F5tt_create()/tt_destroy(t)创建和释放树性质约束ID约束描述P1所有叶子始终在同一深度完全高度平衡P2每个内部节点有 2 或 3 个子节点对应 1 或 2 个键P3键的排序关系满足 BST 性质P4插入后树仍然保持以上所有性质非功能需求所有操作时间复杂度 O(log n)内存无泄漏tt_destroy释放所有节点C99 标准gcc -stdc99 -Wall无警告编译验收标准测试编号测试描述预期结果TC1插入[3,7,1,5,9,2,6,8,4]后执行中序遍历输出有序序列[1,2,3,4,5,6,7,8,9]共9个元素TC2a对上述树搜索已存在的键1-9每个全部返回 1TC2b搜索不存在的键0, 10, 100全部返回 0TC3每次插入一个键后立即调用tt_all_leaves_same_depth每次插入后均返回 1始终完全平衡TC4插入20个不同键乱序搜索全部键并验证平衡20个键全部可搜索到且tt_all_leaves_same_depth返回1