这两种splay操作有区别吗

P3391 【模板】文艺平衡树

白学家 @ 2017-11-25 13:05:45

···

void splay(node * &o,int k) {
    o->pushdown();
    int d=o->cmp(k);
    if (d==1) k-= (o->ch[0]->s )+1;
    if (d!=-1) {
        node *p=o->ch[d];
        p->pushdown();
        int d2=p->cmp(k);
        int k2=(d2==0?k:k- (p->ch[0]->s) -1);
        if (d2!=-1) {
            splay(p->ch[d2],k2);
            if (d==d2) rotate(o,d^1);     else rotate(o->ch[d],d);
        }
        rotate(o,d^1);
    }
}
void splay(node * &o,int k) {
    o->pushdown();
    int d=o->cmp(k);
    if (d==1) k-=o->ch[0]->s+1;
    if (d!=-1) {
        splay(o->ch[d],k);
        rotate(o,d^1);
    }
}

by xunzhen @ 2018-01-11 22:07:22

应该一个是单旋,一个是双旋吧


by _WA自动机 @ 2018-02-10 18:06:53

Splay 和 Spaly。。


|