splay区间翻转不会破坏二叉搜索树的性质吗

发布于 2022-09-06 02:36:19 字数 600 浏览 14 评论 0

当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 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。
列表为空,暂无数据
我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
原文