Arbres de recherche, tas et files de priorité

Cours complet · informatique (MP2I/MPI), chapitre 11 · MP2I et MPI

Travailler ce chapitre sur Adloun Exercices corrigés de ce chapitre

11.1 Deux invariants, deux structures

Le chapitre précédent s'est achevé sur une inégalité : la hauteur d'un arbre à $n$ nœuds est comprise entre $Θ (lo g n)$ et $n - 1$ . Comme toutes les opérations coûtent $O (h)$ , il ne suffit pas d'avoir un arbre : il faut y maintenir un invariant qui l'empêche de dégénérer, et qui réponde à la question qu'on lui pose.

Ce chapitre présente deux invariants, et ils sont différents parce que les questions le sont.

	Arbre binaire de recherche	Tas
Invariant	gauche $<$ racine $<$ droit	racine $\leq$ ses deux fils
Question	« $x$ est-il présent ? »	« quel est le minimum ? »
Forme	quelconque, à équilibrer	toujours complet

Un tas ne sait pas chercher un élément quelconque ; un arbre de recherche ne donne pas son minimum en $O (1)$ . Le chapitre chap:abstraction l'annonçait : une structure ne répond bien qu'aux questions pour lesquelles elle est faite.

11.2 L'arbre binaire de recherche

Définition 11.1Invariant d'ABR

Un arbre binaire étiqueté par un ensemble totalement ordonné est un arbre binaire de recherche si, en tout nœud d'étiquette $e$ :

toutes les étiquettes du sous-arbre gauche sont $< e$ ;
toutes celles du sous-arbre droit sont $> e$ .

Le programme note « l'importance de munir l'ensemble des clés d'un ordre total » : sans comparabilité de deux clés quelconques, la descente n'a pas de sens.

AttentionL'invariant porte sur tout le sous-arbre, pas sur les fils

C'est la faute classique. L'arbre ci-dessous vérifie la condition en chaque nœud pris avec ses deux fils immédiats, et n'est pourtant pas un ABR :

$9 > 3$ le place bien à droite de $3$ , mais il est dans le sous-arbre gauche de $8$ , où tout doit être $< 8$ . Une recherche de $9$ partirait à droite et ne le trouverait jamais.

◆Théorème 11.2Le parcours infixe d'un ABR est trié

Pour tout arbre binaire de recherche $a$ , la liste infixe a est strictement croissante.

Démonstration

Par induction structurelle. Pour $Vide$ , la liste vide est triée.

Soit $a = N œ ud (g, e, d)$ un ABR. Alors $g$ et $d$ en sont aussi, donc par hypothèse d'induction infixe g et infixe d sont triées. Le parcours infixe rend leur concaténation avec $e$ au milieu. Or toutes les étiquettes de $g$ sont $< e$ et toutes celles de $d$ sont $> e$ : la liste obtenue est donc croissante à la jonction comme à l'intérieur de chaque morceau.

ImportantUne caractérisation qui donne un test

Ce théorème fournit la manière la plus sûre de vérifier qu'un arbre est un ABR : parcourir en infixe et contrôler que la suite croît. C'est en $Θ (n)$ , et cela teste l'invariant global, là où une vérification nœud par nœud laisserait passer le contre-exemple ci-dessus.

11.2.1 Rechercher, insérer


(* Renvoie true si x figure dans l'ABR a. Complexité : O(h). *)
let rec appartient x = function
  | Vide -> false
  | Noeud (g, e, d) ->
      if x = e then true
      else if x < e then appartient x g       (* tout ce qui est > e est à droite *)
      else appartient x d

(* Renvoie l'ABR obtenu en insérant x ; si x y figure déjà, renvoie a inchangé. *)
let rec insere x = function
  | Vide -> Noeud (Vide, x, Vide)             (* on insère TOUJOURS en feuille *)
  | Noeud (g, e, d) as a ->
      if x = e then a
      else if x < e then Noeud (insere x g, e, d)
      else Noeud (g, e, insere x d)

Démonstration (Correction de `appartient`)

Par induction structurelle. Sur $Vide$ : l'arbre ne contient rien, false est correct. Sur $N œ ud (g, e, d)$ : si $x = e$ , correct. Si $x < e$ , alors par l'invariant $x$ ne peut pas être dans $d$ , dont toutes les étiquettes valent plus que $e$ , donc plus que $x$ ; chercher dans $g$ seul est donc exhaustif, et l'hypothèse d'induction conclut. Cas $x > e$ symétrique.

iRemarqueLe style fonctionnel ne copie que le chemin

insere ne modifie rien : elle construit un nouvel arbre. Mais elle ne recopie que les nœuds du chemin de la racine à l'insertion — $O (h)$ nœuds — et partage tous les autres sous-arbres avec l'original. L'ancien arbre reste valide, le nouveau existe, et le coût reste $O (h)$ en temps comme en mémoire. C'est le partage gratuit qu'achète l'immuabilité (chapitre chap:abstraction).

11.2.2 Le problème : l'arbre dégénère

AttentionInsérer des données triées produit un peigne

Ce n'est pas un cas d'école : insérer des données déjà triées est le scénario le plus banal qui soit. L'ABR nu offre donc $O (lo g n)$ « en général » et $O (n)$ précisément quand les données arrivent dans l'ordre — c'est-à-dire souvent.

11.2.3 L'arbre bicolore

Définition 11.3Arbre bicolore

Un arbre bicolore (rouge-noir) est un ABR dont chaque nœud porte une couleur, rouge ou noire, avec quatre contraintes :

la racine est noire ;
les feuilles vides sont noires ;
un nœud rouge n'a que des fils noirs — jamais deux rouges de suite ;
tout chemin de la racine à une feuille vide traverse le même nombre de nœuds noirs.

◆Théorème 11.4La hauteur reste logarithmique

Un arbre bicolore à $n$ nœuds internes a une hauteur $h \leq 2 lo g_{2} (n + 1)$ .

Démonstration (Idée)

Soit $b$ le nombre de nœuds noirs sur un chemin racine-feuille, identique pour tous par la contrainte 4. En contractant chaque nœud rouge dans son père, on obtient un arbre dont tous les chemins ont la longueur $b$ , donc un arbre complet de hauteur $b$ : il a au moins $2^{b} - 1$ nœuds, d'où $n \geq 2^{b} - 1$ et $b \leq lo g_{2} (n + 1)$ .

Par la contrainte 3, un chemin ne peut pas contenir deux rouges consécutifs : au plus la moitié de ses nœuds sont rouges, donc $h \leq 2 b \leq 2 lo g_{2} (n + 1)$ .

ImportantCe qu'il faut en retenir, et ce que le programme n'exige pas

Le programme mentionne l'arbre bicolore sans détailler ses rotations : ce qui compte est le résultat — recherche, insertion et suppression en $O (lo g n)$ garantis, dans tous les cas. La démonstration ci-dessus montre d'où vient cette garantie : les contraintes 3 et 4 bornent le rapport entre le chemin le plus court et le plus long à un facteur $2$ . C'est cette borne, et rien d'autre, qui empêche le peigne.

11.3 Le tas

11.3.1 Deux invariants simultanés

Définition 11.5Tas minimum

Un tas est un arbre binaire vérifiant deux propriétés :

forme : l'arbre est complet — tous les niveaux sont pleins sauf éventuellement le dernier, tassé à gauche ;
ordre : l'étiquette de tout nœud est $\leq$ celles de ses fils.

Le minimum est donc à la racine, immédiatement. Mais rien ne dit où se trouve un élément donné : un tas n'est pas fait pour chercher.

ImportantLa contrainte de forme est ce qui rend le tas efficace

Un arbre complet à $n$ nœuds a une hauteur $⌊ lo g_{2} n ⌋$ par construction — il n'y a rien à rééquilibrer, jamais. Et il se range dans un tableau, sans un seul pointeur, comme annoncé au chapitre chap:arbres :

$fils de i : 2 i + 1 et 2 i + 2, p e ˋ re de i : ⌊ \frac{i - 1}{2} ⌋ .$

11.3.2 Les deux opérations, et le même mouvement

Méthode : Insérer : percoler vers le haut

On place l'élément à la première case libre — ce qui préserve la forme — puis on l'échange avec son père tant qu'il lui est inférieur.


/* Insère x dans le tas t de taille *n. Précondition : *n < CAPACITE. */
void inserer(int t[], int* n, int x) {
    assert(n != NULL && *n < CAPACITE);
    int i = *n;
    t[i] = x;
    *n = *n + 1;
    /* INVARIANT : l'invariant de tas tient partout, SAUF peut-être entre i
       et son père. */
    while (i > 0 && t[i] < t[(i - 1) / 2]) {
        int p = (i - 1) / 2;
        int tmp = t[i]; t[i] = t[p]; t[p] = tmp;
        i = p;
    }
}

Terminaison : le variant est $i$ , qui décroît strictement (au moins de moitié). Complexité : $O (lo g n)$ , la hauteur.

Méthode : Extraire le minimum : percoler vers le bas

La racine est le résultat. Pour préserver la forme, on met le dernier élément à sa place, puis on le fait descendre en l'échangeant avec le plus petit de ses fils.


/* Retire et renvoie le minimum. Précondition : *n >= 1. */
int extraire_min(int t[], int* n) {
    assert(n != NULL && *n >= 1);
    int mini = t[0];
    *n = *n - 1;
    t[0] = t[*n];
    int i = 0;
    while (1) {
        int g = 2 * i + 1, d = 2 * i + 2, plus_petit = i;
        if (g < *n && t[g] < t[plus_petit]) { plus_petit = g; }
        if (d < *n && t[d] < t[plus_petit]) { plus_petit = d; }
        if (plus_petit == i) { break; }        /* la place est trouvée */
        int tmp = t[i]; t[i] = t[plus_petit]; t[plus_petit] = tmp;
        i = plus_petit;
    }
    return mini;
}

AttentionÉchanger avec le plus petit des deux fils, jamais avec le premier venu

Si l'on descend en échangeant avec un fils quelconque qui est plus petit, on peut placer au-dessus de l'autre fils une valeur qui lui est supérieure : l'invariant est rompu ailleurs. Les deux lignes de comparaison ne sont pas une optimisation, elles sont la correction.

11.3.3 La file de priorité

Définition 11.6Contrat

Une file de priorité sert les éléments par ordre de priorité, et non d'arrivée.

Opération	Par un tas	Par une liste triée
`inserer(f, x)`	$O (lo g n)$	$O (n)$
`minimum(f)`	$O (1)$	$O (1)$
`extraire_min(f)`	$O (lo g n)$	$O (1)$

Le tas gagne dès que l'on insère autant qu'on extrait — ce qui est le cas de tous ses usages : l'algorithme de Dijkstra (chapitre chap:parcours), le codage de Huffman (chapitre chap:gloutons), l'algorithme A* (chapitre chap:jeux).

11.3.4 Le tri par tas

Méthode : Trier avec un tas

Le programme mentionne le tri par tas à cet endroit précis, et il en découle en deux lignes : on insère les $n$ éléments, puis on extrait $n$ fois le minimum.


(* Trie t par ordre croissant. Complexité : O(n log n) dans TOUS les cas. *)
let tri_par_tas t =
  let f = tas_vide () in
  Array.iter (fun x -> inserer f x) t;
  Array.init (Array.length t) (fun _ -> extraire_min f)

$n$ insertions à $O (lo g n)$ , puis $n$ extractions à $O (lo g n)$ : $Θ (n lo g n)$ .

ImportantUn tri en

O (n lo g n)

dans le PIRE cas, et en place

C'est la propriété qui distingue le tri par tas des autres : le tri rapide est $O (n^{2})$ au pire, le tri par partition-fusion demande $O (n)$ de mémoire supplémentaire. Le tri par tas est $Θ (n lo g n)$ garanti et se fait en place dans le tableau à trier — on construit le tas sur place, puis on extrait de la fin vers le début. Il ne gagne pourtant pas toujours en pratique : ses accès sautent d'un bout à l'autre du tableau, là où le tri rapide progresse de proche en proche. La complexité dit l'ordre de grandeur, pas le temps de la machine (chapitre chap:algo-prog).

11.4 Ce qu'il faut retenir

ImportantDeux invariants, et le prix de chacun

	Chercher $x$	Minimum	Insérer
ABR quelconque	$O (h)$ , jusqu'à $O (n)$	$O (h)$	$O (h)$
Arbre bicolore	$O (lo g n)$ garanti	$O (lo g n)$	$O (lo g n)$
Tas	impossible en mieux que $O (n)$	$O (1)$	$O (lo g n)$

La ligne « impossible » est la plus instructive du tableau. Le tas est meilleur que l'ABR sur le minimum, et infiniment moins bon sur la recherche — parce que son invariant ne compare un nœud qu'à ses descendants, jamais entre frères. Un invariant plus faible achète une opération et en perd une autre, et c'est ce marché qu'il faut savoir lire avant de choisir sa structure.

Continuer sur Adloun : animation, QCM, fiches, exercices