Header
🠖 Chap. 2 : Arbres

Cours

Lexique

Introduction : les structures de données

Les données peuvent être structurées de différentes manières. En voici quelques exemples :
  • les listes, piles ou files qui sont des structures linéaires
  • les dictionnaires où elles sont associées par paire {clé: valeur}
  • les tables ou tableaux
  • les arbres qui permettent de hiérarchiser les données et qui sont l'objet de ce chapitre
  • et les graphes où les données sont en réseau (structure relationnelle) qui seront traités dans le chapitre suivant.

Les arbres

Introduction

Les arbres sont utilisés pour représenter des situations de hiérarchie.
Ainsi on peut les utiliser pour :
  • le découpage d'un livre en chapitres, sections, paragraphes ...
  • l'arborescence d'un système de fichier
  • les formats de fichier XML (par balisage) tel que le HTML
  • l'organigramme d'une organisation
  • la recherche dichotomique
mais aussi de manière moins évidente dans :
  • la compression de données (code Huffman)
  • les expressions arithmétiques
  • les tris, notamment ceux utilisant la stratégie "diviser pour régner"

Définition

Un arbre est une structure de données hiérarchique, qui possède :
  • une racine (premier noeud)
  • des noeuds (ou sommet)
  • des branches (ou arêtes)
  • des feuilles (noeud sans fils)

Les noeuds qui ne sont pas des feuilles sont aussi qualifiés de noeuds internes.

Exemple d'arbre ayant 7 noeuds, 4 feuilles, 6 branches et pour racine : le noeud A.

On utilisera aussi le vocabulaire de la famille pour dire par exemple :
  • le noeud B a deux fils : les noeuds E et F.
  • le père du noeud B est le noeud A.
  • les noeuds E et F sont frères.
Question 1/2 : ✓
30s Chap. 2 : Arbres / 1 - Définitions Mémorisation 0x Réussite 0/0/7

Caractéristiques

Un arbre est caractérisé par :
  • son arité qui est le nombre maximum d'enfant que peut avoir un noeud,
  • sa taille qui est le nombre de noeud qu'il possède,
  • sa hauteur (ou sa profondeur) qui est le nombre de branches entre la racine et la feuille la plus éloignée. On parle aussi de niveau : Un arbre de hauteur 3 possède 4 niveaux. On peut faire l'analogie pour un immeuble de 4 niveaux soit un rez-de-chaussée et 3 étages (hauteur 3). Ainsi un arbre consitué d'un seul noeud (sa racine) aurait une hauteur de 0 et 1 seul niveau.
    Attention : La convention choisie dans les épreuves du baccalauréat confond hauteur et niveau, ainsi un arbre constitué d'un seul noeud (sa racine) est de hauteur 1 et possède 1 seul niveau.
Dans l'exemple de l'Arbre 01 ci-dessus, celui-ci est d'arité 2, de taille 7 et possède 3 niveaux. Il est de hauteur 2 (ou 3 avec la convention utilisée dans les annales de BAC).
Question 1/3 : ✓
30s Chap. 2 : Arbres / 1 - Définitions Mémorisation 0x Réussite 0/0/7
Enfin le chemin d'un noeud sera la suite des noeuds parcourus pour l'atteindre en partant de la racine.
Dans l'abre ci-dessus le chemin du noeud Y est ACGY.

Exemple : Le HTML

Question 1/2 : ✓
Chap. 2 : Arbres / 1 - Définitions Mémorisation 0x Réussite 0/0
Représenter l'arbre correspondant au balisage du code HTML suivant :
<html lang="fr"> <head> <meta charset="utf-8"> <title>Citations</title> <link rel="stylesheet" href="style.css"> <script src="script.js"></script> </head> <body> <div> <p id="citation">Citation</p> <p> <span id="auteur">Auteur</span> <span id="numero">0/0</span> </p> </div> </body> </html>

Les arbres binaires

Vocabulaire

  • Un arbre binaire est un arbre d'arité 2. Cela signifie que la racine et chaque noeud ne peut avoir au maximum que deux enfants. On parlera alors de sous-arbre gauche (noté SAG) et de sous-arbre droit (noté SAD). Le fils gauche est la racine du SAG tandis que le fils droit est la racine du SAD.
  • Un arbre dégénéré est filiforme. Chaque noeud n'a qu'un enfant.
  • Un arbre binaire localement complet est un arbre dont chaque noeud a strictement deux enfants.
  • Un arbre binaire complet est un arbre localement complet avec toutes ses feuilles à la même profondeur. On dit aussi qu'il est parfaitement équilibré.
Question 1/3 : ✓
30s Chap. 2 : Arbres / 1 - Définitions Mémorisation 0x Réussite 0/0/5

Exemple : Expressions arithmétiques

Les expressions arithmétiques sont représentables sous forme d'arbre binaire. En effet les opérateurs d'addition, de soustraction, de multiplication ou de division sont d'arité 2, c'est-à-dire qu'ils s'appliquent à deux opérandes. Les arbres binaires, par définition d'arité 2, sont donc tout désignés pour les repésenter.

Question 1/3 : ✓
Chap. 2 : Arbres / 1 - Définitions Mémorisation 0x Réussite 0/0
Représenter l'expression `(2-5)/(7+1)xx3xx(4+6+8)/9` sous forme d'un arbre binaire.

Représentation d'un arbre binaire

Il existe une multitude de structures de donnée permettant d'implémenter un arbre. En voici quelques uns :

Sous forme d'une liste

Reprenons l'exemple de l'Arbre 03 :
Sa représentation sous forme de liste peut être :
L = [A, B, C, , , G, H]
Les espaces vides dans la liste correspondent aux noeuds vides dans l'arbre binaire complet correspondant. Cette représentation repose sur la relation suivante entre les indices d'un père et de ses fils :
`i_(filsGauche) = 2 xx i_(père) + 1`
`i_(filsDroit) = 2 xx (i_(père) + 1)`

Sous forme de listes imbriquées

Pour l'Arbre 03, rappelé ci-dessous, on peut aussi imaginer cette structure :
L = [A, B, [C, G, H]]
Ici chaque arbre et sous-arbre est représenté par une liste contenant trois éléments : la racine, le SAG et le SAD.

Sous forme d'un dictionnaire

Reprenons toujours l'exemple de l'Arbre 03. Sa représentation sous forme de dictionnaire peut être :
D = {racine:A, sag:B, sad:{racine:C, sag:G, sad:H}}
Ici, chaque arbre et sous-arbre est un dictionnaire avec trois clés : la racine, le SAG et le SAD.

Question 1/3 : ✓
Chap. 2 : Arbres / 2 - TAD et implémentations Mémorisation 0x Réussite 0/0/5
Donner la représentation sous forme de liste de l'arbre binaire suivant :
Donner votre réponse sous la forme [A,B,,C] sans aucun espace.

Implémentation en POO

Un arbre binaire peut être représenté de manière récursive par cette classe Nœud (ici en python) :
class Noeud : def __init__(self, valeur) : self.valeur = valeur self.gauche = None self.droit = None
Ainsi pour créer les deux premiers niveaux (bleu et vert) de l'Arbre binaire 01 ci-dessous, il faut le jeu d'instructions :
a = Noeud("A") a.gauche = Noeud("B") a.droit = Noeud("C")
Remarque : Ici, les attributs sont publics. Il n'y a pas d'underscore _ en préfixe de leur nom. Ils sont directement modifiables par l'utilisateur.
Poursuivre le jeux d'instruction afin de représenter l'Arbre binaire 01 dans son intégralité.
a = Noeud("A") a.gauche = Noeud("B") a.droit = Noeud("C") a.gauche.gauche = Noeud("D") a.gauche.droit = Noeud("E") a.gauche.droit.gauche = Noeud("G") a.gauche.droit.droite = Noeud("H") a.droit.droit = Noeud("F") a.droit.droit.gauche = Noeud("I")

TAD Arbre Binaire

Voici les spécifications du TAD arbre binaire. Pour rappel, les spécifications ne présagent pas de la structure de données qui sera utilisée lors de l'implémentation, elles définissent seulement l'interface du TAD.
Arbre binaire
creerArbre(arbre, racine) → arbre
estVide(arbre) → booléen
nombreFils(arbre) → entier
racine(arbre) → valeur
sag(arbre) → arbre
sad(arbre) → arbre
assembler(arbre, arbre, arbre) → arbre
Voici une implémentation en python (POO) de ce TAD d'arbre binaire.
class Arbre: """Implémentation de la structure de données «Arbre» en Python.""" # creerArbre(arbre, racine) → arbre def __init__(self, racine=None): self._racine = racine # valeur self._gauche = None # Sous-arbre gauche self._droit = None # Sous-arbre droit # estVide(arbre) → booléen def estVide(self): return self._racine is None # racine(arbre) → valeur def racine(self): assert not self.estVide(), "L'arbre est vide." return self._racine # sag(arbre) → arbre def sag(self): return self._gauche # sad(arbre) → arbre def sad(self): return self._droit # assembler(arbre, arbre, arbre) → arbre def assembler(self, sag = None, sad = None): assert not self.estVide(), "L'arbre est vide." self._gauche = sag self._droit = sad # définition de l'impression (print) de l'objet def __str__(self): return "({},{},{})".format(self._racine, self._gauche, self._droit) # définition de l'affichage d'appel de l'objet def __repr__(self): return "Arbre()" # affiche l'arbre binaire dans la console def afficher(self): if self.estVide(): print("L'arbre est vide.") else: self._afficher(0) def _afficher(self, level): if self._droit: self._droit._afficher(level + 1) print("{}{}".format(' ' * 4 * level, self._racine)) if self._gauche: self._gauche._afficher(level + 1)
Commentaires :
  • Les attributs _racine, _gauche et _droit, et sont précédés d'un underscore _ ce qui signifie qu'ils sont privés. Le programmeur signale ainsi que l'utilisateur ne doit pas intéragir directement avec ces attributs mais doit passer par les seules méthodes qu'il a proposées. Cela permet de sécuriser les usages.
  • Python ne permet pas de rendre réellement privé un attribut ou une méthode, comme c'est le cas en C ou en Java. L'underscore _ en préfixe n'est qu'une indication non-bloquante.
  • Des méthodes d'affichage __str__(), __repr__() et afficher() sont également définie pour vous permettent d'afficher l'arbre et ainsi vérifier son contenu.

1 - Récupérer le fichier TAD_Arbre.py.
2 - Créer une instance pour cet arbre grâce à la classe fournie.
3 - S'approprier l'objet en utilisant toutes ses méthodes.

Algorithmes sur les arbres binaires

Afin de mettre en pratique les algorithmes suivants, nous allons utiliser l'implémentation en python présenté précédemment.

Parcours en largeur d'un arbre binaire

Le parcours en largeur d'un arbre binaire consiste à parcourir l'arbre, niveau par niveau en partant de la racine en en lisant les noeuds de gauche à droite.
Le parcours en largeur de l'arbre ci-dessus donne : A-B-C-D-E-F-G-H-I

Pseudo code : L'algorithme de parcours en largeur utilise une file.

f ← file vide p ← liste vide Enfiler l'arbre dans f TANT QUE f n'est pas vide FAIRE arbre ← défiler f ajouter la racine de arbre dans p SI arbre a un fils gauche FAIRE enfiler le sous-arbre gauche dans f SI arbre a un fils droit FAIRE enfiler le sous-arbre droit dans f RETOURNER p

1 - Récupérer le fichier TAD_File.py.
Importer le module dans le fichier TAD_Arbre.py en ajoutant dans les premières lignes l'instruction : from TAD_File import *.
2 - Compléter la méthode parcoursLargeur(self) en y implémentant l'algorithme ci-dessus.
# parcoursLargeur(arbre) → liste (parcours en largeur de l'arbre) def parcoursLargeur(self): f = File() p = [] f.enfiler(self) while not f.est_vide(): arbre = f.defiler() p.append(arbre._racine) if arbre.sag(): f.enfiler(arbre.sag()) if arbre.sad(): f.enfiler(arbre.sad()) return p

Parcours en profondeur d'un arbre binaire

Lors du parcours en profondeur d'un arbre, nous passons sur chaque noeud à trois reprises, avant son fils gauche, entre ses deux fils et après son fils droit.

  • Lorsqu'on traite un noeud dès sa première visite (ronds rouges en cliquant sur l'image), nous obtenons l'ordre du parcours en profondeur préfixe des noeuds. Algorithmiquement, cela revient à faire :
    [racine] + appel récursif sur SAG + appel récursif sur SAD
    Le parcours en profondeur préfixe de l'arbre binaire 06 ci-dessus donne : A-B-D-E-G-H-C-F-I

  • Lorsqu'on traite un noeud lors de sa deuxième visite (carrés bleus), nous obtenons l'ordre du parcours en profondeur infixe des noeud. Algorithmiquement, cela revient à faire :
    appel récursif sur SAG + [racine] + appel récursif sur SAD
    Le parcours en profondeur préfixe de l'arbre binaire 06 ci-dessus donne : D-B-G-E-H-A-C-I-F

  • Lorsqu'on traite un noeud lors de sa troisième visite (triangles verts), nous obtenons l'ordre du parcours en profondeur postfixe des noeud. Algorithmiquement, cela revient à faire :
    appel récursif sur SAG + appel récursif sur SAD + [racine]
    Le parcours en profondeur postfixe de l'arbre binaire 06 ci-dessus donne : D-G-H-E-B-I-F-C-A

Question 1/5 : ✓
1 min Chap. 2 : Arbres / 3 - Algorithmes Mémorisation 0x Réussite 0/0/5

1 - Compléter la méthode _parcoursPre(self, liste) de la classe Arbre() , qui retournent la liste des noeuds obtenue selon un parcours en profondeur préfixe.
def _parcoursPre(self, liste): liste.append(self.racine()) if self.sag() : liste.extend(self.sag().parcoursPre()) if self.sad() : liste.extend(self.sad().parcoursPre()) return liste

2 - Compléter la méthode _parcoursInf(self, liste) de la classe Arbre() , qui retournent la liste des noeuds obtenue selon un parcours en profondeur infixe.
def _parcoursInf(self, liste): if self.sag() : liste.extend(self.sag().parcoursInf()) liste.append(self.racine()) if self.sad() : liste.extend(self.sad().parcoursInf()) return liste

3 - Compléter la méthode _parcoursPost(self, liste) de la classe Arbre() , qui retournent la liste des noeuds obtenue selon un parcours en profondeur postfixe.
def _parcoursPost(self, liste): if self.sag() : liste.extend(self.sag().parcoursPost()) if self.sad() : liste.extend(self.sad().parcoursPost()) liste.append(self.racine()) return liste

Taille d'un arbre binaire

La taille d'un arbre correspond au nombre de nœuds qui le compose, racine et feuilles comprises. Elle est définit par :
  • `T(A) = 0` si A est un arbre vide
  • sinon `T(A) = 1 + T(sag(A))+T(sad(A))`

Pseudo code : Algorithme pour déterminer la taille d'un arbre.

a ← arbreBinaire FONCTION taille(a): SI a EST vide: RETOURNER 0 SINON: t ← 1 SI a A sag: t ← t + taille(sag) SI a A sad: t ← t + taille(sad) RETOURNER t
Compléter la méthode taille(self) dans la définition de la classe Arbre() en y implémentant l'algorithme ci-dessus.
# rechercher(arbre, valeur) → booléen def taille(self): if self.estVide(): return 0 else: t = 1 if self.sag(): t += self.sag().taille() if self.sad(): t += self.sad().taille() return t Solution plus courte def taille(self): return len(self.parcoursPre())

Hauteur d'un noeud

La hauteur (ou la profondeur) d'un noeud est le nombre de branches entre ce noeud et la racine de l'arbre. La hauteur d'un noeud est définit par :

  • `H(x) = 0` si x est la racine de l'arbre
  • `H(x) = 1 + H(y)` si y est le père de x

Attention : La convention utilisée ici est : Le niveau de la racine vaut 1 tandis que sa hauteur (ou sa profondeur) valent 0.

Exemple : Dans cet arbre, le noeud "H" est de hauteur 3.

Pour l'instant nos arbres ne sont pas triés (il ne s'agit pas encore d'arbre binaire de recherche). Ainsi, pour savoir où se situe un noeud et en déduire sa hauteur (ou sa profondeur), il faut parcourir tout l'arbre à sa recherche. L'idée ici va être de descendre dans l'arbre, de manière récursive, en partant de la racine (hauteur 0, niveau 1). Pour chaque noeud rencontré, on va enregistrer dans un dictionnaire sa valeur et son niveau.


1 - S'approprier la méthode hauteurNoeud(self, valeur).
2 - Implémenter l'algorithme ci-dessous afin de compléter la méthode _hauteursNoeuds(self, hauteurs, niv) qui permet, en parcourant l'arbre, de créer le dictionnaire {valeur du noeud : niveau du noeud} utilisé par hauteurNoeud(self, valeur).
def _hauteursNoeuds(self, dicoN, h): dicoN[self._racine] = h if self.sag(): dicoN = self.sag()._hauteursNoeuds(dicoN, h+1) if self.sad(): dicoN = self.sad()._hauteursNoeuds(dicoN, h+1) return dicoN

3 - Ajouter une méthode niveauNoeud(self, valeur), utilisant la précédente hauteurNoeud(self, valeur) et qui retourne le niveau d'un noeud.
def niveauNoeud(self, valeur): return self.hauteurNoeud(valeur) + 1

Pseudo code :

dicoN ← dictionnaire vide a ← arbre binaire h ← 0 FONCTION hauteursNoeuds(a, dicoN, h): AJOUTER à dicoN, le couple (racine(a), h) SI a A un sag : dicoN ← hauteursNoeuds(sag(a), dicoN, h+1) SI a A un sad : dicoN ← hauteursNoeuds(sad(a), dicoN, h+1) RETOURNER dicoN

Hauteur d'un arbre

La hauteur (ou la profondeur) d'un arbre est le nombre de branches entre la racine et sa feuille la plus éloignée.
Elle est définie par :
`H(A) = MAX(H(x))` avec `x` les noeuds de l'arbre A, et `H(x)` la hauteur du noeud.
Compléter la méthode hauteur(self) qui retourne la hauteur de l'arbre.
Pour cela, on peut utiliser la méthode .values() d'un dictionnaire, qui renvoit la liste des valeurs du dictionnaire (ici ces valeurs correspondent aux hauteurs de chaque noeud).
# hauteur(arbre) → entier def hauteur(self): if self.estVide(): return 0 else: return max(self._hauteursNoeuds({}, 1).values())

Les arbres binaires de recherche (ABR)

Un arbre binaire de recherche est une structure de donnée qui permet une recherche dichotomique.
Rappels : La complexité de l'algorithme de recherche par dichotomie est en `O(ln(n))`, ce qui est plus efficace que l'algorithme de recherche séquentielle, qui s'applique à liste quelconque, dont la complexité est `O(n)`. Cette meilleure performance vient du principe "diviser pour régner" (divide and conquer). En effet à chaque étape de cet algorithme la taille du problème est divisée par deux.
Attention ! Ces performances dépendent de l'équilibre de l'arbre. Un arbre parfaitement équilibré permet à l'algorithme de recherche d'atteindre la complexité en `O(ln(n))`. Au contraire un arbre totalement dégénéré, équivaut à une liste, et sa complexité est en `O(n)`.
Un ABR doit satisfaire deux critères récursifs :
  • Les valeurs du SAG doivent être inférieures à celle de la racine.
  • Les valeurs du SAD doivent être supérieures à celle de la racine.

1 - À la main, à partir d'un arbre binaire de recherche vide, ajouter successivement les valeurs 23, 42, 15, 6, 18, 37, 53, 10, 26, 49 et 43.
2 - Combien de comparaisons effectuez-vous pour rechercher la valeur 6 dans cet arbre binaire de recherche ? Pour trouver la valeur 6, il faut faire 3 comparaisons.
3 - Combien de comparaisons effectuez-vous pour rechercher la valeur 43 dans cet arbre binaire de recherche ? Pour trouver la valeur 43, il faut faire 5 comparaisons.

Algorithmes sur les arbres binaires de recherche

Nous allons reprendre l'implémentation précédente du TAD Arbre Binaire et lui ajouter des méthodes afin de pouvoir construire un abre binaire de recherche.

Parcourt des valeurs dans l'ordre croissant

Le parcours infixe d'un ABR permet de visiter les valeurs d'un ABR dans l'ordre croissant.

Recherche d'une valeur

Pseudo code : La recherche dans un ABR est équivalente à une recherche par dichotomie dans une liste triée. Voici l'algotrithme de la méthode à ajouter.
a ← arbre binaire de recherche x ← valeur à rechercher FONCTION rechercher(a, x) : SI x = racine(a) ALORS REPONDRE vrai SINON SI x < racine(a) ALORS SI a A un sag ALORS recherche(sag(a), x) SINON REPONDRE faux SINON SI a A un sad ALORS recherche(sad(a), x) SINON REPONDRE faux

1 - Implémenter la méthode rechercher(self, valeur). # rechercher(arbre_binaire, valeur) → booléen def rechercher(self, valeur): if self._racine == valeur: return True elif valeur < self._racine: if self.sag(): return self.sag().rechercher(valeur) else: return False else: if self.sad(): return self.sad().rechercher(valeur) else: return False
2 - Construire un arbre binaire de recherche avec au moins quatre entiers différents et tester votre implémentation.

Insertion d'une valeur


1 - Rechercher puis implémenter la méthode ajouter(self, valeur) pour ajouter une valeur à un arbre binaire de recherche. # ajouter(arbre_binaire, valeur) → def ajouter(self, valeur): if valeur < self.racine(): if not self.sag(): self._gauche=Arbre(valeur) else: self.sag().ajouter(valeur) elif valeur > self.racine(): if not self.sad(): self._droit=Arbre(valeur) else: self.sad().ajouter(valeur)
2 - Tester votre méthode sur l'arbre précédemment créé.
Une application de cette méthode peut être le tri d'une liste.

1 - Créer un nouveau fichier tri.py dans le même dossier que TAD_Arbre.py.
2 - Dans les premières lignes de ce fichier, importer le module TAD_Arbre.py.
3 - Puis écrire une fonction qui transforme une liste d'entier en un arbre binaire de recherche puis retourne la liste triée.
Quel parcours d'un arbre binaire de recherche permet d'obtenir tous ses nœuds triés ?
Le parcours en profondeur infixe.
Fichier tri.py from TAD_Arbre import * def tri(liste): a = Arbre() for e in liste: a.ajouter(e) return a.parcoursInf()

Recherche du minimum et du maximum


1 - Rechercher puis implémenter les méthodes min(self) et max(self) qui retournent respectivement la plus petite ou la plus grande valeur présente dans un ABR en exploitant ses propriétés pour être la plus efficace possible.
2 - Tester vos méthodes sur l'arbre précédemment créé.

Aller plus loin !

Vérifier un ABR

Nous avons ajouté des méthodes qui ne fonctionnent que sur des arbres binaires de recherche. Afin de les rendre plus robustes, il faudrait s'assurer que l'arbre binaire sur lequel on souhaite les appliquer est bien un ABR.

Suppression d'une valeur d'un ABR

Supprimer une valeur d'un arbre binaire de recherche est un peu plus technique car il faut gérer trois cas différents :
Cas 1 : La valeur à supprimer est une feuille. Il suffit de supprimer la feuille.
Cas 2 : Le noeud possède un seul fils. Il faut supprimer le noeud et faire "remonter" son unique fils.
Cas 3 : Le nœud possède deux fils. Il faut rechercher le nœud qui a la valeur maximale parmi les nœuds de valeur inférieure à la valeur du nœud à supprimer puis remplacer le nœud à supprimer par ce nouveau nœud.
Pour compléter la classe Arbre avec une méthode supprimer(self, x) qui supprime l'élément x de l'arbre binaire de recherche, il faut :
  1. Rajouter un attribut _parent dans le constructeur __init__ de la classe Arbre pour mémoriser le père.
  2. Modifier, lorsque c'est nécessaire, les méthodes écrites précédemment.
  3. Écrire une méthode nombreFils(self, x) qui donne le nombre de fils (0, 1 ou 2) du Noeud x dans l'arbre.
  4. Écrire les trois méthodes correspondant au troix cas expliqué précédement : supprimeFeuille(self, x), supprimeUnFils(self,x) et supprimeDeuxFils(self, x).

Équilibrer un ABR

On a vu qu'un arbre bien équilibré permet d'améliorer l'efficacité de l'algorithme de recherche. En effet un arbre complètement dégénéré conduit à ce que l'algorithme de recherche dans l'arbre corresponde en réalité à une recherche séquentielle beaucoup moins efficace.