Suppression dans un ABR : Les Trois Cas.

1. Vue d'ensemble des cas de suppression

L'algorithme de suppression commence toujours par la recherche du nœud à supprimer, une opération en $O(h)$. Une fois le nœud trouvé, la procédure de suppression effective dépend du nombre de ses enfants. Il existe trois scénarios distincts.

Pour une introduction claire et en français de ces trois cas, je vous propose de visionner la vidéo suivante.

Analysons maintenant chaque cas en détail.

2. Gestion des cas de suppression

Cas 1 : Le nœud à supprimer est une feuille (0 enfant)

C'est le cas le plus simple. Si le nœud à supprimer n'a aucun enfant, il suffit de le retirer de l'arbre en modifiant le pointeur de son parent (fils gauche ou droit) pour qu'il pointe vers null (ou None en Python).

Illustration de la suppression du nœud 45 (une feuille). Le pointeur left de son parent (60) est simplement mis à null.

L'algorithme consiste donc à :

1. Trouver le nœud à supprimer.
2. Trouver son parent.
3. Mettre à null le pointeur du parent qui pointait vers le nœud.

Cas 2 : Le nœud à supprimer a un seul enfant

Ce cas est également assez direct. Pour maintenir la connectivité de l'arbre, on "court-circuite" le nœud à supprimer : on attache son unique sous-arbre directement à son parent. Le parent du nœud supprimé pointe désormais vers l'enfant du nœud supprimé.

La procédure est la suivante :

1. Trouver le nœud Z à supprimer.
2. Identifier son unique enfant C.
3. Modifier le pointeur du parent de Z pour qu'il pointe vers C.

Cette opération préserve la propriété de l'ABR, car tous les éléments dans le sous-arbre de C respectent déjà la relation d'ordre par rapport au parent de Z.

Cas 3 : Le nœud à supprimer a deux enfants

C'est le cas le plus complexe, car nous ne pouvons pas simplement supprimer le nœud sans laisser un "trou" avec deux sous-arbres orphelins. La solution est de trouver un nœud de remplacement qui peut prendre la place du nœud supprimé tout en préservant l'invariant de l'ABR.

Deux candidats sont possibles pour ce remplacement :

• Le successeur en ordre infixe : le plus petit nœud dans le sous-arbre droit.
• Le prédécesseur en ordre infixe : le plus grand nœud dans le sous-arbre gauche.

Par convention, nous utiliserons le successeur.

L'algorithme est le suivant :

1. Soit Z le nœud à supprimer. Trouver son successeur, S (le nœud avec la plus petite clé dans le sous-arbre droit de Z).
2. Copier la valeur de S dans Z. À ce stade, l'arbre contient une valeur en double, mais la structure de l'ABR est (temporairement) valide au niveau de Z.
3. Supprimer récursivement le nœud S de sa position d'origine dans le sous-arbre droit.

Le point clé est que la suppression récursive de S tombera nécessairement dans le cas 1 ou le cas 2. En effet, S, étant le plus petit élément de son sous-arbre, ne peut pas avoir de fils gauche. Il est donc soit une feuille, soit il a un seul fils (droit).

Pour bien comprendre la subtilité de cette approche récursive, je vous recommande de regarder l'explication suivante, qui utilise Python.

3. Implémentation

L'implémentation est l'objectif principal de cette leçon. Nous allons voir deux versions : une en Python, que vous allez implémenter, et une en OCaml, pour vous préparer aux exigences de l'Agrégation.

Implémentation en Python

La vidéo de NeetCodeIO que vous venez de consulter pour la partie conceptuelle propose également une implémentation complète en Python. Votre tâche consiste maintenant à l'écrire vous-même.

Exercice d'implémentation :

En vous basant sur la logique expliquée, implémentez la fonction delete(self, value) pour la classe BinarySearchTree ci-dessous.

class TreeNode:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None

class BinarySearchTree:
    def __init__(self):
        self.root = None




    # ... (les fonctions d'insertion et de recherche que vous avez déjà écrites)

    def _find_min(self, node):
        current = node
        while current and current.left is not None:
            current = current.left
        return current

    def delete(self, key):
        self.root = self._delete_recursive(self.root, key)

    def _delete_recursive(self, node, key):



        # Cas de base: l'arbre est vide
        if not node:
            return node




        # Recherche du noeud à supprimer
        if key < node.key:
            node.left = self._delete_recursive(node.left, key)
        elif key > node.key:
            node.right = self._delete_recursive(node.right, key)
        else:



            # Le noeud à supprimer est trouvé
            



            # Cas 1: 0 ou 1 enfant
            if not node.left:
                return node.right
            elif not node.right:
                return node.left
            



            # Cas 2: 2 enfants
            # Trouver le successeur (le plus petit dans le sous-arbre droit)
            temp = self._find_min(node.right)
            



            # Copier la valeur du successeur dans ce noeud
            node.key = temp.key
            



            # Supprimer le successeur de sa position d'origine
            node.right = self._delete_recursive(node.right, temp.key)
            
        return node

Suggestion de squelette pour votre implémentation. Je vous encourage à l'écrire de zéro pour bien vous l'approprier, mais vous pouvez vous référer à ce code complet si besoin.

Formalisation en OCaml

Pour l'Agrégation, une maîtrise des concepts sous un angle fonctionnel est un atout majeur. Le document suivant, destiné à des classes préparatoires de haut niveau, présente une implémentation de la suppression en OCaml.

L'implémentation OCaml supprime k utilise le pattern matching pour distinguer les cas :

• Noeud (Nil, x, fd) -> fd : Le nœud x n'a pas de fils gauche. On renvoie son fils droit fd. (Cas 1 et 2)
• Noeud (fg, x, Nil) -> fg : Le nœud x n'a pas de fils droit. On renvoie son fils gauche fg. (Cas 2)
• Noeud (fg, x, fd) -> ... : Le nœud a deux fils. On appelle supprime_min fd pour trouver le successeur m et le nouvel arbre droit f, puis on reconstruit le nœud : Noeud (fg, m, f).

Cette approche est purement fonctionnelle : elle ne modifie pas l'arbre en place mais retourne un nouvel arbre.

Conclusion

Aujourd'hui, nous avons décortiqué et implémenté l'algorithme de suppression dans un ABR, l'opération la plus délicate sur cette structure.

Points clés à retenir :

• La suppression se divise en trois cas selon le nombre d'enfants du nœud à supprimer (0, 1 ou 2).
• Les cas avec 0 ou 1 enfant sont simples et consistent en un réarrangement de pointeurs.
• Le cas avec 2 enfants est le plus complexe. Il est résolu en remplaçant la valeur du nœud par celle de son successeur (ou prédécesseur) et en supprimant récursivement ce dernier de sa position initiale.
• Cette suppression récursive se ramène nécessairement à un cas plus simple (0 ou 1 enfant).
• L'ensemble de l'opération (recherche + réarrangement) a une complexité en $O(h)$, confirmant l'analyse de la leçon précédente.

Prochaine étape :
Nous avons maintenant une structure de données complète avec insertion, recherche et suppression efficaces... en théorie. Nous avons vu que la performance dépend crucialement de la hauteur de l'arbre. Les opérations d'insertion et de suppression que nous avons écrites ne garantissent en rien que l'arbre restera équilibré. Au contraire, une suite malheureuse d'opérations peut le rendre complètement dégénéré. Dans la prochaine leçon, nous aborderons de front ce problème du déséquilibre et introduirons le principe des arbres auto-équilibrants (comme les arbres AVL), qui sont la solution canonique à cette limitation des ABR simples.