Probleme – 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.

2. Ce qu'on peut craindre. Le procédé prend toujours dans le sous-arbre droit. Supprimer un nœud à deux fils allège donc systématiquement la droite et laisse la gauche intacte. Répété, ce biais doit déséquilibrer l'arbre vers la gauche — et rien dans la structure ne le corrige, puisqu'un ABR nu ne se rééquilibre jamais.

3. La mesure. On part d'un ABR de $n$ clés insérées en ordre aléatoire, puis on exécute $n^2$ couples « supprimer une clé au hasard, la réinsérer ». La taille reste $n$ à chaque instant — vérifié. Mesuré :

La crainte était fondée. À $n=2048$, la profondeur moyenne passe de $12,4$ à $21,5$ — l'arbre est devenu presque deux fois plus profond, et la hauteur maximale de $24$ à $51$. La variante symétrique — qui tire à pile ou face entre successeur et prédécesseur — reste à $10,75$, c'est-à-dire sous sa valeur de départ. La correction tient en une ligne :

| _, _ ->
    if Random.bool ()
    then let s = minimum d in Noeud (g, s, supprime s d)         (* successeur *)
    else let p = maximum g in Noeud (supprime p g, p, d)         (* prédécesseur *)

La théorie prédit que la profondeur moyenne sous suppression asymétrique croît en $\Theta (\sqrt{n})$ — ce qui donnerait $45$ pour $n=2048$ à la limite ; nos $n^2$ opérations en montrent la moitié du chemin, et la tendance est nette.

La leçon. Une opération correcte peut détruire une propriété qu'aucune de ses postconditions ne mentionne. supprime rend toujours un ABR valide — sa spécification est respectée à la lettre, à chaque appel. Ce qu'elle dégrade est la forme, dont on n'a rien promis, et dont dépend pourtant toute la complexité. C'est précisément pour ne plus dépendre d'une forme non spécifiée que l'on passe à l'arbre bicolore, où l'équilibrage fait partie du contrat.