【数据结构】Splay树

前言

Splay（伸展树）是一种灵活多变的高级数据结构，可以很方便的执行各种动态的区间操作。由丹尼尔·斯立特 Daniel Sleator 和罗伯特·恩卓·塔扬 Robert Endre Tarjan 在 1985 年发明。

Splay 是一颗二叉搜索树，它建立在二叉搜索树（BST）之上，当然也是平衡树的一种，下面简单介绍一下 BST 与平衡树：

首先介绍 BST，也就是所有平衡树的开始，他的名字是二叉查找树.

给定一棵二叉树，每一个节点有一个权值,命名为关键码，而 BST 性质就是，对于树中任何一个节点,都满足一下性质：

这个节点的关键码不小于它的左子树上,任意一个节点的关键码
这个节点的关键码不大于它的右子树上,任意一个节点的关键码

然后我们就可以发现这棵树的中序遍历，就是一个关键码单调递增的节点序列，说的直白点,就是一个排好序的数组（注意是非严格单调递增序列）。

我们知道，在一颗查找二叉树（BST）中，插入过程的均摊时间复杂度为 $O(\log n)$ ，但是在一些特殊情况，BST 树会退化成一条链，导致时间复杂度从 $O(\log n)$ 退化到 $O(n)$ ，这是不可以的，所以产生了一种数据结构——平衡树。

平衡树最主要的功能就是旋转 ，通过等价的旋转，可以最优化 BST 的深度，例如下面的两棵 BST 树的对比，他们实质上是等价的，但是第一颗不平衡，操作时会造成不必要的时间浪费。

不平衡的树

当然除此之外，平衡树还有以下功能（来自平衡树 - 维基百科）：

旋转（ $rotate$ ）：几乎所有平衡树的操作都基于树旋转操作（也有部分基于重构，如替罪羊树），通过旋转操作可以使得树趋于平衡。对一棵查找树（ $search tree$ ）进行查询、新增、删除等动作，所花的时间与树的高度成比例，并不与树的容量成比例。如果可以让树维持平衡，也就是让高度维持在 $O(\log⁡ n)$ 左右，就可以在 $O(\log⁡ n)$ 的复杂度内完成各种基本操作。
插入（ $insert$ ）：在树中插入一个新值。
删除（ $delete$ ）：在树中删除一个值。
查询前驱（ $predecessor$ ）：前驱定义为小于 $x$ ，且最大的数。
查询后继（ $successor$ ）：后继定义为大于 $x$ ，且最小的数。如果维护同时节点大小（ $size$ ），还可以支持以下操作：
查询排名（ $rank$ ）：排名定义为比 $x$ 小的数的个数加一。
查询第 $k$ 大：即排名为 $k$ 的数。

那么实际上 Splay 树（伸展树）的原理是基于类似程序局部性原理的假设：一个节点在一次被访问后，这个节点很可能不久再次被访问。Splay 树的做法就是在每次一个节点被访问后，我们就把它推到树根的位置。正像程序局部性原理的实际效率被广泛证明一样，Splay 树在实际的搜索效率上也是非常高效的。尽管存在最坏情况下单次操作会花费 $O(n)$ 的时间，但是这种情况并不是经常发生，而实际证明伸展树能够保证 $m$ 次连续操作最多花费 $O(m \log n)$ 的时间。

Splay

所有平衡树的思路都是维护一颗 BST 树的平衡状态，也就是不改变中序遍历结果的前提之下，尽可能减少 Splay 树的深度。

前面我们说过了，Splay 的主要思想是：对于查找频率较高的节点，使其处于离根节点相对较近的节点。当然我们统计每一个点的查找次数是不现实的，我们可以理解每一次被查到的节点频率比较高，说白了就是你把每次查找到的点搬到根节点去，这样就可以保证查找的效率。

每次移动的过程就是旋转的过程（ $rotate$ ），在 Splay 中有两种旋转，分别叫做单旋与双旋，我们将他们设计为 $rotate$ 函数与 $splay$ 函数。在设计之前，我们需要先定义一颗 BST 树，如下：

因为 OI 多是面向过程设计，下列写法并不在生产环境适用，若要应用于生产环境中，请使用 Class+指针面向对象设计 BST 树。

1
struct Node
2
{
3
    int fa;    // 节点父亲
4
    int val;   // 节点权值
5
    int cnt;   // 权值出现次数
6
    int size;  // 子树大小
7
    int ch[2]; // 左儿子与右儿子（方便运算）
8
    Node()
9
    {
10
        fa = 0;
11
        val = 0;
12
        cnt = 0;
13
        size = 0;
14
        ch[0] = ch[1] = 0;
15
    }
16
    Node(int Fa, int Val, int Cnt, int Size, int R, int L)
17
    {
18
        fa = Fa;
19
        val = Val;
20
        cnt = Cnt;
21
        size = Size;
22
        ch[0] = L;
23
        ch[1] = R;
24
    }
25
} tree[N];

设计旋转

单旋（rotate）

首先考虑一下，我们要把一个点挪到根，那我们首先要知道怎么让一个点挪到它的父节点。单旋函数就是这个功能。

情况一

考虑下面的情况，我们要把节点 3 移动到它的父亲节点 2 之上（字母节点代表一颗子树）：

这时候如果我们让 X 成为 Y 的父亲，只会影响到 3 个点的关系：

Y 与 3，3 与 2，3 与 1 根据二叉排序树的性质 Y 会成为 2 的左儿子 2 会成为 3 的右儿子 3 会成为 1 的儿子（与原来 2 与 1 的情况相同）

经过变换之后，大概是这样：

情况二

那么反过来，我们把这个时候的节点 2 移到 3 节点之上，与第一个图是相同的，这就是第二种情况。

代码

首先我们写一个 $get$ 函数，以获取此节点是其父亲的哪一个儿子：

1
bool get(int x) { return x == tree[x].ch[1]; }

我们假设是从 u->v，设计函数 $rotate$ 如下：

1
void rotate(int u, int v)
2
{
3
    int u_fa = tree[u].fa; // u_fa = v;
4
    int v_fa = tree[v].fa; // u的目标父亲
5
    int son_u = get(u);    // u在其父亲的位置
6
    int son_v = get(v);    // v在其父亲的位置
7
}

观察上图，我们发现节点 3 的 Y 子树的父亲更改了，可以发现下面两个规律：

Y 子树的位置与 3 在 2 中的位置相反
Y 子树在 2 的目标位置与 3 在 2 中的位置相同

那么我们先获取 Y 子树的位置，然后再把这几个要改变的点相互连接就好了：

1
void rotate(int u)
2
{
3
    int v = tree[u].fa;
4
    // int u_fa = tree[u].fa;           // u_fa = v;
5
    int v_fa = tree[v].fa;              // u的目标父亲
6
    int son_u = get(u);                 // u在其父亲的位置
7
    int son_v = get(v);                 // v在其父亲的位置
8
    int change = tree[u].ch[son_u ^ 1]; // 获取u中需要更改的子树节点
9
    // 把这颗子树接到v的u位置：
10
    tree[change].fa = v;
11
    tree[v].ch[son_u] = change;
12
    // 把v接到u中不同的位置
13
    tree[v].fa = u;
14
    tree[u].ch[son_u ^ 1] = v;
15
    // 把u接到v原来的父亲中
16
    tree[u].fa = v_fa;
17
    tree[v_fa].ch[son_v] = u;
18
}

双旋（splay）

$splay(u,v)$ 是实现把 u 节点直接搬到 v 节点。

最简单的办法，对于 u 这个节点，每次单旋直到 v。

但是，众所周知出题老师拥有极强的卡时能力，可能会构造数据把单旋卡成 $n^2$ ，具体原因我也不清楚啦，反正不要这样用就好了，下面我们来写 $splay$ 函数吧~

OI-Wiki 把 $splay$ 分成了六种情况啊！六种！太麻烦了，实际上就三种啦。

情况一

我们的目标节点 v 就是 u 的父亲，那么就直接 $rotate$ 吧！

情况二

三个点连成了一条线……

这时候先把 2 旋转上去，再把 3 旋转上去就好了

1
else if (get(u) == get(tree[u].fa)) rotate(tree[u].fa), rotate(x);

情况三

三个点歪七扭八，不知道是什么东西……

这时候把 3 旋转两次就好啦

代码

全部代码如下：

1
void splay(int u, int v)
2
{
3
    v = tree[v].fa; // 方便写下面的代码
4
    while (tree[u].fa != v)
5
    {
6
        if (tree[tree[u].fa].fa == v) rotate(u);
7
        else if (get(u) == get(tree[u].fa)) rotate(tree[u].fa), rotate(x);
8
        else rotate(u), rotate(u);
9
    }
10
}

功能函数

Splay 最伟大的两个函数写好了，我们就要实现他作为一颗 BST 树的功能了，一个一个来，我们慢慢讲，因为下面的内容可能还需要修改上面的两个旋转函数。

清空节点

1
void clear(int u) { tree[u].ch[0] = tree[u].ch[1] = tree[u].fa = tree[u].fa = tree[u].size = tree[u].cnt = 0; }

维护 Size

1
void maintain(int u) { tree[u].size = tree[tree[u].ch[0]].size + tree[tree[u].ch[1]].size + tree[u].cnt; }

我们每一次旋转都会改变节点的 Size 值，因此要在 $rotate$ 函数的最后添加这两句：

1
maintain(u); // 维护u的size
2
maintain(v); // 维护v的size

最后完成的 $rotate$ 函数如下：

1
void rotate(int u)
2
{
3
    int v = tree[u].fa;
4
    // int u_fa = tree[u].fa;           // u_fa = v;
5
    int v_fa = tree[v].fa;              // u的目标父亲
6
    int son_u = get(u);                 // u在其父亲的位置
7
    int son_v = get(v);                 // v在其父亲的位置
8
    int change = tree[u].ch[son_u ^ 1]; // 获取u中需要更改的子树节点
9
    // 把这颗子树接到v的u位置：
10
    tree[change].fa = v;
11
    tree[v].ch[son_u] = change;
12
    // 把v接到u中不同的位置
13
    tree[v].fa = u;
14
    tree[u].ch[son_u ^ 1] = v;
15
    // 把u接到v原来的父亲中
16
    tree[u].fa = v_fa;
17
    tree[v_fa].ch[son_v] = u;
18
    maintain(u); // 维护u的size
19
    maintain(v); // 维护v的size
20
}

插入操作

插入操作是一个比较复杂的过程，具体步骤如下（假设插入的值为 $k$ ）：

如果树空了，则直接插入根并退出。
如果当前节点的权值等于 $k$ 则增加当前节点的大小并更新节点和父亲的信息，将当前节点进行 Splay 操作。
否则按照二叉查找树的性质向下找，找到空节点就插入即可（请不要忘记 Splay 操作）。

我们定义一个新变量root，来代表根节点的位置。

实现代码如下：

1
void insert(int k)
2
{
3
    int now = root; // 从根节点开始
4
    if (root == 0)  // 如果没有根节点就新建一个
5
    {
6
        tree[++tot].fa = 0;                 // 根节点没有父亲
7
        tree[tot].val = k;                  // 初始化值
8
        tree[tot].cnt = tree[tot].size = 1; // 初始化cnt与size
9
        root = tot;                         // 把根定为现在加入的新节点
10
    }
11
    else
12
    {
13
        while (1)
14
        {
15
            tree[now].size++;       // 走过这个点，代表它的大小增加了
16
            if (tree[now].val == k) // 如果k值与这个点相同，就放进去
17
            {
18
                tree[now].cnt++;  // 值的个数加一
19
                splay(now, root); // 把更新的点旋转到根
20
                return;
21
            }
22
            int nxt = k < tree[now].val ? 0 : 1; // 按照BST找节点
23
            if (!tree[now].ch[nxt])              // 如果找不到就加一个新的
24
            {
25
                tree[++tot].fa = now;               // 新节点的父亲就是当前的
26
                tree[tot].val = k;                  // 初始化值
27
                tree[tot].cnt = tree[tot].size = 1; // 初始化cnt与size
28
                tree[now].ch[nxt] = tot;            // 加入当前节点的儿子
29
                splay(tot, root);                   // 把新节点移动到根
30
                return;
31
            }
32
            now = tree[now].ch[nxt]; // 向下走
33
        }
34
    }
35
}

同时还要注意每一次 Splay 是把当前节点移动到根，所以要在 $splay$ 最后更新root。

1
void splay(int u, int v)
2
{
3
    v = tree[v].fa; // 方便写下面的代码
4
    while (tree[u].fa != v)
5
    {
6
        if (tree[tree[u].fa].fa == v) rotate(u);
7
        else if (get(u) == get(tree[u].fa)) rotate(tree[u].fa), rotate(x);
8
        else rotate(u), rotate(u);
9
        root = u;
10
    }
11
}

查询 k 的排名

根据二叉查找树的定义和性质，显然可以按照以下步骤查询 $k$ 的排名：

如果 $k$ 比当前节点的权值小，向其左子树查找。
如果 $k$ 比当前节点的权值大，将答案加上左子树 $size$ 和当前节点 $cnt$ 的大小，向其右子树查找。
如果 $k$ 与当前节点的权值相同，将答案加 $1$ 并返回。

实现代码如下：

1
int rank(int k)
2
{
3
    int ans = 0;    // 累计答案
4
    int now = root; // 从根开始
5
    while (1)
6
    {
7
        if (k < tree[now].val) // 如果比它小就向左找
8
        {
9
            now = tree[now].ch[0];
10
        }
11
        else
12
        {
13
            ans += tree[tree[now].ch[0]].size; // 否则加上左子树的大小
14
            if (k == tree[now].val)             // 如果找到了
15
            {
16
                splay(now, root); // 把找到的节点移动到根
17
                return ans + 1;   // 返回答案
18
            }
19
            ans += tree[now].cnt;  // 否则加上这个点的权值数
20
            now = tree[now].ch[1]; // 然后继续向右找
21
        }
22
    }
23
}

查询排名 k 的数

设 $k$ 为剩余排名，具体步骤如下：

如果左子树非空且剩余排名 $k$ 不大于左子树的大小 $size$ ，那么向左子树查找。
否则将 $k$ 减去左子树的和根的大小。如果此时 $k$ 的值小于等于 $0$ ，则返回根节点的权值，否则继续向右子树查找。

实现代码如下：

1
int kth(int k)
2
{
3
    int now = root; // 从根开始
4
    while (1)
5
    {
6
        if (tree[now].ch[0] && k <= tree[tree[now].ch[0]].size) // 如果在左子树中
7
        {
8
            now = tree[now].ch[0]; // 向左找
9
        }
10
        else
11
        {
12
            k -= tree[now].cnt + tree[tree[now].ch[0]].size; // 减去当前的和左子树的和
13
            if (k <= 0)                                      // 如果减完了，说明在当前节点
14
            {
15
                splay(now, root);     // 把找到的节点移动到根
16
                return tree[now].val; // 返回真实值
17
            }
18
            now = tree[now].ch[1]; // 否则继续向右找
19
        }
20
    }
21
}

查询前驱

前驱定义为小于 $x$ 的最大的数，那么查询前驱可以转化为：将 $x$ 插入（此时 $x$ 已经在根的位置了），前驱即为 $x$ 的左子树中最右边的节点，最后将 $x$ 删除即可。

实现代码如下：

1
int pre()
2
{
3
    int now = tree[root].ch[0];
4
    if (!now) return now;                          // 如果没有左子树，直接返回
5
    while (tree[now].ch[1]) now = tree[now].ch[1]; // 在左子树中一直向右走
6
    splay(now, root);               // 把找到的节点移动到根
7
    return now;
8
}

查询后继

后继定义为大于 $x$ 的最小的数，查询方法和前驱类似： $x$ 的右子树中最左边的节点。

实现代码如下：

1
int nxt()
2
{
3
    int now = tree[root].ch[1];
4
    if (!now) return now;                          // 如果没有右子树，直接返回
5
    while (tree[now].ch[0]) now = tree[now].ch[0]; // 在右子树中一直向左走
6
    splay(now, root);                              // 把找到的节点移动到根
7
    return now;
8
}

删除操作

删除操作也是一个比较复杂的操作，具体步骤如下：

首先将 $x$ 旋转到根的位置。
如果（有不止一个 $x$ ），那么将 $tree[x].cnt$ 减 $1$ 并退出。
否则，合并它的左右两棵子树即可。

1
void del(int k)
2
{
3
    rank(k);
4
    if (tree[root].cnt > 1) // 如果此节点数量足够
5
    {
6
        tree[root].cnt--; // 仅仅把cnt减一
7
        maintain(root);
8
        return;
9
    }
10
    if (!tree[root].ch[0] && !tree[root].ch[1]) // 如果只有一个点
11
    {
12
        clear(root); // 直接删掉
13
        root = 0;
14
        return;
15
    }
16
    if (!tree[root].ch[0]) // 如果没有左子树
17
    {
18
        int now = root;          // 从根开始
19
        root = tree[root].ch[1]; // 定义新根为右儿子
20
        tree[root].fa = 0;       // 重置父亲
21
        clear(now);              // 删掉原来的根
22
        return;
23
    }
24
    if (!tree[root].ch[1]) // 如果没有右子树
25
    {
26
        int now = root;          // 从根开始
27
        root = tree[root].ch[0]; // 定义新根为左儿子
28
        tree[root].fa = 0;       // 重置父亲
29
        clear(now);              // 删掉原来的根
30
        return;
31
    }
32
    // 如果左右子树都存在
33
    int now = root, x = pre();       // 从根开始，同时获得新根
34
    tree[tree[now].ch[1]].fa = x;    // 定义原根右儿子的父亲为新根
35
    tree[x].ch[1] = tree[now].ch[1]; // 定义新根的右儿子为原根右儿子
36
    clear(now);                      // 删掉原来的根
37
    maintain(root);                  // 重置新根
38
}

最终 Splay 模板

1
#include <iostream>
2
#include <cstring>
3
#include <cstdio>
4
#define N 100005
5

6
using namespace std;
7

8
struct Node
9
{
10
    int fa;    // 节点父亲
11
    int val;   // 节点权值
12
    int cnt;   // 权值出现次数
13
    int size;  // 子树大小
14
    int ch[2]; // 左儿子与右儿子（方便运算）
15
    Node()
16
    {
17
        fa = 0;
18
        val = 0;
19
        cnt = 0;
20
        size = 0;
21
        ch[0] = ch[1] = 0;
22
    }
23
    Node(int Fa, int Val, int Cnt, int Size, int R, int L)
24
    {
25
        fa = Fa;
26
        val = Val;
27
        cnt = Cnt;
28
        size = Size;
29
        ch[0] = L;
30
        ch[1] = R;
31
    }
32
} tree[N];
33
int tot;  // 不算重的节点个数
34
int root; // 根节点
35

36
bool get(int u) { return u == tree[u].ch[1]; }
37

38
void maintain(int u) { tree[u].size = tree[tree[u].ch[0]].size + tree[tree[u].ch[1]].size + tree[u].cnt; }
39

40
void clear(int u) { tree[u].ch[0] = tree[u].ch[1] = tree[u].fa = tree[u].fa = tree[u].size = tree[u].cnt = 0; }
41

42
void rotate(int u)
43
{
44
    int v = tree[u].fa;
45
    // int u_fa = tree[u].fa;           // u_fa = v;
46
    int v_fa = tree[v].fa;              // u的目标父亲
47
    int son_u = get(u);                 // u在其父亲的位置
48
    int son_v = get(v);                 // v在其父亲的位置
49
    int change = tree[u].ch[son_u ^ 1]; // 获取u中需要更改的子树节点
50
    // 把这颗子树接到v的u位置：
51
    tree[change].fa = v;
52
    tree[v].ch[son_u] = change;
53
    // 把v接到u中不同的位置
54
    tree[v].fa = u;
55
    tree[u].ch[son_u ^ 1] = v;
56
    // 把u接到v原来的父亲中
57
    tree[u].fa = v_fa;
58
    tree[v_fa].ch[son_v] = u;
59
    maintain(u); // 维护u的size
60
    maintain(v); // 维护v的size
61
}
62

63
void splay(int u, int v)
64
{
65
    v = tree[v].fa; // 方便写下面的代码
66
    while (tree[u].fa != v)
67
    {
68
        if (tree[tree[u].fa].fa == v) rotate(u);
69
        else if (get(u) == get(tree[u].fa)) rotate(tree[u].fa), rotate(x);
70
        else rotate(u), rotate(u);
71
        root = u;
72
    }
73
}
74

75
void insert(int k)
76
{
77
    int now = root; // 从根节点开始
78
    if (root == 0)  // 如果没有根节点就新建一个
79
    {
80
        tree[++tot].fa = 0;                 // 根节点没有父亲
81
        tree[tot].val = k;                  // 初始化值
82
        tree[tot].cnt = tree[tot].size = 1; // 初始化cnt与size
83
        root = tot;                         // 把根定为现在加入的新节点
84
    }
85
    else
86
    {
87
        while (1)
88
        {
89
            tree[now].size++;       // 走过这个点，代表它的大小增加了
90
            if (tree[now].val == k) // 如果k值与这个点相同，就放进去
91
            {
92
                tree[now].cnt++;  // 值的个数加一
93
                splay(now, root); // 把更新的点旋转到根
94
                return;
95
            }
96
            int nxt = k < tree[now].val ? 0 : 1; // 按照BST找节点
97
            if (!tree[now].ch[nxt])              // 如果找不到就加一个新的
98
            {
99
                tree[++tot].fa = now;               // 新节点的父亲就是当前的
100
                tree[tot].val = k;                  // 初始化值
101
                tree[tot].cnt = tree[tot].size = 1; // 初始化cnt与size
102
                tree[now].ch[nxt] = tot;            // 加入当前节点的儿子
103
                splay(tot, root);                   // 把新节点移动到根
104
                return;
105
            }
106
            now = tree[now].ch[nxt]; // 向下走
107
        }
108
    }
109
}
110

111
int rank(int k)
112
{
113
    int ans = 0;    // 累计答案
114
    int now = root; // 从根开始
115
    while (1)
116
    {
117
        if (k < tree[now].val) // 如果比它小就向左找
118
        {
119
            now = tree[now].ch[0];
120
        }
121
        else
122
        {
123
            ans += tree[tree[now].ch[0]].size; // 否则加上左子树的大小
124
            if (k == tree[now].val)             // 如果找到了
125
            {
126
                splay(now, root); // 把找到的节点移动到根
127
                return ans + 1;   // 返回答案
128
            }
129
            ans += tree[now].cnt;  // 否则加上这个点的权值数
130
            now = tree[now].ch[1]; // 然后继续向右找
131
        }
132
    }
133
}
134

135
int kth(int k)
136
{
137
    int now = root; // 从根开始
138
    while (1)
139
    {
140
        if (tree[now].ch[0] && k <= tree[tree[now].ch[0]].size) // 如果在左子树中
141
        {
142
            now = tree[now].ch[0]; // 向左找
143
        }
144
        else
145
        {
146
            k -= tree[now].cnt + tree[tree[now].ch[0]].size; // 减去当前的和左子树的和
147
            if (k <= 0)                                      // 如果减完了，说明在当前节点
148
            {
149
                splay(now, root);     // 把找到的节点移动到根
150
                return tree[now].val; // 返回真实值
151
            }
152
            now = tree[now].ch[1]; // 否则继续向右找
153
        }
154
    }
155
}
156

157
int pre()
158
{
159
    int now = tree[root].ch[0];
160
    if (!now) return now;                          // 如果没有左子树，直接返回
161
    while (tree[now].ch[1]) now = tree[now].ch[1]; // 在左子树中一直向右走
162
    splay(now, root);                              // 把找到的节点移动到根
163
    return now;
164
}
165

166
int nxt()
167
{
168
    int now = tree[root].ch[1];
169
    if (!now) return now;                          // 如果没有右子树，直接返回
170
    while (tree[now].ch[0]) now = tree[now].ch[0]; // 在右子树中一直向左走
171
    splay(now, root);                              // 把找到的节点移动到根
172
    return now;
173
}
174

175
void del(int k)
176
{
177
    rank(k);
178
    if (tree[root].cnt > 1) // 如果此节点数量足够
179
    {
180
        tree[root].cnt--; // 仅仅把cnt减一
181
        maintain(root);
182
        return;
183
    }
184
    if (!tree[root].ch[0] && !tree[root].ch[1]) // 如果只有一个点
185
    {
186
        clear(root); // 直接删掉
187
        root = 0;
188
        return;
189
    }
190
    if (!tree[root].ch[0]) // 如果没有左子树
191
    {
192
        int now = root;          // 从根开始
193
        root = tree[root].ch[1]; // 定义新根为右儿子
194
        tree[root].fa = 0;       // 重置父亲
195
        clear(now);              // 删掉原来的根
196
        return;
197
    }
198
    if (!tree[root].ch[1]) // 如果没有右子树
199
    {
200
        int now = root;          // 从根开始
201
        root = tree[root].ch[0]; // 定义新根为左儿子
202
        tree[root].fa = 0;       // 重置父亲
203
        clear(now);              // 删掉原来的根
204
        return;
205
    }
206
    // 如果左右子树都存在
207
    int now = root, x = pre();       // 从根开始，同时获得新根
208
    tree[tree[now].ch[1]].fa = x;    // 定义原根右儿子的父亲为新根
209
    tree[x].ch[1] = tree[now].ch[1]; // 定义新根的右儿子为原根右儿子
210
    clear(now);                      // 删掉原来的根
211
    maintain(root);                  // 重置新根
212
}
213

214
int main()
215
{
216
    return 0;
217
}

前言

Splay

设计旋转

单旋（rotate）

情况一

情况二

代码

双旋（splay）

情况一

情况二

情况三

代码

功能函数

清空节点

维护 Size

插入操作

查询 k 的排名

查询排名 k 的数

查询前驱

查询后继

删除操作

最终 Splay 模板

觉得这篇文章怎么样？

分享这篇文章

评论区

标签

分类

前言

Splay

设计旋转

单旋（rotate）

情况一

情况二

代码

双旋（splay）

情况一

情况二

情况三

代码

功能函数

清空节点

维护 Size

插入操作

查询 k 的排名

查询排名 k 的数

查询前驱

查询后继

删除操作

最终 Splay 模板

觉得这篇文章怎么样？

分享这篇文章

评论区