Problème — Suppression d'une valeur dans un ABR

On localise d'abord le nœud à supprimer comme pour une recherche. Trois cas se présentent une fois trouvé :

• le nœud est une feuille : on le remplace par None ;
• le nœud a un seul enfant : on le remplace par cet enfant ;
• le nœud a deux enfants : on le remplace par son successeur (la plus petite valeur de son sous-arbre droit), que l'on supprime ensuite de ce sous-arbre.

def min_valeur(arbre):
    # plus petite valeur d'un ABR : le noeud le plus a gauche
    while arbre.gauche is not None:
        arbre = arbre.gauche
    return arbre.valeur

def supprimer(arbre, x):
    if arbre is None:
        return None
    if x < arbre.valeur:
        arbre.gauche = supprimer(arbre.gauche, x)
    elif x > arbre.valeur:
        arbre.droit = supprimer(arbre.droit, x)
    else:
        # noeud trouve : on traite les trois cas
        if arbre.gauche is None:
            return arbre.droit        # 0 ou 1 enfant (a droite)
        if arbre.droit is None:
            return arbre.gauche       # 1 enfant (a gauche)
        # deux enfants : on prend le successeur
        succ = min_valeur(arbre.droit)
        arbre.valeur = succ
        arbre.droit = supprimer(arbre.droit, succ)
    return arbre

Dans le cas à deux enfants, le successeur est la plus petite valeur du sous-arbre droit : c'est la seule valeur qui peut prendre la place du nœud supprimé tout en conservant la propriété d'ordre (toutes les valeurs à gauche lui restent inférieures, toutes celles à droite supérieures). La suppression a un coût de $O(h)$, soit $O(\log n)$ pour un arbre équilibré.