Arbres de recherche et tas

Le chapitre 7 a donné une structure de rangement. Il lui manque ce qui fait l'intérêt d'un arbre : un invariant sur les valeurs. Deux invariants différents produisent deux structures aux usages opposés, et c'est tout ce chapitre.

L'arbre binaire de recherche ordonne de gauche à droite : il répond à « cette valeur est-elle là ? » en $O(\log n)$. Le tas ordonne de haut en bas : il répond à « quelle est la plus petite valeur ? » en $O(1)$, et permet de la retirer en $O(\log n)$.

Aucun des deux ne fait le travail de l'autre, et c'est le point à retenir : un tas ne sait pas chercher, un ABR ne sait pas donner son minimum rapidement.

L'arbre binaire de recherche

L'invariant d'ABR porte sur tout nœud, sans exception : toutes les valeurs de son sous-arbre gauche lui sont inférieures, toutes celles de son sous-arbre droit lui sont supérieures.

1                 82              ┌──┴──┐3              3     104           ┌──┴─┐     └──┐5           1    6        146              ┌─┴┐     ┌─┘7              4  7    13

L'erreur classique est de croire qu'il suffit de comparer un nœud à ses enfants immédiats. L'invariant porte sur tout le sous-arbre : placer un 9 comme enfant gauche du 10 violerait la propriété, puisque 9 est supérieur à 8 et se trouverait dans son sous-arbre gauche.

La recherche exploite l'invariant pour éliminer la moitié de l'arbre à chaque comparaison : si la valeur cherchée est inférieure au nœud, elle ne peut être qu'à gauche. C'est la dichotomie du chapitre 4, appliquée à une structure chaînée, et son coût est $O(h)$.

L'insertion suit le même chemin et accroche la nouvelle valeur là où la recherche a échoué, c'est-à-dire toujours comme feuille. C'est ce qui la rend simple : aucune restructuration.

La suppression est la seule opération délicate, avec ses trois cas :

• Feuille : on la détache, c'est tout.
• Un seul enfant : on remplace le nœud par cet enfant, qui remonte avec son sous-arbre.
• Deux enfants : on ne peut détacher ni remplacer directement. On cherche le successeur — la plus petite valeur du sous-arbre droit, obtenue en descendant tout à gauche —, on copie sa valeur dans le nœud à supprimer, et l'on supprime le successeur, qui par construction a au plus un enfant. On se ramène donc toujours à l'un des deux premiers cas.

Le successeur convient parce qu'il est la plus petite valeur supérieure au nœud : le placer là préserve exactement l'invariant, à gauche comme à droite.

La dégénérescence

Toutes ces opérations coûtent $O(h)$, et le chapitre 7 a montré que $h$ va de $\log_2 n$ à $n-1$. Il reste à savoir dans quel cas on tombe.

Or le pire cas n'a rien d'exotique. Insérer des données déjà triées produit une chaîne : chaque valeur étant supérieure à toutes les précédentes, elle part systématiquement à droite, et l'arbre devient une liste chaînée avec un pointeur inutilisé par nœud.

1insertion de 1, 2, 3, 4, 5 dans cet ordre2 3   14    └─ 25        └─ 36            └─ 47                └─ 5        hauteur 4 pour 5 nœuds : recherche en O(n)

C'est exactement le pire cas du tri rapide du chapitre 3, et pour la même raison de fond : une structure qui repose sur une division en deux moitiés s'effondre quand la division est systématiquement déséquilibrée. Et dans les deux cas, les données triées — le cas le plus fréquent en pratique — sont précisément celles qui déclenchent le désastre.

La parade porte un nom : l'équilibrage automatique. Les arbres AVL et rouge-noir maintiennent une hauteur en $O(\log n)$ garantie, en effectuant après chaque insertion ou suppression des rotations — des réarrangements locaux de trois nœuds qui préservent l'invariant tout en réduisant la hauteur.

1        3                          22       ╱          rotation        ╱ ╲3      2          ─────────►      1   34     ╱5    1

Le principe suffit à ce niveau : le coût est une constante ajoutée à chaque modification, en échange d'une garantie qui transforme un $O(n)$ possible en $O(\log n)$ certain. C'est ce que font les TreeMap de Java, les map de C++ et les index de bases de données — sous une variante à plus de deux enfants, l'arbre B, conçue pour minimiser les accès disque du chapitre 7 du cours de systèmes.

Le tas binaire

Le tas (heap) répond à un autre besoin : non pas « où est cette valeur ? » mais « quelle est la plus prioritaire ? ».

Son invariant est vertical. Dans un tas min, tout nœud est inférieur ou égal à ses deux enfants. Rien n'est imposé entre frères, ni entre branches — c'est un ordre beaucoup plus faible que celui de l'ABR, et c'est ce qui le rend bon marché à maintenir.

Deux conséquences immédiates. Le minimum est à la racine, donc accessible en $O(1)$. Et comme aucun ordre n'est imposé horizontalement, on peut exiger en plus que l'arbre soit complet — ce qui autorise la représentation par tableau du chapitre 7, sans un seul pointeur.

1        2                    indice   0   1   2   3   4   52      ┌─┴─┐                          ┌───┬───┬───┬───┬───┬───┐3      4   3                          │ 2 │ 4 │ 3 │ 9 │ 7 │ 5 │4    ┌─┴┐  └┐                         └───┴───┴───┴───┴───┴───┘5    9  7   5                enfants de i : 2i+1 et 2i+2

Deux opérations suffisent, et elles sont symétriques.

Insérer : on place la valeur à la première case libre — la fin du tableau —, ce qui garde l'arbre complet mais casse peut-être l'invariant. On la fait alors remonter tant qu'elle est inférieure à son parent. Au plus $h = \log_2 n$ échanges.

Extraire le minimum : on prend la racine, on met le dernier élément à sa place — pour garder l'arbre complet —, puis on le fait descendre en l'échangeant à chaque étape avec le plus petit de ses enfants, tant qu'il est plus grand. Au plus $\log_2 n$ échanges là aussi.

C'est la file de priorité : une file où l'on ne sort pas le plus ancien mais le plus prioritaire. Le cours de systèmes en avait besoin sans la nommer — l'ordonnancement par priorités du chapitre 4 est exactement cela — et le chapitre 9 s'en servira pour l'algorithme de Dijkstra.

Le tri par tas

De là découle un troisième tri en $n \log n$, et il complète le tableau du chapitre 3.

On construit un tas avec les $n$ valeurs, puis on extrait le minimum $n$ fois : les valeurs sortent triées. Chaque extraction coûte $O(\log n)$, d'où $O(n \log n)$.

Sa singularité est d'être sur place. On construit le tas dans le tableau lui-même, et chaque valeur extraite se range à la place libérée à la fin — d'où l'usage d'un tas max pour obtenir un ordre croissant.

Le tri par tas est donc le seul à être à la fois garanti en $n \log n$ et sans mémoire supplémentaire. Pourquoi n'est-il pas le tri par défaut ? Parce qu'il est plus lent en pratique que le tri rapide : ses accès sautent d'un indice $i$ à $2i+1$, donc à travers tout le tableau, ce qui ruine la localité spatiale du chapitre 7 d'architecture. Le tri rapide, lui, avance séquentiellement.

D'où sa place réelle, annoncée au chapitre 3 : c'est le filet de sécurité d'introsort. On trie rapide, et si la profondeur de récursion dérape — signe d'un mauvais pivot — on bascule sur le tri par tas, qui n'a pas de pire cas. On obtient la vitesse de l'un et la garantie de l'autre.

À vous

L'exercice construit les deux structures, et l'essentiel est dans la mesure.

Pour l'ABR : insérer mille valeurs aléatoires, mesurer la hauteur, puis insérer les mêmes valeurs triées et mesurer à nouveau. L'écart entre une dizaine et mille est l'argument le plus convaincant du chapitre en faveur de l'équilibrage.

Pour le tas : écrire la remontée et la descente, vérifier l'invariant après chaque opération — une fonction de vérification est fournie, servez-vous-en, c'est ainsi qu'on débogue une structure — puis en tirer un tri par tas et compter ses comparaisons.

// ── Arbre binaire de recherche ────────────────────────────────────────────
const noeud = (v) => ({ v, g: null, d: null });

function inserer(A, v) {
  if (A === null) return noeud(v);
  if (v < A.v) A.g = inserer(A.g, v);
  else if (v > A.v) A.d = inserer(A.d, v);
  return A;   // les doublons sont ignorés
}

function chercher(A, v, comparaisons = { n: 0 }) {
  while (A !== null) {
    comparaisons.n++;
    if (v === A.v) return comparaisons.n;
    A = v < A.v ? A.g : A.d;
  }
  return -comparaisons.n;   // négatif : absent, après n comparaisons
}

function hauteur(A) { return A === null ? -1 : 1 + Math.max(hauteur(A.g), hauteur(A.d)); }

// L'invariant porte sur TOUT le sous-arbre, pas sur les enfants immédiats :
// on transmet donc un intervalle autorisé, qui se resserre à la descente.
function estUnAbr(A, min = -Infinity, max = Infinity) {
  if (A === null) return true;
  if (A.v <= min || A.v >= max) return false;
  return estUnAbr(A.g, min, A.v) && estUnAbr(A.d, A.v, max);
}

function infixe(A, sortie = []) {
  if (A === null) return sortie;
  infixe(A.g, sortie); sortie.push(A.v); infixe(A.d, sortie);
  return sortie;
}

// ── Tas min, par tableau ──────────────────────────────────────────────────
function creerTas() {
  const T = [];
  const parent = (i) => Math.floor((i - 1) / 2);

  function remonter(i) {
    // ← à écrire : tant que T[i] est inférieur à son parent, échanger
  }

  function descendre(i) {
    while (true) {
      const g = 2 * i + 1, d = 2 * i + 2;
      let plusPetit = i;
      if (g < T.length && T[g] < T[plusPetit]) plusPetit = g;
      if (d < T.length && T[d] < T[plusPetit]) plusPetit = d;
      if (plusPetit === i) return;
      [T[i], T[plusPetit]] = [T[plusPetit], T[i]];
      i = plusPetit;
    }
  }

  return {
    inserer(v) { T.push(v); remonter(T.length - 1); },
    extraireMin() {
      if (T.length === 0) return undefined;
      const min = T[0];
      const dernier = T.pop();
      if (T.length > 0) { T[0] = dernier; descendre(0); }
      return min;
    },
    taille: () => T.length,
    contenu: () => [...T],
    // L'outil de débogage d'une structure : vérifier l'invariant.
    invariantOk() {
      for (let i = 1; i < T.length; i++) if (T[parent(i)] > T[i]) return false;
      return true;
    },
  };
}

// ── À VOUS ────────────────────────────────────────────────────────────────
// 1. Écrivez remonter().
// 2. Mesurez la hauteur d'un ABR de 1000 valeurs aléatoires, puis triées.
// 3. Écrivez triParTas(tableau) : tout insérer, tout extraire.

let A = null;
for (const v of [8, 3, 10, 1, 6, 14, 4, 7, 13]) A = inserer(A, v);
console.log("infixe :", infixe(A).join(" "), "| est un ABR :", estUnAbr(A));
console.log("hauteur :", hauteur(A));

En travaux pratiques

Ce que la suite en fait

Le bloc V généralise une dernière fois. Un arbre est un graphe sans cycle et avec une racine ; retirer ces deux contraintes donne l'objet du chapitre 9, où les parcours du chapitre 7 reviennent — mais avec une difficulté nouvelle, puisqu'un graphe peut ramener sur un sommet déjà visité et qu'il faut marquer.

Le tas y jouera un rôle précis. L'algorithme de Dijkstra a besoin, à chaque étape, du sommet non traité le plus proche : c'est une extraction de minimum, et c'est le passage d'une recherche linéaire à une file de priorité qui fait descendre son coût.

À retenir