Un tableau associatif par arbre binaire de recherche

Ce qu'on exige des clés : un ordre total. C'est la phrase que le chapitre a citée du programme, et elle est nécessaire : à chaque nœud la descente doit trancher entre « à gauche » et « à droite », donc comparer deux clés quelconques. L'égalité seule ne suffirait pas — c'est tout ce que demande une table de hachage, et c'est la différence de contrat entre les deux structures (chapitre chap:hachage).

(* Un dictionnaire de clés 'c vers des valeurs 'v.
   INVARIANT : pour tout Nd (g, c, v, d), toutes les clés de g sont < c
   et toutes celles de d sont > c. Une clé apparaît au plus une fois. *)
type ('c, 'v) dico = Vide | Nd of ('c,'v) dico * 'c * 'v * ('c,'v) dico

(* Renvoie Some v si c est liée à v, None sinon. Complexité : O(h). *)
let rec trouve c = function
  | Vide -> None
  | Nd (g, k, v, d) ->
      if c = k then Some v
      else if c < k then trouve c g
      else trouve c d

(* Renvoie le dico où c est liée à v, en ÉCRASANT une liaison antérieure.
   Complexité : O(h) en temps et en mémoire neuve. *)
let rec pose c v = function
  | Vide -> Nd (Vide, c, v, Vide)
  | Nd (g, k, w, d) ->
      if c = k then Nd (g, c, v, d)              (* on écrase, on n'empile pas *)
      else if c < k then Nd (pose c v g, k, w, d)
      else Nd (g, k, w, pose c v d)

(* Liste des couples, TRIÉE par clé croissante. Complexité : Theta(n). *)
let rec couples a acc = match a with
  | Vide -> acc
  | Nd (g, k, v, d) -> couples g ((k, v) :: couples d acc)

Correction de trouve : par induction structurelle, exactement comme celle de appartient dans le cours ; si $c<k$, l'invariant garantit qu'aucune clé du sous-arbre droit ne vaut $c$, donc chercher à gauche est exhaustif.

Complexités : $O(h)$ pour trouve et pose, donc $O(\log n)$ si l'arbre est équilibré et $O(n)$ s'il dégénère ; $\Theta (n)$ pour couples, qui rend les clés triées sans le moindre travail supplémentaire.

Le point de contrat à ne pas manquer : pose écrase. C'est la sémantique d'un tableau associatif — une valeur par clé. On verra au chapitre chap:hachage que Hashtbl.add fait l'inverse et empile les liaisons : le même mot recouvre deux contrats différents, et c'est une source d'erreurs bien réelle.