trie.ml

(* Type représentant un trie. *)

type 'a trie =
    Node of ('a option * (char * 'a trie) list) (* la liste des caractères permettant *)
(*                  ^            ^_____________    de continuer sur un sous-arbre     *)
(*                  |                                                                 *)
(*  la valeur stockée au chemin courant, i.e.
    celui qui nous a permis d'arriver jusqu'à cet arbre.
    si value vaut None, le nœud n'est pas terminal.
    S'il vaut Some v, alors le nœud est terminal et il
    est associé à une valeur v.
*)
(* quelques exemples de valeurs *)

(* L'arbre vide, qui associe la clé "" à un nœud non-terminal. *)
let empty = Node (None, [])

(* Le trie représentant { "a" -> 42;   "b" -> "43" } *)
let ex1 = Node (None,   (* Niveau 0 = clé "", pas de valeur *)
                [ ('a',
                   Node (Some 42, [])); (*Niveau 1, clé "a", un sous-arbre avec 42 *)
                  ('b',
                   Node (Some 43, [])); (*Niveau 1, clé "b", un sous-arbre avec 43 *)
                ])
(* Le trie représentant { "" -> 41; "ab" -> 42; "ba" -> 43; "bb" -> 44 }*)
let ex2 = Node (Some 41,   (* Niveau 0 = clé "",  valeur 41 *)
                [ ('a',
                   Node (None,  (*Niveau 1, clé "a", pas de valeur *)
                         [('b',
                           Node (Some 42, [])) (*Niveau 2, clé "ab", valeur 42 *)
                         ]));
                  ('b',
                   Node (None,  (*Niveau 1, clé "b", pas de valeur *)
                         [('a',
                           Node (Some 43, [])); (*Niveau 2, clé "ba", valeur 43 *)
                          ('b',
                           Node (Some 44, [])); (*Niveau 2, clé "bb", valeur 44 *)
                         ]))
                ])

(* Un trie est vide si et seulement si il a la même
   structure que 'empty' ci-dessus. *)
let is_empty e =
  match e with
    Node (None, []) -> true
  | _ -> false


(* Fonction qui implémente la recherche (pseudo-code slide 10)

   Cette fonction renvoie le sous-arbre auquel on peut accéder en
   suivant dans l'ordre tous les caractères de key.
   La fonction suivante (find) s'occupe de tester si ce nœud est terminal.
*)
let find_trie key t =
  let rec find_node i t =
    if i = String.length key then t  (* Si on a parcouru toute la clé
                                        on renvoie le nœud sur lequel on
                                        est arrivé *)
    else
      match t with Node (_, l) -> find_list i l
  (* Sinon, on va chercher le sous-arbre suivant dans la liste l *)

  and find_list i l =
    let ci = key.[i] in
    match l with
      [] -> raise Not_found   (* Si on est en bout de liste, pas de sous-arbre
                                 pour le caractère ci *)
    | (d, t) :: ll ->
      if ci > d then find_list i ll  (* si le caractère cherché est plus grand que
                                        le caractère en tête de liste, on avance *)

      else if ci = d then find_node (i+1) t (* s'ils sont égaux, on a trouvé le bon sous
                                               arbre, on fait l'appel recursif en
                                               avançant au caractère suivant *)
      else raise Not_found           (* sinon, le caractère en tête de liste est plus
                                        grand, donc ci n'est pas dans la liste car
                                        elle est triée, on échoue. *)
  in
  find_node 0 t

(* La fonction find permet de trouver une valeur associé
   à une clé. Elle utilise find_trie qui fait tout le travail et
   elle se contente d'analyser le nœud renvoyé pour savoir si
   c'est un nœud terminal (= avec une valeur) ou non. *)
let find key t =
  match find_trie key t with  (* Peut lever une exception si key ne permet
                                 pas d'atteindre un nœud *)
    Node (Some v, _) -> v
  | Node (None, _) -> raise Not_found  (* dernier cas d'exception, le
                                          nœud trouvé n'est pas terminal *)