关于指针版splay

P3391 【模板】文艺平衡树

xenonex @ 2018-09-15 11:49:58

听说splay的时候无脑上旋能被特殊数据卡成一条链,是真的吗

要怎么改啊……不平衡了就暴力重构?

struct Node
{
    int sum; //以当前节点为根的子树大小 
    Node *ls,*rs; //左右儿子的指针 
};
inline void maintain(Node *p)
{
    p->sum = 1;
    if(p->ls)p->sum += p->ls->sum;
    if(p->rs)p->sum += p->rs->sum;
}
void Lrotate(Node* &p)
{
    Node *k = p->rs;
    p->rs = k->ls;
    k->ls = p;
    p = k;
    maintain(p->ls), maintain(p);
}
void Rrotate(Node* &p)
{
    Node *k = p->ls;
    p->ls = k->rs;
    k->rs = p;
    p = k;
    maintain(p->rs), maintain(p);
}
void splay(Node* &p,int aim) //在以p为根的子树中,把排名为aim的节点splay到根 
{
    int lsize = p->ls?p->ls->sum:0;
    if(lsize+1 == aim)return;
    if(lsize >= aim)splay(p->ls,aim), Rrotate(p);
    else splay(p->rs,aim-lsize-1), Lrotate(p);
}

by clockwhite @ 2018-09-15 11:51:05

tql乍一看以为是slay


by happyZYM @ 2018-09-15 13:01:58

@xenonex 用双旋,也就是分情况讨论。。。


|