TD11

Exercice 1

1. Un arbre binaire est dit arbre AVL si pour tout noeud V de l'arbre
2. les étiquettes situées dans l'arbre à gauche de V sont strictement inférieurs à l'etiquette de V
3. les étiquettes situées dans l'arbre à droite de V sont strictement supérieurs à l'etiquette de V

4. La valeur absolue de la différence entre les deux arbres enfant de V est au plus 1.

A) est un AVL

B) n'est pas un AVL

C) n'est pas un AVL car non équilibré.

L'arbre vide est un AVL.

Un arbre avec une racaine est un AVL si: les arbres à gauche et à droite de cette racine sont des AVL et ...

Exercice 2

On suppose qu'il n'y a pas d'étiquettes INTMAX, INTMIN.

noeud_t* r = ... // r est un arbre
int hr, minr; maxr;
int v = estAVL(r, &hr ,&minr, &maxr)

int estAVL(noeud_t* a, int* h, int* min, int* max){
    if (a==NULL){
        *h=0;
        *min = INT_MAX;
        *max = INT_MIN;
        return 1;
    }
    int vg,hg,maxg,ming,vd,hd,mind,maxd;
    vg = estAVL(a->g, &hg, &ming, &maxg);
    vd = estAVL(a->d, &hd, &mind, &maxd);
    if (vg == 0 || vd == 0) return 0;
    if (hg-hd>1 || hg-hd<-1) return 0;
    if (a->v <= maxg || a->v >= mind) return 0;
    *h = 1+ (hg>hd?hg:hd);
    *min = (h->v > ming? ming:a->v);
    *max = (a->v > maxd?a->v:maxd);
    return 1;
}