Splay模版:P3369[模版/普通平衡树]

用户7267083

发布于 2022-12-08 14:58:15

2820

发布于 2022-12-08 14:58:15

文章被收录于专栏：sukuna的博客sukuna的博客

Splay模版:P3369[模版/普通平衡树]

于2022年3月30日2022年3月30日由Sukuna发布

题目描述

输出格式

对于操作 3,4,5,6.每行输出一个数，表示对应答案.

splay的定义

伸展树（Splay Tree），也叫分裂树，是一种二叉排序树，它能在 O(logn)内完成插入、查找和删除操作. 它由丹尼尔·斯立特Daniel Sleator 和罗伯特·恩卓·塔扬Robert Endre Tarjan在1985年发明的.

在伸展树上的一般操作都基于伸展操作：假设想要对一个二叉查找树执行一系列的查找操作，为了使整个查找时间更小，被查频率高的那些条目就应当经常处于靠近树根的位置. 于是想到设计一个简单方法：在每次查找之后对树进行重构，把被查找的条目搬移到离树根近一些的地方. 伸展树应运而生：伸展树是一种自调整形式的二叉查找树，它会沿着从某个节点到树根之间的路径，通过一系列的旋转把这个节点搬移到树根去. 它的优势在于不需要记录用于平衡树的冗余信息.

总的来说,伸展树在每一次增改查之后就会把被查询的元素放到根部

数据结构定义

struct splay{
    int ch[2];
    int val;//数值
    int size;//子树大小
    int cnt;//每个节点所含副本数
    int parent;
}splay[N];
int total;
int root;

这里用数组来模拟树,树的节点个数为total,根结点记录在root,那么splay[root]就是根结点,其中每个节点记录本身的值,左子树和右子树信息,每个节点含有副本数量,和这个节点对应子树的大小.

PushOff操作

在每一次对树进行操作的之后都要进行一次pushoff操作,来更新size区域.

void pushup(int node_id){
    int l=splay[node_id].ch[0];
    int r=splay[node_id].ch[1];
    splay[node_id].size=splay[l].size+splay[r].size+splay[node_id].cnt;
}

单旋转操作

每次旋转操作其实上都是将父亲和儿子进行交换,就是x和x.parent进行交换.

void rotate (int x) {
    int fa = splay[x].parent;
    int Gfa = splay[fa].parent;
    int k = (splay[fa].ch[1]==x);
    int g = (splay[Gfa].ch[1]==fa);
    splay[Gfa].ch[g]=x;
    splay[x].parent=Gfa;
    
    splay[fa].ch[k]=splay[x].ch[k^1];
    splay[splay[x].ch[k^1]].parent=fa;
    
    splay[x].ch[k ^ 1]=fa;
    splay[fa].parent=x;
    pushup(fa);
    pushup(x);
}

交换需要借助父亲的父亲,也就是祖父的力量,首先我们先记录x是fa=x.parent左儿子还是右儿子,结果记为k(1:右儿子,0:左儿子),然后记录fa是Gfa=fa.parent的左儿子还是右儿子,计为g(1:右儿子,0:左儿子).

下面为了叙述方便,我们定义一个奇怪的定义,就是外孙,比如说x是fa的左儿子,那么x的右儿子就是fa的外孙;x是fa的右儿子,那么x的左儿子就是x的外孙.

这个时候有三个点,分别是父亲、祖父和儿子,分别代表Gfa、fa和x. 首先第一步就是祖父的儿子从fa替换成x. 第二步就是父亲的儿子从x替换成x的外孙. 第三步就是原本x的外孙的位子由fa占领.

这个是最难的一部分,还是希望还是可以记住执行的顺序,一个是替换祖父的儿子,然后替换父亲的儿子,然后替换儿子的儿子,这是替换顺序,替换成什么可以记下来,分别是儿子,父亲的外孙和父亲.

实在太难怎么办?把旋转的画法画下来带进考场,反正CSP是开卷orz.

splay操作

我们需要做到的就是增改查的节点送到根结点,那么我们可以设计一个函数,这个函数叫做splayed(x,y).目的就是把编号为x的节点送到y的儿子处.所以说用形式语言我们可以这么写

.就是x的父亲为y.

说句题外话,因为节点是从1开始编号的,所以说有且只有一个结点就是根结点的父亲为0.所以说想把数送到根结点需要执行splayed(x,0).

我们在之前还是知道rotate操作可以把一个数在树中的层数-1.这就好办,我们每次都做rorate操作,直到这个数的父亲是y为止.但是学过AVL的旋转我们知道,旋转可以分为单旋和双旋的,其实这个也是一样的.

判断究竟是一字旋转还是之字旋转其实就判断(splay[Gfa].ch[0] == fa) ^ (splay[fa].ch[0] == x).这个异或可以判断儿子情况是不是一样的.

但是有一个问题就是,我们不知道旋转能不能做,因为在rotate函数中,我们充分相信fa和Gfa都是有意义的.所以说在splay操作调用rotate时我们要保证x是有意义的.

由于旋转是两个两个来做的,首先第一步,我们判断我们能不能做两次旋转操作,然后判断我们能不能做一次操作.判断的方法在代码中有说.

//将x旋转到goal的儿子
void splayed ( int x, int goal ) {
    while (splay[x].parent != goal) {
        int fa = splay[x].parent, Gfa = splay[fa].parent;
        //能做两次吗?
        if (Gfa!= goal)
            ((splay[Gfa].ch[0] == fa) ^ (splay[fa].ch[0] == x)) ? rotate(x) : rotate (fa);
        //splay[x].parent != goal 判断能做一次旋转操作吗?
        rotate (x);
    }
    //如果goal为0,代表要改根结点
    if (!goal)
        root=x;
}

insert操作

解决了最核心的旋转问题,我们可以专注搞增删改查了.

void insert(int x) {
    int u=root, fa=0;
    while (u && splay[u].val!=x) {
        fa = u;
        u=splay[u].ch[x>splay[u].val];
    }
    if (u)
        splay[u].cnt ++;
    else {
        u=++total;
        if (fa)
            splay[fa].ch[x > splay[fa].val] = u;
        splay[u].ch[0] = splay[u].ch[1] = 0;
        splay[u].val = x;
        splay[u].parent = fa;
        splay[u].cnt = splay[u].size = 1;
    }
    splayed(u,0);
}

我们注意到有一个前提,这个前提就是这个树是一个BST,也就是说我们查找可以根据BST性质来进行查找,查找的目的就是找到合适的地方来处理.

如果查找到的地方是空,说明之前没有插入过值为x的结点,如果找到了就增加引用数即可.

find操作

insert操作其实就是基于find操作执行的,也是满足BST性质,如果你忘了我就告诉你一下,小的往左,大的往右,在空和找到了的地方下停下来.

void find(int x){
    if (!root)
            return;
        int u=root;
        while (splay[u].ch[x > splay[u].val] && x!=splay[u].val)
            u=splay[u].ch[x > splay[u].val];
        splayed (u,0);
}

前序和后序操作

我们首先调用find(x)函数,find(x)函数会帮我找到x并且把x放到根.我们假设x存在,那么x是根结点.那么就很好做,前序结点就是先往左然后一直往右,后序结点就是先往右然后一直往左.

但是万一x没找到呢?也不要紧,那么我们可以知道查询的结果往往是最接近x的结果,所以说我们可以假设,如果找的是前序结点并且当前根结点小于x,那就是根结点.同样的,如果要找后序结点并且根结点大于x,那就是根结点.如果不对的话,那我们还是按照x存在的方法寻找.

int PreSuf (int x, int f) {
    find (x);
    if (splay[root].val>x&&f)
        return root;
    if (splay[root].val < x && !f)
        return root;
    int u = splay[root].ch[f];
    if (!u)
        return 0;
    while (splay[u].ch[f ^ 1])
        u =splay[u].ch[f ^ 1];
    return u;
}

Delete操作

void Delete (int x) {
    int pre = PreSuf(x,0);
    int suf = PreSuf(x,1);
    splayed(pre,0);
    splayed(suf,pre);
    int u = splay[suf].ch[0];
    if (splay[u].cnt>1) {
        splay[u].cnt--;
        splayed ( u, 0 );
    }
    else{
        splay[suf].ch[0] = 0;
    }
}

我们求得x的前序和后序,然后把前序放到根,后序在根的右儿子,这个时候比x前序还小的在根结点左儿子,比x后序还大的在根结点的右儿子的右儿子,x就在根结点的右儿子的左儿子.然后比较cnt,删除即可.

第k个操作

之前的size派上用场了!因为左子树的size就是比x小的个数,右子树的size是比x大的个数.那么我们可以选择往左还是往右,判断的依据是

.如果往右的话,k要减去left.size+1,因为我们不考虑最小的left.size+1个元素了,你现在是k-left.size+1小的元素了.以此类推.

int findkth (int x) {
    if (splay[root].size<x)
        return -1;
    int u=root;
    while (1) {
        if ( x <= splay[splay[u].ch[0]].size )
            u = splay[u].ch[0];
        else if ( x <= splay[u].cnt + splay[splay[u].ch[0]].size )
                return u;
            else {
                x -= ( splay[splay[u].ch[0]].size + splay[u].cnt );
                u = splay[u].ch[1];
            }
    }
}

插入INF和-INF

INF和-INF可以作为哨兵,如果有哨兵存在，那么这些点永远都不会是死在最前面或者死的时候垫在最下面，就帮助我们少考虑很多边界，我昨天没有加哨兵，不停地补刀做手术，还是千疮百孔，病很多都是并发症，医不过来，加了个哨兵，自己就好了

总的代码

#include <stdio.h>
#include <stdlib.h>
#define N 1000005
#define INF 0x7f7f7f7f
struct splay{
    int ch[2];
    int val;//数值
    int size;//子树大小
    int cnt;//每个节点所含副本数
    int parent;
}splay[N];
int total;
int root;
int na;
void pushup(int node_id){
    int l=splay[node_id].ch[0];
    int r=splay[node_id].ch[1];
    splay[node_id].size=splay[l].size+splay[r].size+splay[node_id].cnt;
}

void rotate (int x) {
    int fa = splay[x].parent;
    int Gfa = splay[fa].parent;
    int k = (splay[fa].ch[1]== x);
    splay[Gfa].ch[splay[Gfa].ch[1]==fa] = x;
    splay[x].parent = Gfa;
    splay[fa].ch[k] = splay[x].ch[k^1];
    splay[splay[x].ch[k^1]].parent= fa;
    splay[x].ch[k ^ 1] = fa;
    splay[fa].parent = x;
    pushup(fa);
    pushup(x);
}
//将x旋转到goal的儿子
void splayed ( int x, int goal ) {
    while (splay[x].parent != goal) {
        int fa = splay[x].parent, Gfa = splay[fa].parent;
        if (Gfa!= goal )
            ( (splay[Gfa].ch[0] == fa) ^ (splay[fa].ch[0] == x)) ? rotate(x) : rotate (fa);
        rotate (x);
    }
    if (!goal)
        root=x;
}
void insert(int x) {
    int u=root, fa=0;
    while (u && splay[u].val!=x) {
        fa = u;
        u=splay[u].ch[x>splay[u].val];
    }
    if (u)
        splay[u].cnt ++;
    else {
        u=++total;
        if (fa)
            splay[fa].ch[x > splay[fa].val] = u;
        splay[u].ch[0] = splay[u].ch[1] = 0;
        splay[u].val = x;
        splay[u].parent = fa;
        splay[u].cnt = splay[u].size = 1;
    }
    splayed(u,0);
}

void find(int x){
    if (!root)
            return;
        int u=root;
        while (splay[u].ch[x > splay[u].val] && x!=splay[u].val)
            u=splay[u].ch[x > splay[u].val];
        splayed (u,0);
}
int PreSuf (int x, int f) {
    find (x);
    if (splay[root].val>x&&f)
        return root;
    if (splay[root].val < x && !f)
        return root;
    int u = splay[root].ch[f];
    if (!u)
        return 0;
    while (splay[u].ch[f ^ 1])
        u =splay[u].ch[f ^ 1];
    return u;
}

void Delete (int x) {
    int pre = PreSuf(x,0);
    int suf = PreSuf(x,1);
    splayed(pre,0);
    splayed(suf,pre);
    int u = splay[suf].ch[0];
    if (splay[u].cnt>1) {
        splay[u].cnt--;
        splayed ( u, 0 );
    }
    else{
        splay[suf].ch[0] = 0;
    }
        
}

int findkth (int x) {
    if (splay[root].size<x)
        return -1;
    int u=root;
    while (1) {
        if ( x <= splay[splay[u].ch[0]].size )
            u = splay[u].ch[0];
        else if ( x <= splay[u].cnt + splay[splay[u].ch[0]].size )
                return u;
            else {
                x -= ( splay[splay[u].ch[0]].size + splay[u].cnt );
                u = splay[u].ch[1];
            }
    }
}
void build(){
    insert(INF);
    insert(-INF);
}
int main(){
    int n;
    build();
    scanf("%d",&n);
    int opt,x;
    int u;
    while(n--){
        scanf("%d %d",&opt,&x);
        switch (opt) {
            case 1:
                insert(x);
                break;
            case 2:
                Delete(x);
                break;
            case 3:
                find(x);
                printf("%d\n",splay[splay[root].ch[0]].size);
                break;
            case 4:
                u=findkth(x+1);
                printf("%d\n",splay[u].val);
                break;
            case 5:
                u=PreSuf(x, 0);
                printf("%d\n",splay[u].val);
                break;
            case 6:
                u=PreSuf(x, 1);
                printf("%d\n",splay[u].val);
                break;
            default:
                break;
        }
    }
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2022年3月30日，如有侵权请联系 cloudcommunity@tencent.com 删除

insert