#include <iostream>
#include <fstream>
//#include "Arbore.h"
using namespace std;
template <class T, class T2>
class Hash {
private:
T cheie;
T2 val;
Hash<T,T2> *st;
Hash<T,T2> *dr;
public:
Hash(T cheie, T2 val);
Hash<T,T2> *GetDr();
Hash<T,T2> *GetSt();
T GetCheie();
T2 GetVal();
T2 &ValAddr();
void SetDr(Hash<T,T2> *d);
void SetSt(Hash<T,T2> *s);
};
template <class T, class T2>
Hash<T,T2>::Hash(T cheie, T2 val)
{
this->cheie = cheie;
this->val = val;
this->st = NULL;
this->dr = NULL;
}
template <class T, class T2>
T2 &Hash<T,T2>::ValAddr()
{
return this->val;
}
template <class T, class T2>
void Hash<T,T2>::SetDr(Hash<T,T2> *d)
{
this->dr = d;
}
template <class T, class T2>
void Hash<T,T2>::SetSt(Hash<T,T2> *s)
{
this->st = s;
}
template <class T, class T2>
Hash<T,T2> *Hash<T,T2>::GetDr()
{
return this->dr;
}
template <class T, class T2>
Hash<T,T2> *Hash<T,T2>::GetSt()
{
return this->st;
}
template <class T, class T2>
T Hash<T,T2>::GetCheie()
{
return this->cheie;
}
template <class T, class T2>
T2 Hash<T,T2>::GetVal()
{
return this->val;
}
template <class T, class T2>
class Arbore {
private:
Hash<T,T2> *arb;
Hash<T,T2> *cap;
public:
Arbore();
void adauga(T cheie, T2 val);
void sterge(T cheie);
int exista(T cheie);
void rsd(Hash<T,T2> *n);
T2 operator [](T cheie) const
{
arb = cap;
while(arb)
{
if(arb->GetCheie() == cheie) return arb->GetVal();
if(cheie < arb->GetCheie())
{
if(arb->GetSt()) arb = arb->GetSt();
else throw -1;
}
else
{
if(arb->GetDr()) arb = arb->GetDr();
else throw -1;
}
}
}
T2 &operator [](T cheie)
{
arb = cap;
while(arb)
{
if(arb->GetCheie() == cheie) return arb->ValAddr();
if(cheie < arb->GetCheie())
{
if(arb->GetSt()) arb = arb->GetSt();
else throw -1;
}
else
{
if(arb->GetDr()) arb = arb->GetDr();
else throw -1;
}
}
}
};
template <class T, class T2>
Arbore<T, T2>::Arbore()
{
arb = NULL;
cap = NULL;
}
template <class T, class T2>
void Arbore<T, T2>::adauga (T cheie, T2 val)
{
Hash<T,T2> *n = new Hash<T,T2>(cheie, val);
if(arb == NULL)
{
arb = n;
cap = n;
}
else
{
//comparare si inserare
while(arb)
{
if(cheie <= arb->GetCheie())
{
if(arb->GetSt()) arb = arb->GetSt();
else { arb->SetSt(n); break;}
}
else
{
if(arb->GetDr()) arb = arb->GetDr();
else { arb->SetDr(n); break;}
}
}
}
}
template <class T, class T2>
void Arbore<T, T2>::sterge (T cheie)
{
Hash<T,T2> *aux;
if(cap==NULL) return;
arb = cap;
while(1)
{
if(cheie < arb->GetCheie())
{
if(arb->GetSt())
{
if(cheie == arb->GetSt()->GetCheie())
{
if(arb->GetSt()->GetDr())
{
if(arb->GetSt()->GetSt())
{
aux = arb->GetSt()->GetSt();
arb->SetSt(arb->GetSt()->GetDr());
arb->GetSt()->SetSt(aux);
return;
}
else
{
arb->SetSt(arb->GetSt()->GetDr());
return;
}
}
else if(arb->GetSt()->GetSt())
{
arb->SetSt(arb->GetSt()->GetSt());
return;
}
else if((arb->GetSt()->GetSt() == NULL) && (arb->GetSt()->GetDr() == NULL))
{
arb->SetSt(NULL);
return;
}
}
else
{
arb = arb->GetSt();
}
} else return;
}
else if(cheie > arb->GetCheie())
{
if(arb->GetDr())
{
if(cheie == arb->GetDr()->GetCheie())
{
if(arb->GetDr()->GetDr())
{
if(arb->GetDr()->GetSt())
{
aux = arb->GetDr()->GetDr();
arb->SetDr(arb->GetDr()->GetSt());
arb->GetDr()->SetDr(aux);
return;
}
else
{
arb->SetDr(arb->GetDr()->GetDr());
return;
}
}
else if(arb->GetDr()->GetSt())
{
arb->SetDr(arb->GetDr()->GetSt());
return;
}
else if((arb->GetDr()->GetSt() == NULL) && (arb->GetDr()->GetDr() == NULL))
{
arb->SetDr(NULL);
return;
}
}
else
{
arb = arb->GetDr();
}
} else return;
}
else if(cheie == arb->GetCheie())
{}
}
}
template <class T, class T2>
int Arbore<T,T2>::exista(T cheie)
{
arb = cap;
while(arb)
{
if (cheie == arb->GetCheie())
{
return 1;
}
if(cheie <= arb->GetCheie())
{
if(arb->GetSt()) arb = arb->GetSt();
else { return 0;}
}
else
{
if(arb->GetDr()) arb = arb->GetDr();
else { return 0;}
}
}
return 0;
}
template <class T, class T2>
void Arbore<T,T2>::rsd(Hash<T,T2> *n)
{
if(n != NULL)
{
cout<<n->GetCheie()<<" = "<<n->GetVal()<<endl;
preordine(n->GetSt());
preordine(n->GetDr());
}
}
int main()
{
Arbore<int, int> a;
ifstream f("hashuri.in");
ofstream g("hashuri.out");
int n;
int op, x;
f>>n;
for (int i=0;i<n;i++)
{
f>>op>>x;
switch(op)
{
case 1:
a.adauga(x, 21);
break;
case 2:
a.sterge(x);
break;
case 3:
g<<a.exista(x)<<"\n";
break;
default:
;
}
}
f.close();
g.close();
return 0;
}
Andrei Ciucur aandrei26