伸展树的自动优化核心是“访问驱动重构”，即通过zig、zig-zig、zig-zag旋转将被访问节点伸展至根，不依赖频次统计而天然适配局部热点，均摊时间复杂度o(log n)，适合读多写少、访问局部性强的场景。
伸展树的自动优化，核心不是“预设平衡”，而是“访问驱动重构”——每次查找、插入或删除后，目标节点都会被通过旋转逐步推至根部。这种上浮不是简单搬运，而是利用 zig、zig-zig、zig-zag 三类旋转组合，在保持 bst 有序性的前提下，动态缩短高频路径。它不保证单次操作最快，但对重复访问、局部聚集的场景（比如缓存热点、会话 id 查询、日志时间戳范围扫描），均摊性能显著优于静态平衡树。
高频变量为何能“自动上浮”？
伸展树不记录访问频次，也不维护计数器。它的“高频感知”来自访问行为本身触发的结构响应
- 只要某个键被查找（
search），无论是否存在，只要路径经过，最终都会执行splay操作，把命中节点（或失败时的叶父节点）拉到根； - 插入后立即伸展新节点，使刚加入的数据成为下次访问的“近邻”；
- 删除某节点后，会伸展其替代者（如后继或前驱），延续热度传导。
这相当于把“最近用过”直接映射为“物理位置最高”，天然契合 90-10 法则：10% 的热数据反复出现，它们就会持续靠近根，后续访问深度快速收敛到 O(1)～O(log n) 之间。
三种旋转模式决定上浮效率
伸展不是盲目上提，而是根据节点在访问路径中的相对位置选择最优旋转序列：
- Zig（单旋）：目标节点父节点就是根 → 直接一次左旋或右旋，一步到位；
- Zig-zig（同向双旋）：目标 v、父 p、祖父 g 在一条斜线上（如 v 是 p 的左子，p 是 g 的左子）→ 先绕 p 右旋，再绕 g 右旋；效果是 v 一次升两层，且整段左链被“展平”；
- Zig-zag（折线双旋）：v 和 p 分属不同侧（如 v 是 p 的右子，p 是 g 的左子）→ 先绕 p 左旋，再绕 g 右旋；等效于先校正方向，再上提，避免路径扭曲。
关键点：zig-zag 比 zig-zig 更倾向于将 v 推向中序遍历中间位置，有利于后续区间查询；而 zig-zig 则更激进压缩深度，适合纯点查场景。
实战：手动模拟一次 key=3 上浮过程
假设初始树为：
4
/ \
2 6
/ \ / \
1 3 5 7
查找 3 的路径是 4→2→3。3 的父是 2，祖父是 4，且 3 是 2 的右子、2 是 4 的左子 → 属于 zig-zag 情况：
- 第一步：3 绕 2 左旋 → 2 成为 3 的左子，原 3 的左子（空）挂给 2 的右；
- 第二步：3 绕 4 右旋 → 4 成为 3 的右子，原 4 的左子（现为 2 子树）整体挂给 3 的左。
结果树变为：
3
/ \
2 4
/ / \ \
1 5 6 7
3 已到根，且其左子树（1,2）和右子树（4,5,6,7）规模更均衡——一次访问就完成了局部优化。
使用建议与注意事项
伸展树适合用在读多写少、访问有强局部性、且难以预估数据分布的场景：
- Web 服务器 session 管理：用户 ID 频繁读写，新会话不断插入，旧会话超时删除；
- 内存中 LRU 缓存索引：配合哈希表存储值，伸展树维护访问时序；
- 交互式命令行历史搜索：最近执行的命令最可能再次调用。
慎用场景：
— 数据随机访问、无明显热点（此时伸展开销反成负担）；
— 实时性要求极严的单次操作（最坏 case 可能 O(n)）；
— 需要稳定最坏复杂度的嵌入式或金融系统（应选 AVL 或红黑树）。
