平衡树再总结

平衡树,二叉查找树的改进版,可以做各种奇怪的操作。

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://acxblog.site/archives/scapegoat_tree.html

本文链接:https://acxblog.site/archives/balanced_tree.html
本文采用 CC BY-NC-SA 3.0 协议进行许可