跳转至

Splay 树（伸展树）

伸展树 (Splay tree) 是一种 基于旋转 的 二叉搜索树，它按照“最常用者优先”策略，将刚刚访问过的节点，通过 “伸展” 操作移动到树根，能在 均摊 \(O(\log n)\) 的时间内完成插入、查找、修改和删除操作

伸展

将待伸展节点 \(v\) 移动到树根

每次伸展时，都从 \(v\) 上溯两层（双层伸展），记其父节点为 \(f \mathrm{\ (father)}\) 、“祖父节点” 为 \(g\mathrm{\ (grandfather)}\) ，按 \(v\) ，\(f\) 和 \(g\) 的位置关系 将伸展操作分为以下三类：

LL / RR

LL：g->lc==f 且 f->lc==v ，那么 \(g\) 右旋，\(f\) 右旋

LL2

RR：g->rc==f 且 f->rc==v ，那么 \(g\) 左旋，\(f\) 左旋

LR / RL

LR：g->lc==f 且 f->rc==v ，那么 \(f\) 左旋，\(g\) 右旋

LR2

RL：g->rc==f 且 f->lc==v ，那么 \(f\) 右旋，\(g\) 左旋

无祖父（0L / 0R）

如果 \(v\) 的深度为奇数，若干次双层伸展后，必将出现 \(f\) 是根节点，\(g\) 不存在的情况

0L：g==nullptr 且 f->lc==v ，那么 \(f\) 右旋

0R：g==nullptr 且 f->rc==v ，那么 \(f\) 左旋

代码如下：

node* splay(node* v){
    node* f;
    node* g;
    for(;;){
        if(v->fa==nullptr) return v; // v 已经转到根节点，返回 v
        f=v->fa;
        if(f->fa==nullptr){
            if(f->lc=v) return f=R_rotate(f); // 0L
            if(f->rc=v) return f=L_rotate(f); //0R
        }
        g=f->fa;
        if(g->lc==f){
            if(f->lc==v){ // LL
                g=R_rotate(g);
                f=R_rotate(f);
            }else{ // LR
                f=L_rotate(f);
                g=R_rotate(g);
            }
        }else{
            if(f->rc==v){ // RR
                g=L_rotate(g);
                f=L_rotate(f);
            }else{ // RL
                f=R_rotate(f);
                g=L_rotate(g);
            }
        }
    }
}

左旋 & 右旋

d

我们知道，为了判断 \(v\) ，\(f\) 和 \(g\) 的位置关系，伸展树中引入了 父指针，这使得伸展树的左旋、右旋操作麻烦不少

Pointers4

注意到 (b) 中 \(f\) 结点已经不能通过 \(g\) 结点访问到，所以我们需要引入一个指向 \(f\) 的辅助指针帮助我们访问 \(f\)

代码如下：

node* R_rotate(node* g){
    node* f=g->lc;
    if(f->rc!=nullptr)  f->rc->fa=g;
    g->lc=f->rc;
    f->rc=g;
    f->fa=g->fa;
    if(g->fa!=nullptr){
        if(g->fa->lc==g){
            g->fa->lc=f;
        }else{
            g->fa->rc=f;
        }
    }
    g->fa=f;
    return f;
}
node* L_rotate(node* g){
    node* f=g->rc;
    if(f->lc!=nullptr)  f->lc->fa=g;
    g->rc=f->lc;
    f->lc=g;
    f->fa=g->fa;
    if(g->fa!=nullptr){
        if(g->fa->rc==g){
            g->fa->rc=f;
        }else{
            g->fa->lc=f;
        }
    }
    g->fa=f;
    return f;
}

Note

知乎上 某位匿名大佬给出的 旋转操作 不需要辅助指针 的实现 原文链接

g->parent->left = g->left; // R's left is now f
g->left->parent = g->parent; // f's parent is now R
g->left->right->parent = g; // fr's parent is now g
g->parent = g->left; // g's parent is now f
g->left = g->left->right; // g's left is now fr
g->parent->right = g; // f's right is not g

插入

注意，不能递归进入插入点后才返回，

// Incorrect
if(root==nullptr){
    // Insert to current node
    // cannot mantain root->fa
    return;
}

而应该在其父节点处就判断其左右孩子能不能插入，能插入的话，在父节点内就返回，否则将难以维护父指针

// Correct
if(root->lc==nullptr){
    // Insert to the left child of current node
    root->lc->fa=root;
    return;
}
if(root->rc==nullptr){
    // Insert to the right child of current node
    root->rc->fa=root;
    return;
}

插入操作完整代码如下：

node* insert(node*& root,int _val){
    if(root==nullptr){ // 插入第一个元素
        root=new node;
        root->val=_val;
        return root; // 就一个元素不用 Splay
    }
    if(_val<root->val){
        if(root->lc==nullptr){
            root->lc=new node;
            root->lc->val=_val;
            root->lc->fa=root;
            return splay(root->lc); // 插入的 _val 被转到了根节点，返回它
        }
        return insert(root->lc,_val); // 一路返回
    }else if(_val>root->val){
        if(root->rc==nullptr){
            root->rc=new node;
            root->rc->val=_val;
            root->rc->fa=root;
            return splay(root->rc);  // 插入的 _val 被转到了根节点，返回它
        }
        return insert(root->rc,_val);  // 一路返回
    }else{
        root->cnt++; // 已经存在
        return splay(root); // 也要转到根节点
    }
}

评论