Splay 树

定义

Splay 树是一个二叉平衡搜索树，它可以通过 Splay 操作 将一个结点旋转至根结点或者一个给定的结点的下一层，使得整棵树仍然满足二叉搜索树的性质。

Splay 树可以在均摊 $O(\log n)$ 的时间内完成查找、插入、查询、删除等操作。

二叉搜索树的定义：

  • 空树是一个二叉搜索树；
  • 根结点左子树中的结点权值均小于根结点的权值；
  • 根结点右子树中的结点权值均大于根结点的权值；
  • 根结点的左右子树均为二叉搜索树。

结构

在 Splay 中，一共需要维护如下信息：

  • root：树的根结点编号。
  • tot：当前总共开了点的个数（Splay 树显然使用动态开点）。
  • fa[i]：结点 $i$ 的父亲结点。
  • son[i][0/1]：结点 $i$ 的左右儿子编号，左儿子为 son[i][0]，右儿子为 son[i][1]。
  • val[i]：结点 $i$ 的权值。
  • cnt[i]：权值为 val[i] 的数字的出现个数。
  • siz[i]：结点 $i$ 及其子树的大小。

基本操作

辅助函数

  • pushup(x)：合并左右儿子的信息（即大小），更新至当前结点。
  • get(x)：返回 $0$ 表示 $x$ 是父结点的左儿子，返回 $1$ 表示 $x$ 是父结点的右儿子。
  • clear(x)：销毁结点 $x$，即将一切信息清零。
1
2
3
4
5
6
7
8
9
10
11
void pushup(int x) { // 合并 x 的左儿子与右儿子，得到 x 的大小
  siz[x] = siz[son[x][0]] + siz[son[x][1]] + cnt[x];
}

bool get(int x) { // get(x)=1 说明 x 是右儿子，反之是左儿子
  return x == son[fa[x]][1];
}

void clear(int x) { // 销毁结点 x
  son[x][0] = son[x][1] = fa[x] = val[x] = siz[x] = cnt[x] = 0;
}

旋转

左旋是右旋的逆操作，所以下面只讨论右旋。

旋转操作如上图。

可以发现，右旋是把 $x$ 提到 $z$ 的下面然后把 $y$ 压下去，此时由于 $x$ 有有儿子了，所以如图可以想象成 $B$ 不动，此时就接到了 $y$ 的下面（胡思乱想中）。

实际把图片记住就行了，上面扯一大通 P 用没有

在右旋中，我们需要知道 $x$ 的父亲结点和爷爷结点，所以

1
int y = fa[x], z = fa[y];

然后我们还需要知道 $x$ 是 $y$ 的左儿子还是右儿子，如果 $x$ 是左儿子就右旋，反之左旋。

1
int id = get(x); // 判断 x 是 y 的左儿子还是右儿子

容易发现，在右旋中，改变的边的关系只有 $x-z$，$x-y$，$y-B$，所以我们分别考虑。

修改为 $x-z$

由于 $x$ 替换掉的是 $y$ 的位置，所以需要先知道 $y$ 是 $z$ 的哪个儿子，故先 get(y)。

当 $z$ 点不存在时（即 $z=0$），那么更新 son[z] 会发生错误，因为访问的时候一般是用是否为 $0$ 判断点是否存在。若 $z$ 为根结点，那么就会遍历下去导致错误的答案。

而 $x$ 必然存在，无需判断。

1
2
if (z) son[z][get(y)] = x;
fa[x] = z;

修改为 $x-y$

由于右旋保证了 $y$ 是存在的，所以两种情况都无需判断。

1
son[x][id ^ 1] = y, fa[y] = x;

修改为 $y-B$

$B$ 是 $x$ 的右儿子，而 $x$ 是 $y$ 的左儿子，所以发现 $B$ 就是 son[x][id ^ 1]。

同理此时 $B$ 不一定存在，所以也需要判断。

1
2
son[y][id] = son[x][id ^ 1];
if (son[x][id ^ 1]) fa[son[x][id ^ 1]] = y;

完整代码

1
2
3
4
5
6
7
8
9
10
void rotate(int x) {
  int y = fa[x], z = fa[y];
  int id = get(x); // 判断 x 是 y 的左儿子还是右儿子
  if (z) son[z][get(y)] = x;
  fa[x] = z;
  son[y][id] = son[x][id ^ 1];
  if (son[x][id ^ 1]) fa[son[x][id ^ 1]] = y;
  son[x][id ^ 1] = y, fa[y] = x;
  pushup(y), pushup(x);
}

Splay 操作

Splay 操作规定：每操作（包括但不限于插入、删除，详见代码）一个结点 $x$ 后，都要将这个节点 $x$ 旋转为结点 $k$ 的儿子，若 $k=0$ 则将其旋转至根结点。

根据定义，当 fa[x] != k 时，需要一直向上旋转，故写一个 while 循环。

特殊型

如图，$k$ 是 $x$ 的爷爷结点，此情况称为特殊型。

对于这两种情况，我们只需要将 $x$ 点分别左旋、右旋，就可以让 $x$ 顶替掉 $y$ 的位置，成为 $k$ 的儿子。

同构型

如图，当 $x$ 的爷爷节点非 $k$，且 $x,y,k$ 三点共线时，此情况称为同构型。

此时我们的目标是让 $x$ 顶替掉 $z$​，成为这一条链中深度最浅的链头。

首先，我们将 $y$ 点旋转，此时 $y$ 成为深度最浅的结点，同时 $x,z$ 是 $y$ 的两个儿子。

然后我们将 $x$ 点旋转，让 $x$ 成为 $y$ 的父亲，此时 $x$ 就成为了深度最浅的点，操作完成。

总结：对于同构型，先旋转 $y$，再旋转 $x$。

异构型

如图，当 $x$ 的爷爷结点非 $k$，且 $x,y,z$​ 三点构成折线时，此情况称为异构型。

此时我们的目标同样是让 $x$ 顶替掉 $z$，成为这一条链中深度最浅的链头。

首先，我们将 $x$ 点旋转，此时 $x$ 称为 $z$ 的儿子，三点共线。

然后我们再次将 $x$ 点旋转， $z$ 称为 $x$ 的儿子，此时 $x$​ 就成为了深度最浅的点，操作完成。

总结：对于异构型，先旋转 $x$，再旋转 $x$​。

代码实现

发现无论对于哪种情况，最后都会旋转一次 $x$，所以可以将这一次操作提取出来。

如何判断三点是同构还是异构呢？可以用 $\text{get}(x)\oplus\text{get}(y)$​ 获得。

具体实现详见代码。

判断同构、异构的解释

  • 同构

    此时 $x$ 是 $y$ 的左（右）儿子，$y$ 是 $z$ 的左（右）儿子，儿子左右情况相同，那么 $\text{get}(x)=\text{get}(y)$，异或值为 $0$。

  • 异构

    此时 $x$ 是 $y$ 的左（右）儿子，$y$ 是 $z$ 的右（左）儿子，儿子左右情况不同，那么 $\text{get}(x)\not=\text{get}(y)$，且一个为 $0$ 一个为 $1$，故异或值为 $1$。

1
2
3
4
5
6
7
8
9
10
11
void splay(int x, int k) { // 将 x 转到 k 的下面
  while (fa[x] != k) {
    int y = fa[x], z = fa[y];
    if (z != k) {
      if (get(x) ^ get(y)) rotate(x); // 异构
      else rotate(y); // 同构
    }
    rotate(x);
  }
  if (!k) root = x;// 若旋转为根结点，那么将根结点 root 设为 x
}

时间复杂度分析

本部分来自 OI-wiki。

考虑对 Splay 操作中的三种情况分析复杂度。采用势能分析，定义一个 $n$ 个节点的 Splay 树进行了 $m$ 次 Splay 操作。

可记 $w(x)=\left\lfloor\log\text{size}_x\right\rfloor$，定义势能函数为 $\varphi=\sum w(x)$，其中 $\varphi(0)\le n\log n$。

在第 $i$ 次操作后势能为 $\varphi(i)$​，则我们只需求出初始势能和每次的势能变化量的和即可。

  • 特殊型：势能变化量为

    $$ \begin{aligned} &1+w'(x)+w'(y)-w(x)-w(y)\\ \le\,&1+w'(y)-w(x)\\ \le\,&1+w'(x)-w(x) \end{aligned} $$

  • 同构型：势能变化量为

    $$ \begin{aligned} &1+w'(x)+w'(y)+w'(z)-w(x)-w(y)-w(z)\\ \le\,& 1+w'(y)+w'(z)-w(x)-w(y)\\ \le\,& 1+w'(x)+w'(z)-2w(x)\\ \le\,& 3\big(w'(x)-w(x)\big) \end{aligned} $$

  • 异构型：势能变化量为

    $$ \begin{aligned} &1+w'(x)+w'(y)+w'(z)-w(x)-w(y)-w(z)\\ \le\,& 1+w'(y)+w'(z)-w(x)-w(y)\\ \le\,& 1+w'(z)+w'(y)-2w(x)\\ \le\,& 2w'(x)-w'(z)-w'(y)+w'(z)-w(x)-w(y)\\ \le\,& 2\big(w'(x)-w(x)\big) \end{aligned} $$

由此可见，三种操作的势能全部可以缩放为 $\le 3\big(w'(x)-w(x)\big)$。

令 $w^{(n)}(x)=w'^{(n-1)(x)}$，$w^{(0)}(x)=w(x)$，Splay 操作一次依次访问了 $x_1,x_2,\cdots,x_n$，最终 $x_1$ 成为深度最浅的结点，那么可得：
$$ \begin{aligned} 3\left(\sum\limits_{i=0}^{n-2}\left(w^{(i+1)}(x_1)-w^{(i)}(x_1)\right)+w(n)-w^{(n-1)}(x_1)\right)+1&=3\big(w(n)-w(x_1)\big)+1\\ &\le \log n \end{aligned} $$
继而可得：
$$ \sum\limits_{i=1}^{m}\big(\varphi(m-i+1)-\varphi(m-i)\big)+\varphi(0)=n\log n+m\log n $$
因此，对于 $n$ 个结点的 Splay 树，做一次 Splay 操作的均摊复杂度为 $O(\log n)$。

因此基于 Splay 的操作的时间复杂度也是均摊 $O(\log n)$ 的。

应用 1：维护一个集合

例题：#104. 普通平衡树 - 题目 - LibreOJ (loj.ac)

插入

由于二叉搜索是递归定义的，所以可以用递归的思想考虑（假设插入值为 $k$）：

  • 如果当前结点为空，那么就新建一个结点存储当前值。
  • 如果当前结点的权值等于 $k$，那么更新当前结点的计数器并且更新当前结点与父亲的大小。
  • 若 $k$ 小于权值就进入左子树，大于权值就进入右子树。

注意，最后更新/新建结点之后，必须执行 Splay 操作，否则时间复杂度不正确！

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
void insert(int k) {
  if (!root) { // 树为空，新建节点
    val[++tot] = k;
    ++cnt[tot];
    root = tot;
    pushup(root); // 更新大小
    return ;
  }
  int x = root, y = 0;
  while (true) {
    if (val[x] == k) { // 找到目标
      ++cnt[x]; // 更新计数器
      pushup(x), pushup(y);
      splay(x, 0); // 旋转至根结点
      break;
    }
    y = x, x = son[x][val[x] < k]; // 进入子树
    if (!x) { // 到了空结点，插入新结点
      val[++tot] = k;
      ++cnt[tot];
      fa[tot] = y;
      son[y][val[y] < k] = tot; // 根据二叉搜索树的性质插入
      pushup(tot);
      pushup(y);
      splay(tot, 0);
      break;
    }
}

根据权值查询排名

假设当前给定的权值为 $k$，要查找 $k$​ 的排名。

维护一个 $\text{res}$ 统计当前已经计算了权值小于 $k$ 的结点个数。

  • 当前结点为空，返回 $\text{res}+1$。

  • $k$ 小于当前结点的权值，那么进入当前结点的左子树查找，无需更新 $\text{res}$。

  • $k$​ 大于等于当前结点的权值

    那么当前结点的左子树中的结点都小于 $k$，res += siz[son[x][0]]，加上左子树的大小。

    如果 $k$ 等于当前结点的权值，那么将其旋转至根结点，返回 $\text{res}+1$。

    如果 $k$ 大于当前结点的权值，那么当前结点的权值也小于 $k$ 了，res += cnt[x]，同时进入右子树。

1
2
3
4
5
6
7
8
9
10
11
12
13
int get_rank(int k) { // 查询 k 的排名
  int res = 0, x = root;
  while (true) {
    if (k < val[x]) x = son[x][0]; // k 落在 x 的左子树
    else {
      res += siz[son[x][0]]; // 加上左子树的大小
      if (!x) return res + 1; // 当前结点为空
      if (val[x] == k) return splay(x, 0), res + 1; // 当前结点权值等于 k
      res += cnt[x], x = son[x][1]; // 进入右子树
    }
  }
  return -1;
}

根据排名查询权值

假设当前要查询排名为 $k$​ 的数，但是在下面，$k$ 是实时维护的。

  • 如果 k <= siz[son[x][0]]，那么排名为 $k$ 的数就在左子树中，进入左子树即可。

  • 否则让 k -= cnt[x] + siz[son[x][0]]，相当于减去根结点的数量和左子树大小。

    • 如果此时 $k\le 0$，那么说明 siz[son[x][0]] < k <= cnt[x]，即排名为 $k$ 的数就是当前结点。将其旋转至跟节点后返回即可。

    • 否则进入右子树。

1
2
3
4
5
6
7
8
9
10
11
12
int get_kth(int k) { // 查询排名为 k 的数
  int x = root;
  while (true) {
    if (son[x][0] && k <= siz[son[x][0]]) x = son[x][0]; // 进入左子树
    else {
      k -= cnt[x] + siz[son[x][0]]; // 减去根结点的数量和左子树大小
      if (k <= 0) return splay(x, 0), val[x]; // 说明 siz[son[x][0]] < k <= cnt[x]
      x = son[x][1]; // 进入右子树
    }
  }
  return -1; // 找不到，即树的大小 < k
}

查询根结点的前驱/后继

至于为什么要查询根结点的前驱/后继，将会在后面的操作中给出解释。

如果想要查找一个任意权值 $k$ 的前驱/后继，只需先将 $k$ 插入树中。

由于插入函数中执行了 splay，所以此时 $k$​​ 就位于根结点的位置，可以直接调用函数。

查询完之后删除 $k$ 即可。

由于前驱是小于根结点权值的最大的数，所以只要先进入左子树，然后一直向右找即可。

后继同理。

注意，下面代码返回的是结点编号，所以在最后输出的时候要套一层 val[]。

1
2
3
4
5
6
7
8
9
10
11
12
13
int get_pre() { // 查询根节点的前驱
  int x = son[root][0]; // 进入左子树
  while (son[x][1]) x = son[x][1]; // 一直往右找
  splay(x, 0); // 旋转至根结点
  return x;
}

int get_nxt() { // 查询根节点的后继
  int x = son[root][1]; // 进入右子树
  while (son[x][0]) x = son[x][0]; // 一直往左找
  splay(x, 0); // 旋转至根结点
  return x;
}

合并两颗 Splay 树

设两棵树的根结点分别为 $x,y$，那么要求 $x$ 树中的最大值小于 $y$ 树中的最小值。

  • 若 $x=\varnothing$ 或 $y=\varnothing$，那么返回非空的树或者空树。
  • 否则将 $x$ 树中最大值 splay 至根结点，然后将其右子树设为 $y$。这样就保证了二叉搜索树的性质。

这只是一个辅助删除结点的思想，并不需要具体实现为一个函数。

删除一个结点

假设要删除一个权值为 $k$ 的数。

如果要将权值为 $k$ 的数，那么直接将计数器置为 $0$ 即可。

首先将 $x$ 旋转到根结点。

  • 若 cnt[x] > 1，那么 --cnt[x] 并返回。
  • 否则删除根结点，并合并左右子树。

思路听起来很简单，但是实现起来有一定的理解难度。

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
void erase(int k) { // 删除一个权值为 k 的数
  get_rank(k); // 因为只知道权值为 k，那么可以用查找 k 的排名函数找到权值为 k 的结点并将其旋转至根结点
  if (cnt[root] > 1) { // 直接删除一个数
    --cnt[root];
    pushup(root); // 更新大小
    return ;
  }
  if (!son[root][0] && !son[root][1]) { // 树中只有一个根结点
    clear(root); // 清空根结点
    root = 0; // 根结点置为 0
    return ;
  }
  if (!son[root][0]) { // 左子树为空
    int cur = root;
    root = son[root][1]; // 将根结点设为右子树的根结点
    fa[root] = 0; // 将父亲设为空
    clear(cur); // 清除原来的根结点
    return ;
  }
  if (!son[root][1]) { // 右子树为空
    int cur = root; // 将根结点设为左子树的根结点
    fa[root = son[root][0]] = 0;
    clear(cur);
    return ;
  }
  /*
  由于原树分裂成了左右子树，而左子树的最大值必然小于右子树的最小值，那么左子树为 x，右子树为 y。
  x = get_pre() 得到了 x 中的最大值，并同时通过 splay 操作将其旋转至整棵树的根结点。
  此时将原树的右儿子的父亲设为当前根结点，并且更新儿子关系。
  最后清除原根节点，并且更新根结点大小。
  */
  int cur = root, x = get_pre();
  fa[son[cur][1]] = x;
  son[x][1] = son[cur][1];
  clear(cur);
  pushup(root);
}

完整代码

其中 $N$ 为最大的总共开的点的数量，如果不确定可以用 std::vector 代替。

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
struct Splay {
  int root, tot, val[N], siz[N], cnt[N], fa[N], son[N][2];

  void pushup(int x) { // 合并 x 的左儿子与右儿子，得到 x 的大小
    siz[x] = siz[son[x][0]] + siz[son[x][1]] + cnt[x];
  }

  bool get(int x) { // get(x)=1 说明 x 是右儿子，反之是左儿子
    return x == son[fa[x]][1];
  }

  void clear(int x) { // 销毁结点 x
    son[x][0] = son[x][1] = fa[x] = val[x] = siz[x] = cnt[x] = 0;
  }

  void rotate(int x) {
    int y = fa[x], z = fa[y];
    int id = get(x); // 判断 x 是 y 的左儿子还是右儿子
    if (z) son[z][get(y)] = x;
    fa[x] = z;
    son[y][id] = son[x][id ^ 1];
    if (son[x][id ^ 1]) fa[son[x][id ^ 1]] = y;
    son[x][id ^ 1] = y, fa[y] = x;
    pushup(y), pushup(x);
  }

  void splay(int x, int k) { // 将 x 转到 k 的下面
    while (fa[x] != k) {
      int y = fa[x], z = fa[y];
      if (z != k) {
        if (get(x) ^ get(y)) rotate(x);
        else rotate(y);
      }
      rotate(x);
    }
    if (!k) root = x;
  }

  void insert(int k) {
    if (!root) { // 树为空
      val[++tot] = k;
      ++cnt[tot];
      root = tot;
      pushup(root);
      return ;
    }
    int x = root, y = 0;
    while (true) {
      if (val[x] == k) { // 找到目标
        ++cnt[x];
        pushup(x), pushup(y);
        splay(x, 0);
        break;
      }
      y = x, x = son[x][val[x] < k];
      if (!x) { // 插入新结点
        val[++tot] = k;
        ++cnt[tot];
        fa[tot] = y;
        son[y][val[y] < k] = tot;
        pushup(tot);
        pushup(y);
        splay(tot, 0);
        break;
      }
    }
  }

  int get_rank(int k) { // 查询 k 的排名
    int res = 0, x = root;
    while (true) {
      if (k < val[x]) x = son[x][0]; // k 落在 x 的左子树
      else {
        res += siz[son[x][0]];
        if (!x) return res + 1;
        if (val[x] == k) return splay(x, 0), res + 1;
        res += cnt[x], x = son[x][1];
      }
    }
    return -1;
  }

  int get_kth(int k) { // 查询排名为 k 的数
    int x = root;
    while (true) {
      if (son[x][0] && k <= siz[son[x][0]]) x = son[x][0];
      else {
        k -= cnt[x] + siz[son[x][0]];
        if (k <= 0) return splay(x, 0), val[x];
        x = son[x][1];
      }
    }
    return -1;
  }

  int get_pre() { // 查询根节点的前驱
    int x = son[root][0];
    while (son[x][1]) x = son[x][1];
    splay(x, 0);
    return x;
  }

  int get_nxt() { // 查询根节点的后继
    int x = son[root][1];
    while (son[x][0]) x = son[x][0];
    splay(x, 0);
    return x;
  }

  void erase(int k) { // 删除一个权值为 k 的数
    get_rank(k);
    if (cnt[root] > 1) {
      --cnt[root];
      pushup(root);
      return ;
    }
    if (!son[root][0] && !son[root][1]) { // 树中只有一个根结点
      clear(root);
      root = 0;
      return ;
    }
    if (!son[root][0]) { // 左子树为空
      int cur = root;
      root = son[root][1];
      fa[root] = 0;
      clear(cur);
      return ;
    }
    if (!son[root][1]) { // 右子树为空
      int cur = root;
      fa[root = son[root][0]] = 0;
      clear(cur);
      return ;
    }
    int cur = root, x = get_pre();
    fa[son[cur][1]] = x;
    son[x][1] = son[cur][1];
    clear(cur);
    pushup(root);
  }
} tree;

应用 2：维护一个区间

许可协议

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。