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;
}