Plus petite valeur supérieure ou égale dans un ABR

Recherche séquentielle, dichotomique, arrière · niveau 2

Énoncé

Dans un arbre binaire de recherche $a$ (classe AB du cours), écrire une fonction récursive int plafond(int x, AB a) qui retourne la plus petite valeur de $a$ supérieure ou égale à $x$ , ou Integer.MAX_VALUE s'il n'y en a pas. Son temps de calcul doit être proportionnel à la hauteur de $a$ . Tester sur l'arbre obtenu en insérant $8, 3, 12, 1, 6, 10, 15, 4$ dans un arbre vide.

Corrigé

On raisonne comme pour la fonction dans :

arbre vide : aucune valeur, on retourne Integer.MAX_VALUE ;
si $vr (a) = x$ , la réponse est $x$ ;
si $vr (a) < x$ , la racine et tout le sous-arbre gauche sont $< x$ : la réponse est dans le sous-arbre droit ;
si $vr (a) > x$ , la racine est un candidat ; une meilleure réponse ne peut être que dans le sous-arbre gauche (le sous-arbre droit ne contient que des valeurs $> vr (a)$ ).


static int plafond(int x, AB a) {
    if (vide(a)) return Integer.MAX_VALUE;     // aucune valeur
    if (vr(a) == x) return x;
    if (vr(a) < x) return plafond(x, sad(a));  // tout sag(a) est < x aussi
    return Math.min(vr(a), plafond(x, sag(a))); // vr(a) > x : candidat
}

Avec l'arbre de racine $8$ :


plafond(0) = 1
plafond(5) = 6
plafond(7) = 8
plafond(11) = 12
plafond(15) = 15
plafond(16) = aucune

Chaque appel descend d'un niveau : le nombre d'appels est au plus $h (a) + 2$ , le temps de calcul est proportionnel à la hauteur de l'arbre.