Arbres binaires de recherche de coût minimum

9.1 Arbres binaires

Nous avons déjà rencontré les listes d'entiers (chapitre 7) : une liste est soit vide, soit un couple $(pr)$ formé d'un premier élément $p$ et d'un reste $r$, lui-même une liste. Les arbres binaires se définissent de la même manière, récursivement.

Exemple 9.2écriture parenthésée et représentation graphique

L'arbre $(4(3()())(6()()))$ a la valeur $4$ à sa racine, la feuille $3$ à gauche et la feuille $6$ à droite. Les informaticiens le dessinent racine en haut :

9.1.1 Représentation en Java

La classe AB suit la définition : l'arbre vide est représenté par null, un arbre non vide par un objet qui contient sa valeur racine et ses deux sous-arbres.

static class AB {
    int vr; AB g, d;
    AB(int vr, AB g, AB d) { this.vr = vr; this.g = g; this.d = d; }
}
static boolean vide(AB a) { return a == null; }
static int vr(AB a) { return a.vr; }   // a doit être non vide
static AB sag(AB a) { return a.g; }    // a doit être non vide
static AB sad(AB a) { return a.d; }    // a doit être non vide

L'arbre de l'exemple est construit par new AB(4, new AB(3, null, null), new AB(6, null, null)).

9.1.2 Taille et hauteur

La taille d'un arbre est son nombre de valeurs. Sa hauteur est la longueur (en nombre d'arcs) du plus long chemin depuis la racine. Une feuille est de hauteur $0$ ; par une convention cohérente, l'arbre vide est de hauteur $-1$. Les deux fonctions s'écrivent en suivant la définition récursive : un cas pour l'arbre vide, un cas pour $(v_{r}gd)$.

static int taille(AB a) {
    if (vide(a)) return 0;
    return 1 + taille(sag(a)) + taille(sad(a));
}
static int hauteur(AB a) {
    if (vide(a)) return -1;
    return 1 + Math.max(hauteur(sag(a)), hauteur(sad(a)));
}

Chaque valeur de l'arbre donne lieu à un appel, et chaque appel est en temps constant (hors appels récursifs) : ces fonctions sont en $\Theta (n)$ pour un arbre de taille $n$.

9.2 Arbres binaires de recherche

Exemple 9.4un abr sur les valeurs $1$ à $9$

Toutes les valeurs à gauche de $4$ lui sont inférieures, toutes celles à droite lui sont supérieures, et cela est vrai en chaque sommet.

9.2.1 Afficher les valeurs dans l'ordre

Pour afficher les valeurs d'un abr dans l'ordre croissant, il suffit d'afficher celles du sous-arbre gauche (croissantes), puis la racine, puis celles du sous-arbre droit (croissantes). C'est le parcours gauche--racine--droite (grd). Sa justification est exactement la définition des abr :

static void grd(AB a) { // affiche les valeurs de l'abr a dans l'ordre croissant
    if (vide(a)) return;           // sans rien faire, les valeurs de () sont affichées
    grd(sag(a));                   // (1) les valeurs de g ont été affichées croissantes
    System.out.print(vr(a) + " "); // (2) puis la valeur racine
    grd(sad(a));                   // (3) puis les valeurs de d, croissantes
    // (1), (2), (3) et les propriétés (a), (b) des abr :
    // les valeurs de a ont été affichées croissantes
}