Arbres binaires

Comment un compilateur sait-il que 3 + 4 * 2 vaut 11 et non 14 ? Pas en appliquant des règles de priorité au moment du calcul : en construisant un arbre où la multiplication est plus bas que l'addition. Une fois l'arbre bâti, la priorité n'existe plus — elle est devenue de la structure, et l'évaluation se fait par une récursion de trois lignes.

Les arbres sont partout dès qu'on modélise une hiérarchie : arborescence de fichiers du chapitre 7 du cours de systèmes, page web, arbre de décision de la borne inférieure des tris, arbre d'appels du chapitre 4. Ce chapitre les définit et donne les quatre façons de les parcourir ; le suivant montrera ce qu'ils font gagner.

Vocabulaire

Un arbre est un ensemble de nœuds reliés par des arêtes, tel qu'un nœud unique — la racine — n'a pas de parent, et que tout autre nœud a exactement un parent. Cette seconde condition est ce qui distingue un arbre d'un graphe quelconque, et elle interdit les cycles.

1                    ●  racine, profondeur 02                 ┌──┴──┐3                 ●     ●         profondeur 14              ┌──┴─┐   │5              ●    ●   ●         profondeur 26                        └─┐7                          ●      profondeur 3  →  hauteur de l'arbre = 3

Un arbre binaire est un arbre où chaque nœud a au plus deux enfants, distingués comme gauche et droit — et l'ordre compte : un enfant unique à gauche ne donne pas le même arbre qu'à droite.

Ici encore, la définition est récursive : un arbre binaire est vide, ou bien une racine portant deux arbres binaires. Toutes les fonctions du chapitre s'écriront donc en trois lignes, selon le patron du bloc I — cas de base sur l'arbre vide, appel sur chaque sous-arbre.

Hauteur et taille : l'inégalité qui fonde tout

Un arbre binaire de hauteur $h$ contient au moins $h+1$ nœuds — le cas d'une chaîne, un enfant par niveau — et au plus $2^{h+1} - 1$ — le cas de l'arbre parfait, tous les niveaux remplis.

En inversant, la hauteur d'un arbre de $n$ nœuds vérifie :

Tout le bloc IV tient dans cet encadrement. Un arbre équilibré a une hauteur en $O(\log n)$ ; un arbre dégénéré a une hauteur en $O(n)$, et il n'est plus qu'une liste chaînée déguisée. Comme la plupart des opérations coûtent $O(h)$, l'écart entre les deux est exactement celui qui séparait le bon et le mauvais pivot du chapitre 3.

Deux représentations

Par chaînage. Un nœud est une cellule avec une valeur et deux pointeurs. C'est la cellule du chapitre 5, avec un lien de plus — et c'est bien ainsi qu'il faut voir la progression du semestre : un lien donne une liste, deux donnent un arbre, un nombre quelconque donnera un graphe.

Par tableau. Pour un arbre complet — tous les niveaux remplis sauf peut-être le dernier, comblé de gauche à droite — on peut se passer de pointeurs :

1indice        0     1     2     3     4     5     62           ┌─────┬─────┬─────┬─────┬─────┬─────┬─────┐3           │  A  │  B  │  C  │  D  │  E  │  F  │  G  │4           └─────┴─────┴─────┴─────┴─────┴─────┴─────┘5 6enfants de i :  2i+1  et  2i+2          parent de i :  (i−1) / 2

Aucun pointeur, une mémoire parfaitement contiguë — donc les bénéfices de cache du chapitre 5 — et la navigation par arithmétique. La contrepartie est stricte : cela ne fonctionne que si l'arbre reste complet, faute de quoi le tableau se troue. C'est exactement la représentation du tas au chapitre suivant, et c'est ce qui explique son efficacité.

Les quatre parcours

Un parcours visite tous les nœuds une fois. Il y en a quatre, et il faut les connaître par ce qu'ils produisent, pas seulement par leur nom.

Les trois premiers sont des parcours en profondeur, et leur code est identique à une ligne près :

1préfixe(A)              infixe(A)               suffixe(A)2    si A vide, sortir       si A vide, sortir       si A vide, sortir3    VISITER(A)              infixe(A.gauche)        suffixe(A.gauche)4    préfixe(A.gauche)       VISITER(A)              suffixe(A.droit)5    préfixe(A.droit)        infixe(A.droit)         VISITER(A)

C'est la position de la visite qui change, et rien d'autre. Sur cet arbre :

1                +2             ┌──┴──┐3             3     ×4                ┌──┴──┐5                4     2

Le quatrième est le parcours en largeur : on visite niveau par niveau, de gauche à droite, soit + 3 × 4 2 ici. Il ne s'écrit pas récursivement — il emploie une file, exactement celle du chapitre 6 : on enfile la racine, puis tant que la file n'est pas vide on défile un nœud, on le visite, et on enfile ses deux enfants.

Et si l'on remplace cette file par une pile, on obtient le parcours en profondeur préfixe. Le code est le même à un mot près, et c'est la remarque annoncée au chapitre précédent : la structure choisie décide de l'ordre de visite.

L'arbre d'expression

C'est l'application qui justifie le chapitre, et elle referme la boucle avec le chapitre 6.

Dans un arbre d'expression, les feuilles portent les opérandes et les nœuds internes les opérateurs. Sa construction résout la question des priorités une fois pour toutes : dans 3 + 4 × 2, la multiplication devient un sous-arbre de l'addition, donc elle sera évaluée avant, sans qu'aucune règle de priorité n'intervienne à l'évaluation.

L'évaluation elle-même est une récursion suffixe de quatre lignes :

1fonction évaluer(A)2    si A est une feuille alors retourner sa valeur3    g ← évaluer(A.gauche)4    d ← évaluer(A.droit)5    retourner appliquer(A.opérateur, g, d)

Les deux appels doivent précéder l'application : c'est un parcours suffixe, et c'est pourquoi la notation postfixée du chapitre 6 s'évaluait si simplement à la pile. Les deux mécanismes sont le même : la pile de l'évaluateur postfixé est la pile d'appels de cette récursion.

Un compilateur fait exactement ce chemin. Il lit le texte, construit l'arbre — c'est l'analyse syntaxique — puis le parcourt pour produire les instructions machine du chapitre 6 d'architecture, en émettant les opérandes avant l'opération. La suite d'instructions add $t0, $t1, $t2 que vous y écriviez à la main est la sortie d'un parcours suffixe.

À vous

L'exercice construit un arbre d'expression, puis met en évidence que les trois parcours en profondeur ne diffèrent que d'une ligne : vous écrirez une seule fonction paramétrée par la position de la visite, et vous obtiendrez les trois notations.

Ensuite l'évaluation, puis le parcours en largeur à la file — et enfin la manipulation qui convainc : remplacer la file par une pile dans le même code, et constater que le parcours devient un parcours en profondeur.

Le squelette contient aussi le calcul de la hauteur et de la taille, deux récursions de deux lignes qui servent d'échauffement, et dont vous vérifierez qu'elles respectent l'encadrement posé plus haut.

const noeud = (valeur, gauche = null, droit = null) => ({ valeur, gauche, droit });

// L'arbre de  3 + 4 * 2  : la multiplication est PLUS BAS que l'addition,
// donc elle sera évaluée avant. La priorité est devenue de la structure.
const EXPR = noeud("+", noeud(3), noeud("*", noeud(4), noeud(2)));

// ── Les trois parcours en profondeur, en une seule fonction ───────────────
// position vaut "prefixe", "infixe" ou "suffixe".
function profondeur(A, position, sortie = []) {
  if (A === null) return sortie;
  if (position === "prefixe") sortie.push(A.valeur);
  profondeur(A.gauche, position, sortie);
  // ← à écrire : la visite infixe se place ICI
  profondeur(A.droit, position, sortie);
  // ← et la visite suffixe LÀ
  return sortie;
}

// ── Hauteur et taille ─────────────────────────────────────────────────────
function hauteur(A) {
  if (A === null) return -1;   // un arbre vide a une hauteur de −1
  return 0;   // ← à écrire : 1 + le max des hauteurs des deux sous-arbres
}

function taille(A) {
  if (A === null) return 0;
  return 1 + taille(A.gauche) + taille(A.droit);
}

// ── Évaluation ────────────────────────────────────────────────────────────
function evaluer(A) {
  if (A.gauche === null && A.droit === null) return A.valeur;
  const g = evaluer(A.gauche);
  const d = evaluer(A.droit);
  const ops = { "+": (a, b) => a + b, "-": (a, b) => a - b,
                "*": (a, b) => a * b, "/": (a, b) => a / b };
  return ops[A.valeur](g, d);
}

// ── Parcours en largeur, et son jumeau ────────────────────────────────────
// Une SEULE différence entre les deux : on retire par le début ou par la fin.
function parcours(A, parLeDebut) {
  const attente = [A], sortie = [];
  while (attente.length > 0) {
    const n = parLeDebut ? attente.shift() : attente.pop();
    sortie.push(n.valeur);
    if (n.gauche) attente.push(n.gauche);
    if (n.droit) attente.push(n.droit);
  }
  return sortie;
}

// ── À VOUS ────────────────────────────────────────────────────────────────
// 1. Complétez profondeur() et hauteur().
// 2. Vérifiez l'encadrement : log2(n+1) − 1 ≤ h ≤ n − 1.
// 3. Comparez parcours(A, true) et parcours(A, false). Lequel est en
//    largeur ? Lequel retrouve un parcours en profondeur, et lequel ?

console.log("préfixe :", profondeur(EXPR, "prefixe").join(" "));
console.log("évaluation :", evaluer(EXPR), "(et non 14)");

En travaux pratiques

Ce que la suite en fait

Le chapitre 8 impose un invariant sur les valeurs — un ordre pour l'arbre binaire de recherche, une priorité pour le tas — et c'est cet invariant qui transforme une structure de rangement en structure de recherche. On y verra que l'accès en $O(\log n)$ est conditionnel : il suppose que la hauteur reste logarithmique, ce que l'encadrement de ce chapitre ne garantit pas du tout.

La représentation par tableau y trouvera son emploi : le tas est précisément l'arbre complet pour lequel elle a été inventée, et c'est ce qui permet un tri en $n \log n$ sur place, la combinaison que ni le tri fusion ni le tri rapide n'offraient.

À retenir