Prérequis : programmation orientée objet , récursivité
À l’issue de ce chapitre, vous saurez :
Un arbre est une structure de données hiérarchique composée de nœuds reliés par des arêtes. Un arbre ne contient aucun cycle : entre deux nœuds, il existe un seul chemin. On verra dans le chapitre sur les graphes qu’un arbre est un graphe connexe (d’un seul tenant) et sans cycle.
On retrouve des arbres dans de nombreuses situations :
Dans un arbre, on distingue trois types de nœuds selon leur position :
Les relations s’expriment avec un vocabulaire familial :
Plusieurs mesures permettent de caractériser la structure :
Soit l’arbre suivant :
Identifier les nœuds particuliers :
Identifier les relations :
Calculer les caractéristiques :
Nœuds particuliers :
Relations :
Caractéristiques :
Un arbre binaire est un arbre où chaque nœud possède au plus deux fils, appelés fils gauche et fils droit.
C’est une structure définie de manière récursive. Un arbre binaire peut être :
L’interface décrit les opérations disponibles sur un arbre binaire a, indépendamment de la façon dont il est programmé ; l’implémentation ci-dessous les réalise avec une classe Arbre dont les attributs sont valeur, gauche et droit, l’arbre vide étant représenté par None.
| Opération | Description | Dans l’implémentation ci-dessous |
|---|---|---|
est_vide(a) |
Teste si l’arbre est vide | a is None |
racine(a) |
Renvoie la valeur de la racine | a.valeur |
gauche(a) |
Renvoie le sous-arbre gauche | a.gauche |
droit(a) |
Renvoie le sous-arbre droit | a.droit |
est_feuille(a) |
Teste si la racine est une feuille | a.est_feuille() |
Précondition : les opérations racine, gauche, droit et est_feuille ne s’appliquent qu’à un arbre non vide. Une autre implémentation (par exemple une liste de listes, ou une classe avec un objet « arbre vide ») garderait la même interface : les algorithmes écrits avec ces opérations resteraient valables.
class Arbre:
def __init__(self, valeur, gauche=None, droit=None):
self.valeur = valeur
self.gauche = gauche
self.droit = droit
def __repr__(self):
if self.gauche is None and self.droit is None:
return str(self.valeur)
return str(self.valeur) + "-(" + str(self.gauche) + "," + str(self.droit) + ")"
def est_vide(self):
return False
def est_feuille(self):
return self.gauche is None and self.droit is None
Remarque : dans cette implémentation, un arbre vide est représenté par
None, et un arbre non vide par un objetArbre. La méthodeest_vide()renvoie toujoursFalsecar elle n’est appelée que sur un objet existant.
a.valeura.gauche.valeura.droit.gauche.valeura.gauche.est_feuille()a.gauche.gauche.est_feuille()a = Arbre(5,
Arbre(3, Arbre(1), Arbre(4)),
Arbre(8, Arbre(7), Arbre(9)))
a.valeur → 5 (racine)a.gauche.valeur → 3 (fils gauche de la racine)a.droit.gauche.valeur → 7 (fils gauche du fils droit)a.gauche.est_feuille() → False (le nœud 3 a deux fils)a.gauche.gauche.est_feuille() → True (le nœud 1 n’a pas de fils)La structure récursive des arbres binaires permet d’écrire des algorithmes élégants. Pour chaque fonction, on traitera d’abord le cas de base (arbre vide), puis l’étape de récurrence.
Compléter la fonction taille(arbre) :
def taille(arbre):
if arbre is None:
return ...
return ...
def taille(arbre):
if arbre is None:
return 0
return 1 + taille(arbre.gauche) + taille(arbre.droit)
Compléter la fonction hauteur(arbre) :
def hauteur(arbre):
if arbre is None:
return ...
return ...
def hauteur(arbre):
if arbre is None:
return -1
return 1 + max(hauteur(arbre.gauche), hauteur(arbre.droit))
Écrire une fonction nb_feuilles(arbre) qui renvoie le nombre de feuilles.
def nb_feuilles(arbre):
if arbre is None:
return 0
if arbre.gauche is None and arbre.droit is None:
return 1
return nb_feuilles(arbre.gauche) + nb_feuilles(arbre.droit)
Un parcours permet de visiter tous les nœuds d’un arbre dans un certain ordre.
On distingue trois types de parcours selon l’ordre de traitement de la racine :
def prefixe(arbre):
if arbre is not None:
print(arbre.valeur, end=' ')
prefixe(arbre.gauche)
prefixe(arbre.droit)
def infixe(arbre):
if arbre is not None:
infixe(arbre.gauche)
print(arbre.valeur, end=' ')
infixe(arbre.droit)
def suffixe(arbre):
if arbre is not None:
suffixe(arbre.gauche)
suffixe(arbre.droit)
print(arbre.valeur, end=' ')
Donner l’ordre de visite pour chaque parcours de l’arbre suivant :
Le parcours en largeur visite les nœuds niveau par niveau, de gauche à droite. Il utilise une file (FIFO : First In, First Out).
def largeur(arbre):
if arbre is None:
return
file = [arbre]
while file != []:
noeud = file.pop(0)
print(noeud.valeur, end=' ')
if noeud.gauche is not None:
file.append(noeud.gauche)
if noeud.droit is not None:
file.append(noeud.droit)
Compléter la trace d’exécution du parcours en largeur sur l’arbre précédent :
| Étape | Contenu de la file | Nœud traité |
|---|---|---|
| 0 | [5] | — |
| 1 | 5 | |
| 2 | ||
| 3 | ||
| 4 | ||
| 5 | ||
| 6 | ||
| 7 |
| Étape | Contenu de la file | Nœud traité |
|---|---|---|
| 0 | [5] | — |
| 1 | [3, 8] | 5 |
| 2 | [8, 1, 4] | 3 |
| 3 | [1, 4, 7, 9] | 8 |
| 4 | [4, 7, 9] | 1 |
| 5 | [7, 9] | 4 |
| 6 | [9] | 7 |
| 7 | [] | 9 |
Ordre de visite : 5, 3, 8, 1, 4, 7, 9 (niveau par niveau)
5, 3, 1, 4, 8, 7, 9. Quel est le premier nœud visité ? Quelle est la racine ?
Un ABR est un arbre binaire tel que pour tout nœud :
Une propriété fondamentale est que le parcours infixe d’un ABR donne les valeurs dans l’ordre croissant.
Parmi ces arbres, lesquels sont des ABR ? Justifier.
Arbre 1 :
Arbre 2 :
Arbre 3 :
def rechercher(arbre, x):
if arbre is None:
return False
if x == arbre.valeur:
return True
elif x < arbre.valeur:
return rechercher(arbre.gauche, x)
else:
return rechercher(arbre.droit, x)
La recherche suit un seul chemin de la racine vers une feuille : son coût dépend donc de la hauteur de l’arbre. Un arbre est équilibré lorsque, pour chaque nœud, les hauteurs des sous-arbres gauche et droit sont proches ; sa hauteur est alors de l’ordre de \(\log_2 n\).
Écrire la fonction inserer(arbre, x) qui insère l’élément x dans l’ABR arbre.
def inserer(arbre, x):
if arbre is None:
return Arbre(x)
if x < arbre.valeur:
arbre.gauche = inserer(arbre.gauche, x)
elif x > arbre.valeur:
arbre.droit = inserer(arbre.droit, x)
return arbre
On insère successivement les valeurs 5, 2, 8, 1, 3, 7, 9 dans un ABR initialement vide.
Dessiner l’ABR obtenu après chaque insertion.
Quelle serait la forme de l’arbre si on insérait les valeurs dans l’ordre 1, 2, 3, 5, 7, 8, 9 ?
Comparer les hauteurs des deux arbres et expliquer la conséquence sur les performances.
Arbre final : 5 (racine), fils gauche 2 (fils 1, 3), fils droit 8 (fils 7, 9). Hauteur = 2 (équilibré).
Avec l’ordre trié : 1 (racine), fils droit 2, fils droit 3, etc. Arbre peigne (dégénéré) vers la droite. Hauteur = 6.
L’arbre dégénéré se comporte comme une liste (\(O(n)\)), perdant l’avantage logarithmique (\(O(\log n)\)) de l’arbre équilibré.
valeur, gauche et droit.