Splay 学习笔记 [基础]

Splay

前言

平衡树这方面，我是从 \(\text{Treap}\) 入门的。但是总觉得 \(\text{Treap}\) 左右旋转不是很好，就去学了 \(\text{FHQ-Treap}\)。自从学了这个非旋转的 \(\text{Treap}\) 之后，它的简洁和优美就令我震撼。大部分题已经可以做了！不过平衡树这个数据结构里面一个很常用的优秀平衡树——\(\text{Splay}\) 我还没有学。鉴于以后会有用到 \(\text{Splay}\) 作为前置知识的数据结构，就学了一下 \(\text{Splay}\)。

不过 \(\text{Splay}\) 真的比 \(\text{FHQ-Treap}\) 复杂很多。

参考资料：\(\text{OI wiki}\)。

本博客的两版代码都通过了 \(\text{LibreOJ}\) 的模板题。放上来的代码也是它格式化过的。

定义

首先是定义部分呢。

fa[N]  ch[N][2]  val[N]   cnt[N]      sz[N]   rt    tot 
父节点  左右儿子   节点的值 相同值节点计数  子树大小 根节点 总节点个数

基本函数

一些维护基本信息的函数。

void Maintain(int x) {
    sz[x] = sz[ch[x][0]] + sz[ch[x][1]] + cnt[x];
} // 维护节点大小
bool Get(int x) {
    return x == ch[fa[x]][1];
} // 判断是左儿子还是右儿子，左儿子返回 0，右儿子返回 1
void Clear(int x) {
    ch[x][0] = ch[x][1] = fa[x] = val[x] = sz[x] = cnt[x] = 0;
}

旋转

\(\text{Splay}\) 的旋转分左右旋。但是在 \(\text{Rotate}\) 这个函数的编写上，旋转变成了自适应旋转。一次旋转的结果就是把被旋转的节点往根的方向上提一个节点。

void Rotate(int x) {
    int y = fa[x], z = fa[y], chk = Get(x);
    ch[y][chk] = ch[x][chk ^ 1]; // y 的 x 方向的儿子变成 x 的另一方向的儿子

    if (ch[x][chk ^ 1])
        fa[ch[x][chk ^ 1]] = y; // 要是 x 另一方向真的有儿子的话，更新父亲

    ch[x][chk ^ 1] = y; // x 另一方向儿子变成 y
    fa[y] = x; // y 的父亲变成 x
    fa[x] = z; // x 的父亲变成 z

    if (z)
        ch[z][y == ch[z][1]] = x; // 要是真的有 z 的话，z 的 y 方向的儿子变成 x

    Maintain(y);
    Maintain(x);
}

Splay

这个操作是 \(\text{Splay}\) 能保持平衡的关键。它把一个选定节点一路旋转到根节点。

由于我们的旋转是自适应旋转，双旋不用讨论左右，只需要讨论是转两次 \(x\) 节点，或者是先转一次 \(fa(x)\) 再转一次 \(x\) 即可。

void Splay(int x) {
    for (int f = fa[x]; f = fa[x], f; Rotate(x))
        if (fa[f])
            Rotate(Get(x) == Get(f) ? f : x);

    rt = x;
    // 相同就转父亲，不同就转 x，之后循环体再转一次 x
}

插入

\(\text{Splay}\) 的插入就需要稍微讨论一下。

主要是需要记住在操作结束之后进行一发 Splay 操作。

void Insert(int k) {
    if (!rt) { // 没有根直接插入
        val[++ tot] = k;
        cnt[tot] ++;
        rt = tot;
        Maintain(rt);
        return;
    }

    int cur = rt, f = 0; // 当前位置为根

    while (true) {
        if (val[cur] == k) { // 已有节点，增加计数即可
            cnt[cur] ++;
            Maintain(cur);
            Maintain(f);
            Splay(cur);
            break;
        }

        f = cur; // f(父节点) = 当前节点
        cur = ch[cur][val[cur] < k]; // 当前节点往下走

        if (!cur) { // 当前节点为空，插入
            val[++ tot] = k;
            cnt[tot] ++;
            fa[tot] = f;
            ch[f][val[f] < k] = tot;
            Maintain(tot);
            Maintain(f);
            Splay(tot);
            break;
        }
    }
}

根据值求排名

还是 BST 那一套操作。也需要注意在最后来一发 Splay。

int Rank(int k) {
    int res = 0, cur = rt;

    while (true) {
        if (k < val[cur])
            cur = ch[cur][0]; // 走进左子树
        else {
            res += sz[ch[cur][0]];

            if (k == val[cur]) { // 找到了
                Splay(cur);
                return res + 1;
            }

            res += cnt[cur];
            cur = ch[cur][1];
            // 走到右子树
        }
    }
}

根据排名求值

还是需要注意 Splay 操作。

int Kth(int k) {
    int cur = rt;

    while (true) {
        if (ch[cur][0] && k <= sz[ch[cur][0]])
            cur = ch[cur][0]; // 走到左子树
        else {
            k -= cnt[cur] + sz[ch[cur][0]]; // 减去当前和左子树的

            if (k <= 0) {
                Splay(cur);
                return val[cur]; // 找到了
            }

            cur = ch[cur][1]; // 走到右子树
        }
    }
}

求前驱后继

\(\text{Splay}\) 的求前驱和后继就显得很累赘，但是能很好地体现出它独有的 Splay 操作的特色。

在执行求 \(x\) 的前驱或后继的函数之前，要先插入 \(x\)，这样 \(x\) 就被转到了根。之后执行 Pre() 或者 Nxt()，最后还得 Del(x) 把 \(x\) 这个值再删掉。

但是相对来说会简单一点，比起 \(\text{Treap}\)。不过还是比不上 \(\text{FHQ-Treap}\)。由于根节点一定为 \(x\)，所以前驱直接从左子树往右走，后继直接从右子树往左走。

int Pre() { // 前驱：先插入，再调用这个函数，再删除
    int cur = ch[rt][0]; // 左子树

    if (!cur)
        return cur;

    while (ch[cur][1])
        cur = ch[cur][1]; // 最右边的

    Splay(cur);
    return cur;
}

int Nxt() { // 同理
    int cur = ch[rt][1];

    if (!cur)
        return cur;

    while (ch[cur][0])
        cur = ch[cur][0];

    Splay(cur);
    return cur;
}

删除

在求前驱和后继的时候，我们就先提到了“删除”这个函数。

删除也还挺麻烦的...分情况讨论。

void Del(int k) {
    Rank(k); // 把值为 k 的节点转到根

    if (cnt[rt] > 1) {
        cnt[rt] --;
        Maintain(rt);
        return; // 直接减少计数，不用破坏树的形态
    }

    if (!ch[rt][0] && !ch[rt][1]) {
        Clear(rt);
        rt = 0;
        return; // 只剩根，清掉即可
    }

    if (!ch[rt][0]) {
        int cur = rt;
        rt = ch[rt][1];
        fa[rt] = 0;
        Clear(cur);
        return; // 没有左儿子，把根设置为右儿子，删掉根即可
    }

    if (!ch[rt][1]) {
        int cur = rt;
        rt = ch[rt][0];
        fa[rt] = 0;
        Clear(cur);
        return; // 同理
    }

    int cur = rt;
    int x = Pre();
    fa[ch[cur][1]] = x;
    ch[x][1] = ch[cur][1];
    Clear(cur);
    Maintain(rt);
    // 有左右儿子，还得拆掉根节点，就先找前驱
    // 之后根的右儿子的父亲设置为 x
    // x 的右儿子设置为根的右儿子
    // 类似链表，根的信息就没了联系
    // 清掉根的信息，维护根即可
}

封装

可以使用结构体进行一个封装。

这里是封装后，模板题的代码：（结合个人风格，使用了宏定义）

#include 
#define ch(x,y) ch[(x)][(y)]
using namespace std;
const int N = 100005;
int rt, tot;
int sz[N], ch[N][2], val[N], fa[N], cnt[N];
struct SplayTemplate {
    void Maintain(int x) {
        sz[x] = sz[ch(x, 0)] + sz[ch(x, 1)] + cnt[x];
    }
    bool Get(int x) {
        return x == ch(fa[x], 1);
    }
    void Clear(int x) {
        sz[x] = ch(x, 0) = ch(x, 1) = val[x] = cnt[x] = fa[x] = 0;
    }
    //--------------------------------------------------------------
    void Rotate(int x) {
        int y = fa[x], z = fa[y], chk = Get(x);
        ch(y, chk) = ch(x, chk ^ 1);

        if (ch(x, chk ^ 1))
            fa[ch(x, chk ^ 1)] = y;

        ch(x, chk ^ 1) = y;
        fa[y] = x;
        fa[x] = z;

        if (z)
            ch(z, y == ch(z, 1)) = x;

        Maintain(y);
        Maintain(x);
    }
    void Splay(int x) {
        for (int f = fa[x]; f = fa[x], f; Rotate(x))
            if (fa[f])
                Rotate(Get(f) == Get(x) ? f : x);

        rt = x;
    }
    void Insert(int k) {
        if (!rt) {
            val[++ tot] = k;
            cnt[tot] ++;
            rt = tot;
            Maintain(rt);
            return;
        }

        int cur = rt, f = 0;

        while (1) {
            if (val[cur] == k) {
                cnt[cur] ++;
                Maintain(cur);
                Maintain(f);
                Splay(cur);
                break;
            }

            f = cur;
            cur = ch(cur, val[cur] < k);

            if (!cur) {
                val[++ tot] = k;
                cnt[tot] ++;
                fa[tot] = f;
                ch(f, val[f] < k) = tot;
                Maintain(tot);
                Maintain(f);
                Splay(tot);
                break;
            }
        }
    }
    int Rank(int k) { // 给值求排名
        int res = 0, cur = rt;

        while (1) {
            if (k < val[cur])
                cur = ch(cur, 0);
            else {
                res += sz[ch(cur, 0)];

                if (k == val[cur]) {
                    Splay(cur);
                    return res + 1;
                }

                res += cnt[cur];
                cur = ch(cur, 1);
            }
        }
    }
    int Kth(int k) { // 给排名求值
        int cur = rt;

        while (1) {
            if (ch(cur, 0) && k <= sz[ch(cur, 0)])
                cur = ch(cur, 0);
            else {
                k -= cnt[cur] + sz[ch(cur, 0)];

                if (k <= 0) {
                    Splay(cur);
                    return val[cur];
                }

                cur = ch(cur, 1);
            }
        }
    }
    int Pre() {
        int cur = ch(rt, 0);

        if (!cur)
            return cur;

        while (ch(cur, 1))
            cur = ch(cur, 1);

        Splay(cur);
        return cur;
    }
    int Nxt() {
        int cur = ch(rt, 1);

        if (!cur)
            return cur;

        while (ch(cur, 0))
            cur = ch(cur, 0);

        Splay(cur);
        return cur;
    }
    void Del(int k) {
        Rank(k);

        if (cnt[rt] > 1) {
            cnt[rt] --;
            Maintain(rt);
            return;
        }

        if (!ch(rt, 0) && !ch(rt, 1)) {
            Clear(rt);
            rt = 0;
            return;
        }

        if (!ch(rt, 0)) {
            int cur = rt;
            rt = ch(rt, 1);
            fa[rt] = 0;
            Clear(cur);
            return;
        }

        if (!ch(rt, 1)) {
            int cur = rt;
            rt = ch(rt, 0);
            fa[rt] = 0;
            Clear(cur);
            return;
        }

        int cur = rt;
        int x = Pre();
        fa[ch(cur, 1)] = x;
        ch(x, 1) = ch(cur, 1);
        Clear(cur);
        Maintain(rt);
    }
} SplayTree;

int main() {
    //freopen("Splay.in","r",stdin);
    int n;
    scanf("%d", &n);

    for (int i = 1, x, opt; i <= n; i ++) {
        scanf("%d%d", &opt, &x);

        if (opt == 1)
            SplayTree.Insert(x);
        else if (opt == 2)
            SplayTree.Del(x);
        else if (opt == 3)
            printf("%d\n", SplayTree.Rank(x));
        else if (opt == 4)
            printf("%d\n", SplayTree.Kth(x));
        else if (opt == 5)
            SplayTree.Insert(x), printf("%d\n", val[SplayTree.Pre()]), SplayTree.Del(x);
        else if (opt == 6)
            SplayTree.Insert(x), printf("%d\n", val[SplayTree.Nxt()]), SplayTree.Del(x);
    }

    return 0;
}

后记

要是单纯写个平衡树，打死我我都不写 \(\text{Splay}\)（误）

还是推荐写 \(\text{FHQ-Treap}\)，好写好调。

不过，既然是平衡树，肯定都不是那么容易。