Exercices (pc 6) Corrigé

Exercice 1

int max(int i,int j){
return (i<j)? j : i;
}
int hauteur(Arbre a) {
return (a == NULL)?  0 :  a->h;
}
Arbre NouvelArbre (Element v, Arbre a, Arbre b) {
Arbre r;
r= (Arbre) malloc(sizeof(Noeud));
r->contenu = v;
r->filsG = a;
r->filsD = b;
r->h = max(hauteur(a), hauteur(b)) + 1;
return r;
}

void rotD(Arbre *pa) {
Arbre a= *pa;
Arbre b;
b =a;
a = a->filsG;
b->filsG = a->filsD;
a->filsD = b;
b->h = max(hauteur(b->filsG),hauteur(b->filsD))+1;
a->h = max(hauteur(a->filsG),hauteur(a->filsD))+1;
*pa = a;
}

void rotG(Arbre *pa) {
Arbre a= *pa;
Arbre b;
b = a;
a = a->filsD;
b->filsD = a->filsG;
a->filsG = b;
b->h = max(hauteur(b->filsG),hauteur(b->filsD))+1;
a->h = max(hauteur(a->filsG),hauteur(a->filsD))+1;
*pa = a;
}

Exercice 2

void drotD (Arbre *pa) {
Arbre a= *pa;
rotG(&a->filsG);
rotD(pa);
}
void drotG (Arbre *pa) {
Arbre a= *pa;
rotD(&a->filsD);
rotG(pa);
}

int delta (Arbre a) {
return hauteur(a->filsD) - hauteur(a->filsG);
}

void Reequilibre (Arbre *pa) {
Arbre a= *pa;
if (delta(a) == 2 && delta(a->filsD) >= 0)
  rotG(pa);
else if (delta(a) == 2 && delta(a->filsD) == -1)
  drotG(pa);
else if (delta(a) == -2 && delta(a->filsG) <= 0)
  rotD(pa);
else if (delta(a) == -2 && delta(a->filsG) == 1)
  drotD(pa);
else
  a->h = max(hauteur(a->filsG), hauteur(a->filsD)) + 1;
}
void Inserer (Element x, Arbre *pa) {
Arbre a= *pa;
if (a == NULL)
  *pa = NouvelArbre(x, NULL, NULL);
else if (x < a->contenu) {
  Inserer(x, &a->filsG);
  Reequilibre(pa);
}
else if (x > a->contenu) {
  Inserer(x, &a->filsD);
  Reequilibre(pa);
}
}