Rechercher, insérer, supprimer et maintenir un ensemble ordonné

Fiche pédagogique du chapitre

Objectifs d’apprentissage

À la fin de ce chapitre, l’étudiant devra être capable de :

• énoncer et vérifier la propriété d’ordre d’un arbre binaire de recherche ;
• définir une politique cohérente pour la gestion des clés dupliquées ;
• rechercher une clé de manière itérative ou récursive ;
• insérer une nouvelle clé sans rompre l’invariant d’ordre ;
• déterminer le minimum, le maximum et le successeur d’un nœud ;
• supprimer un nœud dans chacun des trois cas fondamentaux ;
• justifier la correction des opérations à partir de l’invariant de l’arbre ;
• analyser le coût des opérations selon la hauteur et la forme de l’arbre ;
• modéliser un répertoire, un classement, un dictionnaire ordonné ou un index d’étudiants.

Prérequis

• Vocabulaire et représentations des arbres binaires.
• Parcours préfixe, infixe, postfixe et en largeur.
• Récursivité et appels de fonctions.
• Références vers des nœuds et structures chaînées.
• Notions de complexité O(1), O(h), O(log n) et O(n).

Organisation proposée

Introduction

Un arbre binaire de recherche, souvent abrégé ABR, est un arbre binaire qui organise ses clés selon une relation d’ordre. Cette organisation permet d’éliminer une partie du sous-arbre à chaque comparaison : une clé plus petite conduit vers la gauche, tandis qu’une clé plus grande conduit vers la droite.

L’efficacité d’un ABR dépend toutefois de sa forme. Lorsque l’arbre est équilibré, sa hauteur est logarithmique et les principales opérations sont rapides. Lorsqu’il dégénère en chaîne, il perd cet avantage et se comporte comme une liste linéaire.

7.1 Propriété d’ordre

7.1.1 Définition d’un arbre binaire de recherche

Un arbre binaire de recherche est un arbre binaire dans lequel chaque nœud contient une clé comparable. Pour tout nœud x, toutes les clés du sous-arbre gauche sont inférieures à la clé de x et toutes les clés du sous-arbre droit sont supérieures à la clé de x, selon la politique choisie pour les doublons.

7.1.2 Valeurs du sous-arbre gauche

Toutes les clés placées dans le sous-arbre gauche d’un nœud doivent respecter la relation « plus petite que ». Cette règle s’applique récursivement : une clé située plusieurs niveaux plus bas doit rester inférieure à tous les ancêtres pour lesquels elle appartient à la branche gauche.

Par exemple, 45 est l’enfant droit de 40, mais il appartient au sous-arbre gauche de 50. Il doit donc vérifier 40 < 45 < 50.

7.1.3 Valeurs du sous-arbre droit

Toutes les clés du sous-arbre droit sont supérieures à la clé du nœud courant. Dans l’exemple, 55 est inférieur à 60 mais reste supérieur à 50, car il appartient au sous-arbre droit de 50 et au sous-arbre gauche de 60.

7.1.4 Vérification de l’invariant par intervalles

Une méthode robuste consiste à associer à chaque appel récursif un intervalle de clés autorisées. La racine accepte initialement toutes les valeurs. Le sous-arbre gauche reçoit une borne maximale égale à la clé du parent ; le sous-arbre droit reçoit une borne minimale.

7.1.5 Parcours infixe et ordre des clés

Le parcours infixe visite successivement le sous-arbre gauche, le nœud puis le sous-arbre droit. Dans un ABR valide sans doublons, il produit les clés dans un ordre strictement croissant.

Pour l’arbre d’exemple, le résultat est : 20, 30, 40, 45, 50, 55, 60, 70, 80.

7.1.6 Gestion des doublons

La définition de l’ABR doit préciser le traitement des clés égales. Plusieurs politiques sont possibles, mais une seule doit être appliquée uniformément dans la recherche, l’insertion, la suppression et la validation.

7.2 Opérations

Toutes les opérations fondamentales suivent un chemin unique depuis la racine. À chaque nœud, une comparaison détermine si le traitement doit s’arrêter, continuer à gauche ou continuer à droite.

7.2.1 Recherche

La recherche compare la clé cible à la clé du nœud courant. En cas d’égalité, le nœud est trouvé. Une cible plus petite conduit au sous-arbre gauche ; une cible plus grande conduit au sous-arbre droit.

7.2.2 Insertion

L’insertion recherche d’abord la position où la clé devrait se trouver. Lorsque le parcours atteint une référence NULL, un nouveau nœud est créé à cet emplacement. La nouvelle feuille respecte alors l’invariant d’ordre.

7.2.3 Recherche du minimum

Le minimum d’un ABR est le nœud le plus à gauche. En effet, chaque déplacement vers la gauche conduit à une clé plus petite. Si le sous-arbre gauche est absent, le nœud courant est minimal dans son sous-arbre.

Dans l’arbre d’exemple, le chemin 50 -> 30 -> 20 conduit au minimum 20.

7.2.4 Recherche du maximum

Le maximum est obtenu symétriquement en suivant les références droites jusqu’à ce qu’aucun enfant droit n’existe.

Dans l’arbre d’exemple, le maximum est 80.

7.2.5 Recherche du successeur

Le successeur d’une clé est la plus petite clé strictement supérieure. Deux situations doivent être distinguées.

1. Si le nœud possède un sous-arbre droit, son successeur est le minimum de ce sous-arbre droit.

2. Sinon, il faut remonter vers le premier ancêtre pour lequel le nœud appartient au sous-arbre gauche.

7.2.6 Suppression d’un nœud

La suppression est l’opération la plus délicate, car retirer une clé ne doit pas rompre la structure ni l’invariant d’ordre. L’algorithme commence par rechercher la clé, puis traite l’un des trois cas : feuille, un enfant ou deux enfants.

7.3 Cas de suppression

7.3.1 Suppression d’un nœud feuille

Une feuille ne possède aucun enfant. Elle peut être détachée directement en remplaçant la référence du parent par NULL. Si la feuille est également la racine, l’arbre devient vide.

7.3.2 Suppression d’un nœud avec un enfant

Le nœud supprimé est remplacé par son unique enfant. Le sous-arbre porté par cet enfant reste intact et conserve sa position relative par rapport aux ancêtres.

7.3.3 Suppression d’un nœud avec deux enfants

Un nœud ayant deux enfants ne peut pas être remplacé directement par l’un d’eux sans perdre l’autre sous-arbre. On choisit une clé voisine dans l’ordre : le successeur, minimum du sous-arbre droit, ou le prédécesseur, maximum du sous-arbre gauche.

1. Trouver le successeur du nœud à supprimer.

2. Copier la clé et, le cas échéant, les données associées du successeur dans le nœud.

3. Supprimer le successeur de son emplacement d’origine.

4. Le successeur ne possède jamais d’enfant gauche ; sa suppression relève donc d’un cas plus simple.

7.3.4 Suppression avec données associées

Lorsque le nœud contient plusieurs champs, il faut copier l’enregistrement logique complet, pas uniquement la clé. Dans un répertoire, le numéro, le nom et les coordonnées associés au successeur doivent rester cohérents.

7.3.5 Suppression avec compteur de doublons

Avec la politique du compteur, une suppression décrémente d’abord le nombre d’occurrences. Le nœud n’est structurellement retiré que lorsque le compteur atteint zéro.

7.3.6 Tableau récapitulatif

7.4 Analyse des performances

7.4.1 La hauteur comme paramètre central

Une recherche, une insertion ou une suppression suit au plus un chemin de la racine vers une feuille. Leur coût est donc proportionnel à la hauteur h de l’arbre, soit O(h). La valeur de h dépend directement de la forme de l’arbre et de l’ordre des insertions.

7.4.2 Arbre équilibré

Un arbre est équilibré lorsque les hauteurs de ses branches restent proches. Pour n nœuds, sa hauteur est alors de l’ordre de log2(n). Les opérations principales ont une complexité logarithmique.

7.4.3 Arbre dégénéré

Si les clés sont insérées dans un ordre déjà trié, chaque nouvelle clé peut devenir l’enfant droit de la précédente. L’arbre dégénère alors en liste chaînée, avec une hauteur n - 1.

7.4.4 Meilleur cas, cas moyen et pire cas

7.4.5 Influence de l’ordre d’insertion

Les mêmes clés peuvent produire des arbres très différents selon leur ordre d’arrivée. La suite 1, 2, 3, 4, 5, 6, 7 crée une chaîne, tandis que la suite 4, 2, 6, 1, 3, 5, 7 crée un arbre parfait.

7.4.6 Coût spatial

Chaque nœud stocke une clé, une valeur éventuelle et deux références. La mémoire totale de la structure est O(n). Les versions récursives utilisent en plus une pile d’appels de taille O(h). Dans un arbre dégénéré, cette pile peut atteindre O(n).

7.4.7 Limites et arbres auto-équilibrés

Les arbres AVL et rouge-noir réorganisent automatiquement les nœuds après certaines insertions et suppressions. Ils garantissent une hauteur O(log n), au prix d’informations supplémentaires et d’opérations de rotation. Ils seront étudiés au niveau avancé.

Applications

Application 1 — Gestion d’un répertoire

Chaque entrée est indexée par une clé unique, par exemple un numéro de contact. La valeur associée peut contenir le nom, le téléphone et l’adresse électronique. L’ABR permet une consultation ordonnée et un parcours alphabétique si la clé est le nom normalisé.

• Ajouter un contact avec une clé non utilisée.
• Modifier les données sans changer la clé.
• Supprimer un contact par numéro.
• Afficher tous les contacts dans l’ordre des clés.

Application 2 — Classement de valeurs

Les valeurs sont insérées dans l’ABR, puis un parcours infixe produit le classement croissant. Pour conserver les doublons, chaque nœud peut contenir un compteur.

Application 3 — Dictionnaire ordonné

La clé est un mot et la valeur sa définition. L’ordre lexicographique permet de rechercher un mot, de produire la liste alphabétique et d’extraire les entrées comprises dans un intervalle.

Application 4 — Recherche d’un étudiant par numéro

Le numéro d’inscription constitue la clé unique. Les autres champs forment la valeur associée : nom, prénom, filière et moyenne. L’ABR permet une recherche directe sans parcourir toute la liste.

Méthode de résolution et bonnes pratiques

1. Définir précisément la clé et sa relation d’ordre.

2. Choisir et documenter une politique de doublons.

3. Faire retourner la nouvelle racine par les opérations récursives.

4. Tester l’arbre vide, la racine, les feuilles et les nœuds internes.

5. Vérifier l’invariant après chaque insertion et suppression.

6. Utiliser le parcours infixe pour contrôler l’ordre des clés.

7. Mesurer la hauteur afin de détecter un déséquilibre important.

8. Copier toutes les données associées lors du remplacement par un successeur.

Erreurs fréquentes

Travaux dirigés

TD 1 — Vérifier la propriété d’ordre

Pour chacun des arbres proposés par l’enseignant, déterminer s’il s’agit d’un ABR. Lorsqu’un arbre est invalide, identifier le premier nœud qui viole une borne héritée d’un ancêtre.

TD 2 — Construire un ABR

Construire successivement les arbres obtenus avec les suites suivantes et calculer leur hauteur :

• 50, 30, 70, 20, 40, 60, 80 ;
• 20, 30, 40, 50, 60, 70, 80 ;
• 50, 70, 30, 80, 60, 40, 20.

TD 3 — Tracer une recherche

Dans l’arbre d’exemple, tracer la recherche des clés 55, 65 et 20. Indiquer les comparaisons, les décisions et le résultat final.

TD 4 — Minimum, maximum et successeurs

Déterminer le minimum, le maximum et le successeur de 20, 40, 45, 50, 60, 70 et 80.

TD 5 — Insertions

À partir de l’arbre d’exemple, insérer successivement 35, 65, 75 et 10. Dessiner l’arbre après chaque opération et vérifier son parcours infixe.

TD 6 — Suppressions

Effectuer indépendamment les suppressions suivantes : 20, 40, 30 et 50. Pour chaque opération, préciser le cas rencontré et l’éventuel successeur utilisé.

TD 7 — Politique de doublons

Insérer la suite 12, 7, 12, 5, 7, 12 avec : a) doublons à droite ; b) compteur d’occurrences. Comparer la hauteur, la mémoire et la facilité de suppression.

TD 8 — Analyse de complexité

Exprimer en fonction de h puis de n le coût de la recherche, de l’insertion, du minimum, du successeur, de la suppression et du parcours infixe.

TD 9 — Intervalle de clés

Concevoir un algorithme qui affiche uniquement les clés comprises entre a et b sans parcourir inutilement les sous-arbres qui ne peuvent contenir aucune réponse.

TD 10 — Index d’étudiants

Proposer les structures et les opérations nécessaires pour gérer des étudiants indexés par numéro : ajouter, rechercher, modifier la moyenne, supprimer et afficher dans l’ordre des numéros.

Corrigés indicatifs des travaux dirigés

Correction du TD 1

La vérification correcte propage un intervalle autorisé. Une clé peut respecter son parent immédiat tout en étant trop grande ou trop petite par rapport à un ancêtre. Le parcours infixe croissant est un contrôle utile, mais la méthode par bornes exprime directement l’invariant.

Correction du TD 2

Correction du TD 3

Correction du TD 4

Correction du TD 5

35 devient l’enfant gauche de 40 ; 65 devient l’enfant droit de 60 ; 75 devient l’enfant gauche de 80 ; 10 devient l’enfant gauche de 20. Le parcours infixe final doit être : 10, 20, 30, 35, 40, 45, 50, 55, 60, 65, 70, 75, 80.

Correction du TD 6

Correction du TD 7

La politique « égaux à droite » produit plusieurs nœuds et peut allonger fortement une branche. La politique du compteur conserve un seul nœud par clé distincte ; elle économise des références et simplifie le classement, mais impose de gérer occurrence lors des suppressions.

Correction du TD 8

Correction du TD 9

Correction du TD 10

Le numéro est la clé. Les opérations AjouterEtudiant, ChercherEtudiant, ModifierMoyenne et SupprimerEtudiant réutilisent respectivement l’insertion, la recherche et la suppression de l’ABR. La modification de la moyenne ne change pas la structure. Un parcours infixe affiche les étudiants par numéro croissant.

Travail pratique — Gestion d’un index ordonné

Objectif

Implémenter un ABR complet permettant de gérer des étudiants indexés par leur numéro d’inscription, puis mesurer l’influence de l’ordre d’insertion sur la hauteur et le nombre de comparaisons.

Fonctionnalités minimales

• Créer et vider l’arbre.
• Insérer un étudiant en refusant les numéros dupliqués.
• Rechercher un étudiant et compter les comparaisons.
• Modifier les données non clés.
• Afficher les étudiants par numéro croissant.
• Calculer la taille et la hauteur.
• Déterminer le minimum, le maximum et le successeur.
• Supprimer un étudiant dans chacun des trois cas.
• Vérifier automatiquement l’invariant d’ordre.

Jeux d’essai obligatoires

Mesures expérimentales

1. Générer n clés dans un ordre aléatoire et mesurer la hauteur.

2. Insérer les mêmes clés dans l’ordre croissant et mesurer la hauteur.

3. Rechercher toutes les clés et calculer le nombre moyen de comparaisons.

4. Comparer les résultats avec log2(n) et n.

5. Expliquer pourquoi la forme observée influence les temps.

Grille d’évaluation

Synthèse du chapitre

Glossaire

Auto-évaluation