伸展树(Splay Tree)

定义

伸展树(Splay Tree)由 Daniel Sleator 和 Robert Tarjan 于 1985 年提出,是一种自调整二叉搜索树:每次访问某节点后,通过一系列旋转(伸展操作)将其移动到根部。

原理

伸展操作按父子祖三代的形态分为 zig、zig-zig、zig-zag 三种情形组合旋转。虽然单次操作最坏可达 O(n),但势能分析证明任意操作序列的均摊复杂度为 O(log n)。最近访问的元素靠近根部,天然利用访问局部性。

应用

伸展树无需存储平衡因子或颜色,常用于实现可分裂合并的序列(区间翻转等文艺平衡树问题)、缓存类结构和网络流算法中的 Link-Cut Tree 底层组件;Windows NT 内核与部分内存分配器历史上也使用过伸展树。

优缺点

优点是实现相对简单、空间省、对偏斜访问模式接近最优(静态最优性猜想);缺点是最坏单次操作慢、每次读也要写(旋转),并发场景不友好。