Cod sursa(job #1077628)

Utilizator ctlin04UAIC.VlasCatalin ctlin04 Data 11 ianuarie 2014 15:30:02
Problema Hashuri Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 3.17 kb
//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=updatehdif(nod);
    
    aux=updatehdif(aux);
    
    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>=0) nod=rotleft(nod);
    else if (nod->dif==2&&nod->r->dif==-1) { 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==0) return(nod);
    
    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,nod->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);
}