Corrigé CCINP 2026 Informatique MP — Problème 2 (I) (Q12 à Q24) : Ensembles de mots implémentés par tries

Q12. Les tables de hachage (c'est l'implémentation du dict de Python) et les arbres binaires de recherche, équilibrés de préférence (AVL, arbres rouge-noir), qui garantissent un coût logarithmique par opération.

Q13. On prend pour clés les mots de l'ensemble, associés à une valeur sans importance (True, ou () en OCaml). Tester si un mot $m$ appartient à l'ensemble revient à tester si $m$ est une clé du dictionnaire (m in d en Python), ce qui coûte en moyenne $O(1)$ accès à une table de hachage (plus le calcul du haché de $m$, en $O(|m|)$), ou $O(\log N)$ comparaisons de mots dans un arbre binaire de recherche équilibré contenant $N$ mots. En Python, c'est exactement ce qu'offre le type set, un dictionnaire sans valeurs.

Q14. Les mots commençant par la même lettre partagent leur branche ; on obtient 25 nœuds pour 7 mots.

Les nœuds true sont ceux de « en », « bot » (nœuds internes) et des cinq feuilles.

Q15. On construit la liste de la fin vers le début, pour n'utiliser que des ajouts en tête.

let string_to_list s =
  (* aux i acc : la liste des caractères s.[0..i], suivie de acc *)
  let rec aux i acc =
    if i < 0 then acc else aux (i - 1) (s.[i] :: acc)
  in
  aux (String.length s - 1) []

La fonction auxiliaire aux i acc renvoie [s.[0]; …; s.[i]] @ acc : c'est vrai pour $i=-1$, et si c'est vrai au rang $i-1$, l'appel aux (i-1) (s.[i] :: acc) renvoie [s.[0]; …; s.[i-1]] @ (s.[i] :: acc), ce qu'on voulait. Avec $i=n-1$ et acc = [], on obtient la liste de tous les caractères. Le paramètre $i$ décroît strictement jusqu'à $-1$ : il y a $n+1$ appels, chacun en temps constant (accès s.[i] et « cons » en $O(1)$), d'où un coût $\Theta (n)$ ; la récursion est terminale. Essais : string_to_list "lettre" donne ['l'; 'e'; 't'; 't'; 'r'; 'e'], et "" donne [].

Q16. Le trie de l'ensemble vide réduit à un seul nœud, sa racine, qui ne porte aucun mot :

let empty_trie () = Node (false, [])

On ne peut pas faire moins : le type trie n'a pas de constructeur d'arbre vide, tout trie a au moins une racine.

Q17.

let rec max_list lst =
  match lst with
  | [] -> failwith "max_list : liste vide"
  | [x] -> x
  | x :: q -> let m = max_list q in if x >= m then x else m

Par récurrence sur la longueur : un singleton a pour maximum son unique élément ; sinon le maximum de x :: q est le plus grand de x et du maximum de q (non vide). Un appel par élément : coût linéaire. Essais : max_list [3; 7; 2] = 7, max_list [-3; -1; -8] = -1.