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标记

阅读 2k
撰写回答
你尚未登录,登录后可以
  • 和开发者交流问题的细节
  • 关注并接收问题和回答的更新提醒
  • 参与内容的编辑和改进,让解决方法与时俱进
推荐问题