Les tableaux ou les listes (qu’elles soient chaînées ou des listes python) sont des structures séquentielles: elles ont vocation à être utilisées dès lors qu’il est possible d’indexer les valeurs que l’on souhaite représenter, à l’instar des suites mathématiques \((u_n)_{n\in\mathbb N}\).
Cependant, de nombreuses structures du monde qui nous entourent ne se prêtent pas facilement à une énumération, mais plutôt à une hiérarchisation: l’organigramme hiérarchique d’une entreprise, la structure des répertoires sur un disque dur, la classification des espèces en biologie, etc… sont des structures hiérarchiques que l’on représentera plus aisément à l’aide d’un arbre.
Nous étudierons brièvement la structure générale d’arbre dans un chapitre futur. Les arbres binaires sont un type particulier d’arbres.
Un arbre binaire est un cas particulier d’une structure arborescente pour laquelle chaque position (appelée noeud en langage informatique) ne peut aboutir qu’à un maximum de deux autres positions.
Plus précisément:
Dans la figure ci-dessus, on a représenté la structure d’un arbre binaire comportant 12 noeuds. Lorsqu’il n’y a pas de sous-arbre à gauche ou à droite, on représente une liaison plus claire ne pointant sur rien. Cela permet notamment de savoir si l’unique sous-arbre est à gauche ou à droite.
Quelques noeuds ont des noms particuliers:
Définitions:
À tout arbre (qu’ils soient d’ailleurs binaires ou non) sont attachées deux notions importantes:
Définitions:
L’illustration précédente représente un arbre de taille 12 et de hauteur 6 (obtenue en suivant le chemin partant de la racine et empruntant toujours la branche droite jusqu’à la dernière feuille en bas à droite).
S’il n’avait que sa structure, un arbre n’aurait qu’un intérêt limité. Heureusement, un arbre prend tout son potentiel lorsqu’il permet de stocker de l’information (tout comme une tableau, une liste, un dictionnaire…).
Concrètement, à chaque noeud on associera une valeur. Ces valeurs peuvent être d’un type quelconque (entier, nombre à virgule flottante, chaîne de caractère, tableau, tuple, etc), mais on ne considérera que des arbres dont les types sont homogènes, exactement comme pour les tableaux ou les listes (mais pas les tuples qui sont spécifiquement là lorsque l’on a besoin de données hétérogènes).
Dans cet exemple, l’arbre précédent associe à chaque noeud un entier aléatoire compris entre 1 et 100.
Définition: Un arbre binaire est parfait lorsque, pour une hauteur \(h\) donnée, le nombre de noeuds est maximal.
Un arbre parfait est parfaitment équilibré: chaque noeud (sauf les feuilles) ont toujours et systématiquement deux noeuds fils.
On peut montrer que le nombre \(N\) de noeuds d’un arbre parfait (c’est-à-dire sa taille) est toujours égal à:
\[ 1 + 2 + 4 + \cdots + 2^{h-1} = 2^h - 1\]
Dans l’exemple ci-dessus, on a un arbre parfait de hauteur 4. Le nombre de noeuds est bien:
\[ 1 + 2 + 4 + 8 = 15 = 2^4 - 1\]
À l’opposé des arbres parfaits, nous avons les arbres filaires pour lesquels on ne trouvera à chaque noeud qu’un unique fils (excepté pour les feuilles bien entendu).
Définitions:
Un peigne à gauche est un arbre filaire n’ayant que des embranchements à gauche;
Un peigne à droite est un arbre filaire n’ayant que des embranchements à droite;
Un peigne est à l’opposé d’un arbre parfait dans le sens où sa hauteur est égale à sa taille. C’est un arbre le plus déséquilibré possible, car il n’y a jamais de noeuds ayant 2 fils.
Important: Nous verrons en TP et surtout dans le chapitre suivant (sur les arbres binaires de recherche) que la recherche de l’équilibre est très importante, car elle réduit considérablement la complexité des algorithmes.
Tout comme la Cellule
était indispensable à l’implémentation des listes chaînées, ici c’est le Noeud
qui permettra de définir une structure d’arbre binaire.
Concrètement, un noeud doit contenir:
On pourrait représenter un noeud par un tuple (gauche, valeur, droit)
ou bien un tableau [gauche, valeur, droit]
(encore que ce dernier ne serait probablement pas homogène, ce qui pose conceptuellement un problème), mais la manière la plus naturelle d’implémenter un noeud en python (et de loin) est d’utiliser la POO.
On définit donc une classe Noeud
contenant 3 attributs:
Noeud.gauche
qui contient le sous-arbre à gauche;Noeud.valeur
qui contient la valeur;Noeud.droite
qui contient le sous-arbre à droite;On convient qu’un arbre vide sera représenté par la valeur None
.
Voici une représentation de l’arbre précédent où on a mis en évidence ces 3 attributs pour chaque noeud:
Lorsqu’il n’y a pas de sous-arbre, les attributs correspondants valent None
, mais cela n’a pas été représenté pour ne pas alourdir la figure.
Une implémentation rudimentaire de la classe Noeud
peut être celle-ci:
class Noeud:
def __init__(self, valeur, gauche=None, droite=None):
self.valeur = valeur
self.gauche = gauche
self.droite = droite
Notons que les paramètres par défaut pour les sous-arbres à gauche ou à droite permettent de ne rien mettre lorsqu’ils sont vides (None
). L’arbre précédent peut alors être créé grâce à l’instruction:
a = Noeud(3, Noeud(83, droite=Noeud(56, gauche=Noeud(49, Noeud(41), Noeud(89, droite=Noeud(57, Noeud(28), Noeud(31, droite=Noeud(58, gauche=Noeud(45)))))))), Noeud(32))
Ce code n’est pas très lisible (il est cependant possible d’utiliser des indentations si nécessaire). Mais dans la pratique, cela n’est guère important, il est très rare de créer à la main des arbres aussi grands. Les arbres dont nous aurons l’usage seront presque toujours le résultat d’un algorithme, selon le problème que l’on cherche à résoudre.
Il existe de nombreux algorithmes liés aux arbres binaires. Nous n’en étudierons qu’une petite partie, parmis les algorithmes les plus fondamentaux.
Certains de ces algorithmes fondamentaux sont liés à la structure de ces arbres, et ne tiennent pas du tout compte des valeurs (taille et hauteur d’un arbre, parcours d’un arbre).
D’autres au contraire portent à la fois sur les valeurs et la structure (recherche des extremums par exemple), et nécessitent souvent une condition supplémentaire (notamment le fait que les valeurs soient comparables).
Calculer la taille d’un arbre binaire peut se faire récursivement:
def taille(a):
if a is None:
return 0
else:
taille_gauche = taille(a.gauche)
taille_droite = taille(a.droite)
return 1 + taille_gauche + taille_droite
Calculer la hauteur fonctionne quasiment de la même manière:
def hauteur(a):
if a is None:
return 0
else:
hauteur_gauche = hauteur(a.gauche)
hauteur_droite = hauteur(a.droite)
return 1 + max(hauteur_gauche, hauteur_droite)
La grande similitude entre les deux algorithmes précédents n’est pas due au hasard: dans les deux cas, on effectue un parcours de l’arbre. Il existe 3 types de parcours, selon le moment où l’on va traiter le noeud racine:
Illustrons ces trois notions à l’aide d’une fonction qui affiche (dans la console) les valeurs d’un arbre binaire.
Important: Notez que, entre ces trois algorithmes, seule la position de la ligne print(a.valeur)
change.
def parcours_préfixe(a):
if a is None:
return
else:
print(a.valeur)
parcours_préfixe(a.gauche)
parcours_préfixe(a.droite)
a = Noeud(1, Noeud(2), Noeud(3))
parcours_préfixe(a)
Ce programme affichera alors:
A
B
C
On a illustré sur la figure ci-dessous le parcours: suivre la ligne bleue du début jusqu’à la fin. Les ronds rouges marquent le moment où un noeud est affiché.
def parcours_infixe(a):
if a is None:
return
else:
parcours_infixe(a.gauche)
print(a.valeur)
parcours_infixe(a.droite)
a = Noeud(1, Noeud(2), Noeud(3))
parcours_infixe(a)
Ce programme affichera alors:
B
A
C
def parcours_postfixe(a):
if a is None:
return
else:
parcours_postfixe(a.gauche)
parcours_postfixe(a.droite)
print(a.valeur)
a = Noeud(1, Noeud(2), Noeud(3))
parcours_postfixe(a)
Ce programme affichera alors:
B
C
A
Les algorithmes de calcul de la taille et de la hauteur sont, conceptuellement, des parcours postfixe de l’arbre puisque l’on calcule d’abord les tailles (ou les hauteurs) des deux sous-arbres, avant d’en déduire la taille (ou la hauteur) de l’arbre représenté par la racine.
D’autres algorithmes utiliseront plutôt un parcours préfixe ou infixe, selon le cas.
Il est toujours important de se demander à quel moment on doit effectuer le traitement du noeud racine. Cela déterminera le type de parcours à effectuer.
Afin que la recherche d’un extremum ait un sens, on doit supposer que les valeurs (homogènes) stockées dans l’arbre sont comparables, c’est-à-dire qu’il est possible de les comparer à l’aide des opérateurs \(<\), \(>\), \(\leqslant\) ou bien \(\geqslant\). Cela s’appliquera donc naturellement aux entiers, aux flottants, aux chaînes de caractères, ou à des tuples (à condition que les composantes du tuples soient elles-mêmes comparables), mais pas à des dictionnaires par exemple.
Un arbre contenant des dictionnaires peut paraître absurde ? Il n’en est rien: par exemple le format de représentation de données json très utilisé de nos jours est naturellement arborescent (c’est-à-dire que l’on peut le représenter sous la forme d’un arbre, même non binaire), et contient souvent des dictionnaires (au sens python du terme).
Pour rechercher un maximum (ou un minimum), on procède comme pour la recherche du maximum dans un tableau:
maxi
avec la seule valeur dont on dispose: la valeur du noeud courant;maxi
, on ajuste la valeur de cette dernière.On aura donc ici plutôt un parcours préfixe de l’arbre, car la valeur du noeud courant est traitée en premier.
Évidemment, pour rechercher le minimum il suffit de remplacer plus grand par plus petit dans le dernier point de l’algorithme.
Notons que la condition d’arrêt n’est pas — pour une fois — le fait d’avoir un noeud vide, car la notion de maximum ou de minimum ne s’applique pas à un arbre vide.
On obtient alors:
def maximum(a):
if a.gauche is None and a.droite is None:
# C'est une feuille !
return a.valeur
else:
maxi = a.valeur
if a.gauche not is None:
maxi = max(maxi, maximum(a.gauche))
if a.droite not is None:
maxi = max(maxi, maximum(a.droite))
return maxi
def minimum(a):
if a.gauche is None and a.droite is None:
# C'est une feuille !
return a.valeur
else:
mini = a.valeur
if a.gauche not is None:
mini = min(mini, minimum(a.gauche))
if a.droite not is None:
mini = min(mini, minimum(a.droite))
return mini
On a déjà vu qu’il y avait une relation très forte entre la taille \(N\) d’un arbre et sa hauteur \(h\), selon que l’on est dans l’un des cas extrême:
\[ h = \log_2(N + 1) \approx \log_2(N)\]
\[ h = N\]
Le logarithme de base 2 croissant très lentement avec la taille de \(N\), on s’aperçoit qu’il est — et de très loin — beaucoup plus intéressant d’avoir un arbre proche d’un arbre parfait, car les algorithmes de parcours précédents (qu’ils soient pré-, in- ou postfixes) auront une pile d’appel ayant au plus \(\log_2(N+1)\) empilements.
Prenons un exemple numérique: si l’arbre contient \(N = 100\,000\) noeuds (ce qui n’est pas déraisonnable à l’époque du big data), alors un arbre très équilibré aura une hauteur qui se rapprochera de \(h \approx \log_2(100\,000) \approx 17\) par arrondi à la valeur supérieure.
Cela prendra toute son importance au chapitre suivant, où on utilisera des parcours optimisés qui n’explorent qu’une unique branche à la fois. Notamment, rechercher un élément dans une telle situation ne nécessiterait que 17 appels au maximum, alors qu’il y a \(100\,000\) données stockées dans l’arbre.
On peut atteindre des performances similaires à celle d’une recherche dichotomique.