Splay

firstlight Lv2
  2023-08-25 14:44 2023-08-25 14:44 创建   2025-01-22 22:41:04 2025-01-22 22:41:04 更新      

简介：

Splay树 或 伸展树，是一种平衡二叉查找树，它通过 Splay操作 ，每操作一个节点，就将该节点旋转 (双旋) 至根节点 ( 这样既可以保证其时间复杂度，又可以保证其维护值的正确性 ) ，使得整棵树在仍然满足二叉查找树性质的同时，可以使树保持平衡，高度接近，从而使其能够在均摊 时间内完成插入、查找和删除操作。

这种方法避免了普通二叉查找树在数据为单调上升序列时退化为链的问题，有效降低了时间复杂度，但常数很大，有一定局限性。

Splay 树由 和 于 1985 年发明。

代码巨长

二叉查找树的性质：

  1. 若二叉搜索树的左子树不为空，则其左子树上所有点的附加权值均小于其根节点的值
  2. 若二叉搜索树的右子树不为空，则其右子树上所有点的附加权值均大于其根节点的值
  3. 二叉搜索树的左右子树均为二叉搜索树

维护的量：

用结构体存储一个节点的所有信息

1
2
3
4
5
6
7
8
9
10
11
12
struct Node{
    int s[2], p, v;
    int size, flag;
    
    void init(int _v, int _p) // 将单点插入
    {
        v = _v, p = _p;
        size = 1;
    }
}tr[N];

int root, idx;

存该点的左右儿子， 表示左儿子， 表示右儿子

存该节点的父节点

存该节点的权值

存以该节点为根节点的子树的大小，即节点个数

存支持的具体操作的懒标记

存根的值

存树中一共有多少个节点

基本操作：

1.更新操作——pushup( x ) :

更新节点的 值

节点的大小包含它的左子树、它的右子树和它自己

通用代码：

1
2
3
4
void pushup(int x)
{
    tr[x].size = tr[tr[x].s[0]].size + tr[tr[x].s[1]].size + 1;
}

2.旋转操作——rotate( x ) :

将节点进行旋转，利用一个函数同时实现左旋(zag)和右旋(zig)操作

操作本质上是将一个节点上移至其父节点上方，即将该节点变为其父节点的父亲

的操作满足三个条件：

  1. 整棵树的中序遍历不变 (树本质是二叉查找树，必须满足其性质)
  2. 受影响的节点维护的值仍然正确有效
  3. 旋转后的点位于其父节点的同一位置，即若其父节点是其祖父节点的左儿子，则旋转后的点也是其原来祖父节点的左儿子；若其父节点是其祖父节点的右儿子，则旋转后的点也是其原来祖父节点的右儿子 为了满足二叉查找树的性质：由于节点为节点的左 / 右儿子，节点为节点的子节点，所以节点的值一定小于 / 大于（分别对应左儿子和右儿子）节点的值。因此旋转后节点一定在原来节点的位置上

Splay rotate

左旋与右旋可以用同一段代码实现

实现原理：

分为三步 ：

  1. 将节点接在节点下面节点的位置上

  2. 若节点为节点的右儿子，将节点的左儿子接在节点的右儿子的位置上； 若节点为节点的左儿子，将节点的右儿子接在节点的左儿子的位置上 (即将与节点对于节点的方向相反的节点的子节点接在节点下面节点位置上)

  3. 将节点接在节点下面的与上图一致的对应位置上

通过位运算将各节点的位置进行对应

int k = tr[y].s[1] == x 实现对x是否为y的右儿子的判断，用存储，是则，否则

tr[z].s[1]==y 实现根据运行时的具体情况判断节点的正确位置。当成立时，其值为1，说明节点原为节点的右儿子；当不成立时，其值为0，说明节点为节点的左儿子

tr[y].s[k] = tr[x].s[k ^ 1], tr[tr[x].s[k ^ 1]].p = y 和 tr[x].s[k ^ 1] = y, tr[y].p = x 实现将节点对应的子节点接在节点的对应位置。根据上图，与操作的节点的子节点不同，操作节点的右节点，将其接在其父节点的左儿子的位置上；操作节点的左节点，将其接在其父节点的右儿子的位置上。根据异或运算两位相同为0，两位不同为0的性质，可知：当时， ^ ，分别表示右子节点和左子节点；当时， ^ ，分别表示左子节点和右子节点，恰好符合上面的要求

pushup(y),pushup(x) 实现更新节点和节点的。旋转后节点为节点的子节点，应先算出节点的新，才能由此算出节点的新。

通用代码：

1
2
3
4
5
6
7
8
9
void rotate(int x)
{
    int y = tr[x].p, z = tr[y].p;
    int k = tr[y].s[1] == x;
    tr[z].s[tr[z].s[1] == y] = x, tr[x].p = z; // 将x接在y原来的位置上
    tr[y].s[k] = tr[x].s[k ^ 1], tr[tr[x].s[k ^ 1]].p = y;
    tr[x].s[k ^ 1] = y, tr[y].p = x;
    pushup(y), pushup(x); 
}

3.核心操作 —— Splay( x , k ) ：

将点前节点旋转至节点的下面。

由于树满足二叉搜索树的性质，所以节点在节点下的位置取决于节点的值是否大于节点的值。即若节点的值大于节点的值，则节点旋转后作为节点的右儿子；否则为节点的左儿子

Splay(x,0) 表示将节点旋转至根节点

的双旋操作，包含三层节点，一共四种情况，其中两种分别为另外两种的对称形式，可视作同一种情况，所以只讨论其中两种不同的情况即可。

的单旋操作只在仅剩两层时需要，有一种情况，不进行讨论

1.转 - 转 型 ：

Splay zig - zig
该情况又称 - 型

如图所示，在节点为节点的左儿子 / 右儿子，且节点为节点的左儿子 / 右儿子时进行此操作

2.转 - 转 型 ：

Splay zag - zig

该情况又称 - 型

如图所示，在节点为节点的左儿子 / 右儿子，且节点为节点的右儿子 / 左儿子时进行此操作

实现原理 ：

操作可以理解为对 Splay树 的一部分集中进行操作的一种操作

节点不是节点的子节点，则一直进行操作

if (z != k) 实现对是否仅需再对两层的结构进行旋转的判断。为真则只旋转节点即可

if ((tr[y].s[1] == x) ^ (tr[z].s[1] == y))实现对节点、、是否不在一条直线上的判断 (即判断当前情况是否为转 - 转型的初始形态)

通用代码 ：

1
2
3
4
5
6
7
8
9
10
11
12
void splay(int x, int k)
{
    while (tr[x].p != k)
    {
        int y = tr[x].p, z = tr[y].p;
        if (z != k)
            if ((tr[y].s[1] == x) ^ (tr[z].s[1] == y)) rotate(x);
            else rotate(y);
        rotate(x);
    }
    if (!k) root = x; // 如果k的值为0,表示将x转至根节点,需要将root改为x
}

4.建树操作——build( l , r , p ) :

实现原理 ：

将一段区间从中间断开，中间的点作为根节点，左右递归重复操作，即可实现平衡地建树

通用代码 ：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
cosnt int N = 点的个数, INF = 2e9;

int build(int l, int r, int p)
{
    int mid = l + r >> 1;
    int u = nodes[idx -- ];
    tr[u].init(w[mid], p);
    if (l < mid) tr[u].s[0] = build(l, mid - 1, u);
    if (mid < r) tr[u].s[1] = build(mid + 1, r, u);
    pushup(u);
    return u;
}

int main()
{
    for(int i  = 1;i < N;i ++ ) node[ ++ idx] = i;
    scanf("%d", &n);
    for(int i = 1;i <= n;i ++ ) scanf("%d", &w[i]);
    w[0] = w[n + 1] = -INF;
    root = build(0, n + 1, 0);
}

5.查询操作之1——getk( k ) ：

查找 Splay树 中的第大数

实现原理 ：

递归进行查找，查找时会出现三种情况 ：

  1. 当前节点的左子树的大小 时 说明第小的节点在当前节点的左子树，递归左子树

  2. 当前节点的左子树的大小 时 说明第小的节点为当前节点，直接返回当前节点

  3. 其他情况 说明第小的节点在当前节点的右子树，递归右子树。这里注意在右子树继续寻找时，要寻找的是在右子树中排名 - =的节点，即要减去左子树和根，这相当于将右子树接在当前节点的父节点下(这样找才能符合条件)

通用代码 ：

1
2
3
4
5
6
7
8
9
10
11
12
int getk(int k)
{
    int u = root;
    while (true) // 不易爆栈的递归查找
    {
        pushdown(u); // 依照每一道题的具体逻辑编写pushdown函数
        if (tr[tr[u].s[0]].size >= k) u = tr[u].s[0];
        else if (tr[tr[u].s[0]].size + 1 == k) return u;
        else k -= tr[tr[u].s[0]].size + 1, u = tr[u].s[1];
    }
    return -1;
}

6.查询操作之2——getv( v ) :

： 查找 Splay树 中值为的节点

实现原理 ：

通用代码 :

支持操作：

1.单点删除：

待补充

2.区间删除：

实现原理：

的内存回收机制 : 开一个足够大的数组，用一个指针动态维护当前用到了哪一个位置，删除时将当前的节点编号放回数组即可

通用代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void recycle(int u)
{
    if (tr[u].s[0]) recycle(tr[u].s[0]);
    if (tr[u].s[1]) recycle(tr[u].s[1]);
    nodes[ ++ idx] = u;
}

void clean(int start, int number)
{
    int l = getk(start), r = getk(start + number + 1);
    splay(l, 0), splay(r, l);
    recycle(tr[r].s[0]);
    tr[r].s[0] = 0;
    pushup(r), pushup(l);
}

3.单点插入——insert_points( v )

向 Splay树 中插入一个节点

实现原理 ：

首先通过递归找到插入该点的正确位置，同时找到该点正确的父节点

之后取一个新点，用于存储插入节点

将插入节点进行初始化

实现细节 ：

表示插入节点所在的节点的子树 (若插入节点的值小于节点的值，则它在节点的左子树，此时 的值为0，恰好表示节点的左子树；若插入节点的值大于节点的值，则它在节点的右子树，此时 的值为1，恰好表示节点的右子树)

插入操作对插入节点进行了操作，需要将该点旋转至根节点

通用代码 ：

1
2
3
4
5
6
7
8
9
void insert_points(int v)
{
    int u = root, p = 0;
    while(u) p = u, u = tr[u].s[v > tr[u].v]; // 不易爆栈的递归查找
    u = ++ idx; 
    if (p) tr[p].s[v > tr[p].v] = u; // 如果该点不为根,才需要将它的父节点指向它
    tr[u].init(v, p); // 初始化
    splay(u, 0);
}

4.序列插入——insert_interval( start , number ) :

向 Splay树 中插入一个长度为的序列

这种插入方式同样可以用于进行单点插入操作

实现原理 ：

待补充

通用代码 ：

1
2
3
4
5
6
7
8
9
void insert_interval(int start, int number)
{
    for (int i = 0; i < number; i ++ ) scanf("%d", &w[i]);
    int l = getk(start + 1), r = getk(start + 2);
    splay(l, 0), splay(r, l);
    int u = build(0, number - 1, r);
    tr[r].s[0] = u;
    pushup(r), pushup(l);
}

5.区间翻转：

将一段区间进行翻转

该操作是用懒标记实现的

实现原理：

首先找到需要翻转区间左端 (即节点) 的前驱 (即节点 - ) 和区间右端 (即节点) 的后继 (即节点 + )
前驱后继

reverse ：

然后将节点 - 旋转至根节点，再将节点 + 旋转至节点的下面

此时节点 + 的左子树是大于节点 - 的值且小于节点 + 的值的所有数，即需要翻转的整个区间

所以在 + 的左子树的根节点打上翻转懒标记即可

pushdown :

通用代码：

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
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;

int n, m;
struct Node
{
    int s[2], p, v;
    int size, flag;

    void init(int _v, int _p)
    {
        v = _v, p = _p;
        size = 1;
    }
}tr[N];
int root, idx;

void pushup(int x)
{
    tr[x].size = tr[tr[x].s[0]].size + tr[tr[x].s[1]].size + 1;
}

void pushdown(int x)
{
    if (tr[x].flag)
    {
        swap(tr[x].s[0], tr[x].s[1]);
        tr[tr[x].s[0]].flag ^= 1;
        tr[tr[x].s[1]].flag ^= 1;
        tr[x].flag = 0;
    }
}

void rotate(int x)
{
    int y = tr[x].p, z = tr[y].p;
    int k = tr[y].s[1] == x;
    tr[z].s[tr[z].s[1] == y] = x, tr[x].p = z;
    tr[y].s[k] = tr[x].s[k ^ 1], tr[tr[x].s[k ^ 1]].p = y;
    tr[x].s[k ^ 1] = y, tr[y].p = x;
    pushup(y), pushup(x);
}

void splay(int x, int k)
{
    while (tr[x].p != k)
    {
        int y = tr[x].p, z = tr[y].p;
        if (z != k)
            if ((tr[y].s[1] == x) ^ (tr[z].s[1] == y)) rotate(x);
            else rotate(y);
        rotate(x);
    }
    if (!k) root = x;
}

void insert(int v)
{
    int u = root, p = 0;
    while (u) p = u, u = tr[u].s[v > tr[u].v];
    u = ++ idx;
    if (p) tr[p].s[v > tr[p].v] = u;
    tr[u].init(v, p);
    splay(u, 0);
}

int get_k(int k)
{
    int u = root;
    while (true)
    {
        pushdown(u);
        if (tr[tr[u].s[0]].size >= k) u = tr[u].s[0];
        else if (tr[tr[u].s[0]].size + 1 == k) return u;
        else k -= tr[tr[u].s[0]].size + 1, u = tr[u].s[1];
    }
    return -1;
}

void output(int u)
{
    pushdown(u);
    if (tr[u].s[0]) output(tr[u].s[0]);
    if (tr[u].v >= 1 && tr[u].v <= n) printf("%d ", tr[u].v);
    if (tr[u].s[1]) output(tr[u].s[1]);
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i <= n + 1; i ++ ) insert(i);
    while (m -- )
    {
        int l, r;
        scanf("%d%d", &l, &r);
        l = get_k(l), r = get_k(r + 2);
        splay(l, 0), splay(r, l);
        tr[tr[r].s[0]].flag ^= 1;
    }
    output(root);
    return 0;
}

总结：

线段树支持的操作平衡树都可以支持，与线段树一样可以使用懒标记，但线段树的常数是Spaly的，可以用线段树的尽量用线段树

  • 标题: Splay
  • 作者: firstlight
  • 创建于 : 2023-08-25 14:44:00
  • 更新于 : 2025-01-22 22:41:04
  • 链接: https://blog.firstlightport.top/posts/splay/
  • 版权声明: 本文章采用 CC BY-NC-SA 4.0 进行许可。
评论
目录
Splay
  1. 简介：
  2. 二叉查找树的性质：
  3. 维护的量：
  4. 基本操作：
    1. 1.更新操作——pushup( x ) :
      1. 通用代码：
    2. 2.旋转操作——rotate( x ) :
      1. 实现原理：
      2. 通用代码：
    3. 3.核心操作 —— Splay( x , k ) ：
      1. 1.转 - 转 型 ：
      2. 2.转 - 转 型 ：
      3. 实现原理 ：
      4. 通用代码 ：
    4. 4.建树操作——build( l , r , p ) :
      1. 实现原理 ：
      2. 通用代码 ：
    5. 5.查询操作之1——getk( k ) ：
      1. 实现原理 ：
      2. 通用代码 ：
    6. 6.查询操作之2——getv( v ) :
      1. 实现原理 ：
      2. 通用代码 :
  5. 支持操作：
    1. 1.单点删除：
    2. 2.区间删除：
      1. 实现原理：
      2. 通用代码：
    3. 3.单点插入——insert_points( v )
      1. 实现原理 ：
      2. 实现细节 ：
      3. 通用代码 ：
    4. 4.序列插入——insert_interval( start , number ) :
      1. 实现原理 ：
      2. 通用代码 ：
    5. 5.区间翻转：
      1. 实现原理：
      2. 通用代码：
  6. 总结：