OCaml — Arbres binaires de recherche — Fiche de révision MP2I Informatique

Vue d'ensemble

Un arbre binaire quelconque range des entiers sans règle : chercher une valeur oblige à visiter tous les nœuds. L'arbre binaire de recherche (ABR) ajoute une seule contrainte d'ordre, et cette contrainte change tout : chercher, insérer, lister trié deviennent naturels et rapides. En OCaml, on exploite le filtrage sur le type arbre et l'immutabilité : insérer ne modifie pas l'arbre, on en construit un nouveau.

Au programme (MP2I, structures de données)

Propriété caractéristique d'un ABR (ordre gauche/droite).
Recherche d'une valeur par filtrage récursif, coût $O (h)$ où $h$ est la hauteur.
Insertion respectant la propriété d'ABR, en renvoyant un nouvel arbre.
Fait clé : le parcours infixe d'un ABR énumère les étiquettes par ordre croissant.
Piège du déséquilibre : insertion de données déjà triées → peigne de hauteur $n$ .

Prérequis

Le type type arbre = Vide | Noeud of arbre * int * arbre et le filtrage (fiche ocaml-arbres-binaires).
Parcours d'arbre (préfixe, infixe, suffixe) et notion de hauteur.
Récursivité structurelle et concaténation de listes @.
Comparaisons <, =, > sur les entiers.

🎯 Accompagnement Majorant

Un ABR, ce n'est pas « un arbre en plus ». C'est la première structure où un invariant d'ordre rend un algorithme rapide — l'idée qu'on retrouve partout en info. Nos mentors alumni X · Centrale · Mines t'apprennent à raisonner sur l'invariant plutôt qu'à réciter du code.

Trouver un mentor →

La propriété d'ABR

On part toujours du même type qu'en arbres binaires : une étiquette entière et deux sous-arbres.

type arbre = Vide | Noeud of arbre * int * arbre

🔍 Décryptage ligne par ligne

type arbre =on définit un type somme nommé arbre : une valeur de ce type est de l'une des formes listées après le =.

Videpremier constructeur, sans argument : l'arbre vide (l'analogue de la liste vide []).

| Noeud of arbre * int * arbresecond constructeur : un triplet (sous-arbre gauche, étiquette entière, sous-arbre droit). Le type est récursif car arbre apparaît dans sa propre définition.

Définition 1.1 — Arbre binaire de recherche

Un arbre binaire d'entiers est un ABR si, pour tout nœud d'étiquette $x$ :

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

La condition porte sur tout le sous-arbre, pas seulement sur les fils immédiats : c'est une propriété globale, vraie à chaque nœud.

💡 Un ABR

Voici un arbre correct. À la racine $5$ : le sous-arbre gauche ne contient que $3, 1$ (tous $< 5$ ), le droit ne contient que $8$ ( $> 5$ ). Au nœud $3$ : à gauche $1 < 3$ , à droite rien. Chaque nœud respecte la règle.

(*      5
        / \
       3   8
      /
     1        *)

⚠ Il ne suffit pas de regarder père et fils

L'arbre ci-dessous a chaque fils bien placé par rapport à son père immédiat, mais ce n'est PAS un ABR : le $6$ est dans le sous-arbre gauche de $5$ , or $6 > 5$ . La règle exige que toutes les étiquettes de gauche soient $< 5$ .

(*      5
        /
       3
        \
         6      6 > 5 mais placé à gauche de 5 : interdit  *)

Rechercher une valeur

La propriété d'ABR guide la descente : à chaque nœud, une seule comparaison indique le côté à explorer. On n'explore jamais les deux sous-arbres.

Définition 1.2 — Recherche dans un ABR

Chercher $v$ dans un ABR : si l'arbre est vide, $v$ est absent. Sinon, soit $x$ l'étiquette de la racine ; si $v = x$ c'est trouvé, si $v < x$ on cherche uniquement dans le sous-arbre gauche, si $v > x$ uniquement dans le droit.

let rec recherche v a =
  match a with
  | Vide -> false
  | Noeud (g, x, d) ->
      if v = x then true
      else if v < x then recherche v g
      else recherche v d

🔍 Décryptage ligne par ligne

let rec recherche v a =rec car la fonction s'appelle elle-même ; v est la valeur cherchée, a l'arbre. Type inféré : int -> arbre -> bool.

match a withon filtre sur la forme de l'arbre : soit vide, soit un nœud.

| Vide -> falsecas de base : on est arrivé sur un arbre vide sans trouver v, donc v est absent.

| Noeud (g, x, d) ->on nomme les trois composantes du nœud : g gauche, x l'étiquette, d droite.

if v = x then trueégalité : la valeur est ici, on renvoie immédiatement true.

else if v < x then recherche v gsi v est plus petit, la propriété d'ABR garantit qu'il ne peut être qu'à gauche : on descend dans g et on ignore d.

else recherche v ddernier cas (v > x) : on descend uniquement à droite. Un seul chemin est parcouru, d'où l'efficacité.

Recherche de $4$ puis de $8$ dans l'ABR (racine 5, gauche 3→1, droite 8)
Appel	nœud $x$	comparaison	action
recherche 4 (racine)	5	4 < 5	descente à gauche
recherche 4	3	4 > 3	descente à droite
recherche 4	—	Vide	`false` : 4 absent
recherche 8 (racine)	5	8 > 5	descente à droite
recherche 8	8	8 = 8	true : trouvé ✓

📝 Coût de la recherche

Chaque appel descend d'un niveau. Le nombre d'appels est donc borné par la hauteur $h$ de l'arbre : la recherche est en $O (h)$ . Si l'arbre est équilibré, $h \approx lo g_{2} n$ et la recherche est en $O (lo g n)$ . Tout dépend de la forme de l'arbre — voir le piège du déséquilibre.

Insérer une valeur

Insérer suit le même chemin que la recherche, jusqu'à tomber sur un Vide : c'est là qu'on greffe la nouvelle feuille. En OCaml l'arbre est immuable : on ne modifie rien, on reconstruit le chemin descendu en renvoyant un nouvel arbre.

let rec insere v a =
  match a with
  | Vide -> Noeud (Vide, v, Vide)
  | Noeud (g, x, d) ->
      if v = x then a
      else if v < x then Noeud (insere v g, x, d)
      else Noeud (g, x, insere v d)

🔍 Décryptage ligne par ligne

let rec insere v a =on insère v dans a et on renvoie le nouvel arbre. Type : int -> arbre -> arbre.

| Vide -> Noeud (Vide, v, Vide)on a atteint une place libre : on crée une feuille portant v (deux sous-arbres vides). C'est le seul endroit où un nœud apparaît réellement.

if v = x then av est déjà présent : on renvoie l'arbre inchangé (un ABR ne stocke pas de doublon).

else if v < x then Noeud (insere v g, x, d)v doit aller à gauche : on reconstruit un nœud de même étiquette x et même sous-arbre droit d, mais avec le sous-arbre gauche mis à jour par l'appel récursif.

else Noeud (g, x, insere v d)cas v > x : symétrique, on ne touche qu'au sous-arbre droit. Le sous-arbre g non concerné est partagé tel quel avec l'ancien arbre : rien n'est recopié inutilement.

Insertions successives de 5, 3, 8, 1 dans un arbre vide
Étape	chemin suivi	arbre obtenu (parenthésé)
insere 5 dans Vide	Vide → feuille	N(V, 5, V)
insere 3	3 < 5 → gauche (Vide)	N( N(V,3,V), 5, V )
insere 8	8 > 5 → droite (Vide)	N( N(V,3,V), 5, N(V,8,V) )
insere 1	1 < 5 → gauche ; 1 < 3 → gauche (Vide)	N( N( N(V,1,V), 3, V ), 5, N(V,8,V) ) ✓

L'arbre final (avec N pour Noeud et V pour Vide) a la forme :

(*      5
        / \
       3   8
      /
     1        *)

📝 Immutabilité et partage

Chaque insertion crée seulement les nœuds situés sur le chemin descendu ; tous les sous-arbres écartés sont réutilisés sans copie. L'ancien arbre reste valide et intact. C'est la signature du style fonctionnel : on ne mute pas, on renvoie une nouvelle version qui partage l'essentiel avec l'ancienne.

🎯 Accompagnement Majorant

« Renvoyer un nouvel arbre » déroute la plupart des MP2I. Là où en C on modifierait un pointeur en place, OCaml reconstruit le chemin — et le reste est partagé. Nos mentors alumni X · Centrale · Mines te font manipuler les deux visions pour que tu ne les confondes plus jamais.

Trouver un mentor →

Le parcours infixe trie l'ABR

Rappel : le parcours infixe visite d'abord tout le sous-arbre gauche, puis la racine, puis tout le sous-arbre droit. Sur un ABR, cela produit les étiquettes dans l'ordre croissant : à chaque nœud, gauche < racine < droite, et cette règle se propage récursivement.

let rec infixe a =
  match a with
  | Vide -> []
  | Noeud (g, x, d) -> infixe g @ [x] @ infixe d

🔍 Décryptage ligne par ligne

let rec infixe a =renvoie la liste des étiquettes en ordre infixe. Type : arbre -> int list.

| Vide -> []un arbre vide donne la liste vide.

| Noeud (g, x, d) -> infixe g @ [x] @ infixe don concatène : la liste (triée) du gauche, puis le singleton [x], puis la liste (triée) du droit. Gauche < x < droite, donc le résultat est trié.

💡 Sur l'arbre 5 / 3 / 8 / 1

infixe visite : gauche de 5 (= 1 puis 3), puis 5, puis droite de 5 (= 8). Résultat : [1; 3; 5; 8] — trié. Ce fait donne un algorithme de tri : insérer tous les éléments dans un ABR puis lire l'infixe.

📝 Test d'ABR gratuit

Corollaire pratique : un arbre binaire est un ABR si et seulement si son parcours infixe est strictement croissant. C'est souvent la façon la plus simple de vérifier la propriété sur un exemple.

Le piège du déséquilibre

Le coût $O (h)$ est excellent… tant que $h$ est petit. Or la forme de l'ABR dépend entièrement de l'ordre d'insertion, et rien dans insere ne rééquilibre l'arbre.

⚠ Insérer des valeurs déjà triées dégénère l'arbre

Insérons $1, 2, 3, 4$ dans cet ordre. Chaque valeur est plus grande que toutes les précédentes : elle part toujours à droite. On obtient un peigne — une seule branche descendante :

La hauteur vaut $n$ au lieu de $lo g_{2} n$ . La recherche redevient $O (n)$ : l'ABR ne vaut alors pas mieux qu'une liste chaînée. En vraie CPGE, on corrige cela avec des arbres équilibrés (hors programme MP2I), mais tu dois savoir reconnaître ce cas dégénéré.

📝 À retenir

Complexité de recherche/insertion : $O (h)$ . Au mieux (arbre équilibré) $h = O (lo g n)$ ; au pire (peigne) $h = n$ , soit $O (n)$ . La borne $O (lo g n)$ n'est jamais garantie par ce code seul.

Exercices corrigés

Exo 1Descente et infixeFacile

On considère l'ABR obtenu en insérant, dans cet ordre, $4, 2, 6, 1, 3$ dans un arbre vide.

a) Dessine l'arbre. b) Donne le résultat de infixe. c) La recherche de $5$ descend-elle à gauche ou à droite de la racine, et aboutit-elle ?

Voir la correction détaillée

a) Construction. 4 devient la racine. 2 < 4 → gauche. 6 > 4 → droite. 1 < 4 puis 1 < 2 → gauche de 2. 3 < 4 puis 3 > 2 → droite de 2.

b) Infixe. Gauche de 4 = (1, 2, 3), racine 4, droite 6. Résultat : [1; 2; 3; 4; 6] — trié, comme attendu pour un ABR.

c) Recherche de 5.

5 &gt; 4

→ on descend à droite, sur le nœud 6.

5 &lt; 6

→ à gauche de 6, qui est Vide. Donc false :

5

est absent.

Exo 2Minimum d'un ABRIntermédiaire

Écris une fonction minimum : arbre -> int qui renvoie la plus petite étiquette d'un ABR non vide, en exploitant la propriété d'ABR (sans parcourir tout l'arbre). On lèvera failwith "arbre vide" sur Vide.

Voir la correction détaillée

Idée. Dans un ABR, tout ce qui est plus petit qu'un nœud est à sa gauche. Le minimum est donc obtenu en descendant toujours à gauche jusqu'au bout. Le nœud dont le sous-arbre gauche est Vide porte le minimum.

Code.

let rec minimum a =
  match a with
  | Vide -> failwith "arbre vide"
  | Noeud (Vide, x, _) -> x
  | Noeud (g, _, _) -> minimum g

Décryptage. Le cas Noeud (Vide, x, _) filtre précisément un nœud sans fils gauche : son étiquette x est le minimum. Sinon (g non vide) on continue à gauche. Le _ ignore les composantes inutiles. Coût :

O (h)

Vérification. Sur l'arbre de l'exo 1 (racine 4) : 4 a un fils gauche 2, on descend ; 2 a un fils gauche 1, on descend ; 1 a un fils gauche Vide → on renvoie 1. Correct.

Exo 3Vérifier la propriété d'ABRDifficile

Écris est_abr : arbre -> bool qui teste si un arbre binaire est un ABR. On utilisera le corollaire : un arbre est un ABR si et seulement si son parcours infixe est strictement croissant. On pourra écrire une fonction auxiliaire croissante : int list -> bool.

Voir la correction détaillée

Étape 1 — liste strictement croissante.

let rec croissante l =
  match l with
  | [] | [_] -> true
  | a :: b :: reste -> a < b && croissante (b :: reste)

Le cas [] | [_] : une liste de 0 ou 1 élément est trivialement croissante. Sinon on compare les deux premiers a et b : il faut a < b, puis on recommence à partir de b (on n'oublie pas de le remettre en tête avec b :: reste).

Étape 2 — assemblage.

let est_abr a = croissante (infixe a)

On lit l'arbre en infixe puis on teste si la liste obtenue est strictement croissante.

Pourquoi ça marche. Le parcours infixe range gauche < racine < droite à chaque nœud si la propriété d'ABR tient. Réciproquement, si l'infixe est strictement croissant, aucune étiquette de gauche ne dépasse la racine ni aucune de droite ne lui est inférieure : la propriété est satisfaite partout. Le test est en

O (n)

(un parcours + une passe sur la liste).

Piège évité. Un test naïf qui ne compare qu'un nœud à ses fils immédiats est faux (cf. le contre-exemple du 6 à gauche du 5). Passer par l'infixe capture bien la contrainte globale.

Récap final — Ce qu'il faut absolument retenir

L'ABR = un arbre binaire + un invariant d'ordre. Cet invariant se paie une fois (à l'insertion) et se récupère partout : recherche rapide et lecture triée gratuite.

Sais-tu énoncer la propriété d'ABR (gauche < $x$ < droite, pour tout le sous-arbre, à chaque nœud) ?
Sais-tu écrire recherche par filtrage, en ne descendant que d'un côté selon la comparaison ?
Sais-tu que la recherche coûte $O (h)$ , et pourquoi (un seul chemin parcouru) ?
Sais-tu écrire insere qui renvoie un nouvel arbre en reconstruisant le chemin (immutabilité, partage des sous-arbres écartés) ?
Sais-tu qu'insérer une valeur déjà présente laisse l'arbre inchangé ?
Sais-tu que le parcours infixe d'un ABR donne les étiquettes triées par ordre croissant ?
Sais-tu reconnaître le peigne obtenu par insertion de données triées, et que sa hauteur vaut $n$ (recherche $O (n)$ ) ?
Sais-tu tester si un arbre est un ABR via la stricte croissance de son infixe ?

OCaml — Arbres binaires de recherche

Vue d'ensemble

Prérequis

La propriété d'ABR

Rechercher une valeur

Insérer une valeur

Le parcours infixe trie l'ABR

Le piège du déséquilibre

Exercices corrigés

Récap final — Ce qu'il faut absolument retenir

Débloque la fiche complète

Quiz — OCaml : ABR

Fiches associées

C — Premiers pas

C — Pointeurs et allocation dynamique

OCaml — Premiers pas

OCaml — Filtrage et listes

C — Structures et listes chaînées

C — Piles et files

Tu veux aller plus loin sur ce chapitre ?