Algorithmique 2 · C4 Arbres · Chapitre 2 · 5 h

Arbres de recherche et tas

ABR : insertion, recherche, suppression, dégénérescence et équilibrage en survol ; tas binaire, file de priorité et tri par 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.

Quiz · 1 question

On insère les entiers de 1 à 1000 dans l'ordre croissant dans un arbre binaire de recherche non équilibré, puis on cherche la valeur 1000. Combien de comparaisons ?

Environ 10, soit log₂(1000) : c'est la promesse d'un arbre de recherche — log n
1000 : chaque valeur étant supérieure à toutes les précédentes, l'arbre est une chaîne descendant à droite, et la recherche parcourt tous les nœuds — n
Environ 500, la moitié des nœuds en moyenne — n/2

Réponse : C'est la dégénérescence, et le cas est loin d'être théorique — les données triées sont extrêmement fréquentes. Chaque nouvelle valeur étant supérieure à toutes les précédentes, l'insertion part à droite à chaque comparaison et se pose comme enfant droit du dernier inséré. L'arbre obtenu est une CHAÎNE de hauteur 999, c'est-à-dire une liste chaînée dont chaque nœud gaspille un pointeur gauche. La recherche de 1000 descend donc les mille niveaux. La promesse en log n n'est PAS une propriété de l'ABR : c'est une propriété des arbres ÉQUILIBRÉS, et il faut un mécanisme — rotations AVL ou rouge-noir — pour l'obtenir. C'est la même leçon qu'au chapitre 3 avec le pivot du tri rapide.

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.

	Fusion	Rapide	Par tas
Pire cas	$n \log n$	$n^2$	$n \log n$
Mémoire	$O(n)$	$O(\log n)$	$O(1)$
Stable	oui	non	non

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.

Quiz · 1 question

Vous devez maintenir en permanence l'élément le plus prioritaire d'un ensemble où l'on insère et retire sans cesse. Un ABR équilibré ou un tas ?

Un ABR équilibré : il donne aussi le minimum, et il sait en plus rechercher une valeur quelconque — ABR équilibré
Un tas : le minimum est à la racine en O(1) et son invariant, beaucoup plus faible, est bien moins coûteux à maintenir — l'ABR n'est utile que si l'on cherche aussi des valeurs quelconques — tas
Un tableau trié : l'insertion y est certes O(n), mais le minimum est immédiat — tableau trié

Réponse : Les deux structures font le travail, mais le tas le fait moins cher. Son invariant est purement VERTICAL — un nœud est inférieur à ses enfants, rien n'est imposé entre frères — donc une insertion ne demande qu'une remontée le long d'une branche, sans rotation ni restructuration. L'ABR, lui, impose un ordre total lisible par parcours infixe, ce qui coûte des rotations à chaque modification pour rester équilibré. Le tas gagne aussi sur la mémoire : arbre complet, donc tableau contigu, aucun pointeur. Le seul argument en faveur de l'ABR serait de devoir AUSSI chercher une valeur quelconque — chose qu'un tas fait en O(n), puisque rien n'oriente la descente. Le tableau trié, lui, paie O(n) à chaque insertion par le décalage.

À 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.

Exercice de code

Mesurez la dégénérescence d'un ABR, puis écrivez la remontée d'un tas et le tri par tas.

Point de départ

// ── 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));

Solution

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;
}

function chercher(A, v) {
  let n = 0;
  while (A !== null) {
    n++;
    if (v === A.v) return n;
    A = v < A.v ? A.g : A.d;
  }
  return -n;
}

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

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;
}

function creerTas() {
  const T = [];
  const parent = (i) => Math.floor((i - 1) / 2);

  function remonter(i) {
    // Symétrique exacte de descendre : tant que l'invariant est violé avec
    // le parent, on échange et on remonte d'un niveau. Au plus log2(n) tours.
    while (i > 0 && T[i] < T[parent(i)]) {
      const p = parent(i);
      [T[i], T[p]] = [T[p], T[i]];
      i = p;
    }
  }

  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],
    invariantOk() {
      for (let i = 1; i < T.length; i++) if (T[parent(i)] > T[i]) return false;
      return true;
    },
  };
}

function triParTas(tableau) {
  const tas = creerTas();
  for (const v of tableau) tas.inserer(v);
  const sortie = [];
  while (tas.taille() > 0) sortie.push(tas.extraireMin());
  return sortie;
}

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(" "), "  (trié, sans avoir trié)");
console.log("est ABR :", estUnAbr(A), "| hauteur", hauteur(A));

console.log("");
console.log("— l'argument du chapitre : hauteur selon l'ordre d'insertion —");
const N = 1000;
const valeurs = Array.from({ length: N }, (_, i) => i);
const melange = [...valeurs].sort(() => Math.random() - 0.5);

for (const [nom, source] of [["aléatoire", melange], ["déjà triée", valeurs]]) {
  let R = null;
  for (const v of source) R = inserer(R, v);
  const h = hauteur(R);
  const c = Math.abs(chercher(R, N - 1));
  console.log("   insertion " + nom.padEnd(12) + " -> hauteur " + String(h).padStart(4) +
    " | chercher " + (N - 1) + " coûte " + String(c).padStart(4) + " comparaisons" +
    "   (log2(" + N + ") ≈ " + Math.round(Math.log2(N)) + ")");
}
// Un facteur cent sur la même structure et les mêmes valeurs : seul l'ordre
// d'insertion change. C'est pourquoi les bibliothèques n'exposent jamais
// d'ABR nu, mais des arbres auto-équilibrés.

console.log("");
console.log("— tas —");
const tas = creerTas();
for (const v of [9, 4, 7, 1, 8, 3, 2]) {
  tas.inserer(v);
  if (!tas.invariantOk()) console.log("   INVARIANT CASSÉ après insertion de " + v);
}
console.log("   contenu du tableau :", tas.contenu().join(" "), " (pas trié, et ce n'est pas le but)");
console.log("   invariant tenu     :", tas.invariantOk());
const extraits = [];
while (tas.taille() > 0) extraits.push(tas.extraireMin());
console.log("   extractions        :", extraits.join(" "), " (triées, elles)");

console.log("");
console.log("tri par tas :", triParTas([5, 2, 9, 1, 7, 3]).join(" "));

En travaux pratiques

Travaux pratiques 8 · 3 h

L'arbre qui dégénère, et le tas qui n'en a pas le droit

Constater qu'un arbre de recherche peut perdre tout son intérêt sur une entrée ordinaire, puis implémenter le tas, qui garantit sa forme par construction.

Avant de commencer

Le TP 7 : arbres et parcours
Le TP 3 : mesures comparatives

Énoncé

L'arbre de recherche — Implémentez insertion, recherche et parcours infixe. Insérez mille valeurs aléatoires et vérifiez que le parcours infixe donne une suite triée.
Mesurer la hauteur — Mesurez la hauteur après insertion de 1000, 10 000 et 100 000 valeurs aléatoires. Comparez au logarithme en base deux de n.
Le faire dégénérer — Insérez les mêmes valeurs, mais TRIÉES. Mesurez à nouveau la hauteur et le temps de recherche. Dessinez l'arbre obtenu pour cinq valeurs. Indice : Vous venez de construire une liste chaînée avec deux fois plus de pointeurs.
La suppression — Écrivez la suppression, en traitant les trois cas : feuille, un enfant, deux enfants. Le troisième est le seul difficile.
Le tas — Implémentez un tas binaire dans un TABLEAU, avec insertion et extraction du minimum. Vérifiez l'invariant après chaque opération.
Pourquoi un tableau — Écrivez les formules donnant père, fils gauche et fils droit à partir d'un indice. Expliquez pourquoi elles ne fonctionnent que sur un arbre complet.
Le tri par tas — Écrivez le tri par tas et comparez-le au tri rapide du TP 3, sur entrée aléatoire ET sur entrée triée.
La file de priorité — Emballez votre tas dans une file de priorité avec une valeur et une priorité. Vous l'utiliserez telle quelle au TP 9.

C'est réussi quand

Votre parcours infixe donne une suite triée sur mille insertions aléatoires
Vous exhibez l'entrée qui rend votre arbre de hauteur n − 1
Votre tas maintient son invariant, vérifié automatiquement après chaque opération
Le tri par tas ne dégénère PAS sur l'entrée triée, contrairement au tri rapide

Correction

La hauteur mesurée

n         aléatoire   log2(n)   TRIÉE
1 000        21          10          999
10 000       31          13        9 999
100 000      42          17       99 999

recherche sur 100 000, entrée triée : 100 000 comparaisons
au lieu de 17

Sur entrée aléatoire, la hauteur vaut environ 2,2 fois log2(n) : le comportement est bon sans aucune garantie. Sur entrée triée, l'arbre devient une liste — et l'entrée triée n'est pas un cas tordu, c'est le cas le plus courant qui soit : des identifiants croissants, des dates, une reprise de sauvegarde.

La suppression, et son cas difficile

Noeud *supprimer(Noeud *n, int v) {
  if (!n) return NULL;
  if (v < n->valeur)      n->g = supprimer(n->g, v);
  else if (v > n->valeur) n->d = supprimer(n->d, v);
  else {
      if (!n->g) { Noeud *d = n->d; free(n); return d; }   /* 0 ou 1 fils */
      if (!n->d) { Noeud *g = n->g; free(n); return g; }
      /* DEUX fils : remplacer par le successeur infixe */
      Noeud *s = n->d;
      while (s->g) s = s->g;          /* le plus petit du sous-arbre droit */
      n->valeur = s->valeur;
      n->d = supprimer(n->d, s->valeur);
  }
  return n;
}

Le cas à deux fils est le seul délicat : on ne peut pas simplement raccrocher, il faut choisir un remplaçant qui préserve la propriété d'ordre. Le successeur infixe convient parce qu'il est, par construction, plus grand que tout le sous-arbre gauche et plus petit que le reste du droit. Le prédécesseur conviendrait tout aussi bien.

Le tas dans un tableau

pour un nœud d'indice i (à partir de 0) :
  père      = (i - 1) / 2
  fils gauche = 2i + 1
  fils droit  = 2i + 2

t = [1, 3, 5, 7, 9, 8]
              1
            /   \
           3     5
          / \   /
         7   9 8

Aucun pointeur, aucune allocation : la structure de l'arbre est dans l'ARITHMÉTIQUE des indices. Cela n'est possible que parce qu'un tas est un arbre COMPLET — aucun trou —, ce qui est garanti par construction : on insère toujours à la première place libre. Un arbre de recherche, lui, a des trous, et ne peut pas être rangé ainsi.

Insertion et extraction

void inserer(Tas *t, int v) {
  int i = t->n++;
  t->d[i] = v;
  while (i > 0 && t->d[(i-1)/2] > t->d[i]) {     /* remonter */
      echanger(&t->d[i], &t->d[(i-1)/2]);
      i = (i-1)/2;
  }
}

int extraire_min(Tas *t) {
  int min = t->d[0];
  t->d[0] = t->d[--t->n];
  int i = 0;
  while (1) {                                     /* redescendre */
      int g = 2*i+1, d = 2*i+2, p = i;
      if (g < t->n && t->d[g] < t->d[p]) p = g;
      if (d < t->n && t->d[d] < t->d[p]) p = d;
      if (p == i) break;
      echanger(&t->d[i], &t->d[p]);
      i = p;
  }
  return min;
}

Les deux opérations parcourent une seule branche : O(log n) garanti, sans cas moyen ni pire cas distincts. L'invariant du tas est plus FAIBLE que celui de l'ABR — il n'ordonne qu'entre père et fils, pas entre frères — et c'est exactement ce qui permet de le maintenir en gardant l'arbre complet. Moins de garanties, mais garanties toujours.

Le tri par tas, et pourquoi il ne dégénère pas

n = 1 000 000      aléatoire   TRIÉE
tri rapide          0,10 s      24 s (ou plantage)
tri par tas         0,18 s      0,18 s
tri fusion          0,14 s      0,12 s

le tri par tas est O(n log n) dans TOUS les cas,
sur place, sans mémoire supplémentaire

Presque deux fois plus lent que le tri rapide en moyenne — mauvaise localité, beaucoup de sauts dans le tableau — et jamais catastrophique. C'est pourquoi la bibliothèque standard du C++ utilise l'introsort : tri rapide par défaut, bascule vers le tri par tas si la profondeur dépasse 2 log n. On obtient la vitesse du premier avec la garantie du second.

La file de priorité

typedef struct { int sommet; int priorite; } Element;

/* même tas, comparaison sur .priorite */
void   fp_inserer(FilePrio *f, int sommet, int priorite);
Element fp_extraire_min(FilePrio *f);
int     fp_vide(const FilePrio *f);

C'est la structure dont Dijkstra a besoin au TP 9 : extraire à chaque étape le sommet non traité le plus proche. Avec un tas, chaque extraction coûte log n au lieu de n — ce qui fait passer l'algorithme de O(n²) à O((n+m) log n), et rend calculable un réseau de plusieurs centaines de milliers de sommets.

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

Flashcards · 6 cartes

Énoncez l'invariant d'un ABR, et l'erreur classique.: Pour TOUT nœud : toutes les valeurs de son sous-arbre gauche lui sont inférieures, toutes celles de son sous-arbre droit lui sont supérieures. L'erreur classique est de ne comparer qu'aux enfants IMMÉDIATS : l'invariant porte sur tout le sous-arbre. Conséquence utile : un parcours infixe énumère les valeurs dans l'ordre croissant, quel que soit l'ordre d'insertion.
Quels sont les trois cas de la suppression dans un ABR ?: FEUILLE : on la détache. UN ENFANT : on remplace le nœud par cet enfant, qui remonte avec son sous-arbre. DEUX ENFANTS : on cherche le SUCCESSEUR — la plus petite valeur du sous-arbre droit, en descendant tout à gauche —, on copie sa valeur dans le nœud, et on supprime le successeur, qui a au plus un enfant par construction. Le successeur convient parce qu'il est la plus petite valeur supérieure au nœud : l'invariant est préservé des deux côtés.
Pourquoi un ABR dégénère-t-il, et quelle est la parade ?: Parce que les opérations coûtent O(h) et que h va de log₂ n à n−1. Insérer des données DÉJÀ TRIÉES produit une chaîne : chaque valeur part à droite, l'arbre devient une liste avec un pointeur perdu par nœud. C'est le pire cas du tri rapide, pour la même raison — une division systématiquement déséquilibrée. Parade : l'équilibrage automatique (AVL, rouge-noir) par ROTATIONS, réarrangements locaux qui préservent l'invariant et garantissent O(log n).
Quel est l'invariant d'un tas min, et qu'autorise sa faiblesse ?: 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 bien plus faible que celui de l'ABR. Conséquences : le minimum est à la racine en O(1), et comme aucun ordre horizontal n'est requis, on peut exiger en plus que l'arbre soit COMPLET — d'où la représentation par tableau, sans un seul pointeur, avec les enfants de i en 2i+1 et 2i+2.
Décrivez insertion et extraction dans un tas.: INSÉRER : placer la valeur à la première case libre (la fin du tableau) pour garder l'arbre complet, puis la faire REMONTER tant qu'elle est inférieure à son parent — au plus log₂ n échanges. EXTRAIRE LE MINIMUM : prendre la racine, y mettre le DERNIER élément pour rester complet, puis le faire DESCENDRE en l'échangeant avec le plus petit de ses enfants tant qu'il est plus grand — au plus log₂ n échanges. C'est la file de priorité.
Pourquoi le tri par tas n'est-il pas le tri par défaut, alors qu'il est garanti n log n et sur place ?: Parce qu'il est plus lent en pratique que le tri rapide : ses accès sautent de l'indice i à 2i+1, donc à travers tout le tableau, ce qui ruine la localité spatiale, alors que le tri rapide avance séquentiellement. Sa place réelle est celle de FILET DE SÉCURITÉ dans 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.