平衡树——Treap和Splay

综合技术 2018-12-08 阅读原文

二叉搜索树($BST$):一棵带权二叉树,满足左子树的权值均小于根节点的权值,右子树的权值均大于根节点的权值。且左右子树也分别是二叉搜索树。(如下)

$BST$的作用:维护一个有序数列,支持插入$x$,删除$x$,查询排名为$x$的数,查询$x$的排名,求$x$的前驱后继等操作。

时间复杂度:$O(操作数times 树深度)$。

(显然插入一个有序序列$BST$的深度稳定在$O(N)$)

平衡树:深度稳定在$O(log{节点数})$的$BST$。

使深度稳定的几种方法:增加一个破坏单调性的第二权值($Treap$),每插入一个数进行旋转保持平衡($Splay$),维护每个子树的$size$并使左右子树的$size$保持平衡($SBT$)等。

本文主要给出$Treap$和$Splay$的实现方法。

$Treap$:顾名思义,该数据结构是$Tree$与$Heap$的结合体。

思想:在第一关键字满足$BST$性质的同时,为每个节点随机生成一个第二关键字,并通过旋转使得第二关键字满足堆性质。

旋转(网上讲的很清楚了a QAQ):分为左右旋两种,如图(图源网络w):

例如:(图源网络,图中点内是第一关键字(满足$BST$),点外是随机生成的第二关键字(满足堆))

优点:常数小,实现简单。

缺点:应用范围较小,略有$0.001$%运气因素(不过能随机出来$10^5$个递增的数就可以去买彩票了w)

例题: bzoj3224普通平衡树

代码:

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<ctime>

using namespace std;
#define MAXN 100005
#define MAXM 500005
#define INF 0x7fffffff
#define ll long long

struct Treap{
    int l,r; //左儿子、右儿子
    int num,rnd; //该节点的第一关键字(权值)、该节点的第二关键字
    int cnt,siz; //该节点权值的出现次数、以该节点为根的子树的大小 
}tr[MAXN];
int tot,root; //当前节点数、当前根节点 

inline int read(){
    int x=0,f=1;
    char c=getchar();
    for(;!isdigit(c);c=getchar())
        if(c=='-')
            f=-1;
    for(;isdigit(c);c=getchar())
        x=x*10+c-'0';
    return x*f;
}

inline void update(int k){
    tr[k].siz=tr[k].cnt;
    tr[k].siz+=tr[tr[k].l].siz;
    tr[k].siz+=tr[tr[k].r].siz;
    return; 
}
inline void zig(int &k){ //将以k为根的子树左旋(看图) 
    int tp=tr[k].r;
    tr[k].r=tr[tp].l; //将k的右儿子置为k的右儿子的左儿子 
    tr[tp].l=k; //将k的右儿子的左儿子置为k 
    tr[tp].siz=tr[k].siz; //右儿子成为新的根,size等于k的size 
    update(k); //更新k的size 
    k=tp; //以k为根的子树变为以k的右儿子为根的子树,换根 
    return;
}
inline void zag(int &k){ //将以k为根的子树右旋(同上) 
    int tp=tr[k].l;
    tr[k].l=tr[tp].r;
    tr[tp].r=k;
    tr[tp].siz=tr[k].siz;
    update(k);
    k=tp;return;
}
inline void ins(int x,int &k){ //插入数x 
    if(k==0){ //当前节点为空则在此处新建节点 
        k=++tot;
        tr[k].cnt=tr[k].siz=1;
        tr[k].rnd=rand(); 
        tr[k].num=x;
        return;
    }
    tr[k].siz++; //插入的节点在该子树内,size+1 
    if(x==tr[k].num) tr[k].cnt++; //如果该数已经出现过则不用新建节点,将该节点的cnt+1即可 
    else if(x<tr[k].num){
        ins(x,tr[k].l); //x小于当前节点的关键字则插入当前节点的左子树 
        if(tr[tr[k].l].rnd<tr[k].rnd) zag(k); 
        //如果左儿子的第二关键字不满足小根堆性质就把左儿子转上来,容易证明此时一定满足堆性质 
    }
    else{
        ins(x,tr[k].r); //x大于当前节点的关键字则插入当前节点的右子树
        if(tr[tr[k].r].rnd<tr[k].rnd) zig(k); //同上 
    }
    return;
}

inline void del(int x,int &k){ //删除数x 
    if(k==0) return; //如果x没出现则返回 
    if(x==tr[k].num){
        if(tr[k].cnt>1) tr[k].cnt--,tr[k].siz--; 
        //如果该节点出现次数>=1则不用移除节点,出现次数-1即可 
        else if(tr[k].l*tr[k].r==0) 
            k=tr[k].l+tr[k].r;
        //如果该节点的儿子数<=1则可以直接删除,即拿它的儿子代替它 
        else if(tr[tr[k].l].rnd<tr[tr[k].r].rnd) zag(k),del(x,k);
        else zig(k),del(x,k);
        //否则将该节点旋转到可以直接删除的位置再删除 
        return;
    }
    tr[k].siz--; //删除的节点在该子树内,size-1 
    if(x<tr[k].num) del(x,tr[k].l); //x在当前节点的左子树 
    else del(x,tr[k].r); //x在当前节点的右子树 
    return;
}

inline int qrnk(int x,int k){ //查询x数的排名(相当于查询有多少个数小于x) 
    if(k==0) return 0;
    if(x==tr[k].num) return tr[tr[k].l].siz+1; 
    //找到了x,此时小于x的数的个数等于左子树的大小,排名需要+1 
    else if(x<tr[k].num) return qrnk(x,tr[k].l);
    //x在当前节点的左子树中,直接递归左子树 
    else return qrnk(x,tr[k].r)+tr[tr[k].l].siz+tr[k].cnt;
    //x在当前节点的右子树中,此时该节点及其左子树的权值均小于x,需要将这部分size加入答案 
}

inline int qnum(int x,int k){ //查询排名为x的数 
    if(k==0) return 0;
    if(tr[tr[k].l].siz<x && x<=tr[tr[k].l].siz+tr[k].cnt) return tr[k].num;
    //此时的排名正好确定在当前节点(大于等于当前节点的权值第一次出现的位置,小于等于该权值最后一次出现的位置),返回该节点的权值(第一关键字)即可 
    else if(tr[tr[k].l].siz>=x) return qnum(x,tr[k].l);
    // 排名为x的数在当前节点的左子树中,直接递归 
    else return qnum(x-(tr[tr[k].l].siz+tr[k].cnt),tr[k].r);
    //排名为x的数在当前节点的右子树中,此时该节点及其左子树不影响右子树中数的排名,需要减去这部分size 
}

inline int qpre(int x,int k){ //查询x数的前驱(最大的小于x的数) 
    if(k==0) return -INF; 
    if(x<=tr[k].num) return qpre(x,tr[k].l);
    //x在当前节点的左子树中,此时该节点不影响答案,递归左子树 
    else return max(qpre(x,tr[k].r),tr[k].num);
    //x在当前节点的右子树中,此时该节点的权值小于等于x,又因为该节点的权值大于该节点左子树中的所有权值,将答案与k取max即可 
}

inline int qnxt(int x,int k){ //查询x数的后继(最小的大于x的数),基本同上 
    if(k==0) return INF;
    if(x>=tr[k].num) return qnxt(x,tr[k].r); 
    else return min(qnxt(x,tr[k].l),tr[k].num);
}

int main(){
    srand(time(0));
    int T=read();
    while(T--){
        int op=read(),x=read();
        switch(op){
            case 1:ins(x,root);break;
            case 2:del(x,root);break;
            case 3:printf("%dn",qrnk(x,root));break;
            case 4:printf("%dn",qnum(x,root));break;
            case 5:printf("%dn",qpre(x,root));break;
            case 6:printf("%dn",qnxt(x,root));break;
        }
    }return 0;
}

$Splay$:待更……

博客园-原创精华区

责编内容by:博客园-原创精华区阅读原文】。感谢您的支持!

您可能感兴趣的

平衡树初阶——AVL平衡二叉查找树+三大平衡树(Treap + Splay + SBT)模板【超详解... 平衡树初阶——AVL平衡二叉查找树 一、什么是二叉树 1. 什么是树。 计算机科学里面的树本质是一个树状图。树首先是一个有向无环图,由根节点指向子结点。但是不严格的说,我们也研究无向树。所谓无向树就是将有向树的所有...
Go 系列文章 11: semaphore 后续更新和修正: https://github.com/cch123/golang-notes/blob/master/semaphore.md 数据结构 // Go 语言中暴露的 semaphore 实现 //...
Data structure: the treap! Here’s a quick sketch I did yesterday about a randomized data structure: the treap . It’s basically a really cool way t...
【数据结构】【平衡树】Treap 百度百科 Pre_knowledge 二叉排序树 二叉排序树是一棵二叉树。每个节点对应一个权值v,对于每个节点,一定满足如下性质: 二叉排序树的每个节点的左子树要么为空,要么左子树的任意节点的权值v'一定...
紫荆花之恋 本题是动态点分治的经典毒瘤题。让我调了一天代码,还被卡了常…. 想法很简单,点分树上每个节点和其儿子都开一棵treap,然后写个树上倍增求距离和该点分树上以该节点为根的子树中的节点所对的该节点的儿子。由于要插入,所以我们可以记下点分...