Question 1

---

Créez un nouveau trie ex_2 qui est le trie du premier exemple, auquel vous aurez ajouté les mots "tac" et "tact".

Question 2

---

Écrivez une fonction compter_mots: trie -> int qui renvoie le nombre de mots contenus dans le trie. Votre fonction doit renvoyer 3 sur ex_1 et 5 sur ex_2.

Question 3a

---

Écrivez une fonction existe_liste: (char * trie) list -> char -> bool, qui cherche la présence d'un caractère dans une liste de couples (caractère, trie) et renvoie true si le caractère est trouvé, false sinon.

Question 3b

---

Écrivez une fonction recherche_liste: (char * trie) list -> char -> trie, qui, en supposant qu'un caractère est présent dans la liste donnée en entrée, renvoie le trie correspondant.

Question 3c

---

Écrivez une fonction recherche: trie -> char list -> bool, qui cherche la présence d'un mot dans un trie, et renvoie true si elle la trouve, false sinon.

Notez bien que la fonction prend en argument un char list et pas une chaine de caractère. Cela vous simplifiera la tâche. Je vous fourni une fonction s2l: string -> char list qui réalise la conversion, ce sera ainsi plus simple d'écrire des tests.

Comment « modifier » un trie ?

---

En OCaml, la plupart des structures de données sont immutables, c'est à dire qu'on ne peut pas les modifier. Il faut donc renvoyer une nouvelle version de la structure.

Je vous donne un exemple sur une structure simple : une fonction qui insère un élément à sa place dans une liste croissante.

let rec insere (l: int list) (x: int): int list = match l with 
    |[] -> [x]
    |y::q -> if x < y then x::l 
             else y::(insere q x)
;;

Ainsi, la fonction insere renvoie toujours une nouvelle liste, construite à partir de la liste originelle.

Question 4

---

Écrivez une fonction ajout: trie -> char list -> trie qui prend un trie et une chaine de caractère en argument, et renvoie le trie auquel on a ajouté la chaine de caractère.

Question 5

---

En déduire une fonction creer_trie: string list -> trie qui créé un trie contenant tous les mots d'une liste de mots. Quelle est la complexité ce creer_trie, en fonction de L la taille maximale d'un mot et de n le nombre de mots ?

Question 6

---

Créez le trie correspondant et vérifiez avec vos fonctions compter_mots et recherche que c'est cohérent.

Question 7

---

Écrivez une fonction liste_mots: trie -> string list qui renvoie la liste de tous les mots d'un trie. Je vous fourni pour cela la fonction l2s, qui fait l'inverse de s2l, et rev_l2s, qui inverse l'ordre des lettres en plus.

Question 8

---

Écrivez une fonction liste_suite: trie -> char list -> string list qui prend en argument un préfixe et qui renvoie tous les mots suffixes possibles permettant de terminer ce mot.

Question 9

---

Quelle est la complexité de cette opération, en fonction de k la taille du préfixe et de p le nombre de suffixes possibles ?

Question bonus

---

Les trie ne sont pas toujours le meilleur outil pour ce genre d'opérations, car on est obligé de procéder lettre par lettre. Quand tous les mots possibles ont le même groupement de lettres, on pourrait "compresser" ce groupement en un seul noeud.

La structure devient alors un « arbre radix ».

Réfléchissez à comment vous pourriez implémenter un tel arbre.

Vous pouvez utiliser le module Map, qui réalise une sorte d'équivalent de dictionnaire :

• module StringMap = Map.Make(String);; pour "importer" le type StringMap, un dictionnaire dont les clés sont des string
• StringMap.empty : le dictionnaire vide, de type 'a StringMap.t où 'a est le type des valeurs du dictionnaire.
• StringMap.add : string -> 'a -> 'a StringMap.t -> 'a StringMap.t : ajoute une nouvelle association au dictionnaire (mais sans le modifier : c'est un nouveau dictionnaire qui est renvoyé)
• StringMap.mem : string -> 'a StringMap.t -> bool : teste si un élément est présent dans la map
• StringMap.find : string -> 'a StringMap.t -> 'a : récupère un élément présent dans la map

Voir la documentation du module Map.