当splay区间翻转的时候是直接交换了左右子树的指针的,那么这样不会改变二叉搜索树的性质吗
struct Node{
Node* ch[2];
int v;
int s;
int flip;
int cmp(int x)const{
int d = x - ch[0]->s;
if(d==1)return -1;
return d<=0 ? 0:1;
}
void maintain()
{
s = 1 + ch[0]->s + ch[1]->s;
}
void pushdown()
{
if(flip)//类似于线段树的lazy标记
{
flip=0;
swap(ch[0],ch[1]);
ch[0]->flip = !(ch[0]->flip);
ch[1]->flip = !(ch[1]->flip);
}
}
};
比如这个结构体的pushdown标记