Arbres

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

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

10.1 Une structure qui se définit par elle-même

Les structures du chapitre chap:sequentielles étaient linéaires : chaque élément avait au plus un suivant. L'arbre rompt avec cela — un nœud peut avoir plusieurs fils — et c'est ce qui lui donne son pouvoir : une recherche dans une liste de $n$ éléments coûte $O (n)$ , dans un arbre bien formé $O (lo g n)$ .

C'est aussi le premier objet vraiment inductif du livre. Sa définition tient en deux règles, sa preuve en deux cas, son code en deux motifs. Tout ce qui a été posé au chapitre chap:induction s'applique ici sans adaptation.

10.2 Définition et vocabulaire

Définition 10.1Arbre binaire, par induction

L'ensemble des arbres binaires étiquetés par $E$ est le plus petit ensemble tel que :

$Vide \frac{g arbre e \in E d arbre}{N œ ud ( g , e , d )}$


type 'a arbre = Vide | Noeud of 'a arbre * 'a * 'a arbre


typedef struct noeud_s {
    int etiquette;
    struct noeud_s* gauche;    /* NULL joue le rôle de Vide */
    struct noeud_s* droit;
} noeud;

Définition 10.2Le vocabulaire, celui du programme

nœud : un Nœud de la définition ; racine : celui du sommet ;
feuille : un nœud dont les deux fils sont vides ; nœud interne : les autres ;
fils et père : $g$ et $d$ sont les fils de $N œ ud (g, e, d)$ , qui est leur père ;
étiquette : la valeur $e$ portée par un nœud ;
sous-arbre : tout arbre atteint en descendant ;
profondeur d'un nœud : le nombre d'arcs qui le séparent de la racine — celle-ci est à la profondeur $0$ ;
hauteur de l'arbre : la plus grande profondeur atteinte.

AttentionLa hauteur de l'arbre vide vaut

- 1

C'est une convention, et le programme la fixe explicitement. Elle n'est pas arbitraire : elle est la seule qui rende vraie l'identité

$h (N œ ud (g, e, d)) = 1 + max (h (g), h (d))$

dans tous les cas, y compris pour une feuille — dont les deux fils sont vides, et dont la hauteur vaut alors $1 + max (- 1, - 1) = 0$ . Avec la convention $h (Vide) = 0$ , il faudrait un cas particulier pour les feuilles, et toutes les formules du chapitre porteraient une exception.

10.3 Les fonctions de base, et leurs preuves

Exemple 10.3Taille et hauteur


(* Nombre de nœuds de a. *)
let rec taille = function
  | Vide -> 0
  | Noeud (g, _, d) -> 1 + taille g + taille d

(* Hauteur de a ; celle de l'arbre vide vaut -1. *)
let rec hauteur = function
  | Vide -> -1
  | Noeud (g, _, d) -> 1 + max (hauteur g) (hauteur d)

Terminaison : les appels portent sur $g$ et $d$ , strictement plus petits pour l'ordre induit, qui est bien fondé. Complexité : chaque nœud est visité exactement une fois, donc $Θ (n)$ pour un arbre de $n$ nœuds — et $O (h)$ en espace de pile.

Proposition 10.4Encadrement du nombre de nœuds

Pour un arbre binaire de hauteur $h \geq - 1$ et de taille $n$ :

$h + 1 \leq n \leq 2^{h + 1} - 1.$

Démonstration

Par induction structurelle. Pour $Vide$ , avec $h = - 1$ et $n = 0$ , l'encadrement s'écrit $0 \leq 0 \leq 0$ : il tient, et c'est pourquoi l'énoncé part de $h \geq - 1$ et non de $h \geq 0$ .

Soit $a = N œ ud (g, e, d)$ , de hauteur $h = 1 + max (h_{g}, h_{d})$ et de taille $n = 1 + n_{g} + n_{d}$ .

Minoration. Supposons $h_{g} \geq h_{d}$ , donc $h = 1 + h_{g}$ . Par hypothèse d'induction $n_{g} \geq h_{g} + 1$ , et $n_{d} \geq 0$ . Donc $n \geq 1 + (h_{g} + 1) = h + 1$ .

Majoration. Par hypothèse d'induction, $n_{g} \leq 2^{h_{g} + 1} - 1 \leq 2^{h} - 1$ puisque $h_{g} \leq h - 1$ , et de même pour $n_{d}$ . Donc

$n \leq 1 + 2 (2^{h} - 1) = 2^{h + 1} - 1.$

ImportantLa conséquence qui gouverne tout le chapitre suivant

En inversant la majoration : $h \geq lo g_{2} (n + 1) - 1$ . La hauteur d'un arbre à $n$ nœuds vaut donc au mieux $Θ (lo g n)$ , et au pire $n - 1$ — le cas du peigne, où chaque nœud n'a qu'un fils, et qui n'est rien d'autre qu'une liste chaînée déguisée.

Comme toutes les opérations de recherche coûteront $O (h)$ , tout l'enjeu du chapitre chap:tas sera d'empêcher l'arbre de dégénérer.

iRemarqueL'arbre complet dans un tableau

Le programme demande de « mentionner la représentation d'un arbre complet dans un tableau ». Si l'arbre est complet — tous les niveaux remplis, le dernier tassé à gauche — on peut se passer de pointeurs : en rangeant la racine à l'indice $0$ , les fils du nœud d'indice $i$ sont aux indices $2 i + 1$ et $2 i + 2$ , et son père à $⌊(i - 1) /2 ⌋$ . Aucun pointeur, aucune allocation, une mémoire contiguë : c'est la représentation qu'utilisera le tas au chapitre chap:tas.

10.4 Arbres d'arité quelconque

Définition 10.5Arbre général

Un arbre (sans qualificatif) autorise un nombre quelconque de fils par nœud.


type 'a arbre_general = N of 'a * 'a arbre_general list

Méthode : Conversion « fils gauche, frère droit »

Le programme demande la « conversion d'un arbre d'arité quelconque en un arbre binaire ». Le procédé est classique et se dit en une phrase : le fils gauche du binaire est le premier fils du général ; le fils droit est le frère suivant.


let rec vers_binaire (N (e, fils)) = Noeud (freres fils, e, Vide)
and freres = function
  | [] -> Vide
  | N (e, f) :: reste -> Noeud (freres f, e, freres reste)

La conversion est bijective, et elle permet de n'écrire qu'une fois les algorithmes sur les arbres. En revanche elle allonge : trois frères deviennent une chaîne de hauteur trois.

iRemarqueÀ quoi servent les arbres

Le programme laisse les illustrations « au choix du professeur » et en cite plusieurs : expressions arithmétiques, arbres préfixes (trie), arbres de décision, dendrogrammes, arbres de classification. On les retrouvera : l'arbre de décision au chapitre chap:apprentissage, le dendrogramme de la classification hiérarchique au même endroit, l'arbre syntaxique au chapitre chap:grammaires, et l'arbre de preuve au chapitre chap:deduction.

Exemple 10.6L'expression arithmétique comme arbre


type expr =
  | Cst of int
  | Plus of expr * expr
  | Fois of expr * expr

(* Évalue e. La structure de la fonction EST la structure du type. *)
let rec evalue = function
  | Cst n -> n
  | Plus (a, b) -> evalue a + evalue b
  | Fois (a, b) -> evalue a * evalue b

L'arbre porte la priorité des opérateurs dans sa forme : $2 + 3 \times 4$ et $(2 + 3) \times 4$ sont deux arbres différents, et aucune parenthèse n'est nécessaire. C'est précisément ce qu'un analyseur syntaxique construit — chapitre chap:grammaires.

10.5 Parcours

Définition 10.7Trois ordres de parcours en profondeur

Un parcours visite chaque nœud une fois. Pour un arbre binaire, la question est quand traiter la racine par rapport à ses sous-arbres :

préfixe : racine, puis gauche, puis droit ;
infixe : gauche, puis racine, puis droit ;
postfixe : gauche, puis droit, puis racine.


let rec prefixe = function
  | Vide -> []
  | Noeud (g, e, d) -> e :: (prefixe g @ prefixe d)

let rec infixe = function
  | Vide -> []
  | Noeud (g, e, d) -> infixe g @ (e :: infixe d)

let rec postfixe = function
  | Vide -> []
  | Noeud (g, e, d) -> postfixe g @ postfixe d @ [e]

Exemple 10.8Les trois parcours de l'arbre de la page précédente

préfixe	8, 3, 1, 6, 4, 9, 7
infixe	1, 3, 4, 6, 8, 7, 9
postfixe	1, 4, 6, 3, 7, 9, 8

AttentionCes trois fonctions sont en

O (n^{2})

, et c'est le `@` qui coûte

La concaténation @ recopie sa liste de gauche (chapitre chap:langage-ocaml). Sur un peigne gauche, le coût devient quadratique. La bonne écriture passe un accumulateur :


(* Renvoie la liste infixe de a, suivie de acc. Complexité : O(n). *)
let rec infixe_acc a acc =
  match a with
  | Vide -> acc
  | Noeud (g, e, d) -> infixe_acc g (e :: infixe_acc d acc)

Chaque nœud n'entraîne qu'un ::, en $O (1)$ : le parcours redevient $Θ (n)$ . C'est une illustration exacte de la mise en garde du chapitre chap:langage-ocaml : une complexité peut être ruinée par une seule opération mal choisie.

iRemarqueLe parcours et la pile d'appels

Le programme suggère d'« évoquer le lien avec l'empilement de blocs d'activation lors de l'appel à une fonction récursive ». Le parcours préfixe empile la racine avant de descendre, le postfixe la traite après être remonté : ce sont exactement la descente et la remontée de la pile d'exécution du chapitre chap:recursivite. Un parcours en profondeur écrit avec une pile explicite et le même parcours écrit récursivement font littéralement la même chose — l'un avec la pile du programme, l'autre avec celle de la machine.

ImportantLe parcours infixe d'un arbre de recherche est trié

C'est le résultat le plus utile de la section, et il sera démontré au chapitre suivant. Il donne déjà l'intuition : dans l'arbre dessiné plus haut, la ligne infixe est $1, 3, 4, 6, 8, 7, 9$ — presque triée, mais pas tout à fait, car cet arbre n'est pas un arbre binaire de recherche. Un arbre où elle le serait exactement mérite un nom, et c'est le sujet du chapitre chap:tas.

10.6 Ce qu'il faut retenir

ImportantArbres : quatre points

Le type est inductif : deux constructeurs, donc deux motifs, donc deux cas de preuve. La terminaison est acquise par l'ordre induit.
$h (Vide) = - 1$ , et $h + 1 \leq n \leq 2^{h + 1} - 1$ : la hauteur est entre $Θ (lo g n)$ et $n - 1$ .
Toute opération de recherche coûtera $O (h)$ : équilibrer, c'est tout gagner.
Trois parcours en profondeur — préfixe, infixe, postfixe — et l'on écrit avec un accumulateur, jamais avec @.

Continuer sur Adloun : animation, QCM, fiches, exercices