)
伸展树 (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）"操作。
三种伸展情形：
| 情形 | 条件 | 操作 |
|---|---|---|
| Zig | x的父节点p是根 | 对p单旋（将x转为根） |
| Zig-Zig | x与p在祖父g的同侧（同左或同右） | 先旋p，再旋x（避免退化） |
| Zig-Zag | x与p在祖父g的异侧（一左一右） | 对x连续旋转两次 |
摊销复杂度：单次操作最坏 O(n)，但 m 次操作总代价 O(m·log n)（摊销 O(log n)），无需存储额外的平衡信息（无颜色、无高度字段）。
When（何时）
- 访问模式具有时间局部性时（近期访问的节点很快被再次访问），伸展树优于AVL/红黑树，因为热点节点自动移至根附近。
- 需要最简实现时：伸展树不需要额外的平衡信息（颜色、高度），代码更简洁。
- 允许摊销分析、不要求单次操作的最坏保证时。
- 竞技编程中因实现简洁常被采用。
Where（何处）
- GCC：
libiberty中的符号表使用伸展树实现（早期版本）。 - Windows NT内核：虚拟内存管理器使用伸展树管理VAD（Virtual 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查找 → 对找到（或最近）节点执行splay |
| insert(key) | O(log n) | BST插入 → 对新节点splay |
| delete(key) | O(log n) | search → 删除根 → 合并左右子树 |
删除策略
- Splay 目标节点 z 至根。
- 分离左子树 L 和右子树 R。
- 在 L 中 splay 最大节点 m（使 m 成为 L 的根，m 无右孩子）。
- 令
m->right = R，完成合并。
需求定义
功能需求
| ID | 需求描述 |
|---|---|
| F1 | splay_insert(t, key)：插入整数 key，忽略重复 |
| F2 | splay_search(t, key)：搜索 key，将最近访问节点splay至根；找到返回节点指针，否则返回 NULL |
| F3 | splay_delete(t, key)：删除 key 对应节点（若存在） |
| F4 | splay_inorder(t, &size)：中序遍历，返回有序整数数组（调用者释放） |
| F5 | splay_create()/splay_destroy(t)：创建和释放树 |
性质约束
| ID | 约束描述 |
|---|---|
| P1 | 搜索后，被访问节点（或其前驱）成为根 |
| P2 | 中序遍历始终输出有序序列（BST性质不变） |
| P3 | 空树上的搜索、删除、遍历操作不导致崩溃 |
非功能需求
- 摊销时间复杂度 O(log n)
- 无内存泄漏
- C99 标准，
gcc -std=c99 -Wall无警告编译
验收标准
| 测试编号 | 测试描述 | 预期结果 |
|---|---|---|
| TC1 | 插入[5,3,7,1,4,6,8]，搜索所有 7 个键 | 全部返回非 NULL |
| TC2 | 依次搜索1,7,4,8,3，每次检查t->root->key | 每次搜索后根节点等于被搜索的键 |
| TC3 | 对插入上述序列的树执行中序遍历 | 输出严格递增序列[1,3,4,5,6,7,8] |
| TC4 | 删除键 3 和 7 后：搜索已删除键；搜索剩余键 | 已删除键返回 NULL；剩余键返回非 NULL |
| TC5 | 对空树调用search(42)、delete(99)、inorder | 不崩溃，search返回NULL，inorder返回空数组 |