伸展树 (Splay Tree) — 5W1H故事与需求定义066伸展树极简的优雅Who谁发明者Daniel Dominic Sleator 和 Robert Endre Tarjan于1985年在论文《Self-Adjusting Binary Search Trees》中提出发表于Journal of the ACM。理论背景Robert Tarjan 同时也是斐波那契堆、不相交集合Union-Find等数据结构的发明人之一Sleator 则是竞争分析competitive analysis领域的奠基人。使用者GCC编译器链接器的符号表管理、网络路由缓存、数据库查询优化器凡具有访问局部性temporal locality特征的应用均是理想场景。What什么伸展树是一种自调整二叉搜索树核心思想每次访问搜索、插入、删除某节点后通过一系列旋转将该节点移至树根——称为伸展splay操作。三种伸展情形情形条件操作Zigx的父节点p是根对p单旋将x转为根Zig-Zigx与p在祖父g的同侧同左或同右先旋p再旋x避免退化Zig-Zagx与p在祖父g的异侧一左一右对x连续旋转两次摊销复杂度单次操作最坏 O(n)但 m 次操作总代价 O(m·log n)摊销 O(log n)无需存储额外的平衡信息无颜色、无高度字段。When何时访问模式具有时间局部性时近期访问的节点很快被再次访问伸展树优于AVL/红黑树因为热点节点自动移至根附近。需要最简实现时伸展树不需要额外的平衡信息颜色、高度代码更简洁。允许摊销分析、不要求单次操作的最坏保证时。竞技编程中因实现简洁常被采用。Where何处GCClibiberty中的符号表使用伸展树实现早期版本。Windows NT内核虚拟内存管理器使用伸展树管理VADVirtual Address Descriptor树。数据库缓冲池利用伸展树将热点页保持在树的浅层实现高效LRU近似。网络路由IP查找表的快速访问。Why为何自适应性频繁访问的元素自动靠近根形成访问频率越高越快的自然优化——无需额外缓存层。无额外存储相比红黑树1 bit颜色、AVL树2 bit高度差伸展树节点只需 key 三个指针空间更紧凑。实现简单核心逻辑仅三种旋转情形代码量远少于红黑树的5个修复情形。理论优雅Tarjan 用势能分析potential function Σ log(size(x))严格证明摊销 O(log n)是摊销分析的经典教学案例。How如何核心操作操作摊销复杂度说明splay(x)O(log n)将节点 x 旋转至根search(key)O(log n)BST查找 → 对找到或最近节点执行splayinsert(key)O(log n)BST插入 → 对新节点splaydelete(key)O(log n)search → 删除根 → 合并左右子树删除策略Splay 目标节点 z 至根。分离左子树 L 和右子树 R。在 L 中 splay 最大节点 m使 m 成为 L 的根m 无右孩子。令m-right R完成合并。需求定义功能需求ID需求描述F1splay_insert(t, key)插入整数 key忽略重复F2splay_search(t, key)搜索 key将最近访问节点splay至根找到返回节点指针否则返回 NULLF3splay_delete(t, key)删除 key 对应节点若存在F4splay_inorder(t, size)中序遍历返回有序整数数组调用者释放F5splay_create()/splay_destroy(t)创建和释放树性质约束ID约束描述P1搜索后被访问节点或其前驱成为根P2中序遍历始终输出有序序列BST性质不变P3空树上的搜索、删除、遍历操作不导致崩溃非功能需求摊销时间复杂度 O(log n)无内存泄漏C99 标准gcc -stdc99 -Wall无警告编译验收标准测试编号测试描述预期结果TC1插入[5,3,7,1,4,6,8]搜索所有 7 个键全部返回非 NULLTC2依次搜索1,7,4,8,3每次检查t-root-key每次搜索后根节点等于被搜索的键TC3对插入上述序列的树执行中序遍历输出严格递增序列[1,3,4,5,6,7,8]TC4删除键 3 和 7 后搜索已删除键搜索剩余键已删除键返回 NULL剩余键返回非 NULLTC5对空树调用search(42)、delete(99)、inorder不崩溃search返回NULLinorder返回空数组