Prenons ce code :

type arbre =
  | Fin
  | Noeud of char * arbre * arbre

let a =
  Noeud(
    'k',
    Noeud(
      'g',
      Noeud(
        'f',
        Noeud('a', Fin, Fin),
        Fin
      ),
      Noeud('i', Fin, Fin)
    ),
    Noeud('k', Fin, Fin)
  )

N’hésitez pas à dessiner l’arbre a si ça vous aide.

Quelle est la taille de a ?

Quelle est la profondeur de a ?

Que vaut la racine de a ?

Combien a a-t-il de feuilles ?

On va passer à un exercice plus concret. Imaginons que vous conceviez une application pour gérer les relevés de notes de l’université. Lors de la remise des bulletins, vous devez associer à chaque numéro d’anonymat un nom d’étudiant·e. Mais il y a beaucoup d’étudiants, alors pour accélérer la recherche dans la liste, vous décidez de passer par un dictionnaire binaire.

Le fonctionnement est le même qu’un arbre binaire classique, mais on associe à chaque nœud un couple, qui sera ici de type int * string (numéro d’étudiant et nom). On classe les données dans l’arbre selon le numéro d’étudiant uniquement.

L’exercice est de créer le type dico_binaire et les fonctions ajouter (qui prend un arbre, un numéro et un nom) et trouver_nom (qui prend un arbre et un numéro) correspondantes.

type dico_binaire =
  | Fin
  | Noeud of (int * string) * dico_binaire * dico_binaire

let rec ajouter (num : int) (nom : string) (dic : dico_binaire) : dico_binaire =
  match dic with
  | Fin -> Noeud((num, nom), Fin, Fin)
  | Noeud((num_actuel, nom_actuel), gauche, droite) ->
    if num_actuel = num then (* Les deux numéros sont les mêmes : on met à jour le nom *)
      Noeud((num_actuel, nom), gauche, droite)
    else if num_actuel > num then (* On insère à gauche *)
      Noeud((num_actuel, nom_actuel), ajouter num nom gauche, droite)
    else (* On insère à droite *)
      Noeud((num_actuel, nom_actuel), gauche, ajouter num nom droite)

let rec trouver_nom (num : int) (dic : dico_binaire) : string =
  match dic with
  | Fin -> "Introuvable"
  | Noeud((n, nom), gauche, droite) ->
    if num = n then
      nom
    else if num < n then
      trouver_nom num gauche
    else
      trouver_nom num droite

Si vous voulez aller plus loin, essayez de rendre dico_binaire polymorphe (pour accepter autre chose que des entiers et du texte), et créez la fonction supprimer (dic : ('a, 'b) dico_binaire) (cle : 'a) : ('a, 'b) dico_binaire.

Si vous voulez vous entraîner à la démonstration par induction structurelle, essayer de prouver les propriétés suivantes :

1. La profondeur d’un arbre binaire est inférieure à sa taille.
2. La taille d’un arbre binaire est inférieure à 2 puissance : profondeur moins 1.