#Arbres binaires de rechercheCopier le lien

Prérequis: arbres, hauteurs et parcours (chapitre précédent), récursivité sur les structures.

Objectifs:

• Énoncer l'invariant de recherche et montrer qu'il ordonne tout l'arbre, pas seulement les paires parent-enfant.
• Dérouler recherche, insertion et suppression, y compris le cas délicat des deux enfants.
• Expliquer pourquoi la hauteur, et non la taille, gouverne tous les coûts, et ce que les arbres équilibrés y ajoutent.

#L'invariant de rechercheCopier le lien

Un arbre binaire de recherche (BST) est un arbre binaire dont chaque nœud porte une clé telle que, pour tout nœud N:

toutes les clés du sous-arbre gauche de N sont < clé(N) < toutes les clés du sous-arbre droit de N

L'invariant porte sur les sous-arbres entiers, pas sur les seuls fils directs. Un arbre peut vérifier clé(gauche) < clé(racine) < clé(droit) à chaque nœud et pourtant ne pas être un BST: sur

1      502     /  \3   30    704     \5      60        <- 60 est bien > 30 (son parent)...

le nœud 60 viole l'invariant: il habite le sous-arbre gauche de 50 mais 60 > 50. Une recherche de 60 partirait à droite et échouerait. C'est l'erreur classique de validation, traitée en exercice.

Conséquence de l'invariant: le parcours infixe visite les clés en ordre trié croissant, en O(n). Le BST est ainsi un ensemble ordonné dynamique.

#Animation interactiveCopier le lien

Insérez et cherchez des clés, puis observez le chemin parcouru: à chaque nœud, une seule comparaison élimine tout un sous-arbre.

Fait à vérifier en manipulant: insérez 50, 30, 70, 20, 40, 60, 80 puis appelez le parcours infixe (ou constatez l'ordre de vos insertions face à l'arbre obtenu). Quel que soit l'ordre d'insertion de ces clés, le parcours infixe rend 20, 30, 40, 50, 60, 70, 80: l'invariant impose l'ordre, pas la forme.

#Le contrat: quelles opérations un BST doit-il rendre?Copier le lien

Un BST est l'implantation d'un ensemble dynamique ordonné. Deux familles d'opérations, à ne pas confondre:

Requêtes — RECHERCHER(S, k) renvoie un pointeur vers l'élément de clé k ou NIL; MINIMUM(S) et MAXIMUM(S) renvoient la plus petite et la plus grande clé; SUCCESSEUR(S, x) et PRÉDÉCESSEUR(S, x) renvoient la clé immédiatement supérieure ou inférieure à celle de x, ou NIL.

Modifications — INSÉRER(S, x) ajoute l'élément pointé par x; SUPPRIMER(S, x) retire l'élément pointé par x.

Une précision d'énoncé qui a son importance: SUPPRIMER prend un pointeur sur un élément, pas une valeur de clé. Supprimer « la clé 42 » suppose donc une recherche préalable pour obtenir le pointeur — d'où la distinction entre le coût de la suppression elle-même (qui suit un chemin, O(h)) et celui de « trouver puis supprimer » (qui est le même O(h) pour un BST, mais ne l'est pas pour une liste chaînée, où la recherche domine).

Les requêtes d'ordre n'ont de sens que si les clés sont prises dans un ensemble totalement ordonné (les entiers, les mots sous l'ordre alphabétique): sans ordre total, parler du « plus petit » élément ou du « suivant » n'a pas de contenu. C'est cette hypothèse, inscrite dans l'invariant de recherche, qui permet la propriété la plus utile du BST:

un appel à MINIMUM, suivi de n − 1 appels à SUCCESSEUR, énumère les n éléments de l'ensemble en ordre trié.

C'est aussi ce qu'un parcours infixe réalise directement en O(n). Une table de hachage, elle, ne sait faire aucune de ces quatre requêtes: elle rend le dictionnaire pur (RECHERCHER, INSÉRER, SUPPRIMER en O(1) attendu) mais perd toute notion d'ordre. Le choix entre les deux structures se joue exactement là.

#Opérations et coûtsCopier le lien

Toutes les opérations suivent un chemin racine-feuille: leur coût est O(h), où h est la hauteur. Pour un arbre presque complet (la meilleure forme possible), h = ⌊log₂ n⌋, soit h = Θ(log n) et n entre 2^h et 2^(h+1) − 1. Un arbre seulement équilibré (AVL, rouge-noir) garantit aussi h = Θ(log n), mais avec une constante plus grande: h ≤ 1,44 log₂ n en AVL, h ≤ 2 log₂ n en rouge-noir. Pour un arbre dégénéré (clés insérées déjà triées), h = n − 1 et le BST n'est qu'une liste chaînée déguisée, avec le pire coût O(n).

La borne inférieure est la même pour tout arbre binaire: n nœuds ne peuvent pas tenir dans moins de ⌊log₂ n⌋ + 1 niveaux. La borne supérieure, elle, n'est pas automatique — c'est exactement ce que l'équilibrage achète.

#RechercheCopier le lien

1class Noeud:2    def __init__(self, valeur):3        self.valeur = valeur4        self.gauche = None5        self.droit = None6 7def rechercher(noeud, valeur):8    if noeud is None or noeud.valeur == valeur:9        return noeud                 # arbre vide (échec) ou clé trouvée10    if valeur < noeud.valeur:11        return rechercher(noeud.gauche, valeur)12    return rechercher(noeud.droit, valeur)

Sur l'arbre 50 / (30, 70) / (20, 40, 60, 80), la recherche de 40 descend 50 → 30 → 40: trois comparaisons et tous les autres sous-arbres sont écartés sans être visités. C'est la recherche binaire du tableau trié, transposée dans un arbre; la différence est que l'arbre reste dynamique sans décaler des éléments.

#InsertionCopier le lien

L'insertion emprunte exactement le chemin d'une recherche qui échoue, puis accroche la nouvelle clé à la place de l'échec: une feuille. L'invariant est préservé car la nouvelle clé arrive dans son propre intervalle.

1def inserer(noeud, valeur):2    if noeud is None:3        return Noeud(valeur)          # attache ici: position de l'échec de recherche4    if valeur < noeud.valeur:5        noeud.gauche = inserer(noeud.gauche, valeur)6    elif valeur > noeud.valeur:7        noeud.droit = inserer(noeud.droit, valeur)8    # valeur == noeud.valeur: rien (ensemble, pas de doublons)9    return noeud10 11racine = None12for v in [50, 30, 70, 20, 40, 60, 80]:13    racine = inserer(racine, v)

Notez le passage noeud.gauche = inserer(...): la fonction renvoie le sous-arbre éventuellement modifié, même convention qui servira à la suppression. Insérer 50, 30, 20, 40, 70 dans cet ordre donne:

1       502      /  \3     30   704    / \5   20  40

Insérez maintenant 10, 5, 3, 1: chaque clé descend la branche gauche, l'arbre s'allonge sans jamais se rééquilibrer. La forme dépend entièrement de l'ordre d'arrivée; seule la distribution triée en infixe est garantie.

#Suppression: les trois casCopier le lien

1. Feuille (aucun enfant): détacher, renvoyer None au parent.
2. Un seul enfant: court-circuiter le nœud, le parent pointe directement sur l'enfant.
3. Deux enfants: remplacer la clé du nœud par celle de son successeur infixe (le minimum du sous-arbre droit, qui n'a pas de fils gauche par définition) puis supprimer ce successeur, ce qui retombe sur le cas 1 ou 2.

Le cas 3 est correct car le successeur infixe de N est la plus petite clé strictement supérieure à clé(N): elle est à sa place au sommet des deux sous-arbres, tous les autres ordres relatifs restent intacts.

1def trouver_min(noeud):2    while noeud.gauche is not None:3        noeud = noeud.gauche4    return noeud5 6def supprimer(noeud, valeur):7    if noeud is None:8        return None                   # clé absente: arbre inchangé9    if valeur < noeud.valeur:10        noeud.gauche = supprimer(noeud.gauche, valeur)11    elif valeur > noeud.valeur:12        noeud.droit = supprimer(noeud.droit, valeur)13    else:14        # noeud à supprimer trouvé

À rejouer sur 50 / (30, 70) / (20, 40, 60, 80): la suppression de 30 (deux enfants) prend le successeur infixe, c'est-à-dire le minimum du sous-arbre droit de 30. Ce sous-arbre droit se réduit à la feuille 40: la clé 40 remonte à la place de 30, puis l'ancien nœud 40 (cas feuille) est détaché. Arbre résultat: 50 / (40, 70) / (20, ∅, 60, 80), parcours infixe 20, 40, 50, 60, 70, 80. La clé 30 a disparu, l'ordre est intact: le successeur est par définition la plus petite clé strictement supérieure à 30, il est donc à sa place au sommet des deux sous-arbres restants.

Détail de conception du cas 3: déplacer une clé (recopier successeur.valeur) est plus simple que recâbler des nœuds; dans un vrai dictionnaire, on déplace aussi la charge associée à la clé. Une variante, la suppression paresseuse, se contente de marquer le nœud supprimé. Dans tous les cas le coût reste O(h).

#Parcours et sérialisationCopier le lien

1def infixe(noeud, acc):2    """Remplit acc avec les clés en ordre croissant."""3    if noeud is None:4        return acc5    infixe(noeud.gauche, acc)6    acc.append(noeud.valeur)7    infixe(noeud.droit, acc)8    return acc9 10print(infixe(racine, []))    # [20, 40, 50, 60, 70, 80] après la suppression de 30

Le parcours préfixe d'un BST sert de sérialisation compacte: réinsérer les clés dans l'ordre préfixe reconstruit exactement le même arbre, ce que l'ordre infixe ne garantit pas (il donne toujours un peigne droite).

#BST ou table de hachageCopier le lien

Règle pratique: accès pur par clé et aucun besoin d'ordre, la table de hachage gagne; intervalles, getline triée, énumération ordonnée ou garantie de pire cas, le BST équilibré gagne. En Python: dict pour le premier cas, sortedcontainers.SortedDict ou un module tiers pour le second (l'arbre rouge-noir est livré en standard dans les TreeMap de Java).

#Arbres équilibrésCopier le lien

Un BST naïf ne contrôle pas sa hauteur: insérer des clés déjà triées produit un peigne de hauteur n − 1. Les AVL et rouge-noir réparent l'arbre par rotations lors de chaque insertion/suppression pour garantir h = O(log n) (hauteur ≤ 1,44 log₂ n en AVL, ≤ 2 log₂ n en rouge-noir). Le coût des opérations reste O(log n) dans le pire cas, au prix d'un rééquilibrage constant mais borné. Sans ce mécanisme, la colonne « équilibré » du tableau des coûts n'est qu'un espoir statistique: sur des clés triées ou presque, elle ressemble à la colonne « dégénéré ».

#Exercice 1: valider un BST correctementCopier le lien

Écrire est_bst(racine) qui distingue l'arbre à 60 sous 30 (invalide) d'un vrai BST.

Correction: transportez un intervalle (min, max) le long de la récursion, hérité de tous les ancêtres et pas seulement du parent. Chaque nœud doit vérifier min < clé < max; le fils gauche hérite de (min, clé) et le fils droit de (clé, max).

1def est_bst(noeud, borne_min=float('-inf'), borne_max=float('inf')):2    if noeud is None:3        return True4    if not (borne_min < noeud.valeur < borne_max):5        return False6    return (est_bst(noeud.gauche, borne_min, noeud.valeur)7            and est_bst(noeud.droit, noeud.valeur, borne_max))

Sur l'arbre à 60: à la racine 50, intervalle (−∞, +∞), ok. Descendre à gauche transmet (−∞, 50); le nœud 60 vérifie 60 < 50, faux. La version naïve qui ne compare qu'aux fils aurait répondu vrai.

Variante correcte sans paramètres: faire le parcours infixe et vérifier que la séquence est strictement croissante, O(n) et O(h) mémoire.

#Exercice 2: suppression sur papierCopier le lien

Sur 50 / (30, 70) / (20, 40, 60, 80), supprimer successivement 20 (feuille), puis 50 (deux enfants). Donner le parcours infixe après chaque étape.

Correction:

1. Suppression de 20: feuille, détachée. Infixe: 30, 40, 50, 60, 70, 80.
2. Suppression de 50 (racine, deux enfants): le successeur infixe est le minimum du sous-arbre droit, soit 60 (branche gauche: 70 → 60). La clé 60 remonte en racine, puis l'ancien nœud 60 (feuille) est supprimé du sous-arbre droit. Arbre: 60 / (30, 70) / (∅, 40, ∅, 80). Infixe: 30, 40, 60, 70, 80: même ensemble, ordre intact, un nœud de moins.

Attention au piège symétrique: prendre le prédécesseur (maximum du sous-arbre gauche, ici 40) est tout aussi correct. Prendre « n'importe quelle feuille » ne l'est pas.

#Mini-quizCopier le lien