184ms / 3.15MB

代码:2.61KB C++11

时空以及编程复杂度都还好吧= =,大家似乎都很喜欢Splay?蒟蒻有点强迫症,对于随机化(以及具有随机性,复杂度的logn是均摊意义)的算法总有抵触心理,但不得不说,Splay与Treap的时空复杂度与编程复杂度较之于AVL与Red—Black都是很优秀的,更重要的是他们支持合并O_O,从目前看来,SBT(Size Blanced tree)似乎没有支持合并的操作,废话说了一大堆,说正事。

SBT的基本操作——zig(左旋),zag(右旋),maintain,insert,erase(删除),rank(大小为k的数的排名),select(排名为k的数),pred(前驱),succ(后继)

除了maintain,其他的都与普通的BST(二茬排序树)一模一样,

所以我这里就介绍一下maintain

SBT只维护一个key:键值,一个size:子树中节点的个数。

我们考虑,什么样的二叉树是平衡的?

对于每个节点,其左子树的节点数都大致等于右子树的节点数,即size[left]~=(近似等于)size[right]

可是这个大致,范围就很宽了,我们不好确定,

那么我们考虑,什么样的二叉树一定是不平衡的?

对于每个节点,

若其左子树的左子树的节点数大于等于其右子树的节点数,这时我们画个图就可以清楚地看到,这树不平衡,我们只需通过一次zag(根)即可将其平衡。

若其左子树的右子树的节点数大于等于其右子树的节点数,这时,我们需要先将其左子树平衡(你可以选择递归,但其实没有必要,接着看看下面两种情况就能明白),然后一个zag(根)就可以使树平衡。

若其右子树的右子树的节点数大于等于其左子树的节点数,这时类比情况1,我们只需一个zig(根)

若其右子树的左子树的节点数大于等于其左子树的节点数,这时类比情况2,我们先平衡右子树,再zig(根)

很明显,这4中情况是对称的,我们无需一一列举,所以我们可以设置一个flag,

flag为false表示当前节点插入到左子树中,这时只有可能出现情况1,2

flag为true表示当前节点插入到右子树中,这时只有可能出现情况3,4

那么我们在旋转完当前的根后,还是有必要再检查一下其左右子书是否都已平衡,递归调用一下就好了,可以证明在一个平衡树中插入后进行的maintain递归的效率均摊是O(1)的,而且99%总是O(1)的= =

蒟蒻觉得SBT应该就是这样了,还算清楚吧?

参考代码:

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=100100;
int M;
struct Size_Blanced_Tree{
    int rt,NodeCnt;
    int key[N],s[N],left[N],right[N];
    void clear(){
        rt=0,NodeCnt=0;
        memset(key,0,sizeof(key));
        memset(s,0,sizeof(s));
        memset(left,0,sizeof(left));
        memset(right,0,sizeof(right));
    }
    void zig(int &p){
        int k=right[p];
        right[p]=left[k];
        left[k]=p;
        s[k]=s[p];
        s[p]=s[left[p]]+s[right[p]]+1;
        p=k;
    }
    void zag(int &p){
        int k=left[p];
        left[p]=right[k];
        right[k]=p;
        s[k]=s[p];
        s[p]=s[left[p]]+s[right[p]]+1;
        p=k;
    }
    void maintain(int &p,bool flag){
        if (!flag){
            if (s[left[left[p]]]>s[right[p]])zag(p);
            else{
                if (s[right[left[p]]]>s[right[p]]){
                    zig(left[p]);
                    zag(p);
                }else return;
            }
        }else{
            if (s[right[right[p]]]>s[left[p]])zig(p);
            else{
                if (s[left[right[p]]]>s[left[p]]){
                    zag(right[p]);
                    zig(p);
                }else return;
            }
        }
        maintain(left[p],false);
        maintain(right[p],true);
        maintain(p,true);
        maintain(p,false);
    }
    void insert(int &p,int x){
        if (!p){
            p=++NodeCnt;key[p]=x;s[p]=1;
            return; 
        }
        s[p]++;
        if (x<key[p])insert(left[p],x);
            else insert(right[p],x);
        maintain(p,x>=key[p]);
    }
    int erase(int &p,int x){
        s[p]--;int tmp;
        if (x==key[p] || (x<key[p] && !left[p]) || (x>key[p] && !right[p])){
            tmp=key[p];
            if (!left[p] || !right[p])p=left[p]+right[p];
            else key[p]=erase(left[p],key[p]+1);
            return tmp;
        }
        if (x<key[p])tmp=erase(left[p],x);else tmp=erase(right[p],x);
        return tmp;
    }
    int rank(int &p,int x){
        if (!p)return 1;int tmp=0;
        if (x<=key[p])tmp=rank(left[p],x);
        else tmp=s[left[p]]+1+rank(right[p],x);
        return tmp;
    }
    int select(int &p,int x){
        if (x==s[left[p]]+1)return key[p];
        if (x<=s[left[p]])return select(left[p],x);
        else return select(right[p],x-1-s[left[p]]);
    }
    int pred(int &p,int x){
        if (!p)return x;int tmp;
        if (x<=key[p])tmp=pred(left[p],x);
        else{tmp=pred(right[p],x);if (tmp==x)tmp=key[p];}
        return tmp;
    }
    int succ(int &p,int x){
        if (!p)return x;int tmp;
        if (x>=key[p])tmp=succ(right[p],x);
        else{tmp=succ(left[p],x);if (tmp==x)tmp=key[p];}
        return tmp;
    }
}T;
int main(){
    scanf("%d",&M);
    T.clear();
    int &rt=T.rt=0;
    while (M--){
        int opt,x;
        scanf("%d%d",&opt,&x);
        if (opt==1)T.insert(rt,x);
        else if (opt==2)T.erase(rt,x);
        else if (opt==3)printf("%d\n",T.rank(rt,x));
        else if (opt==4)printf("%d\n",T.select(rt,x));
        else if (opt==5)printf("%d\n",T.pred(rt,x));
        else if (opt==6)printf("%d\n",T.succ(rt,x));
    }
    return 0;
}