Arbres binaires de recherche : rechercher et insérer

Un cap pour ce chapitre

Ce que vous saurez faire

Vérifier la propriété globale d’un ABR.
Tracer une recherche et une insertion.
Relier le coût à la hauteur.

Les bases utiles pour commencer

Une propriété portant sur des sous-arbres entiers

Nous adoptons une convention sans doublons : toutes les clés du sous-arbre gauche sont strictement inférieures à la clé du nœud, et toutes celles du sous-arbre droit sont strictement supérieures. La règle s’applique récursivement à chaque nœud. Elle ne concerne pas seulement les deux enfants immédiats.

Une racine 8 peut avoir un enfant gauche 3, mais un descendant 12 placé sous ce 3 rendrait l’ensemble invalide : 12 appartient au sous-arbre gauche de 8 tout en étant supérieur à 8. Pour vérifier un ABR, on doit donc conserver les contraintes héritées des ancêtres, sous forme de bornes autorisées.

À chaque descente, conservez un intervalle de clés autorisées. Partir à gauche de 8 fixe une borne supérieure 8 ; aller ensuite à droite de 3 ajoute une borne inférieure 3. Une clé dans cette région doit satisfaire simultanément 3 < clé < 8, et non seulement dépasser 3.

Rechercher en suivant un seul chemin

Pour rechercher une clé k, on compare k à la racine. Si elles sont égales, la recherche réussit. Si k est plus petite, on poursuit seulement à gauche ; sinon seulement à droite. Si l’on atteint un sous-arbre vide, la clé est absente. Ce dernier cas est une conclusion normale, pas une erreur d’exécution.

Dans l’arbre 8, gauche 3 avec enfants 1 et 6, droite 10 avec enfant droit 14, chercher 6 compare successivement 8, 3 puis 6. Chercher 7 suit 8, 3, 6 puis atteint le sous-arbre droit vide de 6. Les comparaisons éliminent des régions entières grâce à la propriété d’ordre.

def contient(arbre, cle):
    # Un nœud est (valeur, gauche, droite) ; None est vide.
    courant = arbre
    while courant is not None:
        valeur, gauche, droite = courant
        if cle == valeur:
            return True
        courant = gauche if cle < valeur else droite
    return False

Insérer au premier emplacement vide

L’insertion suit les mêmes comparaisons qu’une recherche. Lorsque le sous-arbre approprié est vide, on y place la nouvelle feuille. Insérer 7 dans l’exemple le place comme enfant droit de 6. On ne le place pas directement sous 8 au seul motif qu’il est inférieur à 8 : il faut poursuivre les contraintes jusqu’au bon emplacement.

Pour un doublon, plusieurs politiques sont possibles. Ici, nous ne créons pas de nouveau nœud si la clé existe déjà. Une autre convention pourrait autoriser des doublons dans une branche déterminée, mais elle devrait être annoncée et appliquée partout, y compris dans les tests et les parcours.

Cette insertion fonctionnelle renvoie l’arbre obtenu sous forme de tuples. L’appelant doit conserver ce retour, notamment lorsque la racine était vide. Les branches non modifiées peuvent être partagées puisqu’aucun tuple existant n’est muté.

def inserer(arbre, cle):
    if arbre is None:
        return (cle, None, None)
    valeur, gauche, droite = arbre
    if cle < valeur:
        return (valeur, inserer(gauche, cle), droite)
    if cle > valeur:
        return (valeur, gauche, inserer(droite, cle))
    return arbre  # Doublon ignoré.

arbre = None
for cle in [8, 3, 10, 1, 6, 14]:
    arbre = inserer(arbre, cle)

La hauteur gouverne les recherches

Une recherche ne visite qu’un chemin, donc son travail dépend de la hauteur. Dans un arbre suffisamment équilibré, cette hauteur est logarithmique en la taille. Dans une chaîne de n nœuds, une recherche peut effectuer n comparaisons. Un ABR ordinaire ne garantit pas spontanément l’équilibre.

Insérer des clés déjà triées, toujours à droite, crée précisément une chaîne. Le parcours infixe restera trié, mais l’avantage en recherche se sera dégradé. Les mécanismes de rééquilibrage dépassent cette introduction : l’objectif est d’expliquer le lien entre ordre d’insertion, forme, hauteur et coût, sans attribuer un coût logarithmique à tous les arbres.

Exemple suivi : construire l’arbre et ses contraintes

Insérons 8,3,10,1,6,14 puis 4. Huit devient racine. Trois se place à gauche et dix à droite. Un descend à gauche de trois ; six à droite de trois ; quatorze à droite de dix. Pour quatre, on compare 8 puis 3 puis 6 : quatre est inférieur à huit, supérieur à trois, inférieur à six. Le premier emplacement compatible vide est donc le fils gauche de six.

Les bornes héritées y sont 3 et 6. Le nouveau nœud respecte aussi automatiquement la borne supérieure huit. Pour rechercher 5 après cette insertion, on visite 8,3,6,4 puis la droite vide de 4 : quatre comparaisons de clés, sans compter le test de vacuité comme comparaison de valeur. Une absence n’impose pas de parcourir les autres branches, car les comparaisons ont déjà prouvé qu’elles ne peuvent contenir la cible.

Exemple suivi : mesurer l’effet de l’ordre d’insertion

Les clés 1 à 7 insérées dans l’ordre croissant produisent une chaîne de hauteur six. Chercher 7 y examine sept clés. Insérons plutôt 4,2,6,1,3,5,7 : la racine partage les valeurs en deux groupes de trois, puis chaque groupe est partagé à son tour. La hauteur vaut deux et la recherche de 7 examine seulement 4,6,7. Les mêmes clés donnent donc des coûts très différents.

Dans les deux structures, le parcours infixe produit 1,2,3,4,5,6,7. Cette séquence vérifie l’ordre, mais ne mesure pas l’équilibre. Pour comparer, donnez taille, hauteur et nombre de clés réellement comparées sur une recherche précise. La racine se trouve en une comparaison, même dans une longue chaîne ; c’est le pire cas qui se dégrade avec la hauteur. Les doublons sont ignorés dans notre convention et n’augmentent donc ni taille ni hauteur.

À vous de faire varier les choses

Changez l’ordre d’insertion et cherchez une clé

Entrez au plus douze entiers de -99 à 99 séparés par des virgules. Les doublons sont ignorés. Les entrées hors de ce domaine sont signalées ; comparez un ordre trié avec un ordre qui répartit les branches.

Lire le résultat de l’expérience initiale

Sous-arbre vide : clé absente.

Chaque comparaison conserve seulement la branche compatible avec la propriété de recherche.

Clé comparée	Décision
8	Chercher à gauche
3	Chercher à droite
6	Chercher à droite

Indice 2

La même clé n’est jamais créée deux fois.

Comprendre la correction

Les hauteurs sont six et deux. Les deux infixes sont 1 à 7. Dans la chaîne, chercher 1 demande une comparaison et chercher 7 en demande sept ; dans l’arbre réparti, les deux recherches en demandent trois. Réinsérer 4 ne change aucune structure. Le contenu trié est identique, mais le coût dépend du chemin emprunté et de la hauteur.

Les erreurs qui méritent un détour

Vérifier uniquement les enfants immédiats.: Les bornes des ancêtres s’appliquent à tous les descendants.
Annoncer un coût logarithmique sans condition de forme.: Une chaîne est un ABR valide mais donne des recherches linéaires.

La fiche à garder

L’essentiel à retenir

L’ordre d’un ABR concerne des sous-arbres entiers.
Recherche et insertion suivent un seul chemin de comparaisons.
La hauteur et l’ordre d’insertion influencent le coût.

Cette notion au bac

Retrouvez ces idées dans un sujet complet, avec des indices, une correction expliquée et des ateliers.

Le prochain pas

Coûts en temps et en mémoire

Retrouver le catalogue de Terminale

Ce chapitre s’appuie sur le programme officiel de Terminale (PDF, nouvel onglet). Les explications et exercices sont proposés pour l’apprentissage.