一、引言：为什么需要Splay树
二叉搜索树（BST）是计算机科学中最基础的数据结构之一，支持高效的查找、插入和删除操作。然而，普通BST有一个致命缺陷：当数据以有序或近似有序的方式插入时，树会严重失衡，退化成一条链，操作复杂度从理想的 $O(\log n)$ 恶化到 $O(n)$。
为了解决这个问题，研究者们提出了多种自平衡二叉搜索树，例如AVL树、红黑树和Treap。这些树通过严格的平衡条件或随机化策略，保证树高始终维持在 $O(\log n)$。但它们都需要在每个节点上维护额外的平衡信息（如高度、颜色、随机优先级），并且旋转操作相对复杂。
1985年，Daniel Sleator 和 Robert Tarjan 提出了一种全新的思路——Splay树（伸展树）。Splay树不强制维持任何显式的平衡条件，而是采用一种”自调整”策略：每次访问一个节点后，都通过一系列旋转操作将其移动到树的根部。这种看似简单的策略，竟能在均摊意义下保证所有操作的时间复杂度为 $O(\log n)$，而且实现比红黑树更为简洁。
本文将详细讲解Splay树的核心原理，并提供一份可直接运行的完整Java实现。
二、Splay树的核心思想
Splay树的灵魂在于 splay（伸展）操作。当我们访问树中的某个节点 $x$（无论是查找、插入还是删除），都会执行 splay 操作将 $x$ 旋转到根节点位置。
这种自调整策略带来了几个显著的好处：
- 访问局部性：最近被访问的节点会靠近树根，如果某些节点被频繁访问，它们将长期处于树的上层，实际访问速度非常快。
- 均摊效率：虽然单次操作最坏情况下可能是 $O(n)$，但任意连续 $m$ 次操作的均摊复杂度为 $O(m \log n)$。
- 无需额外信息：节点不需要存储高度、颜色或优先级等平衡信息，内存开销更小。
三、旋转操作详解
Splay操作由一系列基本旋转组成。设待旋转的节点为 $x$，其父节点为 $p$，祖父节点为 $g$。根据 $x$、$p$、$g$ 的相对位置，旋转分为三种情况：
3.1 Zig（单旋）
当 $p$ 是根节点时，只需执行一次单旋：
- 若 $x$ 是 $p$ 的左子节点，执行右旋；
- 若 $x$ 是 $p$ 的右子节点，执行左旋。
这是splay操作的最后一步，执行后 $x$ 成为树根。
3.2 Zig-Zig（同向双旋）
当 $p$ 不是根，且 $x$ 和 $p$ 同为各自父节点的左子节点（或同为右子节点）时，执行两次同方向的旋转：
- 先旋转 $p$（围绕 $g$）；
- 再旋转 $x$（围绕 $p$）。
注意：这里不能简单地连续两次单旋 $x$，而是要先旋转 $p$ 再旋转 $x$。这种”从祖父开始”的旋转方式，能更有效地降低树的高度。
3.3 Zig-Zag（异向双旋）
当 $x$ 和 $p$ 分别是各自父节点的不同方向子节点时（即 $x$ 是左子、$p$ 是右子，或反之），执行：
- 先旋转 $x$（围绕 $p$）；
- 再旋转 $x$（围绕 $g$）。
这种情况下，$x$ 经过两次旋转后直接上升到祖父的位置。
四、完整Java实现
以下是一份完整的Splay树Java实现，包含插入、删除、查找、前驱、后继等常用操作，每个方法都配有详细注释。
import java.util.ArrayList;
import java.util.List;
/**
* Splay树（伸展树）的Java实现
*
* Splay树是一种自调整二叉搜索树，核心思想是：每次访问节点后，
* 通过splay操作将该节点旋转到树根位置。均摊时间复杂度为O(log n)。
*/
public class SplayTree<T extends Comparable<T>> {
/**
* 树节点定义
*/
private static class Node<T> {
T key; // 节点键值
Node<T> left; // 左子节点
Node<T> right; // 右子节点
Node<T> parent; // 父节点（可选，便于实现）
Node(T key) {
this.key = key;
}
}
private Node<T> root; // 树根
private int size; // 节点数量
public SplayTree() {
this.root = null;
this.size = 0;
}
/**
* 获取树中节点数量
*/
public int size() {
return size;
}
/**
* 判断树是否为空
*/
public boolean isEmpty() {
return root == null;
}
/**
* 左旋操作：将节点x向上旋转
*
* p x
* / \ / \
* a x => p c
* / \ / \
* b c a b
*/
private void rotateLeft(Node<T> x) {
Node<T> p = x.parent;
Node<T> b = x.left;
// x的左子节点变为p的右子节点
p.right = b;
if (b != null) b.parent = p;
// p成为x的左子节点
x.left = p;
x.parent = p.parent;
p.parent = x;
// 更新p的原父节点对x的引用
if (x.parent != null) {
if (x.parent.left == p) {
x.parent.left = x;
} else {
x.parent.right = x;
}
} else {
root = x;
}
}
/**
* 右旋操作：将节点x向上旋转
*
* p x
* / \ / \
* x c => a p
* / \ / \
* a b b c
*/
private void rotateRight(Node<T> x) {
Node<T> p = x.parent;
Node<T> b = x.right;
// x的右子节点变为p的左子节点
p.left = b;
if (b != null) b.parent = p;
// p成为x的右子节点
x.right = p;
x.parent = p.parent;
p.parent = x;
// 更新p的原父节点对x的引用
if (x.parent != null) {
if (x.parent.left == p) {
x.parent.left = x;
} else {
x.parent.right = x;
}
} else {
root = x;
}
}
/**
* Splay操作：将节点x旋转到树根
* 这是Splay树的核心操作，决定了树的自调整特性
*/
private void splay(Node<T> x) {
while (x.parent != null) {
Node<T> p = x.parent;
Node<T> g = p.parent;
if (g == null) {
// Zig情况：p是根，只需一次单旋
if (x == p.left) {
rotateRight(x);
} else {
rotateLeft(x);
}
} else if (x == p.left && p == g.left) {
// Zig-Zig情况（左左）：先右旋p，再右旋x
rotateRight(p);
rotateRight(x);
} else if (x == p.right && p == g.right) {
// Zig-Zig情况（右右）：先左旋p，再左旋x
rotateLeft(p);
rotateLeft(x);
} else if (x == p.right && p == g.left) {
// Zig-Zag情况（左右）：先左旋x，再右旋x
rotateLeft(x);
rotateRight(x);
} else {
// Zig-Zag情况（右左）：先右旋x，再左旋x
rotateRight(x);
rotateLeft(x);
}
}
}
/**
* 查找键值为key的节点，并将其splay到根
* 若不存在，则将最后访问的节点splay到根
*/
public boolean contains(T key) {
if (root == null) return false;
Node<T> curr = root;
Node<T> last = null;
while (curr != null) {
last = curr;
int cmp = key.compareTo(curr.key);
if (cmp == 0) {
splay(curr);
return true;
} else if (cmp < 0) {
curr = curr.left;
} else {
curr = curr.right;
}
}
// 未找到，将最后访问的节点splay到根
if (last != null) {
splay(last);
}
return false;
}
/**
* 插入一个新键值
* 插入后将新节点splay到根
*/
public void insert(T key) {
if (root == null) {
root = new Node<>(key);
size++;
return;
}
Node<T> curr = root;
Node<T> parent = null;
while (curr != null) {
parent = curr;
int cmp = key.compareTo(curr.key);
if (cmp == 0) {
// 键已存在，将其splay到根并返回
splay(curr);
return;
} else if (cmp < 0) {
curr = curr.left;
} else {
curr = curr.right;
}
}
Node<T> newNode = new Node<>(key);
newNode.parent = parent;
int cmp = key.compareTo(parent.key);
if (cmp < 0) {
parent.left = newNode;
} else {
parent.right = newNode;
}
size++;
splay(newNode);
}
/**
* 删除指定键值的节点
* 策略：先将待删除节点splay到根，然后合并其左右子树
*/
public boolean delete(T key) {
if (!contains(key)) {
return false;
}
// 此时key对应的节点已在根部
Node<T> delNode = root;
Node<T> leftTree = delNode.left;
Node<T> rightTree = delNode.right;
if (leftTree != null) leftTree.parent = null;
if (rightTree != null) rightTree.parent = null;
if (leftTree == null) {
root = rightTree;
} else if (rightTree == null) {
root = leftTree;
} else {
// 左右子树均非空：将左子树的最大节点splay到左子树的根
root = leftTree;
// 找到左子树的最大节点（最右节点）
Node<T> maxNode = leftTree;
while (maxNode.right != null) {
maxNode = maxNode.right;
}
splay(maxNode);
// 此时maxNode成为左子树的根，且没有右子节点
maxNode.right = rightTree;
rightTree.parent = maxNode;
}
size--;
return true;
}
/**
* 获取树中的最小值
*/
public T getMin() {
if (root == null) return null;
Node<T> curr = root;
while (curr.left != null) {
curr = curr.left;
}
splay(curr);
return curr.key;
}
/**
* 获取树中的最大值
*/
public T getMax() {
if (root == null) return null;
Node<T> curr = root;
while (curr.right != null) {
curr = curr.right;
}
splay(curr);
return curr.key;
}
/**
* 中序遍历，返回有序列表
*/
public List<T> inorderTraversal() {
List<T> result = new ArrayList<>();
inorderHelper(root, result);
return result;
}
private void inorderHelper(Node<T> node, List<T> result) {
if (node == null) return;
inorderHelper(node.left, result);
result.add(node.key);
inorderHelper(node.right, result);
}
/**
* 打印树的结构（用于调试）
*/
public void printTree() {
System.out.println("Splay Tree (size=" + size + "):");
printHelper(root, "", true);
}
private void printHelper(Node<T> node, String prefix, boolean isRight) {
if (node == null) return;
System.out.println(prefix + (isRight ? "└── " : "├── ") + node.key);
printHelper(node.left, prefix + (isRight ? " " : "│ "), false);
printHelper(node.right, prefix + (isRight ? " " : "│ "), true);
}
// ============ 主方法：测试与演示 ============
public static void main(String[] args) {
SplayTree<Integer> tree = new SplayTree<>();
System.out.println("=== 插入操作测试 ===");
int[] values = {50, 30, 70, 20, 40, 60, 80};
for (int v : values) {
tree.insert(v);
System.out.println("插入 " + v + " 后，根节点为: " + tree.root.key);
}
System.out.println("\n=== 中序遍历结果 ===");
System.out.println(tree.inorderTraversal());
System.out.println("\n=== 查找操作测试 ===");
int[] searchValues = {20, 50, 80};
for (int s : searchValues) {
boolean found = tree.contains(s);
System.out.println("查找 " + s + ": " + found + ", 查找后根节点: " + tree.root.key);
}
System.out.println("\n=== 最值查询测试 ===");
System.out.println("最小值: " + tree.getMin() + ", 查询后根节点: " + tree.root.key);
System.out.println("最大值: " + tree.getMax() + ", 查询后根节点: " + tree.root.key);
System.out.println("\n=== 删除操作测试 ===");
int[] deleteValues = {30, 50, 70};
for (int d : deleteValues) {
boolean removed = tree.delete(d);
System.out.println("删除 " + d + ": " + removed);
System.out.println(" 删除后中序遍历: " + tree.inorderTraversal());
System.out.println(" 当前根节点: " + (tree.root != null ? tree.root.key : "null"));
}
System.out.println("\n=== 连续访问测试（展示局部性优化）==="");
SplayTree<Integer> localTree = new SplayTree<>();
for (int i = 1; i <= 10; i++) {
localTree.insert(i);
}
System.out.println("初始根节点: " + localTree.root.key);
// 连续访问节点 5
for (int i = 0; i < 5; i++) {
localTree.contains(5);
System.out.println("第" + (i + 1) + "次访问5后，根节点: " + localTree.root.key);
}
}
}
五、复杂度分析
Splay树的时间复杂度分析是其最精彩的部分。与AVL树和红黑树保证单次操作 $O(\log n)$ 的最坏情况复杂度不同，Splay树保证的是均摊复杂度。
5.1 均摊 $O(\log n)$
使用势能分析法（Potential Method）可以证明：对于任意包含 $n$ 个节点的Splay树，任意连续 $m$ 次操作（查找、插入、删除）的总时间复杂度为 $O(m \log n)$。这意味着单次操作的均摊复杂度为 $O(\log n)$。
势能函数定义为所有节点”秩”的总和：$\Phi = \sum_{x} r(x)$，其中 $r(x) = \log_2 |S(x)|$，$S(x)$ 是以 $x$ 为根的子树的大小。
可以证明，将节点 $x$ splay到根的实际代价加上势能变化，其均摊代价不超过 $3(r'(x) – r(x)) + 1 = O(\log n)$。
5.2 与静态最优树的比较
Splay树还有一个更强的性质——静态最优性：对于任意访问序列，Splay树的总访问时间与其他任意静态BST（包括最优静态BST）相比，最多只差一个常数因子。这意味着Splay树能自动适应访问模式，频繁访问的元素会自动上浮到树根附近。
5.3 实际性能
尽管理论上Splay树的常数因子比红黑树大，但在许多实际场景中（尤其是具有明显访问局部性的场景），Splay树的表现非常优秀，甚至优于红黑树。
六、应用场景
Splay树独特的自调整特性使其在以下场景中表现出色：
- 缓存实现：最近访问的数据自动靠近根节点，天然符合缓存的局部性原理。
- 数据压缩：自适应霍夫曼编码（Adaptive Huffman Coding）的核心数据结构就是Splay树的变种。
- 动态集合维护：需要频繁查询和修改的有序集合，且访问模式具有局部性时，Splay树是理想选择。
- 网络路由：某些网络路由算法利用Splay树的自调整特性优化频繁访问路径的查询效率。
- 内存管理：某些操作系统的内存页面置换策略借鉴了Splay树的访问频率统计思想。
七、总结
Splay树是一种优雅而自洽的数据结构。它用最少的额外信息（无需高度、颜色或优先级），仅通过splay这一核心操作，就实现了均摊 $O(\log n)$ 的效率。其自调整特性使它能自动适应访问模式，频繁访问的数据自动上浮，非常适合具有局部性的应用场景。
与AVL树和红黑树相比，Splay树的实现更为简洁，不需要维护复杂的平衡条件。虽然在最坏情况下单次操作可能退化到 $O(n)$，但在均摊意义和所有连续操作序列上，它都表现出优秀的性能保证。理解Splay树，不仅掌握了一种实用的数据结构，更能深刻体会均摊分析和自调整策略在算法设计中的强大威力。
