浅谈 Splay 伸展树

0X?F 前言

（真的轻喷，语言不要太过激进，想喷的别在评论区喷，私信喷我。）

感谢 AgOH 大佬用视频教会了我

\text{Splay}

，所以可能很多地方跟 AgOH 写的一样（虽然码风基本一样）。

写的可能不好，轻喷。如果旋转看不懂可以看这里：Link。

0XFF 什么是 $\text{Splay}$ ？

\text{Splay}

是一种神奇的平衡树，之所以说它神奇，是因为像其他平衡树都需要维护树高保持在

\log

级别，但是

\text{Splay}

即使树像一条链，仍能维持复杂度（

\log

级别），发明它的人就是大家熟知的 Tarjan 神仙。

0X1F 粗讲 $\text{Splay}$

\text{Splay}

的意思是伸展，所以大致思想如下：

每次操作总要把节点弄到根节点，然后操作。

至于“弄”的意思，就看下面了。

0X2F 旋转

这是

\text{Splay}

最重要的操作，也是必须要背下来的。

旋转分为两种：

单旋
双旋

单旋又分两种：

左旋（ $zag$ ）
右旋（ $zig$ ）

双旋也分为两种：

同构调整
异构调整

其实很简单，接着往下看吧：

0X2F - 1 左旋（ $zag$ ）

记住一句口诀：左旋拎右左挂右（本口诀选自 AgOH 大佬的视频）。

看看下面的图就知道了：

可以看出，旋转其实就是相当于在中序遍历不变的情况下换了一种树的结构。

代码：

CPP

void zag(int &node){
  int r = spl[node].r;    //好好理解一下
  spl[node].r = spl[r].l;
  spl[r].l = node;
  node = r;
  update(spl[node].l);   //这里是更新节点子树内大小
  update(node);
}

0X2F - 2 右旋（ $zig$ ）

还有一句口诀：右旋拎左右挂左（还是选自 AgOH 大佬）。

还是一样的图：

应该很简单：

CPP

void zig(int &node){
  int l = spl[node].l;
  spl[node].l = spl[l].r;
  spl[l].r = node;
  node = l;
  update(spl[node].r);
  update(node);
}

0X2F - 3 同构调整

分两种情况讨论。

第一种：

第二种：

我们的目标是把

3

号节点旋转到最顶上，那么该怎么操作呢？

第一种，对

1

进行

zig

，再对

2

进行

zig

，就可以了！

第二种，对

1

进行

zag

，再对

2

进行

zag

，就可以了！

~~是不是很简单。~~

0X2F - 4 异构调整

也分两种情况讨论。

第一种：

第二种：

目标还是一样。

第一种，对

2

进行

zag

，再对

1

进行

zig

，就可以了！

第二种，对

2

进行

zig

，再对

1

进行

zag

，就可以了！

~~是不是也很简单~~

以上的四种旋转都是基本功，务必要记好。

0X3F $\text{Splay}$ 的定义与基本操作

\text{Splay}

定义如下：

CPP

struct Node{
  int ch[2];
  int fa, val, size;  //fa 表示父亲，val 表示值，size 表示子树大小
}spl[N];

这里的左右儿子之所以从

l, r

变成了

ch_{0/1}

，是因为后面的简化版代码做准备，

ch_0

表示左儿子，

ch_1

表示右儿子。

还有就是更新子树大小，这个也很容易：

CPP

void update(int node){
  spl[node].size = spl[spl[node].ch[0]].size + spl[spl[node].ch[1]].size + 1;
}

还有初始化节点信息：

CPP

void newnode(int &node, int fa, int val){
  spl[node = ++cnt].val = val;
  spl[cnt].fa = fa;
  spl[cnt].size = 1;
}

这里因为没有返回值所以要用引用。

0X4F $\text{Splay}$ 的重要操作

一共有

4

个：

$ident$
$connect$
$rotate$
$splaying$

0X4F - 1 $ident$

确定

x

是父亲的哪个儿子。

代码：

CPP

bool ident(int x, int fa){
  return spl[fa].ch[1] == x;  //左儿子 0，右儿子 1
}

0X4F - 2 $connect$

建立父子关系。

代码：

CPP

void connect(int x, int fa, int k){   //x 是 fa 的 ch[k]
  spl[fa].ch[k] = x;
  spl[x].fa = fa;
}

这个也很简单，但在后面很重要。

0X4F - 3 $rotate$

我们发现

zag

和

zig

写起来忒长了吧，还要分类，~~谁愿意去写啊！~~ 于是，我们来写简化版，能自动适应左右旋转。

我们发现其实左旋和右旋就是一个异或的关系，所以左右旋转都可以根据儿子的左右关系来确定左右旋转，而左右旋转一共要更改

3

个父子关系，所以，简单的代码来了：

CPP

void rotate(int x){
  int fa = spl[x].fa, ffa = spl[fa].fa, k = ident(x, fa);
  connect(spl[x].ch[k ^ 1], fa, k);
  connect(x, ffa, ident(fa, ffa));
  connect(fa, x, k ^ 1);
  update(fa);
  update(x);
}

这里可以自己动手画画图，由于版面原因不再过多阐述。

0X4F - 4 $splaying$

\text{Splay}

的最重要的操作之一，是把

x

伸展到

top

的儿子的位置上。

我们可以对于双旋找规律，我们知道了下面两个规律（并不是按照双旋的普通旋转定律来的）：

无论是哪种旋转（包括四种旋转），总是要旋转 $x$ 。
如果父亲的 $ident$ 和父亲的父亲的 $ident$ 相同，旋转 $x$ ，否则，旋转父亲。

所以，来看看简单的代码吧：

CPP

void splaying(int x, int top){   //为什么需要用 top 的儿子，因为我们要判断最后一步是否是左右旋转
  if(!top){
    root = x;
  }
  for(; spl[x].fa != top; ){
    int fa = spl[x].fa, ffa = spl[fa].fa;
    if(ffa != top){   //如果是双旋
      ident(fa, ffa) ^ ident(x, fa) ? rotate(x) : rotate(fa);
    }
    rotate(x);   //反正最后都要旋 x
  }
}

显然代码很短。

0X5F 一些不那么重要的操作

注意：

\text{Splay}

不对重复值节点进行操作是没有问题的。

0X5F - 1 插入（ $\text{insert}$ ）

显然跟二叉搜索树无异，只不过需要把节点伸展到根节点。

代码：

CPP

void insert(int &node, int val, int fa){
  if(!node){
    newnode(node, fa, val);
    splaying(node, 0);  //0 表示伸展到根节点
  }
  else if(val < spl[node].val){
    insert(spl[node].ch[0], val, node);
  }
  else{
    insert(spl[node].ch[1], val, node);
  }
}

0X5F - 2 删除（ $\text{del}$ ）

首先找到要删除的节点，伸展到根节点，分以下情况讨论：

如果当前节点无后继，也就是右子树为空，那么直接把根节点变成根节点的左儿子即可。
如果有后继，让后继伸展到根节点的右儿子那里，然后将后继的左儿子指向根节点的左儿子，再把 $root$ 更为后继即可。

很简单吧，代码来喽：

CPP

void delnode(int x){   //删除节点
  splaying(x, 0);
  if(spl[x].ch[1]){
    int p = spl[x].ch[1];
    while(spl[p].ch[0]){   //找到后继
      p = spl[p].ch[0];
    }
    splaying(p, x);   //伸展上去
    connect(spl[x].ch[0], p, 0);   //建立关系
    root = p;
    spl[p].fa = 0;   //清空
    update(root);
  }
  else{
    root = spl[x].ch[0];
    spl[root].fa = 0;
  }
}

void del(int &node, int val){  //寻找节点，这里引用不引用无所谓
  if(val == spl[node].val){
    delnode(node);
  }
  else if(val < spl[node].val){
    del(spl[node].ch[0], val);
  }
  else{
    del(spl[node].ch[1], val);
  }
}

按照思路打就对了。

0X5F - 3 查询数的排名（ $\text{rank}$ ）

这个很简单，但是一定一定找到节点后要伸展，不然会 T 的很惨。

代码：

CPP

int _rank(int val){
  int node = root, rk = 1, pre = 0;
  while(node){
    if(val <= spl[node].val){
      pre = node;
      node = spl[node].ch[0];
    }
    else{
      rk += spl[spl[node].ch[0]].size + 1;
      node = spl[node].ch[1];
    }
  }
  if(pre){   //并不是没有
    splaying(pre, 0);
  }
  return rk;
}

0X5F - 4 查询排名的数（ $\text{query}$ ）

这个也很简单，前驱后继都是用这个完成的：

CPP

int query(int rk){   //真 简单
  int node = root;
  while(node){
    if(spl[spl[node].ch[0]].size + 1 == rk){
      splaying(node, 0);
      break;
    }
    else if(spl[spl[node].ch[0]].size >= rk){
      node = spl[node].ch[0];
    }
    else{
      rk -= spl[spl[node].ch[0]].size + 1;
      node = spl[node].ch[1];
    }
  }
  return spl[node].val;
}

0X6F 代码

板题为普通平衡树，代码：

CPP

#include<bits/stdc++.h>

#define endl '\n';

using namespace std;

const int N = 1e5 + 5;

int n;

struct Node{
  int ch[2];
  int fa, val, size;
}spl[N];

int cnt, root;

void update(int node){
  spl[node].size = spl[spl[node].ch[0]].size + spl[spl[node].ch[1]].size + 1;
}

bool ident(int x, int fa){
  return spl[fa].ch[1] == x;
}

void connect(int x, int fa, int k){
  spl[fa].ch[k] = x;
  spl[x].fa = fa;
}

void rotate(int x){
  int fa = spl[x].fa, ffa = spl[fa].fa, k = ident(x, fa);
  connect(spl[x].ch[k ^ 1], fa, k);
  connect(x, ffa, ident(fa, ffa));
  connect(fa, x, k ^ 1);
  update(fa);
  update(x);
}

void splaying(int x, int top){
  if(!top){
    root = x;
  }
  for(; spl[x].fa != top; ){
    int fa = spl[x].fa, ffa = spl[fa].fa;
    if(ffa != top){
      ident(fa, ffa) ^ ident(x, fa) ? rotate(x) : rotate(fa);
    }
    rotate(x);
  }
}

void newnode(int &node, int fa, int val){
  spl[node = ++cnt].val = val;
  spl[cnt].fa = fa;
  spl[cnt].size = 1;
}

void delnode(int x){
  splaying(x, 0);
  if(spl[x].ch[1]){
    int p = spl[x].ch[1];
    while(spl[p].ch[0]){
      p = spl[p].ch[0];
    }
    splaying(p, x);
    connect(spl[x].ch[0], p, 0);
    root = p;
    spl[p].fa = 0;
    update(root);
  }
  else{
    root = spl[x].ch[0];
    spl[root].fa = 0;
  }
}

void insert(int &node, int val, int fa){
  if(!node){
    newnode(node, fa, val);
    splaying(node, 0);
  }
  else if(val < spl[node].val){
    insert(spl[node].ch[0], val, node);
  }
  else{
    insert(spl[node].ch[1], val, node);
  }
}

void del(int &node, int val){
  if(val == spl[node].val){
    delnode(node);
  }
  else if(val < spl[node].val){
    del(spl[node].ch[0], val);
  }
  else{
    del(spl[node].ch[1], val);
  }
}

int _rank(int val){
  int node = root, rk = 1, pre = 0;
  while(node){
    if(val <= spl[node].val){
      pre = node;
      node = spl[node].ch[0];
    }
    else{
      rk += spl[spl[node].ch[0]].size + 1;
      node = spl[node].ch[1];
    }
  }
  if(pre){
    splaying(pre, 0);
  }
  return rk;
}

int query(int rk){
  int node = root;
  while(node){
    if(spl[spl[node].ch[0]].size + 1 == rk){
      splaying(node, 0);
      break;
    }
    else if(spl[spl[node].ch[0]].size >= rk){
      node = spl[node].ch[0];
    }
    else{
      rk -= spl[spl[node].ch[0]].size + 1;
      node = spl[node].ch[1];
    }
  }
  return spl[node].val;
}

void Solve(){
  cin >> n;
  while(n--){
    int op;
    cin >> op;
    if(op == 1){
      int x;
      cin >> x;
      insert(root, x, 0);
    }
    else if(op == 2){
      int x;
      cin >> x;
      del(root, x);
    }
    else if(op == 3){
      int x;
      cin >> x;
      cout << _rank(x) << endl;
    }
    else if(op == 4){
      int x;
      cin >> x;
      cout << query(x) << endl;
    }
    else if(op == 5){
      int x;
      cin >> x;
      cout << query(_rank(x) - 1) << endl;
    }
    else{
      int x;
      cin >> x;
      cout << query(_rank(x + 1)) << endl;
    }
  }
}

signed main(){
  Solve();
  return 0;
}

由于前面有注释，这里就不给了。

0X7F 时间复杂度证明

Tarjan 的伟大不在于发明了

\text{Splay}

，而是证明出了其复杂度，至于复杂度证明可以看：证明

\text{Splay}

复杂度。

0X8F 为何不能可持久化

并不是因为旋转，请品一品以下 lxl 的对话：

0X8F 最后的感谢

感谢 AgOH 大佬让我学会了

\text{Splay}

！！！

AgOH 大佬视频：点这里。

文章操作

0X?F 前言

0XFF 什么是 $\text{Splay}$ ？

0X1F 粗讲 $\text{Splay}$

0X2F 旋转

0X2F - 1 左旋（ $zag$ ）

0X2F - 2 右旋（ $zig$ ）

0X2F - 3 同构调整

0X2F - 4 异构调整

0X3F $\text{Splay}$ 的定义与基本操作

0X4F $\text{Splay}$ 的重要操作

0X4F - 1 $ident$

0X4F - 2 $connect$

0X4F - 3 $rotate$

0X4F - 4 $splaying$

0X5F 一些不那么重要的操作

0X5F - 1 插入（ $\text{insert}$ ）

0X5F - 2 删除（ $\text{del}$ ）

0X5F - 3 查询数的排名（ $\text{rank}$ ）

0X5F - 4 查询排名的数（ $\text{query}$ ）

0X6F 代码

0X7F 时间复杂度证明

0X8F 为何不能可持久化

0X8F 最后的感谢

相关推荐

评论

浅谈 Splay 伸展树

文章操作

0X?F 前言

0XFF 什么是 Splay\text{Splay}Splay？

0X1F 粗讲 Splay\text{Splay}Splay

0X2F 旋转

0X2F - 1 左旋（zagzagzag）

0X2F - 2 右旋（zigzigzig）

0X2F - 3 同构调整

0X2F - 4 异构调整

0X3F Splay\text{Splay}Splay 的定义与基本操作

0X4F Splay\text{Splay}Splay 的重要操作

0X4F - 1 identidentident

0X4F - 2 connectconnectconnect

0X4F - 3 rotaterotaterotate

0X4F - 4 splayingsplayingsplaying

0X5F 一些不那么重要的操作

0X5F - 1 插入（insert\text{insert}insert）

0X5F - 2 删除（del\text{del}del）

0X5F - 3 查询数的排名（rank\text{rank}rank）

0X5F - 4 查询排名的数（query\text{query}query）

0X6F 代码

0X7F 时间复杂度证明

0X8F 为何不能可持久化

0X8F 最后的感谢

相关推荐

评论

0XFF 什么是 $\text{Splay}$ ？

0X1F 粗讲 $\text{Splay}$

0X2F - 1 左旋（ $zag$ ）

0X2F - 2 右旋（ $zig$ ）

0X3F $\text{Splay}$ 的定义与基本操作

0X4F $\text{Splay}$ 的重要操作

0X4F - 1 $ident$

0X4F - 2 $connect$

0X4F - 3 $rotate$

0X4F - 4 $splaying$

0X5F - 1 插入（ $\text{insert}$ ）

0X5F - 2 删除（ $\text{del}$ ）

0X5F - 3 查询数的排名（ $\text{rank}$ ）

0X5F - 4 查询排名的数（ $\text{query}$ ）