Le $k$-ième plus petit en $O(h)$

L'idée : augmenter chaque nœud de la taille de son sous-arbre. Cette information suffit à savoir, à chaque nœud, de quel côté se trouve le rang cherché.

(* Le champ entier porte la TAILLE du sous-arbre enraciné ici.
   INVARIANT : dans N (g, e, d, t), on a t = 1 + taille(g) + taille(d). *)
type 'a arbre_t = V | N of 'a arbre_t * 'a * 'a arbre_t * int

let tll = function V -> 0 | N (_, _, _, t) -> t
let noeud g e d = N (g, e, d, 1 + tll g + tll d)   (* le SEUL constructeur *)

let rec insere x = function
  | V -> noeud V x V
  | N (g, e, d, _) as a ->
      if x = e then a
      else if x < e then noeud (insere x g) e d
      else noeud g e (insere x d)

(* Renvoie le k-ième plus petit élément, k >= 1. Complexité : O(h). *)
let rec kieme k = function
  | V -> failwith "hors bornes"
  | N (g, e, d, _) ->
      let ng = tll g in
      if k = ng + 1 then e            (* la racine EST le rang cherché *)
      else if k <= ng then kieme k g
      else kieme (k - ng - 1) d       (* on RETRANCHE ce qu'on a sauté *)

Spécification : entrée un ABR augmenté de $n$ nœuds et un entier $k$ avec $1\le k\le n$ ; sortie l'élément de rang $k$ dans l'ordre croissant. Terminaison : chaque appel descend d'un niveau ; le variant est la hauteur du sous-arbre courant. Correction : l'invariant de rang est « l'élément cherché est le $k$-ième du sous-arbre courant ». À la racine il tient par hypothèse ; si $k\le n_g$, l'ABR garantit que les $n_g$ plus petits sont exactement ceux de $g$, et le rang y est inchangé ; sinon on saute $g$ et la racine, soit $n_g+1$ éléments, d'où le nouveau rang $k-n_g-1$. Complexité : $O(h)$, donc $O(\log n)$ sur un arbre équilibré.

Mesuré sur un arbre équilibré de $1023$ nœuds : kieme 700 visite $8$ nœuds, contre $1023$ éléments parcourus par la liste infixe.

Le prix. Trois lignes de discipline. Le champ t est redondant : il duplique une information déjà présente dans la structure. Toute fonction qui construit un nœud doit donc le recalculer, sans quoi l'invariant est rompu — et rien ne le signalera. On s'en protège en n'exposant qu'un seul constructeur, noeud, qui calcule la taille lui-même : le type abstrait du chapitre chap:abstraction sert exactement à cela. On paye aussi un mot mémoire par nœud, et la mise à jour du champ sur tout le chemin d'insertion — mais ce chemin était déjà parcouru, donc la complexité ne change pas.