首页 > 其他分享 >splay 树

splay 树

时间：2024-07-10 13:09:13浏览次数：2  
标签：rt ch int tr splay fa nw

Splay树

感谢OI-WIKI讲解

1.定义

splay是一种平衡二叉搜索树，由splay操作使时间复杂度O（nlogn）

2.变量

rt根节点编号

tot节点个数计数

tr[].fa父节点编号

tr[].ch[0/1]左右儿子编号

tr[].val该点记录的权值

tr[].cnt该点记录的权值出现次数

tr[].sz子树大小

int rt,tot;
struct node{
    int fa,ch[2],val,cnt,sz;
    void clear(){
        //delete the node
        fa=ch[0]=ch[1]=val=sz=cnt=0;
    }
    node(){
        fa=ch[0]=ch[1]=val=sz=cnt=0;
    }
}tr[200005];

3基本操作

1.maintain，即更新子树大小为当前点cnt与左右节点sz之和。代码如下

2.clear：销毁节点，即清零，代码如上

3.get：判断是否为右儿子，代码如下

void maintain(int x){
    //push_up
    tr[x].sz=tr[tr[x].ch[0]].sz+tr[tr[x].ch[1]].sz+tr[x].cnt;
}
int get(int x){
    //is the right son
    return x==tr[tr[x].fa].ch[1];
}

4.rotate操作

做父亲的父亲，自己多了一个儿子，父亲少了一个儿子，将一儿子过继给父亲即可

做父亲的父亲，父亲认你当父亲，你就要认爷爷当父亲

void rotate(int x){
    int y=tr[x].fa,z=tr[y].fa,ck=get(x),cy=get(y);
    //get its son to the father's son
    tr[y].ch[ck]=tr[x].ch[ck^1];
    if(tr[x].ch[ck^1])tr[tr[x].ch[ck^1]].fa=y;
    //be your father's dad
    tr[x].ch[ck^1]=y;
    tr[y].fa=x;
    //be your grandfather's son
    tr[x].fa=z;
    if(z)tr[z].ch[cy]=x;
    //renew the information
    maintain(x);
    maintain(y);
}

 

5.splay操作

当所有人的祖先（根节点）

1：父亲是根

rotate一下即可做根

 

2.你和父亲都是左儿子或都是右儿子

先rotate父亲，做爷爷的父亲，然后自己再做父亲的父亲

 

 

3.一个是左儿子，一个是右儿子

rotate两次，即可做爷爷。

void splay(int x){
    for(;tr[x].fa;rotate(x)){
        int f=tr[x].fa;
        if(tr[f].fa){
            if(get(x)==get(f))rotate(f);
            //zig-zag
            else rotate(x);
            //zig-zig
        }else{
            //only zig
        }
    }
    rt=x;
    //splay to root
}

6.insert操作

以二叉搜索树性质为基础，小了查左儿子，大了查右儿子

相等个数加一，不等新建节点

最后更新sz

void ins(int k){
    if(!rt){
        tr[++tot].val=k;
        tr[tot].cnt++;
        rt=tot;
        maintain(rt);    
        //the tree is empty so just add it as root
        return ;
    }
    int c=rt,f=0;
    //c refers to now,while f refers to father
    while(1){
        if(tr[c].val==k){
            //find it
            tr[c].cnt++;
            maintain(c);
            //update value directly
            maintain(f);
            //to avoid zig-zig make father's data unuseable father should be maintained
            splay(c);
            break;
        }
        f=c;
        c=tr[c].ch[k>tr[c].val];
        //update the node index and faher index
        if(!c){
            tr[++tot].fa=f;
            tr[tot].val=k;
            tr[tot].cnt=1;
            tr[f].ch[k>tr[f].val]=tot;
            c=tot;
            //make a new node
            maintain(c);
            maintain(f);
            //to avoid zig-zig make father's data unuseable father should be maintained
            splay(c);
            //to make time ok,need to splay everynode up
            //can't find it
            break;
        }
    }
}

7.rank查询

查询到节点，前面左儿子大小之和+1就是rank

int rk(int k){
    int ans=0,nw=rt;
    //ans means the rank
    while(1){
        if(k<tr[nw].val){
            nw=tr[nw].ch[0];
            //to left
        }else{
            ans+=tr[tr[nw].ch[0]].sz;
            if(!nw)return ans+1;//cant find
            if(tr[nw].val==k){
                splay(nw);
                //splay to root
                return ans+1;
                //add itself
            }
            ans+=tr[nw].cnt;
            nw=tr[nw].ch[1];
            //to right
        }
    }
}

8.查询rank为k的数

如果k小于左子树sz就找左子树，否则如果剩下的k小于等于当前节点cnt就是当前节点，否则在右子树。

int kth(int k){
    int nw=rt;
    while(1){
        if(tr[nw].ch[0]&&k<=tr[tr[nw].ch[0]].sz){
            nw=tr[nw].ch[0];
            //k is contained in the left subtree
        }else{
            k-=tr[tr[nw].ch[0]].sz+tr[nw].cnt;
            if(k<=0){
                //k is in the root
                splay(nw);
                return tr[nw].val;
                //splay and answer
            }
            nw=tr[nw].ch[1];
            //to right
        }
    }
}

 

9.合并两个值域不相交的splay（用于删除节点）

将之与较小的树中最大的数splay到根，另一棵树作右子树

    int nw=rt,lst=pre();//pre of root
    tr[tr[nw].ch[1]].fa=lst;
    tr[lst].ch[1]=tr[nw].ch[1];
    //get right son
    tr[nw].clear();
    maintain(rt);

10.删除节点

先splay到根，cnt>1就减少1，如果该树为空则直接删，如果仅有一子树则将根传给该子树，否则合并两棵子树

void del(int k){
    rk(k);
    //splay to root
    if(tr[rt].cnt>1){
        tr[rt].cnt--;
        //have more than 1 elements
        maintain(rt);
        //recalculate
        return ;
    }
    if(tr[rt].ch[0]+tr[rt].ch[1]==0){
        //have no son
        tr[rt].clear();
        rt=0;
        //be an empty tree
        return ;
    }
    if(tr[rt].ch[0]==0){
        //to left son
        int tmp=rt;
        rt=tr[rt].ch[1];
        tr[rt].fa=0;
        //root dont have dad
        tr[tmp].clear();
        //clear the node
        return ;
    }
    if(tr[rt].ch[1]==0){
        //to right son
        int tmp=rt;
        rt=tr[rt].ch[0];
        tr[rt].fa=0;
        //root dont have dad
        tr[tmp].clear();
        //clear the node
        return ;
    }
    int nw=rt,lst=pre();//pre of root
    tr[tr[nw].ch[1]].fa=lst;
    tr[lst].ch[1]=tr[nw].ch[1];
    //get right son
    tr[nw].clear();
    maintain(rt);
}

11.查前驱

先插入，前驱即为左子树最靠右的点，之后删除

int pre(){
    //first insert,and splay to root
    int nw=tr[rt].ch[0];
    if(!nw)return nw;
    //it's the smallest number in the tree
    while(tr[nw].ch[1])nw=tr[nw].ch[1];
    //to the right subtree
    splay(nw);
    //splay to root
    return nw;
}
int ask_pre(int x){
    ins(x);
    int ans=tr[pre()].val;
    del(x);
    return ans;
}

12.查后继

先插入，后继即为右子树最靠左的点，之后删除

int nxt(){
    //first insert,and splay to root
    int nw=tr[rt].ch[1];
    if(!nw)return nw;
    //it's the largest number in the tree
    while(tr[nw].ch[0])nw=tr[nw].ch[0];
    //to the right subtree
    splay(nw);
    //splay to root
    return nw;
}
int ask_nxt(int x){
    ins(x);
    int ans=tr[nxt()].val;
    del(x);
    return ans;
}

 

13.代码（有注释）

#include <bits/stdc++.h>
using namespace std;
int rt,tot;
struct node{
    int fa,ch[2],val,cnt,sz;
    void clear(){
        //delete the node
        fa=ch[0]=ch[1]=val=sz=cnt=0;
    }
    node(){
        fa=ch[0]=ch[1]=val=sz=cnt=0;
    }
}tr[200005];
void maintain(int x){
    //push_up
    tr[x].sz=tr[tr[x].ch[0]].sz+tr[tr[x].ch[1]].sz+tr[x].cnt;
}
int get(int x){
    //is the right son
    return x==tr[tr[x].fa].ch[1];
}
void rotate(int x){
    int y=tr[x].fa,z=tr[y].fa,ck=get(x),cy=get(y);
    //get its son to the father's son
    tr[y].ch[ck]=tr[x].ch[ck^1];
    if(tr[x].ch[ck^1])tr[tr[x].ch[ck^1]].fa=y;
    //be your father's dad
    tr[x].ch[ck^1]=y;
    tr[y].fa=x;
    //be your grandfather's son
    tr[x].fa=z;
    if(z)tr[z].ch[cy]=x;
    //renew the information
    maintain(x);
    maintain(y);
}
void splay(int x){
    for(;tr[x].fa;rotate(x)){
        int f=tr[x].fa;
        if(tr[f].fa){
            if(get(x)==get(f))rotate(f);
            //zig-zag
            else rotate(x);
            //zig-zig
        }else{
            //only zig
        }
    }
    rt=x;
    //splay to root
}
void ins(int k){
    if(!rt){
        tr[++tot].val=k;
        tr[tot].cnt++;
        rt=tot;
        maintain(rt);    
        //the tree is empty so just add it as root
        return ;
    }
    int c=rt,f=0;
    //c refers to now,while f refers to father
    while(1){
        if(tr[c].val==k){
            //find it
            tr[c].cnt++;
            maintain(c);
            //update value directly
            maintain(f);
            //to avoid zig-zig make father's data unuseable father should be maintained
            splay(c);
            break;
        }
        f=c;
        c=tr[c].ch[k>tr[c].val];
        //update the node index and faher index
        if(!c){
            tr[++tot].fa=f;
            tr[tot].val=k;
            tr[tot].cnt=1;
            tr[f].ch[k>tr[f].val]=tot;
            c=tot;
            //make a new node
            maintain(c);
            maintain(f);
            //to avoid zig-zig make father's data unuseable father should be maintained
            splay(c);
            //to make time ok,need to splay everynode up
            //can't find it
            break;
        }
    }
}
int rk(int k){
    int ans=0,nw=rt;
    //ans means the rank
    while(1){
        if(k<tr[nw].val){
            nw=tr[nw].ch[0];
            //to left
        }else{
            ans+=tr[tr[nw].ch[0]].sz;
            if(!nw)return ans+1;//cant find
            if(tr[nw].val==k){
                splay(nw);
                //splay to root
                return ans+1;
                //add itself
            }
            ans+=tr[nw].cnt;
            nw=tr[nw].ch[1];
            //to right
        }
    }
}
int kth(int k){
    int nw=rt;
    while(1){
        if(tr[nw].ch[0]&&k<=tr[tr[nw].ch[0]].sz){
            nw=tr[nw].ch[0];
            //k is contained in the left subtree
        }else{
            k-=tr[tr[nw].ch[0]].sz+tr[nw].cnt;
            if(k<=0){
                //k is in the root
                splay(nw);
                return tr[nw].val;
                //splay and answer
            }
            nw=tr[nw].ch[1];
            //to right
        }
    }
}
int pre(){
    //first insert,and splay to root
    int nw=tr[rt].ch[0];
    if(!nw)return nw;
    //it's the smallest number in the tree
    while(tr[nw].ch[1])nw=tr[nw].ch[1];
    //to the right subtree
    splay(nw);
    //splay to root
    return nw;
}
int nxt(){
    //first insert,and splay to root
    int nw=tr[rt].ch[1];
    if(!nw)return nw;
    //it's the largest number in the tree
    while(tr[nw].ch[0])nw=tr[nw].ch[0];
    //to the right subtree
    splay(nw);
    //splay to root
    return nw;
}
void del(int k){
    rk(k);
    //splay to root
    if(tr[rt].cnt>1){
        tr[rt].cnt--;
        //have more than 1 elements
        maintain(rt);
        //recalculate
        return ;
    }
    if(tr[rt].ch[0]+tr[rt].ch[1]==0){
        //have no son
        tr[rt].clear();
        rt=0;
        //be an empty tree
        return ;
    }
    if(tr[rt].ch[0]==0){
        //to left son
        int tmp=rt;
        rt=tr[rt].ch[1];
        tr[rt].fa=0;
        //root dont have dad
        tr[tmp].clear();
        //clear the node
        return ;
    }
    if(tr[rt].ch[1]==0){
        //to right son
        int tmp=rt;
        rt=tr[rt].ch[0];
        tr[rt].fa=0;
        //root dont have dad
        tr[tmp].clear();
        //clear the node
        return ;
    }
    int nw=rt,lst=pre();//pre of root
    tr[tr[nw].ch[1]].fa=lst;
    tr[lst].ch[1]=tr[nw].ch[1];
    //get right son
    tr[nw].clear();
    maintain(rt);
}
int ask_pre(int x){
    ins(x);
    int ans=tr[pre()].val;
    del(x);
    return ans;
}
int ask_nxt(int x){
    ins(x);
    int ans=tr[nxt()].val;
    del(x);
    return ans;
}
int main(){
    int n;
    cin>>n;
    while(n--){
        int op;
        cin>>op;
        if(op==1){
            int x;
            cin>>x;
            ins(x);
        }else if(op==2){
            int x;
            cin>>x;
            del(x);
        }else if(op==3){
            int x;
            cin>>x;
            cout<<rk(x)<<'\n';
        }else if(op==4){
            int k;
            cin>>k;
            cout<<kth(k)<<'\n';
        }else if(op==5){
            int x;
            cin>>x;
            cout<<ask_pre(x)<<'\n';
        }else{
            int x;
            cin>>x;
            cout<<ask_nxt(x)<<'\n';
        }
    }
}

 

14.代码（无注释）

#include <bits/stdc++.h>
using namespace std;
int rt,tot;
struct node{
    int fa,ch[2],val,cnt,sz;
    void clear(){
        fa=ch[0]=ch[1]=val=sz=cnt=0;
    }
    node(){
        fa=ch[0]=ch[1]=val=sz=cnt=0;
    }
}tr[200005];
void maintain(int x){
    tr[x].sz=tr[tr[x].ch[0]].sz+tr[tr[x].ch[1]].sz+tr[x].cnt;
}
int get(int x){
    return x==tr[tr[x].fa].ch[1];
}
void rotate(int x){
    int y=tr[x].fa,z=tr[y].fa,ck=get(x),cy=get(y);
    tr[y].ch[ck]=tr[x].ch[ck^1];
    if(tr[x].ch[ck^1])tr[tr[x].ch[ck^1]].fa=y;
    tr[x].ch[ck^1]=y;
    tr[y].fa=x;
    tr[x].fa=z;
    if(z)tr[z].ch[cy]=x;
    maintain(x);
    maintain(y);
}
void splay(int x){
    for(;tr[x].fa;rotate(x)){
        int f=tr[x].fa;
        if(tr[f].fa){
            if(get(x)==get(f))rotate(f);
            else rotate(x);
        }
    }
    rt=x;
}
void ins(int k){
    if(!rt){
        tr[++tot].val=k;
        tr[tot].cnt++;
        rt=tot;
        maintain(rt);    
        return ;
    }
    int c=rt,f=0;
    while(1){
        if(tr[c].val==k){
            tr[c].cnt++;
            maintain(c);
            maintain(f);
            splay(c);
            break;
        }
        f=c;
        c=tr[c].ch[k>tr[c].val];
        if(!c){
            tr[++tot].fa=f;
            tr[tot].val=k;
            tr[tot].cnt=1;
            tr[f].ch[k>tr[f].val]=tot;
            c=tot;
            maintain(c);
            maintain(f);
            splay(c);
            break;
        }
    }
}
int rk(int k){
    int ans=0,nw=rt;
    while(1){
        if(k<tr[nw].val){
            nw=tr[nw].ch[0];
        }else{
            ans+=tr[tr[nw].ch[0]].sz;
            if(!nw)return ans+1;
            if(tr[nw].val==k){
                splay(nw);
                return ans+1;
            }
            ans+=tr[nw].cnt;
            nw=tr[nw].ch[1];
        }
    }
}
int kth(int k){
    int nw=rt;
    while(1){
        if(tr[nw].ch[0]&&k<=tr[tr[nw].ch[0]].sz){
            nw=tr[nw].ch[0];
        }else{
            k-=tr[tr[nw].ch[0]].sz+tr[nw].cnt;
            if(k<=0){
                splay(nw);
                return tr[nw].val;
            }
            nw=tr[nw].ch[1];
        }
    }
}
int pre(){
    int nw=tr[rt].ch[0];
    if(!nw)return nw;
    while(tr[nw].ch[1])nw=tr[nw].ch[1];
    splay(nw);
    return nw;
}
int nxt(){
    int nw=tr[rt].ch[1];
    if(!nw)return nw;
    while(tr[nw].ch[0])nw=tr[nw].ch[0];
    splay(nw);
    return nw;
}
void del(int k){
    rk(k);
    if(tr[rt].cnt>1){
        tr[rt].cnt--;
        maintain(rt);
        return ;
    }
    if(tr[rt].ch[0]+tr[rt].ch[1]==0){
        tr[rt].clear();
        rt=0;
        return ;
    }
    if(tr[rt].ch[0]==0){
        int tmp=rt;
        rt=tr[rt].ch[1];
        tr[rt].fa=0;
        tr[tmp].clear();
        return ;
    }
    if(tr[rt].ch[1]==0){
        int tmp=rt;
        rt=tr[rt].ch[0];
        tr[rt].fa=0;
        tr[tmp].clear();
        return ;
    }
    int nw=rt,lst=pre();
    tr[tr[nw].ch[1]].fa=lst;
    tr[lst].ch[1]=tr[nw].ch[1];
    tr[nw].clear();
    maintain(rt);
}
int ask_pre(int x){
    ins(x);
    int ans=tr[pre()].val;
    del(x);
    return ans;
}
int ask_nxt(int x){
    ins(x);
    int ans=tr[nxt()].val;
    del(x);
    return ans;
}
int main(){
    int n;
    cin>>n;
    while(n--){
        int op;
        cin>>op;
        if(op==1){
            int x;
            cin>>x;
            ins(x);
        }else if(op==2){
            int x;
            cin>>x;
            del(x);
        }else if(op==3){
            int x;
            cin>>x;
            cout<<rk(x)<<'\n';
        }else if(op==4){
            int k;
            cin>>k;
            cout<<kth(k)<<'\n';
        }else if(op==5){
            int x;
            cin>>x;
            cout<<ask_pre(x)<<'\n';
        }else{
            int x;
            cin>>x;
            cout<<ask_nxt(x)<<'\n';
        }
    }
}

 

标签：rt,ch,int,tr,splay,fa,nw
From： https://www.cnblogs.com/rabbit-fan/p/18293829

相关文章

  • display grid的基本用法
    display:grid是CSS网格布局的一部分，它用于创建一个基于网格的布局系统。网格布局允许开发者通过定义行和列来更精确地控制元素的位置和对齐。以下是display:grid的一些基本用法：一、基本用法<divclass="grid-container"><divclass="grid-item">1</div><divclass="g......
  • 2024-07-07 如何把ipad当作windows副屏使用 ==》 通过软件dute display和数据线连接
    windows：进入dutedisplay官网https://www.duetdisplay.com/zh#download，下载并安装ipad：在苹果应用商店搜索dutedisplay，选中并下载 注意：你需要注册一个dutedisplay账号，才能登录该软件，它是付费的，so，我看到付费我就放弃了。如果，你给钱了，那么，接下来我也不知道对不对，你用ipad充电线......
  • FHQ treap(再见splay------)
    但凡打过平衡树的应该都知道\(\huge{二逼平衡树}\)这道题，抄了两个小时的splay版题解，然后发现了\(\color{maroon}FHQtreap\)：$\large\color{green}这是splay$structjjtree{ inlinevoidup(rintx){sz[x]=sz[son[x][0]]+sz[son[x][1]]+cnt[x];} inlineboolso(rintx){retu......
  • splay-前驱后继
    在平衡树中，经常会让我们查一下一个值的前驱和后继是谁，写两个函数就非常麻烦好吧，所以这里咱们用一点小技巧来让他变成一个函数（这里的前驱后继定义时包括与本身相等的值）代码点击查看代码intnxt(intk) { if(!m[rt].size)return0; introot=rt; while(k!=m[root].val&......
  • splay-前驱后继
    在平衡树中，经常会让我们查一下一个值的前驱或后继是谁，写两个函数就非常麻烦好吧，所以这里咱们用一点小技巧来让他变成一个函数（这里的前驱后继定义时包括与本身相等的值）代码点击查看代码intnxt(intk) { if(!m[rt].size)return0; introot=rt; while(k!=m[root].val&......
  • 平衡树专题Splay
    写在前面：部分来自孙宝（@Steven24）的博客，表示感谢。认识什么是Splay就是BST的一种，整体效率是很高的，均摊的次数是O(logn)级别的。基本操作就是把节点旋转到BST的root，从而改善BST的平衡性，但是很多人会在旋转中转晕建议找个动图看看，或是上B站找个几分钟的视频看看就理解了。烧烤......
  • Klipper RP2040 display ssd1306 0.96 屏幕配置
    接线屏幕接线parampinGNDGNDVCCVCCSCLSDA编码器接线parampinGNDGNDEN1VCCEN2CLklipper配置#显示屏及旋钮[display]lcd_type:ssd1306#i2c_bus:i2c0dencoder_pins:^gpio24,^gpio23encoder_steps_per_detent:2c......
  • [题解]P2042 [NOI2005] 维护数列 - Splay解法
    P2042[NOI2005]维护数列一道思路不难，但实现细节很多的平衡树题，调了一天半终于做出来了w。对于初始序列，我们可以直接构建一条链（毕竟一个一个调用插入函数也可能形成一条链）。题解有递归直接构建成一棵严格平衡的二叉树的，这样也可以，常数可能会小一点。其中区间反转就是裸的文艺......
  • [题解]P3391 文艺平衡树 - Splay解法
    P3391【模板】文艺平衡树给定序列\(1,2,\dots,n\)，接下来\(m\)次操作，每次操作给定\(l,r\)，你需要翻转\([l,r]\)。所有操作结束后，请输出这个序列。我们先从“普通平衡树”这一题出发，思考一下Splay操作的本质。我们把一个节点Splay到根节点后，中序遍历在自己前面的节点都在左边，中......
  • [笔记]Splay树
    前置知识：树的左旋、右旋。Splay树是一种平衡树。能够做到每个操作均摊\(O(\logN)\)。前言与上文AVL树不同之处在于，AVL树在任何操作结束后，都能保证每个节点的左右子树高度相差不超过\(1\)。相应地，每个操作都是严格的\(O(\logN)\)。而Splay树并没有对“平衡”的确切定义，任何结......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99