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 用双旋,也就是分情况讨论。。。