splay区间翻转不会破坏二叉搜索树的性质吗
当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标记
如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱,如果其他用户或者作者回复了您的评论,将不能在第一时间通知您!
发布评论