数据结构
2024-07-06数据结构-伸展树（Splay）
Filberte
·
2023-09-25 22:00:54
·
算法·理论
伸展树，英文名叫 Splay Tree，是著名的 Tarjan 先生发明的一个神奇的数据结构。其本质是一棵二叉查找树，可以实现平衡树的所有操作，而且它的所有操作都基于伸展操作（将某个节点调整到根）。
另外提一嘴，这玩意叫 Splay，并不叫 Spaly。
基本操作
平衡树所有的操作 Splay 都可以做，而且在树上启发式合并的时候 Treap 甚至有时间复杂度上的优势。
旋转操作
与 treap 的旋转操作类似，这里将左旋和右旋合二为一了。先上一张经典的图：
我们把节点 x 的父亲称作 y，把 y 的父亲（如果有的话）称作 z。首先我们判断下 x 是 y 的左儿子还是右儿子，记为 k，若 k = 0 说明是左儿子， k = 1 说明是右儿子。先把 x 偏向 y 那一侧的儿子跟 y 相连，接着把 x 和 y 相连，最后把 x 和 z 相连（如果有的话）。不要忘了更新旋转后的 siz 等信息，更新时必须按照父子关系更新。
代码：
int get(int x){return ch[fa[x]][1] == x;}
void rotate(int x) {
int y = fa[x], z = fa[y] , k = get(x);//判断
ch[y][k] = ch[x][k ^ 1];
if(ch[x][k ^ 1]) fa[ch[x][k ^ 1]] = y;// x 的某个子节点 & y
ch[x][k ^ 1] = y;
fa[y] = x;// x & y
if(z) ch[z][ch[z][1] == y] = x;
fa[x] = z;//x & z
push_up(y);push_up(x);
}
Splay操作
伸展树最核心的操作，其目的就是把节点 x 调整都根节点。将 x 的父节点称作 p，p 的父亲称作 g。如何操作主要取决于 3 个因素： p 是不是根节点，x 是 p 的左儿子还是右儿子， p 是 g 的左儿子还是右儿子。
如果 p 是根节点，那么旋一次即可，一步到位，非常简单。
接下来假设 p 不是根节点。有四种不同的情况：x 为 p 左儿子且 p 为 g 左儿子，x 为 p 右儿子且 p 为 g 右儿子，x 为 p 右儿子且 p 为 g 左儿子，x 为 p 左儿子且 p 为 g 右儿子。由于 1,2 两种情况类似， 3,4 两种情况类似，只分析第 1 种和第 3 种。
zig-zig / zag-zag ：如图所示，对应第 1 种情况（第 2 种情况也是相同处理的方式，因为我们已经把左旋右旋合二为一了）。此时我们先将 g 旋转一次，再将 x 旋转一次，就能得到图右边的新形态。这里注意旋转时的顺序，如果顺序不同，会导致得到的树的形态不同，最终无法进行势能分析。
zig-zag/zag-zig：如图所示，对应第 3 种情况。此时我们是将 x 连续旋转两次，就能把它旋转到根。
这样子，我们每次可以将 x 的深度减少 2（最后一次可能是 1），最后总能将 x 调整到根节点。
代码：
void splay(int x) {
while(fa[x]){
if(fa[fa[x]]) rotate(get(x) == get(fa[x]) ? fa[x] : x);
rotate(x);
}
rt = x;
}
合并操作
这里的合并操作，要求伸展树 x 中每个元素都小于伸展树 y 中每个元素，与后文的启发式合并作区分。如果 x 树或者 y 树为空，那么直接返回另一棵树的根节点即可。否则将 x 中最大的元素 mx 旋到根，此时 mx 的右子树为空，直接把 y 接上就好了记得更新节点信息。
删除操作
首先在原树中找到 x 这个数，把它旋到根，如果值为 x 的数不止一个，直接减掉一个就行；如果只有一个，那么合并它的左右儿子。
插入操作
在原树上找这个值，找得到就把这个值的次数加一，更新节点信息；找不到就新建一个节点。最后别忘了把这个点旋到根。
查询操作
求 x 的排名，就相当于找小于等于 x - 1 的数有多少个，最后加一就是结果。
求排名为 x 的数，不断判断以目前节点为根的子树大小与剩余排名的关系，若小于，去左子树找；否则如果左子树的大小加上这个值的次数小于等于剩余排名，返回这个数；前两者都不满足，就去右子树找。
求某个数的前驱，就先在树中找到这个数，接着找到它左子树里最靠右边的节点。后继同理，在右子树里找最左边的节点。
当然，找到某个点后还是要通过把这个点旋到根节点的方式，来保证均摊的时间复杂度。
总结
其实还是挺好写的，但是在访问一个点后容易忘掉把它旋到根节点，修改一个点的值后容易忘记更新节点信息。
当然像刘昊，花花这种对璇那么上心的人肯定是不会忘的啦。
时间复杂度分析
这一部分其实才是伸展树算法的难点（但貌似不会也没有关系）。它采用了一个叫“势能分析” 的神奇分析方法，但众所周知，信息是一个看结果的学科，谁爱分析谁分析去吧。
定理：假设最多有 n 个点，在进行 m 次 Splay 操作后，总复杂度是 O(m \log n + n \log n)。
证明谁爱写谁写，反正不会没关系。有了这个定理，我们就可以证明对于所有操作，均摊都是 O(\log n) 的。
放一张 oi-wiki 的图上来，感兴趣的读者可以自行阅读。
#include
using namespace std;
const int inf = 1e9 + 100;
const int N = 1e5 + 100;
int ch[N][2], fa[N];
int val[N], siz[N], cnt[N], idx;
int rt;
int New(int x){
val[++idx] = x;
siz[idx] = cnt[idx] = 1;
return idx;
}
int get(int x){return ch[fa[x]][1] == x;}
void push_up(int x){siz[x] = siz[ch[x][0]] + siz[ch[x][1]] + cnt[x];}
void rotate(int x) {
int y = fa[x], z = fa[y] , k = get(x);//判断
ch[y][k] = ch[x][k ^ 1];
if(ch[x][k ^ 1]) fa[ch[x][k ^ 1]] = y;// x 的某个子节点 & y
ch[x][k ^ 1] = y;
fa[y] = x;// x & y
if(z) ch[z][ch[z][1] == y] = x;
fa[x] = z;//x & z
push_up(y);push_up(x);
}
void splay(int x) {
while(fa[x]){
if(fa[fa[x]]) rotate(get(x) == get(fa[x]) ? fa[x] : x);
rotate(x);
}
rt = x;
fa[x] = 0;
push_up(x);
}
void init(){
New(-inf), New(inf);
rt = 1, ch[1][1] = 2, siz[1] = 2, fa[2] = 1;
}
int get_rank(int u, int k,int f){
if(!u){
splay(f);
return 0;
}
if(k == val[u]){
int res = siz[ch[u][0]] + cnt[u];
splay(u);
return res;
}
if(k < val[u]) return get_rank(ch[u][0], k, u);
int res = siz[ch[u][0]] + cnt[u];
return get_rank(ch[u][1], k, u) + res;
}
int get_num(int u, int k, int f){
if(!u){
splay(f);
return inf;
}
if(siz[ch[u][0]] >= k) return get_num(ch[u][0], k, u);
if(siz[ch[u][0]] + cnt[u] >= k){
splay(u);
return val[u];
}
return get_num(ch[u][1], k - siz[ch[u][0]] - cnt[u], u);
}
void ins(int u, int k , int f){
if(!u){
u = New(k);
fa[u] = f;
ch[f][k > val[f]] = u;
push_up(u);
push_up(f);
splay(u);
return ;
}
if(val[u] == k){
cnt[u]++;
push_up(u);
push_up(f);
splay(u);
return ;
}
ins(ch[u][k > val[u]], k, u);
}
int merge(int x, int y){
if(!x){
fa[y] = 0;
return y;
}
if(!y){
fa[x] = 0;
return x;
}
int t = x;
while(ch[t][1]) t = ch[t][1];
splay(t);
ch[t][1] = y;fa[t] = 0;
fa[y] = t;
return t;
}
void clear(int u){
fa[ch[u][0]] = fa[ch[u][1]] = 0;
cnt[u] = siz[u] = val[u] = ch[u][0] = ch[u][1] = 0;
}
void del(int u, int k, int f){
if(!u){
splay(f);
return ;
}
if(val[u] == k){
splay(u);
if(cnt[u] > 1) {
cnt[u]--;
push_up(u);
return ;
}
fa[ch[u][0]] = fa[ch[u][1]] = 0;
rt = merge(ch[u][0], ch[u][1]);
fa[u] = cnt[u] = siz[u] = val[u] = ch[u][0] = ch[u][1] = 0;
return ;
}
del(ch[u][k > val[u]], k, u);
push_up(u);
}
int get_pre(int k){
int ans = 1, u = rt;
while(u){
if(val[u] == k){
if(ch[u][0]){
u = ch[u][0];
while(ch[u][1]) u = ch[u][1];
ans = u;
}
break;
}
if(val[u] < k && val[u] > val[ans]) ans = u;
u = ch[u][k > val[u]];
}
splay(ans);
return val[ans];
}
int get_nxt(int k){
int ans = 2, u = rt;
while(u){
if(val[u] == k){
if(ch[u][1]){
u = ch[u][1];
while(ch[u][0]) u = ch[u][0];
ans = u;
}
break;
}
if(val[u] > k && val[u] < val[ans]) ans = u;
u = ch[u][k > val[u]];
}
splay(ans);
return val[ans];
}
int main(){
int n;cin >> n;
init();
for(int i = 1;i <= n;i++) {
int opt, x;
cin >> opt >> x;
if(opt == 1) ins(rt, x, 0);
if(opt == 2) del(rt, x, 0);
if(opt == 3) cout << get_rank(rt, x - 1, 0) << endl;
if(opt == 4) cout << get_num(rt, x + 1, 0) << endl;
if(opt == 5) cout << get_pre(x) << endl;
if(opt == 6) cout << get_nxt(x) << endl;
}
return 0;
}
树上启发式合并
（定理 2 肯定是对的，但笔者显然不想，也不会去证明）
问题：对于 x 个 满足二叉查找树性质的树，假如它们一共有 n 个节点，我们每次任意选择两棵树，将小的那棵树当中每一个节点往大的那棵树合并，直到合并到 1 棵树。
定理1：正常平衡树可以在 O(n \log^2n) 的复杂度内解决此问题。
证明1：每次合并整体分析比较难搞，不如考虑每个元素对于总时间复杂度的贡献。当 x 所在的树需要和一棵更大的 Splay 树合并的时候，才会需要不超过 O(\log n) 的时间复杂度把它插入到新的树里。而合并后 x 所在树的大小至少翻倍，所以对于每个数，它至多插了 O(\log n) 次。一共有 n 个点，所以时间复杂度为 O(n\log^2n)。
定理2：对于一个 n 个点的 Splay 树，有 m 次插入/删除/查找操作，那么可以在 O(n + m + \sum \log(d_i + 1)) 的时间复杂度内完成这 m 次操作，其中 d_i 表示第 i 个操作的元素与第 i - 1 个元素在操作时排名之差。
这个我不会证。
定理2的引理： 对于两棵大小分别为 n 和 m 的 Splay 树（m \le n），合并它们的复杂度是 O(m (\log n -\log m ))。
定理3 ：Splay 可以在 O(n \log n) 的时间复杂度内完成上述操作。
证明3：我们将 O(n + m + \sum \log(d_i + 1)) 化为 O(n + m) + O(\sum \log(d_i + 1))。对于前半段，这是启发式合并的模板，每个点可以均摊 O(1) 的进行插入（放在一起分析），而每个节点所在的子树往上合并时大小翻倍，所以每个点最多被合并 O(\log n) 次，总共 n 个点，复杂度是 O(n\log n)；考虑每棵树对于时间复杂度的贡献。与证明 1 相同，假设这 x 个 Splay 树的大小分别是 a_1,a_2\dots a_x，记 s_i = \sum_{j = 1}^i a_i，那么对于某个元素，其对总复杂度的贡献不会超过 O( \log\dfrac{s_2}{s_1} + \log\dfrac{s_3}{s_2} + \dots + \log\dfrac{s_x}{s_{x - 1}}) = O(\log s_x) < O(\log n)，那么最多 n 个节点，不会超过 O(n\log n)。
所以总复杂度是 O(n\log n)。
总而言之，当我们需要不断合并两个平衡树的时候，用伸展树来实现可以让时间复杂度更优。