关于SBT板子
  • 板块学术版
  • 楼主rb_tree
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/10/14 21:03
  • 上次更新2024/10/14 22:35:23
查看原帖
关于SBT板子
740948
rb_tree楼主2024/10/14 21:03

rt,我正在写的SBT板子在maintain上有问题,主要是没办法判断所访问结点是否为空结点,访问了nullptr 导致的,求大佬指导一下或者给个SBT板子

#include<cstdio>
using namespace std;
struct node
{
    int value,size;
    node *l,*r;
    node(int _value):value(_value),size(1),l(nullptr),r(nullptr){}
    inline void resize(){ size=l->size+r->size+1; }
};
inline void right_rotate(node *&t)
{
    node *k=t->l;
    t->l=k->r;
    k->r=t;
    k->size=t->size;
    t->resize();
    t=k;
    return;
}
inline void left_rotate(node *&t)
{
    node *k=t->r;
    t->r=k->l;
    k->l=t;
    k->size=t->size;
    t->resize();
    t=k;
    return;
}
inline void _insert(node *&t,int val)
{
    if(t==nullptr) t=new node(val);
    else
    {
        t->size++;
        if(val<t->value) _insert(t->l,val);
        else _insert(t->r,val);
    }
}
inline void maintain(node *&t)
{
    if(t->l->l->size>t->r->size)
    {
        right_rotate(t);
        maintain(t->r);
        maintain(t);
        return;
    }
    if(t->l->r->size>t->r->size)
    {
        left_rotate(t->l);
        right_rotate(t);
        maintain(t->l);
        maintain(t->r);
        maintain(t);
    }
    if(t->r->r->size>t->l->size)
    {
        left_rotate(t);
        maintain(t->l);
        maintain(t);
        return;
    }
    if(t->r->l->size>t->l->size)
    {
        left_rotate(t->r);
        right_rotate(t);
        maintain(t->l);
        maintain(t->r);
        maintain(t);
    }
}
inline void insert(node *&t,int val)
{
    if(t==nullptr) t=new node(val);
    else
    {
        t->size++;
        if(val<t->value) insert(t->l,val);
        else insert(t->r,val);
    }
    maintain(t);
}
int main()
{
    node *root=new node(0);
    insert(root,114);
    insert(root,514);
    insert(root,1919);
    insert(root,810);
    insert(root,114514);
    insert(root,1919810);
    return 0;
}
2024/10/14 21:03
加载中...