Arbres Binaires : Définition, Recherche et Insertion

1. Modéliser un arbre binaire avec un type algébrique

Tout comme nous avons défini les listes de manière récursive ([] ou h :: t), nous pouvons définir un arbre binaire. Un arbre binaire est soit vide, soit il est constitué d'un nœud qui contient une valeur et deux sous-arbres (gauche et droit), qui sont eux-mêmes des arbres binaires.

Cette définition se traduit directement en un type algébrique en OCaml.

La définition que vous venez de voir est la suivante :

type 'a arbre =
  | F  (* Feuille, représente un arbre vide *)
  | N of 'a arbre * 'a * 'a arbre (* Noeud interne *)

• C'est un type somme avec deux constructeurs : F et N.
• F est un constructeur constant qui représente un arbre vide (une feuille externe). C'est notre cas de base, analogue à la liste vide [].
• N est un constructeur qui prend un triplet : un sous-arbre gauche ('a arbre), une valeur ('a), et un sous-arbre droit ('a arbre). C'est notre cas récursif.
• Le type est polymorphe ('a), ce qui signifie que nous pouvons créer des arbres de n'importe quel type de données : int arbre, string arbre, etc.

2. L'invariant de l'arbre binaire de recherche (ABR)

Un arbre binaire générique n'est pas particulièrement efficace pour la recherche. Pour le rendre utile, nous lui imposons une contrainte d'ordre : l'invariant de l'arbre binaire de recherche.

Cette propriété doit être vraie pour tous les nœuds de l'arbre. C'est elle qui nous permettra de rechercher des éléments efficacement.

3. Implémentation de la recherche (cherche)

Comment l'invariant de l'ABR nous aide-t-il à rechercher une valeur x ?
À partir de la racine de l'arbre (ou d'un sous-arbre) de valeur v :

• Si x = v, nous avons trouvé la valeur.
• Si x < v, il est inutile de regarder dans le sous-arbre droit. Nous continuons la recherche récursivement dans le sous-arbre gauche.
• Si x > v, nous continuons la recherche récursivement dans le sous-arbre droit.
• Si nous arrivons à une feuille (F), cela signifie que la valeur n'est pas dans l'arbre.

Cet algorithme élimine une grande partie de l'arbre à chaque étape. Sa complexité est proportionnelle à la hauteur de l'arbre, $O(h)$, bien meilleure que la complexité linéaire $O(n)$ pour une recherche dans une liste.

Voici le code pour référence :

let rec cherche arbre valeur =
  match arbre with
  | F -> false
  | N (g, v, d) ->
      if v = valeur then true
      else if valeur < v then cherche g valeur
      else cherche d valeur

Notez l'élégance de cette fonction : sa structure suit exactement celle du type de données qu'elle manipule.

4. Implémentation de l'insertion (insere)

L'insertion d'une nouvelle valeur doit préserver l'invariant de l'ABR. L'approche la plus simple est l'insertion aux feuilles :

1. On recherche l'emplacement où la valeur devrait se trouver, comme pour la fonction cherche.
2. Quand on atteint une feuille (F), on la remplace par un nouveau nœud contenant la valeur.

Un point crucial en programmation fonctionnelle est l'immutabilité. Nous ne modifions pas l'arbre existant. Au lieu de cela, la fonction insere retourne un nouvel arbre qui inclut la valeur ajoutée. Lors de la remontée de la récursion, les nœuds du chemin parcouru sont recréés pour pointer vers les sous-arbres (potentiellement modifiés).

Le code correspondant est le suivant :

let rec insere arbre valeur =
  match arbre with
  | F -> N (F, valeur, F)
  | N (g, v, d) ->
      if v = valeur then arbre (* La valeur existe déjà, on ne change rien *)
      else if valeur < v then N (insere g valeur, v, d) (* On reconstruit le noeud avec le nouveau sous-arbre gauche *)
      else N (g, v, insere d valeur) (* On reconstruit le noeud avec le nouveau sous-arbre droit *)

• Cas de base (F): on crée un nœud terminal.
• Cas récursif (N(g, v, d)):
  • Si valeur < v, l'insertion se fait dans le sous-arbre gauche. L'appel insere g valeur retourne un nouveau sous-arbre gauche. On crée alors un nouveau nœud N avec ce nouveau sous-arbre gauche, l'ancienne valeur v et l'ancien sous-arbre droit d.
  • Le cas valeur > v est symétrique.

5. Exercice de synthèse

Mettez en pratique ce que vous venez d'apprendre. L'exercice consiste à construire un ABR à partir d'une liste d'entiers. C'est l'occasion parfaite de réutiliser la fonction d'ordre supérieur fold_left de la leçon précédente !

Objectif : Écrire une fonction construire_abr : int list -> int arbre qui prend une liste d'entiers et retourne un ABR contenant ces entiers.

Utilisez List.fold_left pour itérer sur la liste d'entrée. L'accumulateur sera l'ABR en cours de construction, qui commence comme un arbre vide (F). À chaque étape, vous insérez l'élément courant de la liste dans l'accumulateur.

(* Votre code ici *)
let construire_abr (l : int list) : int arbre =
  ...

(* On réutilise la fonction insere définie précédemment *)
let rec insere arbre valeur =
  match arbre with
  | F -> N (F, valeur, F)
  | N (g, v, d) as a -> (* 'as a' permet de retourner l'arbre inchangé plus simplement *)
      if v = valeur then a
      else if valeur < v then N (insere g valeur, v, d)
      else N (g, v, insere d valeur)

let construire_abr (l : int list) : int arbre =
  List.fold_left (fun acc x -> insere acc x) F l

(* Testons-le : *)
(* let mon_arbre = construire_abr [7; 2; 9; 1; 5; 8];; *)
(* `mon_arbre` correspondra à l'arbre de l'exemple du PDF. *)

Conclusion

Aujourd'hui, vous avez franchi une étape importante en passant des structures linéaires (listes) aux structures arborescentes. Vous avez vu comment la programmation fonctionnelle, grâce aux types algébriques et à la récursivité, offre un cadre de pensée particulièrement adapté à la manipulation de telles structures.

Points clés à retenir :

• Un type algébrique récursif est un outil puissant pour modéliser des structures de données comme les arbres binaires en OCaml.
• L'invariant de l'ABR est la propriété d'ordre qui garantit une recherche efficace en $O(h)$.
• Les opérations de recherche et d'insertion sont implémentées par des fonctions récursives dont la structure reflète celle du type de données.
• En programmation fonctionnelle, l'insertion ne modifie pas l'arbre existant mais en crée une nouvelle version, un concept clé lié à l'immutabilité.

Dans notre prochaine leçon, nous reviendrons sur les algorithmes de tri, un sujet central pour l'Agrégation. Nous implémenterons le tri fusion en OCaml, en exploitant une nouvelle fois la puissance et l'élégance de l'approche fonctionnelle pour résoudre un problème algorithmique classique.