Chapitre 7 : Les arbres binaires de recherche.

Introduction :

Un arbre binaire de recherche est conçu pour organiser les données de manière à faciliter les recherches. Chaque nœud a deux enfants : les valeurs plus petites vont à gauche, et les valeurs plus grandes à droite.

Cela permet de diviser rapidement l'ensemble des données et d'accélérer les recherches..

1. Définition:

A copier dans le cahier.

Un arbre binaire de recherche est un arbre binaire où pour chaque noeud, les valeurs du sous-arbre gauche sont inférieures à la valeur de ce noeud et les valeurs du sous-arbre droit sont supérieures à la valeur de ce noeud.

2. Complément :

Cette définition est volontairement ambigüe sur les inégalités, car on peut établir plusieurs règles :

Les valeurs sont distinctes et les inégalités sont strictes.
Les inégalités sont larges : les valeurs du sous-arbre gauche d'un noeud sont inférieures ou égales à la valeur de ce noeud et les valeurs du sous-arbre droit d'un noeud sont supérieures ou égales à la valeur de ce noeud.
Les valeurs du sous-arbre gauche d'un noeud sont inférieures ou égales à la valeur de ce noeud et les valeurs du sous-arbre droit d'un noeud sont strictement supérieures à la valeur de ce noeud.
Les valeurs du sous-arbre gauche d'un noeud sont strictement inférieures à la valeur de ce noeud et les valeurs du sous-arbre droit d'un noeud sont supérieures ou égales à la valeur de ce noeud.

3. Exercice :

A faire dans le cahier.

Lorsque l'on ajoute une valeur dans un arbre binaire de recherche, le noeud contenant cette valeur doit respecter les règles de l'arbre binaire de recherche.

Dans cet exercice, on considèrera que toutes les valeurs de l'arbre sont distinctes.

On considère cet arbre binaire de recherche:

S'agit-il un arbre binaire de recherche?
Recopier cet arbre dans votre cahier.
Ajouter le nombre 55 à cet arbre.
Ajouter le nombre 56 à cet arbre.
Est-ce que l'arbre aurait été le même si on avait d'abord ajouté 56 puis 55 ?

4. Exercice : Construire un arbre donné

À l'aide de la classe ArbreBinaire (avec les méthodes ajout_gauche et ajout_droit), implémentez en Python l'arbre binaire de recherche suivant :

Contraintes :

La racine vaut 50, avec 30 à gauche et 70 à droite.
Dans le sous-arbre gauche : 20 est le fils gauche de 30 (avec 10 à gauche de 20) et 40 est le fils droit de 30 (avec 35 à gauche de 40).
Dans le sous-arbre droit : 60 est le fils gauche de 70 et 80 son fils droit.

Votre code doit créer une variable racine contenant la racine de l'arbre construit.

Tests :

Affichage :

Console:

>>>

5. Exercice : Recherche dans un ABR

Créer une fonction recherche_valeur qui prend en paramètres un objet ArbreBinaire représentant un arbre binaire de recherche et une valeur valeur_cherchee, puis retourne un booléen qui vaut True si la valeur cherchée est présente dans l'arbre et False sinon.

On recopiera le code de la classe ArbreBinaire ainsi que la construction de l’arbre de l’exercice précédent pour tester la fonction.

Exemples attendus :

recherche_valeur(racine, 35) renvoie True
recherche_valeur(racine, 99) renvoie False

# RECOPIER LE CODE DE L EXERCICE PRECEDENT ICI def recherche_valeur(arbre, valeur_cherchee): if arbre is None: return ... if valeur_cherchee == arbre.valeur: return ... elif valeur_cherchee < arbre.valeur: return ... else: return ...

Tests :

Affichage :

Console:

>>>

6. Exercice : Ajout dans un ABR

Créer une fonction ajout_valeur qui prend en paramètres un objet ArbreBinaire représentant un arbre binaire de recherche et une valeur valeur_a_ajouter et ajoute cette valeur à l'arbre.

On supposera qu'il n'y a que des valeurs distinctes.

On recopiera le code de la classe ArbreBinaire et la construction de l’arbre vus précédemment pour tester la fonction.

Exemples attendus :

ajout_valeur(racine, 65)
recherche_valeur(racine, 65) renvoie True

# COPIER ICI LE CODE DE LA CLASSE ET LA CONSTRUCTION DE L'ARBRE def ajout_valeur(arbre, valeur_a_ajouter): if valeur_a_ajouter < arbre.valeur: if arbre.gauche is None: ... else: ... else: if arbre.droit is None: ... else: ...

Tests :

Affichage :

Console:

>>>

7. Exercice : Création d'un ABR à partir d'une liste

Créer une fonction crea_arbre_recherche(liste) qui prend comme paramètre une liste non vide et qui renvoie un objet ArbreBinaire de recherche contenant ces valeurs.

On recopiera la fonction ajout_valeur de l’exercice précédent pour insérer les éléments un par un dans l’arbre.

Exemple :

racine = crea_arbre_recherche([50,30,70,20,40,60,80])
# on obtient un arbre dont la racine vaut 50 et organisé comme un ABR

Tests :

Affichage :

Console:

>>>

8. Arbre équilibré :

Un arbre binaire est dit équilibré si pour chaque noeud de l'arbre, la hauteur du sous-arbre gauche et la hauteur du sous-arbre droit à une différence au plus d'un.

9. Exercice : ABR équilibré par sous-listes (file)

On veut créer un arbre binaire de recherche (ABR) aussi équilibré que possible à partir d’une liste de valeurs.

Algorithme proposé :

1) Trier la liste.
2) Insérer l’élément central dans un arbre (il devient la racine).
3) Créer une file.
4) Enfiler la sous-liste à gauche de cet élément (si non vide).
5) Enfiler la sous-liste à droite de cet élément (si non vide).
6) Tant que la file n’est pas vide :
   a) Défile une sous-liste.
   b) Insérer son élément central dans l’arbre.
   c) Enfiler sa sous-liste gauche si non vide.
   d) Enfiler sa sous-liste droite si non vide.

Écrire la fonction crea_arbre_recherche_optimise(liste) qui renvoie la racine de l’ABR construit.

La liste est supposée non vide.

class ArbreBinaire: def __init__(self, valeur): self.valeur = valeur self.gauche = None self.droit = None def ajout_gauche(self, valeur): self.gauche = ArbreBinaire(valeur) def ajout_droit(self, valeur): self.droit = ArbreBinaire(valeur) class File: def __init__(self): self.elements = [] def enfiler(self, x): self.elements.append(x) def defiler(self): return self.elements.pop(0) def est_vide(self): return self.elements == [] # COPIER LA FONCTION AJOUT_VALEUR ICI !!! def crea_arbre_recherche_optimise(liste): assert len(liste) != 0, "La liste doit etre non vide" # on trie la liste liste_ordonnee = sorted(liste) # on récupère l'indice de l'élément central indice_central = ... # on crée la racine avec la valeur centrale racine = ... # on crée une file pour gérer les sous-listes à traiter file = File() # sous-listes gauche et droite de l'élément central sous_liste_gauche = liste_ordonnee[:indice_central] sous_liste_droite = liste_ordonnee[indice_central+1:] # on enfile ces sous_listes si elles sont non vides. if sous_liste_gauche != []: ... if sous_liste_droite != []: ... # tant que la file n'est pas vide while not file.est_vide(): # on sort une sous-liste de la file sous_liste = ... # on calcule l'indice central de cette sous-liste indice_central = ... # on insère la valeur centrale dans l'arbre ... # on récupère ses parties gauche et droite partie_gauche = ... partie_droite = ... #on les enfile si elles sont non vides if partie_gauche: ... if partie_droite: ... return racine

Tests :

Affichage :

Console:

>>>

10. Recherche dans un arbre binaire équilibré :

Un algorithme de recherche dans un arbre binaire équilibré de hauteur \(n\) est en \( O(\log_2(n)) \)

11. Exercice : (sujet 36 - 2025) Insertion récursive dans un ABR

Un arbre binaire de recherche est soit vide, représenté en Python par la valeur None, soit un nœud, contenant une étiquette et deux sous-arbres gauche et droit et représenté par une instance de la classe Noeud donnée ci-dessous.

On considère ici que les étiquettes des nœuds sont des entiers et que les arbres binaires de recherche considérés ne contiennent pas de doublons.

Compléter la méthode récursive inserer afin qu’elle permette d’insérer une clé dans l’arbre binaire de recherche non vide sur lequel on l’appelle.

Voici un exemple d’utilisation :

arbre = Noeud(7)
for cle in (3, 9, 1, 6):
    arbre.inserer(cle)
arbre.gauche.etiquette    # 3
arbre.droit.etiquette     # 9
arbre.gauche.gauche.etiquette  # 1
arbre.gauche.droit.etiquette   # 6

class Noeud: def __init__(self, etiquette): '''Méthode constructeur pour la classe Noeud. Crée une feuille d'étiquette donnée.''' self.etiquette = etiquette self.gauche = None self.droit = None def inserer(self, cle): '''Insère la clé dans l'arbre binaire de recherche en préservant sa structure.''' if cle < self.etiquette: if self.gauche != None: ... else: ... else: if self.droit != None: ... else: ...

Tests :

Affichage :

Console:

>>>

12. Parcours en profondeur infixé :

Mettre dans une liste les valeurs rencontrées lors d'un parcours en profondeur infixé d'un arbre binaire de recherche produit une liste triée!

13. Exercice : Parcours infixe d’un ABR → liste triée

A faire dans le cahier.

On souhaite illustrer l’énoncé :

« Mettre dans une liste les valeurs rencontrées lors d’un parcours en profondeur infixé d’un arbre binaire de recherche produit une liste triée. »

Exécutez le programme ci-dessous, regardez son affichage et essayez de comprendre son fonctionnement, puis répondre aux questions suivantes :

Lors de l'exécution de la dernière ligne (print(parcours_infixe(construire_abr(LISTE_DESORDONNEE)))), résumez en quelques mots ce qu'il s'est produit.
Tracer sur votre cahier le "haut" de l'arbre binaire de recherche construit lors l'exécution de cette commande. On souhaite voir :
- La racine.
- L'enfant gauche de la racine.
- L'enfant droit de la racine.
- Les enfants directs de l'enfant gauche et de l'enfant droit de la racine.

class Noeud: def __init__(self, etiquette): self.etiquette = etiquette self.gauche = None self.droit = None def inserer(racine, cle): """Insère la clé dans l'ABR de racine "racine" (valeurs distinctes).""" if cle < racine.etiquette: if racine.gauche is None: racine.gauche = Noeud(cle) else: inserer(racine.gauche, cle) elif cle > racine.etiquette: if racine.droit is None: racine.droit = Noeud(cle) else: inserer(racine.droit, cle) # sinon la clé est déjà présente, on ne fait rien def construire_abr(liste): """Construit un ABR contenant toutes les valeurs de "liste" (liste non vide).""" if not liste: return None racine = Noeud(liste[0]) for valeur in liste[1:]: inserer(racine, valeur) return racine def parcours_infixe(arbre): """Renvoie la liste des étiquettes selon le parcours infixe (gauche, racine, droite).""" if arbre is None: return [] gauche = parcours_infixe(arbre.gauche) racine = [arbre.etiquette] droite = parcours_infixe(arbre.droit) return gauche + racine + droite # Une liste de nombres dans le désordre pour tester LISTE_DESORDONNEE = [42, 17, 8, 99, 23, 55, 4, 88, 73, 16, 61, 12, 3, 37, 29, 19, 95, 7, 50, 2, 65, 82, 14, 31, 5, 97, 1, 33, 11, 70, 27, 21, 46, 67, 92, 13, 39, 25, 28, 6] print(parcours_infixe(construire_abr(LISTE_DESORDONNEE)))

Tests :

Affichage :

Console:

>>>