好吧 Splay 还是太超标了。

【显然】

当你遇到【显然】时，请自证。

0x01 平衡树

首先我们来聊聊平衡树。

顾名思义，就是平衡的树）

平衡树是一颗二叉树，左右子树高度一般相同，最多相差 1，这也保证了时间复杂度。

平衡树有很多种：

Splay（代码适中，非常灵活）
红黑树（代码巨长，不用管他，但是特别快）
Treap（代码适中，较快）
AVL（代码适中，较快）
B 树
B+ 树
SBT

0x02 Splay

Splay，一种平衡树。

说实话，这玩意特别玄学，当然，还是有证明保证时间复杂度的。

0x03 左旋，右旋

可以看到这张图片，图丑勿喷。

先来看右旋，右旋是从左图到右图的过程。

首先，设

x

的父节点为

y

，

y

的父节点为

z

（可以为空）。然后设出

A

，

B

，

C

三颗树，分别为

x

的左子树，

x

的右子树，

y

的右子树，如图所示。

让

x

代替

y

，同时将

y

移动到

x

的右子树。

A

还为

x

的左子树，

B

变为

y

的左子树，

C

还是

y

的右子树，

f

部分不变。

这样就完成了 Splay 的右旋，左旋只需要反过来就可以了。

Splay 之所以这么定义左旋和右旋是因为，如果你对一颗 Splay 进行一次合法的左旋或右旋，中序遍历将不会改变。这样的性质让 Splay 成为了一种优秀的数据结构。

0x04 splay 操作

这大概是 Splay 的最重要的一个部分了。

定义函数 splay(x, k) 表示将

x

旋转到

k

的下方，特别的

k=0

表示将

x

转到根节点。

约定

接下来将使用旋转某个节点代替左旋或右旋某个节点。

具体地：

当 $x$ 为 $x$ 的父节点的左儿子，则旋转 $x$ 即右旋 $x$ 。
当 $x$ 为 $x$ 的父节点的右儿子，则旋转 $x$ 即左旋 $x$ 。

考虑递归完成这个操作，考虑当前状态，其中

x

为要操作的节点，

y

为

x

的父节点，

f

为

y

的父节点。

如果

f=k

就旋转

x

，退出递归就可以了。

剩下的依旧两种情况。

第一种情况中

x

，

y

，

f

成一条链直线。

第二种情况中

x

，

y

，

f

成一条折线。

这是处理这两种情况的方法。

对于第一种情况，旋转

y

，旋转

x

。

对于第二种情况，旋转

x

，旋转

x

。

图片中只给出了两种中一种的旋转方法，剩下的一个十分【显然】。

注意，虽然图片只给了一种，但是文字解释是全面的，因为旋转分 2 种，上面有定义。

作者并不知道什么叫做 zig，zig-zig，zig-zag，zag-zig 等令我晕头转向的东西，请谅解 qwq。

0x05 插入

最一般的情况，如果只给你一个数值

x

要插入的话，把 Splay 当成一颗二叉搜索树，找到

x

的位置即可。接下来，需要将

x

旋转到树根。

请注意，这一步是 Splay 时间复杂度的保证。

来看一个变种，对序列进行维护。

此时，假设我们要将序列

y

插入

x

之后。我们假设我们已经通过一种未知手段将原序列以及

y

构建成了一棵树。

设

x

的后继为

z

，使用 splay(x, 0) 操作将

x

转到根，然后使用 splay(z, x) 操作将

z

转到

x

的下面，然后将

y

序列构建的树插入到

z

的左子树就可以了。

0x06 实战

终于来到了激动人心的实战时刻了！

例题：文艺平衡树

这道题目是一道不错的入门题，需要支持翻转操作。

考虑 Splay 维护什么信息。

左右儿子

ch

数组，父亲节点

p

，当前节点的数值

val

必不可少。

随后，由于需要查询数组中第

pos

个数，在 Splay 树中的位置，所以需要维护一个

siz

。

又因为这道题目中对区间进行操作，所以需要懒标记

laz

。

懒标记下传时，只需要将左右子树调换一下，然后让

laz_{now}=0

，同时让

laz_{ch_{now,0}}

和

laz_{ch_{now,1}}

反转即可。

同时，旧事重提，我们应该怎么输出最后的数列呢？

追溯到左旋，右旋部分。我们提到，Splay 的左旋，右旋可以保持 Splay 的中序遍历，所以最后直接输出 Splay 的中序遍历即可。

例题代码

CPP

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5;

int n, m, rt, idx;

struct Splay{
    int ch[2], p, v;
    int siz, laz;

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

void pushup(int u){
    tr[u].siz = tr[tr[u].ch[0]].siz + tr[tr[u].ch[1]].siz + 1;
}

void pushdown(int u){
    if (tr[u].laz){
        swap(tr[u].ch[0], tr[u].ch[1]);
        tr[tr[u].ch[0]].laz ^= 1;
        tr[tr[u].ch[1]].laz ^= 1;
        tr[u].laz = 0;
    }
}

int getdir(int x){
    return tr[tr[x].p].ch[1] == x;
}

void output(int u){
    pushdown(u);
    if (tr[u].ch[0]) output(tr[u].ch[0]);
    if (tr[u].v >= 1 && tr[u].v <= n) cout << tr[u].v << " ";
    if (tr[u].ch[1]) output(tr[u].ch[1]);
}

void rotate(int x){
    int y = tr[x].p, z = tr[y].p;
    int a = getdir(x), b = getdir(y);
    tr[z].ch[b] = x, tr[x].p = z;
    tr[y].ch[a] = tr[x].ch[a ^ 1], tr[tr[x].ch[a ^ 1]].p = y;
    tr[x].ch[a ^ 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 (getdir(x) != getdir(y)) rotate(x);
            else rotate(y);
        }
        rotate(x);
    }
    if (!k) rt = x;
}

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

int get_k(int k){
    int u = rt;
    while (1){
        pushdown(u);
        if (tr[tr[u].ch[0]].siz >= k) u = tr[u].ch[0];
        else if (tr[tr[u].ch[0]].siz + 1 == k) return u;
        else k -= tr[tr[u].ch[0]].siz + 1, u = tr[u].ch[1];
    }
    return -1; // You have no egg!
}

int main(){
    cin >> n >> m;
    for (int i = 0; i <= n + 1; i ++ ) insert(i);

    for (int i = 1; i <= m; i ++ ){
        int l, r; cin >> l >> r;
        l = get_k(l), r = get_k(r + 2);
        splay(l, 0), splay(r, l);
        tr[tr[r].ch[0]].laz ^= 1;
    }

    output(rt);
    return 0;
}

代码解释

代码中的 rotate 函数，这里实际上实现了上面为了方便叙述定义的旋转操作，是某位压行大佬发明的写法。

代码中的 insert 函数，把 Splay 当作一颗二叉搜索树。注意：这里其实不可以这么用，因为有反转操作，但是由于 insert 函数只在初始的时候使用过，所以可以这么用。

get_k 函数通过

siz

变量，找到 Splay 中按照中序遍历的第

k

个数。

0x07 写在后面

很抱歉只给出了一道例题，但是希望可以起到帮助。

有问题可以在评论区提出。如果有帮助，欢迎点赞支持哦。

浅谈 splay

文章操作

0x01 平衡树

0x02 Splay

0x03 左旋，右旋

0x04 splay 操作

0x05 插入

0x06 实战

0x07 写在后面

相关推荐

评论

浅谈 splay