投稿
  1. 高性能架构探索首页
  2. C/C++

Splay

admin • • C/C++ • 阅读 178

前置芝士

熟练掌握二叉排序树的操作，了解 (Treap) 的左旋和右旋。

引言

(Treap) 巧妙地使用随机数，解决了二叉查找树保持平衡的问题。但随机数的不稳定，导致它在极小概率的情况下不能保持树的平衡。故我们需要一种更加稳定的数据结构（虽然它不是很好写）。

正文

(Splay) ，又名分裂树，是一种二叉排序树，它能在 (O(log_n)) 内完成插入、查找和删除操作。它由丹尼尔·斯立特 (Daniel Sleator) 和 罗伯特·恩卓·塔扬 (Robert Endre Tarjan) 在1985年发明的。1

(Splay) 的变量

(Splay) 的每个节点 (x) 有如下七种变量：
(val_x) : 该节点的值。
(siz_x) : 该节点的子树包含的节点数量；
(sons_{x, 0}、sons_{x, 1}): 该节点的左右子节点；
(fa_x) : 该节点的父亲节点；
(num_x) : (val_x) 的数量；

具体操作

初始化节点

即将该节点上述5个变量的值清空。

void init (int x) {
    fa[x] = siz[x] = num[x] = val[x] = sons[x][0] = sons[x][1] = 0;
    return ;
}

更新节点

更新该节点的子树包含的节点数（ (siz) 数组）。

void pushup (int x) {
    siz[x] = siz[sons[x][0]] + siz[sons[x][1]] + num[x];
    return ;
}

判断节点与父亲的关系

int get (int x) {
    return sons[fa[x]][1] == x;
}

连接节点

设要将 (x) 连接到 (y) 的 (z) 儿子上（0为左儿子，1为右儿子，下同）。

void link (int x, int y, int z) {
    if (x)
        fa[x] = y;
    if (y)
        sons[y][z] = x;
    return ;
}

旋转

此处的旋转和 (Treap) 中的旋转有略微的不同。(Treap) 中的旋转是将当前节点挪至其原位置的左儿子或右儿子中，而 (Splay) 的旋转是将当前节点上移，但旋转的过程大致相同。
设 (f) 为当前节点x的父亲，(ff) 为 (f) 的父亲，(d1) 为 (f) 与 (x) 的关系（左儿子为0，右儿子为1），(d2) 为 (ff) 与 (f) 的关系。先将 (x) 的 (d1) ^ 1儿子连接到 (f) 点的 (d1) 儿子，再将 (ff) 连接到 (f) 的 (d1) ^ 1 儿子上，最后将已经移至原 (f) 位置的 (x) 点连接到 (ff) 点的 (d2) 儿子上。

Splay

这是笔者在学习 (Splay) 时自己手绘的上旋步骤，可以方便读者更好地理解 (Splay) 的上旋操作。

void rotate (int x) {
    int f = fa[x], ff = fa[f], d1 = get (x), d2 = get (f);
    link (sons[x][d1 ^ 1], f, d1);
    link (f, x, d1 ^ 1);
    link (x, ff, d2);
    pushup (f);
    pushup (x);
    return ;
}

(splay)

(splay) 操作是 (Splay) 平衡树的核心，它保证了在经过插入删除等操作后，树的平衡性和随机性不受到破坏。（这里的 (splay) ，非指数据结构名，而是该数据结构的一种将某节点上旋到规定节点的一种操作。以下用" (Splay) "指数据结构名，" (splay) "指 (Splay) 的连续上旋操作）。
设目前需要上旋的节点为 (x) ，(x) 的父亲节点为 (f) 。现要将该点上旋，分三种情况讨论：

1、(f) 为目标点。此时可以直接上旋；

2、(f) 与 (f) 的父亲节点的关系和 (x) 与 (f) 的关系相同（即 (get(x) = get (f)) ）。此时，先上旋 (f) ，再上旋 (x)；

3、(f) 与 (f) 的父亲节点的关系和 (x) 与 (f) 的关系不同（即 (get(x) ≠ get (f)) ）。此时，连续上旋两次 (x) ；

若模拟上述操作可发现，在使用这种方式进行上旋的时候，树的平衡性并没有遭到破坏，因此 (Splay) 可以随意对树的任意节点使用。无特殊情况下，为了方便操作，一般直接旋到根节点。

void splay (int x, int top = 0) {
    for (int now; (now = fa[x]) && now != top; rotate (x))
        if (fa[now])
            rotate (get (now) == get (x) ? now : x);
    if (!top)
        rt = x;
    return ;
}

求根节点前缀

因为二叉排序树的性质，直接求左子树的最大值即可。

int pre () {
    int now = sons[rt][0];
    while (sons[now][1])
        now = sons[now][1];
    return now;
}

求根节点后继

因为二叉排序树的性质，直接求右子树的最小值即可。

int suc () {
    int now = sons[rt][1];
    while (sons[now][0])
        now = sons[now][0];
    return now;
}

求某数（(x)）的排名

从根节点向下遍历，若 (x) 大于当前节点的值，则在最终返回答案中加上 左子树的节点数 和 当前节点的同值的数，并查询右儿子；若 (x) 小于当前节点的值，则直接查询左儿子。

int find (int x) {
    int now = rt, ret = 0;
    while (1)
        if (x == val[now]) {
            ret += siz[sons[now][0]] + 1;
            splay (now);
            return ret;
        } else if (x < val[now]) {
            now = sons[now][0];
            continue ;
        } else {
            ret += siz[sons[now][0]] + num[now];
            now = sons[now][1];
        }
    return ret;
}

查询某排名的数

和 (Treap) 的操作相同，可以直接查看我在 (Treap) 中的教程。此处不再赘述。

int ranks (int x) {
    int now = rt;
    while (1)
        if (x <= siz[sons[now][0]])
            now = sons[now][0];
        else if (x > siz[sons[now][0]] + num[now]) {
            x -= (siz[sons[now][0]] + num[now]);
            now = sons[now][1];
        } else {
            splay (now);
            return val[now];
        }
}

插入操作

和 (Treap) 中的插入操作几乎相同。但是和 (Treap) 不同的是，不需要使用随机数进行保持平衡，而是在每次插入完成后直接将插入的点 (Splay) 到根节点，以此用一种很暴力的方式来保持树的平衡。

void ins (int x) {
    if (!rt) {
        rt = ++ cnt;
        num[rt] = siz[rt] = 1;
        val[rt] = x;
        return ;
    }
    int now = rt, f = 0;
    while (1) {
        if (val[now] == x) {
            num[now] ++;
            pushup (now);
            pushup (f);
            splay (now);
            return ;
        }
        f = now;
        now = sons[now][val[now] < x];
        if (!now) {
            now = ++ cnt;
            num[now] = siz[now] = 1;
            val[now] = x;
            fa[now] = f;
            sons[f][val[f] < x] = now;
            pushup (f);
            splay (now);
            return ;
        }
    }
    return ;
}

删除操作

首先运行一遍 (find) 函数，不过不是为了寻找排名，而是将需删除的节点移至根节点，方便在删除结点之后的连边操作。其他操作与 (Treap) 相同。

void del (int x) {
    find (x);
    if (num[rt] > 1) {
        num[rt] --;
        pushup (rt);
        return ;
    }
    if (!sons[rt][0] && !sons[rt][1]) {
        init (rt);
        rt = 0;
        return ;
    }
    if (!sons[rt][0] && sons[rt][1]) {
        int t = rt;
        rt = sons[rt][1];
        fa[rt] = 0;
        init (t);
        return ;
    }
    if (sons[rt][0] && !sons[rt][1]) {
        int t = rt;
        rt = sons[rt][0];
        fa[rt] = 0;
        init (t);
        return ;
    }
    if (sons[rt][0] && sons[rt][1]) {
        int p1 = rt, p2 = pre ();
        splay (p2);
        link (sons[p1][1], rt, 1);
        init (p1);
        pushup (rt);
        return ;
    }
}

整体代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int n, m, cnt, rt, sons[N][2], fa[N], val[N], siz[N], num[N];
void init (int x) {
    fa[x] = siz[x] = num[x] = val[x] = sons[x][0] = sons[x][1] = 0;
    return ;
}
int get (int x) {
    return sons[fa[x]][1] == x;
}
void link (int x, int y, int z) {
    if (x)
        fa[x] = y;
    if (y)
        sons[y][z] = x;
    return ;
}
void pushup (int x) {
    siz[x] = siz[sons[x][0]] + siz[sons[x][1]] + num[x];
    return ;
}
void rotate (int x) {
    int f = fa[x], ff = fa[f], d1 = get (x), d2 = get (f);
    link (sons[x][d1 ^ 1], f, d1);
    link (f, x, d1 ^ 1);
    link (x, ff, d2);
    pushup (f);
    pushup (x);
    return ;
}
void splay (int x, int top = 0) {
    for (int now; (now = fa[x]) && now != top; rotate (x))
        if (fa[now])
            rotate (get (now) == get (x) ? now : x);
    if (!top)
        rt = x;
    return ;
}
void ins (int x) {
    if (!rt) {
        rt = ++ cnt;
        num[rt] = siz[rt] = 1;
        val[rt] = x;
        return ;
    }
    int now = rt, f = 0;
    while (1) {
        if (val[now] == x) {
            num[now] ++;
            pushup (now);
            pushup (f);
            splay (now);
            return ;
        }
        f = now;
        now = sons[now][val[now] < x];
        if (!now) {
            now = ++ cnt;
            num[now] = siz[now] = 1;
            val[now] = x;
            fa[now] = f;
            sons[f][val[f] < x] = now;
            pushup (f);
            splay (now);
            return ;
        }
    }
    return ;
}
int find (int x) {
    int now = rt, ret = 0;
    while (1)
        if (x == val[now]) {
            ret += siz[sons[now][0]] + 1;
            splay (now);
            return ret;
        } else if (x < val[now]) {
            now = sons[now][0];
            continue ;
        } else {
            ret += siz[sons[now][0]] + num[now];
            now = sons[now][1];
        }
    return ret;
}
int ranks (int x) {
    int now = rt;
    while (1)
        if (x <= siz[sons[now][0]])
            now = sons[now][0];
        else if (x > siz[sons[now][0]] + num[now]) {
            x -= (siz[sons[now][0]] + num[now]);
            now = sons[now][1];
        } else {
            splay (now);
            return val[now];
        }
}
int pre () {
    int now = sons[rt][0];
    while (sons[now][1])
        now = sons[now][1];
    return now;
}
int suc () {
    int now = sons[rt][1];
    while (sons[now][0])
        now = sons[now][0];
    return now;
}
void del (int x) {
    find (x);
    if (num[rt] > 1) {
        num[rt] --;
        pushup (rt);
        return ;
    }
    if (!sons[rt][0] && !sons[rt][1]) {
        init (rt);
        rt = 0;
        return ;
    }
    if (!sons[rt][0] && sons[rt][1]) {
        int t = rt;
        rt = sons[rt][1];
        fa[rt] = 0;
        init (t);
        return ;
    }
    if (sons[rt][0] && !sons[rt][1]) {
        int t = rt;
        rt = sons[rt][0];
        fa[rt] = 0;
        init (t);
        return ;
    }
    if (sons[rt][0] && sons[rt][1]) {
        int p1 = rt, p2 = pre ();
        splay (p2);
        link (sons[p1][1], rt, 1);
        init (p1);
        pushup (rt);
        return ;
    }
}
int main () {
    scanf ("%d", &n);
    for (int i = 1; i <= n; i ++) {
        int opt, x;
        scanf ("%d%d", &opt, &x);
        if (opt == 1)
            ins (x);
        else if (opt == 2)
            del (x);
        else if (opt == 3)
            printf ("%dn", find (x));
        else if (opt == 4)
            printf ("%dn", ranks (x));
        else if (opt == 5) {
            ins (x);
            printf ("%dn", val[pre ()]);
            del (x);
        } else if (opt == 6) {
            ins (x);
            printf ("%dn", val[suc ()]);
            del (x);
        }
    }
    return 0;
}

References

[1] Sleator, Daniel D.; Tarjan, Robert E., Self-Adjusting Binary Search Trees (PDF), Journal of the ACM, 1985, 32 (3): 652–686

原文链接: https://www.cnblogs.com/HarryHuang2004/p/13219936.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍;

也有高质量的技术群，里面有嵌入式、搜广推等BAT大佬

    Splay

原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/362286

非原创文章文中已经注明原地址，如有侵权，联系删除

关注公众号【高性能架构探索】，第一时间获取最新文章

转载文章受原作者版权保护。转载请注明原作者出处！

赞 (0)
adminadmin
0 0
上一篇 2023年3月2日 下午2:17
下一篇 2023年3月2日 下午2:17

相关推荐