Nous avons étudié dans le dernier paragraphe du chapitre précédent la relation entre la taille \(N\) de l’arbre — c’est-à-dire le nombre de noeuds — et sa hauteur \(h\), qui est la longueur du plus long chemin allant de la racine de l’arbre à l’une de ses feuilles. C’est aussi le nombre de niveaux de l’arbre lorsqu’il est représenté graphiquement.
Si l’arbre est parfaitement équilibré (on dit dans ce cas que l’arbre est parfait), alors on a
\[ h \approx \log_2(N)\]
Si à l’inverse l’arbre a une structure filaire (par exemple un peigne à gauche ou à droite), on aura
\[ h = N\]
On a représenté ci-dessus deux arbres comportant 15 noeuds: l’un est parfait, l’autre filaire.
Dans la pratique, tout arbre binaire se situera quelque part entre ces deux extrémités. Plus l’arbre sera équilibré, plus il se rapprochera d’un arbre parfait et plus sa hauteur se rapprochera de la valeur \(\log_2(N)\). À l’inverse, plus l’arbre sera filaire (et donc déséquilibré), plus sa hauteur tendra à se rapprocher de sa taille.
Comment rechercher un élément dans un arbre binaire ? Il suffit a priori d’effectuer un parcours de l’arbre, jusqu’à trouver l’élément recherché ou bien se rendre compte qu’il n’y est pas. Cela nécessite — comme pour une recherche dans un tableau ou une liste — de parcourir dans le pire des cas l’intégralité de la structure de donnée. On a donc nécessairement un algorithme linéaire.
Dans le cas d’un tableau ou d’une liste — et en dehors de toute autre contrainte comme par exemple lorsque le tableau est déjà trié — on ne peut pas faire mieux que cette recherche linéaire.
Si on dispose d’un arbre binaire, on ne peut pas non plus faire mieux que cela, à moins de disposer d’informations supplémentaires.
Plus précisément, si l’arbre est relativement équilibré et qu’à chaque étape de la recherche on dispose d’un moyen de choisir à coup sûr le sous-arbre à gauche ou bien le sous-arbre à droite, alors on a la garantie de terminer notre recherche (positivement ou non) en un nombre d’étapes inférieur ou égal à la hauteur \(h\) de l’arbre.
Autrement dit, on pourra avoir un algorithme dont la complexité est proportionnelle à \(\log_2(N)\) plutôt qu’un algorithme linéaire. C’est exactement ce que nous avions réussi à obtenir avec la recherche dichotomique.
Nous allons précisément étudier dans ce chapitre comment obtenir de telles conditions, c’est-à-dire comment contraindre un arbre binaire afin qu’il offre des performances proches de celles d’une recherche dichotomique, et ce sans avoir besoin d’effectuer un tri préalable (qui est lui-même bien plus coûteux qu’une recherche dichotomique).
Définition: Un arbre binaire de recherche (ABR):
Remarquons que la contrainte supplémentaire imposée à l’ABR ne permet pas de stocker des doublons en son sein. Si avoir des doublons est important, on peut s’en sortir de trois manières:
On autorise les valeurs supérieures ou égales à \(x\) dans le sous-arbre à droite:
On autorise les valeurs inférieures ou égales à \(x\) dans le sous-arbre à gauche:
On autorise les doublons indifféremment à gauche ou à droite, ce qui est bien plus symétrique:
Cette dernière possibilité est tout aussi symétrique que celle avec les inégalités strictes, mais elle a le désavantage de ne pas offrir une route unique lorsque l’on effectue une recherche, ce qui nuira à la complexité des algorithmes (dans le pire des cas, on pourrait avoir les mêmes performances qu’avec un arbre binaire quelconque, c’est-à-dire un algorithme linéaire).
Pour toute la suite du chapitre, nous choisirons — arbitrairement — la première possibilité: un ABR sera un arbre binaire pour lequel toutes les valeurs strictement inférieures à \(x\) seront dans le sous-arbre à gauche et toutes les valeurs supérieures ou égales à \(x\) seront dans le sous-arbre à droite.
Notre définition autorise donc le stockage de doublons dans l’arbres.
Voici un exemple d’ABR:
On peut constater de visu que toutes les valeurs inférieures à 11 sont dans le sous-arbre à gauche de la racine, alors que le sous-arbre à droite contient des valeurs supérieures ou égales à 11 (la valeur 11 apparaît d’ailleurs deux fois dans l’arbre).
Non seulement cette propriété est vérifiée pour la racine, mais on peut constater qu’elle est vraie pour tout noeud de l’arbre: c’est une condition nécessaire pour avoir un ABR.
Prenons l’ABR ci-dessous:
Il s’agit structurellement d’un arbre parfait, mais c’est aussi un ABR: les 15 valeurs stockées satisfont bien aux contraintes d’ordre.
Sur le schéma ci-dessous, on a mis en évidence les noeuds qu’il est nécessaire d’examiner pour rechercher la valeur 11, qui est bien contenue dans l’arbre.
En partant de la racine:
Pour le cas de 11, on a pu conclure positivement à la recherche en examinant exactement 4 noeuds sur les 15 que comporte l’arbre.
Sur le schéma ci-dessous, on a mis en évidence les noeuds qu’il est nécessaire d’examiner pour rechercher la valeur 42, qui n’est pas dans l’arbre.
Lorsque la valeur recherchée n’est pas dans l’arbre, la recherche s’arrêtera négativement dès lors que l’on arrivera sur un noeud vide. Comme l’arbre est ici parfait, on a besoin d’examiner exactement 5 noeuds (dont un noeud vide) pour conclure.
Les deux exemples précédents se généralisent de la manière suivante:
Algorithme de recherche dans un ABR:
En partant de la racine, on procède pour chaque noeud comme suit:
Le point important est que cet algorithme nous fait passer au niveau suivant de l’arbre à chaque étape, ce qui nous garantit que le nombre d’étapes est au maximum égal à la hauteur de l’arbre.
L’algorithme décrit précédemment se traduit presque mot pour mot en python, à l’aide d’une fonction récursive:
def recherche_ABR(x, a):
"""
Répond True ou False selon que x est dans l'ABR a ou non.
"""
if a is None:
# Condition d'arrêt
return False
else:
if x == a.valeur:
return True
elif x < a.valeur:
return recherche_ABR(x, a.gauche)
else:
# x >= a.valeur, forcément
return recherche_ABR(x, a.droite)
Il apparaît très clairement à la lecture de cette implémentation l’aspect mutuellement exclusif des conditions, garantissant qu’un chemin unique sera choisi à chaque étape.
De ce fait, la complexité dans le pire des cas est proportionnelle à la hauteur \(h\) de l’arbre.
L’exemple de la partie précédente était quasiment idéal, dans le sens où l’ABR était structurellement parfait.
Si à l’inverse on avait choisi un ABR entièrement filaire (c’est toujours possible, comme nous le verrons en TP), on aurait eu une recherche banalement linéaire, exactement comme si l’on cherchait une valeur dans un tableau ou bien une liste.
Indépendamment de ces deux cas extrêmes, la question primordiale de comment construire un ABR se pose.
Supposons que l’on dispose déjà d’un ABR. Comment faire pour insérer une nouvelle valeur (homogène à celles qui sont déjà stockées dans l’arbre) ?
L’algorithme suivant réalise cela, en recherchant récursivement la position dans laquelle on pourra insérer la nouvelle valeur (exactement comme pour l’algorithme décrit précédemment), puis en reconstruisant des noeuds en remontant jusqu’à la racine. Plus précisément, pour insérer une valeur \(v\), en partant de la racine de l’ABR:
Cet algorithme renvoie donc une copie de l’arbre initial, augmenté d’un nouveau noeud de valeur \(v\) placé au bon endroit , de façon à ce qu’il soit encore un ABR.
Voici son implémentation en python:
def insertion_ABR(x, a):
"""
Insère la nouvelle valeur x dans l'ABR dont la racine est a.
"""
if a is None:
return Noeud(x)
else:
v = a.valeur
if x < v:
# On insère x dans le sous-arbre à gauche
nouveau_gauche = insertion_ABR(x, a.gauche)
return Noeud(v,
gauche=nouveau_gauche,
droite=a.droite)
else:
# On insère x dans le sous-arbre à droite
nouveau_droite = insertion_ABR(x, a.droite)
return Noeud(v,
gauche=a.gauche,
droite=nouveau_droite)
Observons l’impact de cet algorithme sur un ABR.
On part de l’ABR initial ci-dessous:
On insère la valeur 5:
On insère la valeur 1:
On insère la valeur 7:
On insère la valeur 7 (une deuxième fois):
Important: Cet algorithme d’insertion place une valeur donnée à l’emplacement du premier noeud vide que l’on aurait rencontré avec l’algorithme de recherche (légèrement modifié pour qu’il ne s’interrompe pas lorsque l’on rencontre la valeur que l’on cherche à insérer — ce qui revient à retirer le cas d’égalité).
Il s’agit d’une question légitime. Dans l’exemple précédent, l’arbre obtenu après quatre insertions restait relativement équilibré (mais notons néanmoins que l’on a un arbre de profondeur 5 pour 11 valeurs, alors qu’un arbre parfait de profondeur 4 peut déjà à lui seul contenir 15 valeurs).
Est-ce toujours le cas ?
Prenons pour exemple la situation suivante: on cherche à insérer les chiffres de 0 à 9 dans un arbre vide (qui est un ABR). Quel arbre obtient-on à la fin ? On va voir que cela dépend de l’ordre d’insertion:
Si on insère les valeurs dans l’ordre croissant, on obtient un peigne à droite:
Si au contraire on insère les valeurs dans l’ordre décroissant, on obtient un peigne à gauche:
Si on mélange aléatoirement les valeurs avant de les insérer dans l’arbre, on peut tomber sur un arbre relativement équilibré. Avec l’ordre d’insertion [2, 6, 0, 1, 5, 4, 3, 9, 8, 7]
, on obtient par exemple:
Ce n’est pas optimal (profondeur de 5 plutôt que le minimum théorique de 4), mais c’est tout de même bien équilibré.
Nous ferons en TP une étude statistique sur l’insertion aléatoire, avec laquelle on peut conjecturer que la profondeur moyenne est de l’ordre de \(2\times \log_2(N)\), ce qui reste proportionnel à \(\log_2(N)\), mais demanderait une étude mathématique poussée que nous ne ferons évidemment pas en Terminale. Ce genre d’étude est toujours du domaine de la recherche, des articles ont été publiés il y a moins de 20 ans sur le sujet.
On peut montrer que, sous réserve d’avoir un arbre proche d’un arbre équilibré, l’ordre de grandeur de l’algorithme de recherche (ainsi que d’autres algorithmes sur les ABR) reste proportionnel à \(\log_2(N)\), ce qui est aussi performant qu’une recherche dichotomique sur un tableau trié.
Le remplissage aléatoire évoqué au paragraphe précédent donne un début de piste quand à la manière d’obtenir un ABR équilibré, mais il existe des moyens plus systématiques: