Splay 树（伸展树）¶

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

伸展¶

将待伸展节点 $v$ 移动到树根

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

LL / RR¶

LL：g->lc==f 且 f->lc==v ，那么 $g$ 右旋， $f$ 右旋

RR：g->rc==f 且 f->rc==v ，那么 $g$ 左旋， $f$ 左旋

LR / RL¶

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

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);
            }
        }
    }
}

左旋 & 右旋¶

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

注意到 (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); // 也要转到根节点
    }
}

Splay 树（伸展树）¶

伸展¶

LL / RR¶

LR / RL¶

无祖父（0L / 0R）¶

左旋 & 右旋¶

插入¶

评论