Arbres
Cours · informatique (MP2I/MPI), chapitre 10 · MP2I et MPI · le début du chapitre, la suite sur Adloun
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 éléments coûte , dans un arbre bien formé .
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
L'ensemble des arbres binaires étiquetés par est le plus petit ensemble tel que :
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;- 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 : et sont les fils de , qui est leur père ;
- étiquette : la valeur 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 ;
- hauteur de l'arbre : la plus grande profondeur atteinte.
C'est une convention, et le programme la fixe explicitement. Elle n'est pas arbitraire : elle est la seule qui rende vraie l'identité
dans tous les cas, y compris pour une feuille — dont les deux fils sont vides, et dont la hauteur vaut alors . Avec la convention , 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
(* 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 et , strictement plus petits pour l'ordre induit, qui est bien fondé. Complexité : chaque nœud est visité exactement une fois, donc pour un arbre de nœuds — et en espace de pile.
Pour un arbre binaire de hauteur et de taille :