Splay 操作与均摊分析

Splay 操作是伸展树中最核心的调整过程,它在每次访问某节点后,通过一连串特定的双层旋转把该节点旋转到树根。虽然单次 Splay 在最坏情况下可能很慢,但用势能法进行均摊分析可以证明,任意一系列操作的平均代价仍为对数级,这使 Splay 操作成为均摊复杂度分析的教科书案例。

概述

伸展树是一种自调整的二叉搜索树,不显式维护平衡信息,而是依赖 Splay 操作把近期访问的节点提升到靠近根的位置,从而带来良好的局部性和均摊性能。理解 Splay 的关键在于其三种旋转组合以及配套的均摊分析方法,后者由 Daniel Sleator 与 Robert Tarjan 在提出伸展树时给出。

核心原理

Splay 通过三类旋转把目标节点逐步上移:

• Zig:当目标节点的父节点即为根时,做一次单旋直接把它转到根。
• Zig-Zig:当目标节点与父节点相对祖父同为左儿子或同为右儿子时,先旋转父节点再旋转目标节点。
• Zig-Zag:当目标节点与父节点方向相反时,连续对目标节点做两次方向不同的旋转。
• 均摊分析:定义势能为各节点子树大小对数之和,证明每次 Splay 的实际代价加上势能变化不超过对数级,由此得到均摊对数复杂度。

应用场景

Splay 操作使伸展树天然适合有局部性访问模式的数据,如缓存、区间维护、可翻转序列等;其均摊分析方法本身也被推广到许多自调整结构。势能法作为一种通用的均摊分析框架,还用于分析动态数组扩容、并查集、斐波那契堆等结构。

常见问题

问:为什么 Zig-Zig 要先旋父节点再旋自己,而不是连旋两次自己?答:先旋父节点的顺序能更均衡地压缩访问路径,是保证均摊分析成立的关键;若顺序错误,均摊复杂度可能退化。

问:均摊对数是否意味着单次操作也是对数?答:不是。单次 Splay 最坏可达线性,但在一系列操作中,昂贵操作会通过势能变化被廉价操作补偿,平均下来每次为对数级。