Problème — La suppression dans un ABR, et la dégradation qu'elle provoque

1. Les trois cas.

(* Renvoie le minimum de l'arbre. Précondition : a n'est pas vide. *)
let rec minimum = function
  | Vide -> failwith "arbre vide"
  | Noeud (Vide, e, _) -> e            (* le minimum est TOUT À GAUCHE *)
  | Noeud (g, _, _) -> minimum g

(* Renvoie l'ABR privé de x. Si x est absent, renvoie l'arbre inchangé.
   Précondition : a est un ABR. Complexité : O(h). *)
let rec supprime x = function
  | Vide -> Vide
  | Noeud (g, e, d) ->
      if x < e then Noeud (supprime x g, e, d)
      else if x > e then Noeud (g, e, supprime x d)
      else match g, d with
        | Vide, _ -> d                 (* (a) et (b) : au plus un fils *)
        | _, Vide -> g
        | _, _ ->                      (* (c) deux fils : le SUCCESSEUR remonte *)
            let s = minimum d in
            Noeud (g, s, supprime s d)

(a) Feuille : on rend Vide. (b) Un seul fils : on rend ce fils — les deux premiers motifs traitent les deux cas d'un coup. (c) Deux fils : on ne peut supprimer le nœud sans le remplacer, et le seul remplaçant valide est le successeur — le plus petit du sous-arbre droit — ou le prédécesseur. On le remonte, puis on le supprime de sa position d'origine ; ce second appel tombe forcément dans le cas (a) ou (b), puisque le minimum d'un arbre n'a pas de fils gauche.

Préservation de l'invariant (cas (c), les autres étant immédiats). Soit $s$ le minimum de $d$. Toutes les étiquettes de $g$ sont $<e<s$, donc $<s$ : l'invariant tient à gauche. Toutes celles de $d\setminus \{s\}$ sont $>s$ par minimalité de $s$ : il tient à droite. Terminaison : chaque appel descend d'un niveau, le variant est la hauteur du sous-arbre. Complexité : $O(h)$ pour la descente, plus $O(h)$ pour le minimum et la suppression secondaire, soit $O(h)$.

Mesuré sur $2,4,6,8,10,12,13,14$ : retirer $2$ (feuille), $14$ (un fils), $12$ (deux fils) ou $99$ (absent) rend à chaque fois un ABR valide, contrôlé par la croissance du parcours infixe.