Pagini recente » Cod sursa (job #125075) | Cod sursa (job #663829) | Rezultatele filtrării | Cod sursa (job #1655563) | Cod sursa (job #1077601)
//AVL- operatii de baza
#include<fstream>
using namespace std;
typedef struct avl {
int h, dif, val;
avl *l, *r;
avl () { l=0; r=0; h=0; dif=0; val=-1; }
};
avl *root;
int op, x, n;
avl *updatehdif(avl *nod) {
if (nod->r==0&&nod->l==0) { nod->h=0; nod->dif=0; }
else if (nod->r==0) {
nod->h=nod->l->h+1;
nod->dif=-nod->l->h;
}
else if (nod->l==0) {
nod->h=nod->r->h+1;
nod->dif=nod->r->h;
}
else {
nod->h=max(nod->r->h,nod->l->h)+1;
nod->dif=nod->r->h-nod->l->h;
}
return(nod);
}
avl *rotright(avl *nod) {
avl *aux=nod->l;
nod->l=aux->r;
aux->r=nod;
nod->h=max(nod->r->h,nod->l->h)+1;
nod->dif=nod->r->h-nod->l->h;
aux->h=max(aux->r->h,aux->l->h)+1;
aux->dif=aux->r->h-aux->l->h;
return(aux);
}
avl *rotleft(avl *nod) {
avl *aux=nod->r;
nod->r=aux->l;
aux->l=nod;
nod=updatehdif(nod);
aux=updatehdif(aux);
return(aux);
}
avl *balance(avl *nod) {
nod=updatehdif(nod);
if (nod->dif==-2&&nod->l->dif<=0) nod=rotright(nod);
else if (nod->dif==-2&&nod->l->dif==1) { nod->l=rotleft(nod->l); nod=rotright(nod); }
else if (nod->dif==2&&nod->r->dif==1) nod=rotleft(nod);
else if (nod->dif==2&&nod->r->dif<=0) { nod->r=rotright(nod->r); nod=rotleft(nod); }
return(nod);
}
avl *insert(avl *nod, avl *newnod) {
if (nod==0) return(newnod);
if (newnod->val<=nod->val) nod->l=insert(nod->l, newnod);
else nod->r=insert(nod->r, newnod);
return( balance(nod) );
}
avl *erase(avl *nod, int val) {
if (nod->val==val) {
if (nod->l==0&&nod->r==0) return(0);
else if (nod->l==0&&nod->r!=0) return(nod->r);
else if (nod->r==0&&nod->l!=0) return(nod->l);
else {
avl *p;
for (p=nod->r; p->l!=0; p=p->l);
nod->val=p->val;
nod->r=erase(nod->r,val);
return( balance(nod) );
}
}
else if (nod->val>val) nod->l=erase(nod->l,val);
else nod->r=erase(nod->r,val);
return( balance(nod) );
}
int cauta(avl *nod, int val) {
if (nod==0) return(0);
else if (nod->val==val) return(1);
else if (nod->val>val) return( cauta(nod->l,val) );
else return( cauta(nod->r,val) );
}
int main(void) {
ifstream fin("hashuri.in");
ofstream fout("hashuri.out");
fin>>n;
root=new avl;
for (; n>0; --n) {
fin>>op>>x;
int ex=cauta(root,x);
if (op==1&&ex==0) {
avl *aux=new avl;
aux->val=x;
root=insert(root, aux);
}
else if (op==2&&ex==1) root=erase(root, x);
else if (op==3) fout<<ex<<"\n";
}
return(0);
}