Minimum, maximum, est-ce un abr ? — exercice corrigé d'algorithmique (école d'ingénieur) (chapitre 9)

Minimum, maximum, est-ce un abr ?

Arbres binaires de recherche de coût minimum · niveau 2

Énoncé

Écrire int min(AB a) et int max(AB a) pour un abr non vide, en $Θ (h)$ où $h$ est la hauteur.
Un étudiant propose de tester si un arbre binaire est un abr en vérifiant, en chaque nœud, que la racine du sous-arbre gauche est plus petite et que celle du sous-arbre droit est plus grande. Donner un contre-exemple.
Écrire boolean estABR(AB a) correcte, en $Θ (n)$ . Indication : passer en paramètres les bornes que doivent respecter les valeurs du sous-arbre.

Corrigé

Le minimum est tout en bas à gauche, le maximum tout en bas à droite :


static int min(AB a) { return vide(sag(a)) ? vr(a) : min(sag(a)); }   // a non vide
static int max(AB a) { return vide(sad(a)) ? vr(a) : max(sad(a)); }

On descend d'un niveau par appel : $Θ (h)$ .

L'arbre $(5 (3 () (8 () ())) (9 () ()))$ passe le test local ( $3 < 5 < 9$ et $3 < 8$ ), mais $8$ est dans le sous-arbre gauche de $5$ alors que $8 > 5$ : ce n'est pas un abr.
Toutes les valeurs du sous-arbre gauche doivent être inférieures à la racine, et celles du sous-arbre droit supérieures : on transmet ces bornes.


static boolean estABR(AB a, long bi, long bs) {   // toutes les valeurs dans ]bi, bs[
    if (vide(a)) return true;
    return bi < vr(a) && vr(a) < bs
        && estABR(sag(a), bi, vr(a)) && estABR(sad(a), vr(a), bs);
}
static boolean estABR(AB a) { return estABR(a, Long.MIN_VALUE, Long.MAX_VALUE); }


contre-exemple (5 (3 () (8 () ())) (9 () ())) : localement ordonné = true, estABR = false

Les bornes en long évitent d'exclure les valeurs Integer.MIN_VALUE et Integer.MAX_VALUE. Un appel par sous-arbre : $Θ (n)$ .