我的算法书 - Splay：伸展树

一句话算法

Splay 每次访问一个点后，都把它旋转到根，让刚用过的点变得更容易再次访问。

问题模型

维护一个可重复元素集合，支持六类普通平衡树操作：

插入一个数；
删除一个数；
查询一个数的排名；
查询第 $k$ 小的数；
查询一个数的前驱；
查询一个数的后继。

普通二叉搜索树可能退化成链。Splay 不依赖随机数或显式平衡因子，而是用访问后的旋转调整树形，使一串操作的均摊复杂度保持在 $O(\log n)$ 。

核心直觉

Splay 的核心动作只有一个：把节点 $x$ 旋到目标位置。

如果 $x$ 是父亲的左孩子，就对父亲做右旋；如果 $x$ 是父亲的右孩子，就对父亲做左旋。单次旋转只改变局部三段子树的位置，不改变中序遍历顺序，所以二叉搜索树性质仍然成立。

真正让 Splay 有效的是“双旋”：

zig-zig： $x$ 、父亲、祖父在同一条斜线上，先旋父亲，再旋 $x$ 。
zig-zag： $x$ 、父亲、祖父形成折线，连续旋两次 $x$ 。

“为什么不是一直单旋”

一直单旋也能把点转到根，但容易只把长链整体平移。双旋会更强地压缩访问路径，这正是 Splay 均摊高效的关键。

节点信息

每个节点维护：

value：节点的值；
count：这个值出现次数；
size：子树中元素总数，包含重复值；
child[0]、child[1]：左右孩子；
parent：父节点。

其中：

size(u)=size(left(u))+size(right(u))+count(u)

排名和第 $k$ 小查询都依赖这个 size。

算法步骤

Rotate

设要上旋的点是 x，父亲是 y，祖父是 z。

判断 x 是 y 的左孩子还是右孩子。
把 x 的相反方向子树接到 y 对应方向。
把 y 接成 x 的相反方向孩子。
把 x 接到 z 原来连接 y 的位置。
更新 y 和 x 的 size。

Splay

把 x 旋到 goal 的儿子位置；当 goal=0 时，就是旋到根。

若 x 的父亲就是 goal，做一次单旋。
否则看 x、父亲、祖父的方向：
- 方向相同：先旋父亲，再旋 x；
- 方向不同：连续旋两次 x。
重复直到 x 到达目标位置。

插入

按二叉搜索树规则查找插入位置。
如果值已经存在，只增加 count。
否则新建节点，接到对应父亲下面。
把这个节点伸展到根。

删除

先找到目标值并伸展到根。
如果 count>1，只减少 count。
如果只有一棵子树，直接用这棵子树替代根。
如果左右子树都存在：
- 取出左子树和右子树；
- 在左子树中找到最大节点；
- 把这个最大节点伸展成根；
- 把原右子树接到新根右边。

算法证明

关键不变量： 每次操作后，中序遍历仍然是从小到大的序列，size 仍然等于子树元素个数。

旋转不破坏顺序

以左旋为例。旋转前局部结构可以抽象成：

    y
   / \
  A   x
     / \
    B   C

中序遍历是：

A, y, B, x, C

旋转后：

      x
     / \
    y   C
   / \
  A   B

中序遍历仍然是：

A, y, B, x, C

所以一次旋转不破坏二叉搜索树性质。splay 只是多次旋转，因此也不破坏顺序。

插入正确

新节点先按二叉搜索树规则接到叶子位置，所以中序顺序正确。随后把它伸展到根，旋转不改变中序顺序，因此插入后仍是一棵合法二叉搜索树。

删除正确

目标节点被伸展到根后，所有比它小的值都在左子树，所有比它大的值都在右子树。

若左右子树都存在，左子树最大值没有右孩子。把它伸展为根后，再把原右子树接到它右边，仍满足：

\text{左子树所有值} < \text{新根} < \text{右子树所有值}

因此删除后的中序序列正好是原集合删去一个目标值。

复杂度分析

设当前集合大小为 $n$ 。

单次操作最坏可能是 $O(n)$ 。
任意连续 $m$ 次操作的总时间复杂度是 $O(m\log n)$ 均摊。
因此插入、删除、排名、第 $k$ 小、前驱、后继的均摊时间复杂度都是 $O(\log n)$ 。
空间复杂度是 $O(n)$ 。

代码实现

cpp

        1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253

        #include <climits>
#include <iostream>
#include <vector>
using namespace std;

struct Splay {
    struct Node {
        int child[2] = {0, 0};
        int parent = 0;
        int value = 0;
        int count = 0;
        int size = 0;
    };

    vector<Node> tree;
    int root = 0;

    Splay(int max_nodes = 0) {
        tree.reserve(max_nodes + 1);
        tree.push_back(Node()); // node 0 is the null sentinel.
    }

    int node_size(int u) const {
        return u == 0 ? 0 : tree[u].size;
    }

    void pushup(int u) {
        if (u == 0) return;
        tree[u].size = node_size(tree[u].child[0]) +
                       node_size(tree[u].child[1]) +
                       tree[u].count;
    }

    int new_node(int value, int parent) {
        tree.push_back(Node());
        int id = (int)tree.size() - 1;
        tree[id].value = value;
        tree[id].count = 1;
        tree[id].size = 1;
        tree[id].parent = parent;
        return id;
    }

    int direction(int u) const {
        int p = tree[u].parent;
        return tree[p].child[1] == u;
    }

    void connect(int child, int parent, int dir) {
        if (parent != 0) tree[parent].child[dir] = child;
        if (child != 0) tree[child].parent = parent;
    }

    void rotate(int x) {
        int y = tree[x].parent;
        int z = tree[y].parent;
        int dx = direction(x);
        int dy = (z == 0 ? 0 : direction(y));
        int middle = tree[x].child[dx ^ 1];

        connect(middle, y, dx);
        connect(y, x, dx ^ 1);
        connect(x, z, dy);

        pushup(y);
        pushup(x);
        if (z == 0) root = x;
    }

    void splay(int x, int goal = 0) {
        if (x == 0) return;
        while (tree[x].parent != goal) {
            int y = tree[x].parent;
            int z = tree[y].parent;
            if (z != goal) {
                if (direction(x) == direction(y)) rotate(y);
                else rotate(x);
            }
            rotate(x);
        }
        if (goal == 0) root = x;
    }

    int find(int value) {
        int u = root;
        int last = 0;
        while (u != 0) {
            last = u;
            if (value == tree[u].value) {
                splay(u);
                return u;
            }
            u = tree[u].child[value > tree[last].value];
        }
        if (last != 0) splay(last);
        return 0;
    }

    void insert(int value) {
        if (root == 0) {
            root = new_node(value, 0);
            return;
        }

        int u = root;
        int parent = 0;
        while (u != 0) {
            parent = u;
            if (value == tree[u].value) {
                tree[u].count++;
                pushup(u);
                splay(u);
                return;
            }
            u = tree[u].child[value > tree[u].value];
        }

        int dir = value > tree[parent].value;
        int id = new_node(value, parent);
        tree[parent].child[dir] = id;
        pushup(parent);
        splay(id);
    }

    void erase(int value) {
        int target = find(value);
        if (target == 0 || tree[target].value != value) return;

        if (tree[target].count > 1) {
            tree[target].count--;
            pushup(target);
            return;
        }

        int left = tree[target].child[0];
        int right = tree[target].child[1];

        if (left == 0) {
            root = right;
            if (root != 0) tree[root].parent = 0;
            return;
        }
        if (right == 0) {
            root = left;
            tree[root].parent = 0;
            return;
        }

        tree[left].parent = 0;
        tree[right].parent = 0;
        root = left;

        int u = left;
        while (tree[u].child[1] != 0) u = tree[u].child[1];
        splay(u);

        tree[root].child[1] = right;
        tree[right].parent = root;
        pushup(root);
    }

    // Rank is 1-based: the smallest value has rank 1.
    int rank_of(int value) {
        int u = root;
        int last = 0;
        int rank = 1;
        while (u != 0) {
            last = u;
            if (value <= tree[u].value) {
                u = tree[u].child[0];
            } else {
                rank += node_size(tree[u].child[0]) + tree[u].count;
                u = tree[u].child[1];
            }
        }
        if (last != 0) splay(last);
        return rank;
    }

    int kth(int k) {
        int u = root;
        while (u != 0) {
            int left_size = node_size(tree[u].child[0]);
            if (k <= left_size) {
                u = tree[u].child[0];
            } else if (k <= left_size + tree[u].count) {
                splay(u);
                return tree[u].value;
            } else {
                k -= left_size + tree[u].count;
                u = tree[u].child[1];
            }
        }
        return -1;
    }

    int predecessor(int value) {
        int u = root;
        int best = 0;
        int answer = INT_MIN;
        while (u != 0) {
            if (tree[u].value < value) {
                best = u;
                answer = tree[u].value;
                u = tree[u].child[1];
            } else {
                u = tree[u].child[0];
            }
        }
        if (best != 0) splay(best);
        return answer;
    }

    int successor(int value) {
        int u = root;
        int best = 0;
        int answer = INT_MAX;
        while (u != 0) {
            if (tree[u].value > value) {
                best = u;
                answer = tree[u].value;
                u = tree[u].child[0];
            } else {
                u = tree[u].child[1];
            }
        }
        if (best != 0) splay(best);
        return answer;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int m;
    cin >> m;

    Splay splay(m + 5);
    while (m--) {
        int operation, x;
        cin >> operation >> x;

        if (operation == 1) splay.insert(x);
        if (operation == 2) splay.erase(x);
        if (operation == 3) cout << splay.rank_of(x) << '\n';
        if (operation == 4) cout << splay.kth(x) << '\n';
        if (operation == 5) cout << splay.predecessor(x) << '\n';
        if (operation == 6) cout << splay.successor(x) << '\n';
    }

    return 0;
}

测试用例

输入：

输出：

解释：

插入后集合为 {3,5,5,7}；
5 的排名是 2；
第 3 小是 5；
5 的前驱是 3，后继是 7；
删除一个 5 后，7 的排名是 3。

应用分类详解

Splay 的本质是动态维护一棵可旋转的二叉搜索树。它适合“访问局部性强”或“需要通过旋转暴露某个点/区间”的问题。

一、普通平衡树操作

典型模式： 插入、删除、排名、第 $k$ 小、前驱、后继混合出现。

识别信号： 题面要求动态排名、动态第 $k$ 小、动态前驱后继。

核心建模： 用二叉搜索树维护值的顺序，用 size 维护排名信息，每次访问后伸展到根。

应用场景	经典题目	核心思路
普通平衡树模板	luogu-P3369	六个基本操作
普通平衡树加强版	luogu-P6136	操作次数多，要求稳定的对数级维护

二、访问局部性强的动态集合

典型模式： 最近访问过的元素很可能再次被访问。

识别信号： 查询集中在少量热点元素，或者操作序列有明显连续性。

核心建模： Splay 会把访问点放到根，热点元素自然更靠近根。

应用场景	经典题目	核心思路
动态排名维护	普通平衡树类题目	最近查询的值被伸展到根
可自适应搜索结构	理论模型	不需要预先知道热点分布

三、序列区间操作

典型模式： 维护一个序列，支持区间翻转、区间删除、区间插入。

识别信号： 题面出现“把 [l,r] 暴露出来”“翻转一段”“删除一段”。

核心建模： 按排名建 Splay，用两个哨兵把区间旋到某个节点的子树位置，再打标记或修改。

应用场景	经典题目	核心思路
文艺平衡树	luogu-P3391	用排名伸展暴露区间并打翻转标记
序列维护	区间编辑类题目	通过两次 splay 把目标区间变成一棵子树

经典例题

1. luogu-P3369

普通平衡树模板题。适合练习本文模板的六个基础操作。

2. luogu-P6136

普通平衡树数据加强版。重点是实现细节要稳定，size、count、父指针更新不能漏。

3. luogu-P3391

文艺平衡树。它使用的是“按排名维护序列”的 Splay，比普通平衡树多了哨兵和区间翻转标记。

参考

本书相关章节：data_structure/BST、data_structure/treap、data_structure/fhq-treap
Splay Tree Datastructure