Splay

又称伸展树。有两种写法：递归版（无需维护父指针）、非递归版（维护父指针版本）。在区间维护操作、信息和 LCT 上有广泛的应用。

Splay 的核心操作为splay(x)，即将点 x 旋转到根。依赖于 Rotate，Splay 有两种版本：双旋和单旋（Spaly）。在特殊构造下的数据 Spaly 可以被卡掉。

区间的旋转操作

维护一个 lazy。由于区间是中序遍历得到的结果，翻转后的区间是中序遍历全部翻转过后的结果，因此只需记录懒标记，在需要访问儿子的地方前设置 pushdown 即可。

递归版

Rotate(&x, d):

维护 x 的被引用状态，需要向 Rotate 传递方向参数。作用是将 x 的儿子旋到 x 处。

void rot(Node *&x, int d) {
    Node *y=x->ch[d]; y->pud();
    x->ch[d]=y->ch[!d], y->ch[!d]=x;
    x->upd(), y->upd(), x=y;
}

Splay(&x, k):

Splay 过程将 Find 和 Splay 进行合并。查找到结点之后直接进行旋转。k 是需要查找的键值，x 需要维护引用状态。

void splay(Node *&x, int k) {
    x->pud();
    int d=x->cmp(k);
    if(d!=-1 && x->ch[d]!=nil) {
        x->ch[d]->pud();
        int d2=x->ch[d]->cmp(k);
        if(d2!=-1 && x->ch[d]->ch[d2]!=nil) {
            splay(x->ch[d]->ch[d2], k);
            if(d==d2) rot(x, d), rot(x, d);
            else rot(x->ch[d], d2), rot(x, d);
        }
        else rot(x, d);
    }
}

非递归版

在需要维护特定结点地址并将其旋到根节点的时候，需要同时维护父指针和非递归版 splay。
如果需要 Find 的话，效率往往比非递归版要低。

结构体的成员函数

dir()

如果父指针为 nil，返回 -1，否则返回父指针的对应儿子方向。

nroot()

如果不在根处，返回 1，否则返回 0. 常见于 LCT 中的 splay。

Rotate(x)

作用是将 x 向上旋一格。由于 y,z 是直接计算，因此只算一个参。
需要注意指针指向 nil 的情况。
（假设 x 是 y 的右子树）顺序是先将 x 的左子树接到 y 的右子树，更新 x 的左子树的父指针。
然后再更新 x 的父指针和 x 的新的父节点的儿子（这里需要用到还没被更改的 y）。
最后再将 y 接到 x 的左子树，更新 y 的父指针。
此时一般只需要更新 y 从儿子更新上来的信息（因为只有 y 的儿子发生了变化），然后在 splay 完之后再更新 x 的信息。

void rot(Node *x) {
    Node *y=x->f, *z=y->f;
    int d=x->dir();
    y->ch[d]=x->ch[!d];
    if(x->ch[!d]!=nil) x->ch[!d]->f=y;
    x->f=z;
    if(y->dir()!=-1) z->ch[y->dir()]=x;
    x->ch[!d]=y, y->f=x, y->upd();
}

Splay(x)

若要区间翻转，一般选择先用栈将点到根的结点全部下放后再进行处理。

Node *stk[N];
void splay(Node *x, Node *f) {
    int z=0;
    Node *y=x;
    stk[++z]=y;
    while(y->f!=f) stk[++z]=y=y->f;
    while(z) stk[z--]->pud();
    while(x->f!=f) {
        y=x->f;
        if(y->f==f) rot(x);
        else if(y->dir() == x->dir()) rot(y), rot(x);
        else rot(x), rot(x);
    }
    x->upd();
    if(f==nil) rt=x;
}

替罪羊树

https://pst.iorinn.moe/archives/scapegoat_tree.html

本文链接：https://pst.iorinn.moe/archives/balanced_tree.html
许可： https://pst.iorinn.moe/license.html
若无特别说明，博客内的文章默认将采用 CC BY 4.0 许可协议进行许可☆

网站

加入讨论吧...