Imaginons une bibliothèque qui contienne vraiment beaucoup de livres l, répartis dans 17 576 salles reliées les unes aux autres par des portes.
Chaque salle contient une porte d'entrée et, possiblement, deux portes de sorties vers deux autres salles.
Pour retrouver facilement l'emplacement d'un livre, les bibliothécaires astucieux ont eu l'idée suivante. Dans la toute première salle, dans laquelle on entre par la porte d'entrée de la bibliothèque, ils ont mis tous les ouvrages dont le titre commence par MDB.
Si en revanche le titre commence par trois lettres venant avant MDB dans l'ordre alphabétique, alors il faut prendre la porte de sortie de gauche. Sinon, il faut prendre la porte
de sortie de droite.
On continue alors la recherche dans la salle suivante.
Si on est allé dans la salle de gauche, par exemple, on y trouve tous les ouvrages dont le titre commence par GBN. Là, de même, si le titre commence par trois lettres venant avant GBN dans l'ordre alphabétique, alors il faut prendre la porte de sortie de gauche, sinon la porte de droite. Et ainsi de
suite jusqu'à ce qu'on parvienne à la salle contenant tous les livres dont les trois premières lettres du titre sont celles du titre qui nous intéresse.
Une telle organisation est incroyablement efficace. En effet, avec la répartition choisie par les bibliothécaires, il ne faut jamais traverser plus de 15 salles pour trouver un ouvrage, alors qu'il y à, rappelons-le, 17576 salles au total.
******
Lu LHABIUS 7e PULIED WING UE IEUNIGIUIIS
On peut visualiser les salles de cette bibliothèque comme un arbre binaire, où chaque nœud correspond à une salle.
Un nœud est étiqueté par un mot de trois lettres et ses deux sous-arbres correspondent aux salles adjacentes.
Dans l'exemple ci-dessus, le haut de cet arbre ressemble à ceci :
___MDB____
/ \\
_GEN_ _SEP_
/ \\ / \\
... _JOH_ ... ...
/ \\
... ...
Comme on l'a compris, quand on se dirige du côté gauche, on trouve des mots plus petits dans l'ordre alphabétique et quand on se dirige du côté droit, on trouve des mots plus grands. Et cette propriété n'est pas vraie seulement pour la racine.
Elle est valable pour tous les nœuds de l'arbre.
Ainsi, dans le sous-arbre droit du nœud marqué JCH, on trouvera des mots plus grands que JCH et plus petits que MDB (car on reste à gauche de la racine).
De même, dans le sous-arbre gauche du nœud marqué SEP, on trouvera des mots plus petits que SEP mais plus grands que MDB (car on reste à droite de la racine).Et ainsi de suite.
On appelle cela un arbre binaire de recherche.
","title":"Arbres binaires de recherche","tagtitle":"h1"},{"edit":"D'une manière générale, un arbre binaire de recherche (abrégé en ABR ou en anglais BST Binary Search Tree) est un arbre binaire dont les nœuds contiennent des valeurs qui peuvent être comparées entre elles, comme des entiers ou des chaînes de caractères par exemple, et tel que, pour tout nœud de l'arbre, toutes les valeurs situées dans le sous-arbre gauche (resp. droit) sont plus petites (resp. plus grandes) que la valeur située dans le nœud.
Ainsi, les deux arbres de gauche sont des ABR, mais celui de droite n'en est pas un:
___3___ / \\ _1_ _4_ / \\ / \\ _2_ / \\ | ___3___ / \\ _2_ _4_ / \\ / \\ _1_ / \\ | ___3___ / \\ _2_ _4_ / \\ / \\ _1_ / \\ |
Pour l'arbre de droite, la propriété est bien vérifiée pour la racine, mais
elle ne l'est pas pour le nœud étiqueté par 2, qui contient 1 dans son sous-
arbre droit.
Comme l'illustrent les deux arbres de gauche, les mêmes valeurs peuvent être stockées dans plusieurs ABR différents.
Représentation en Python
Un ABR étant un arbre binaire, on le représente en Python exactement comme à la séquence précédente avec notre classe Noeud.
On nc fait qu'ajouter deux
contraintes :
- les valeurs contenues dans les nœuds peuvent être comparées avec les opérations <, >=, etc., de Python (c'est le cas des entiers et des chaînes de caractère notamment);
- les arbres vérifient la propriété d'ABR.
Ces deux contraintes ne sont pas encodées en Python.
Elles sont uniquement supposées ou garanties, selon le cas, par les fonctions que nous allons écrire dans les sections suivantes.
class Noeud:
\"\"\"un noeud d'un arbre binaire\"\"\"
def __init__(self, g, v, d):
self.gauche = g
self.valeur = v
self.droit = d
def __eq__(self, n):
return n is not None \\
and self.gauche == n.gauche \\
and self.valeur == n.valeur \\
and self.droit == n.droit
Opérations
Les fonctions définies à la séquence précédent sur les arbres binaires, à savoir taille, hauteur et parcours_infixe restent valables pour des ABR.
En particulier, le parcours infixe d'un ABR affiche les valeurs contenues dans
l'ABR par ordre croissant.
En effet, il commence par afficher les valeurs du sous-arbre gauche, puis affiche la racine, et affiche enfin les valeurs du sous-arbre droit.
Dans ce qui suit, nous allons maintenant programmer des opérations qui sont spécifiques aux ABR.
Comme on l'a compris avec l'exemple introductif, la propriété d'ABR
tire tout son intérêt de l'efficacité de la recherche qu'elle permet.
En effet, pour chercher une valeur dans un ABR, il suffit de la comparer à la valeur à la racine puis, si elle est différente, de se diriger vers un seul des deux sous-arbres.
On élimine ainsi complètement la recherche dans l'autre sous-arbre.
Écrivons une fonction
def appartient(x, a):
qui détermine si la valeur x apparaît dans l'ABR a.
On commence par le cas d'un arbre vide, pour lequel la réponse est évidente.
if a is None:
return False
Dans le cas contraire, cela veut dire que l'arbre contient au moins un nœud.
On peut donc comparer la valeur x avec la valeur située à la racine de l'arbre, c'est-à-dire a.valeur.
Si la valeur x est plus petite, il faut continuer la recherche dans le sous-arbre gauche, ce que l'on fait récursivement.
if x < a.valeur:
return appartient(x, a.gauche)
(Ne pas oublier le return, pour renvoyer le résultat de l'appel récursif.)
Si la valeur x est en revanche plus grande que a.valeur, alors on procède de même à une recherche dans le sous-arbre droit.
elif x > a.valeur:
return appartient(x, a.droit)
Enfin, si elle n'est ni plus petite ni plus grande, c'est que les deux valeurs
sont égales.
Autrement dit, la valeur x apparaît à la racine de l'arbre, ce que l'on signale en renvoyant True.
else:
return True
Le code complet est le suivant :
Programme — Recherche dans un ABR
def appartient(x, a):
\"\"\"détermine si x apparaît dans l'ABR a\"\"\"
if a is None:
return False
if x < a.valeur:
return appartient(x, a.gauche)
elif x > a.valeur:
return appartient(x, a.droit)
else:
return True
Tester le programme appartient avec les instructions suivantes et conclure:
a5 = Noeud(Noeud(Noeud(None,2,None),4,Noeud(None,5,None)), \\
8, \\
Noeud(Noeud(None,10,None),12,Noeud(None,14,None) ))
print(appartient(2,a5))
print(appartient(15,a5))
Efficacité
Quelle est l'efficacité de la fonction appartient, en terme du nombre d'opérations effectuées pour rechercher une valeur x dans un arbre à qui contient N éléments?
Si les éléments sont répartis à peu près équitablement entre les deux sous-arbres, la fonction appartient élimine la moitié des éléments à chaque étape.
Cela fait écho à la recherche dichotomique dans un tableau trié, où chaque étape divise par deux le nombre d'éléments à examiner.
Comme on l'a vu, c'est extrêmement efficace. Ainsi, il ne faut pas plus de 20 étapes pour chercher parmi un million de valeurs.
D'autre part, il n'y aucun risque de provoquer l'erreur RecursionError dans
ce cas.
Cela étant, rien ne garantit que les éléments sont équitablement répartis, à chaque étape, entre les deux sous-arbres.
En particulier, l'arbre a peut tout à fait être un peigne, comme les deux arbres suivants :
__O_ __O__
/ \\ / \\
__O__ __O__
/ \\ / \\
__O__ __O__ / \\ / \\
ou plus généralement un arbre complètement filiforme dont la hauteur est égale au nombre de nœuds.
Dans ce cas, la recherche est au contraire peu efficace, car elle est susceptible de parcourir l'arbre tout entier, par exemple dans le cas
d'une recherche infructueuse.
À cet égard, un ABR linéaire n'est pas meilleur qu'une liste chaînée.
D'une manière générale, le coût de la recherche dans un ABR est majoré par sa hauteur. En effet, chaque étape de la recherche descend dans l'un des deux sous-arbres. Du coup, on ne peut répéter cela un nombre de fois plus grand que la hauteur de l'arbre, par définition.
La hauteur d'un ABR dépend directement de la façon dont il a été construit, ce qui est discuté dans les deux sections suivantes.
Mettre le résultat ici (code et figure).
Nous allons écrire une fonction ajoute(x, a) qui ajoute un nouvel élément x dans l'ABR a.
Ainsi, nous pourrons construire des ABR par ajouts successifs d'éléments avec la fonction ajoute, en partant d'un arbre vide.
Dans le principe, ajouter un nouvel élément dans un ABR n'est pas plus compliqué que de le chercher :
- s'il est plus petit, on va à gauche; - s'il est plus grand, on va à droite.
Et quand on arrive à un arbre vide, on ajoute un nouveau nœud.
Si par exemple il s'agit d'ajouter l'élément 2 dans l'arbre
___3___
/ \\
_1_ _4_
/ \\ / \\
alors on commence par aller à gauche, car 2 est plus petit que 3, puis on va à droite, car 2 est plus grand que 1, puis enfin on ajoute un nouveau nœud contenant 2 car on est arrivé sur un arbre vide.
On obtient donc cet arbre :
___3___
/ \\
_1_ _4_
/ \\ / \\
_2_
/ \\
En pratique, cependant, il n'est pas si facile de mettre en œuvre cette idée.
Naïvement, on pourrait penser que la fonction ajoute ne renvoie rien et se contente de modifier l'arbre reçu en argument, pour lui greffer un nouveau nœud.
Mais si l'arbre est vide, c'est-à-dire vaut None, une telle modification n'est pas possible. [l faudrait faire alors un cas particulier pour l'insertion dans un arbre vide, en dehors de notre fonction ajoute, ce qui est extrêmement déplaisant.
Par ailleurs, il faudrait faire également des cas particuliers dans la fonction ajoute elle-même, lorsqu'elle s'apprête à se rappele récursivement sur un sous-arbre vide.
Pour cette raison, nous allons adopter la même approche qu'avec les listes chaînées, à savoir ne pas modifier les arbres reçus en arguments mais en renvoyer de nouveaux.
Dit autrement, nous choisissons d'utiliser nos objets de classe Noeud de façon immuable, comme nous l'avions fait avec les objets de la classe Cellule.
Écrivons donc une fonction ajoute qui renvoie un nouvel arbre contenant x et tous les éléments de a.
def ajoute(x, a):
Comme pour la recherche, on procède récursivement.
Le cas de base est celui de l'ajout dans un arbre vide. Dans ce cas, il convient de renvoyer un arbre contenant un unique nœud, dont la valeur est x.
iF a is None:
return Noeud(None, x, None)
Si en revanche l'arbre a n'est pas vide, on compare x et a.valeur. Si x est plus petit, on doit l'ajouter dans le sous-arbre gauche.
L'appel récursif ajoute(x, a.gauche) nous renvoie, par définition, un arbre qui contient x et tous les éléments de a.gauche.
C'est le sous-arbre gauche de notre résultat, par dessus lequel nous réinstallons une racine de même valeur a.valeur et un sous-arbre droit a.droit inchangé.
if x < a.valeur:
return Noeud(ajoute(x, a.gauche), a.valeur, a.droit)
Si en revanche x est supérieur ou égal à a.valeur, on doit l'ajouter au sous-
arbre droit.
On procède de façon similaire, avec cette fois un appel récursif ajoute(x,a.droit).
else:
return Noeud(a.gauche, a.valeur, ajoute(x, a.droit))
On note qu'on ne fait pas ici de traitement particulier dans le cas où x est égal à a.valeur.
Ceci est discuté un tout petit peu plus loin.
Ceci achève donc notre fonction ajoute. Le code complet est le suivant :
Programme — Ajout dans un ABR
def ajoute(x, a):
\"\"\"ajoute x à l'arbre a, renvoie un nouvel arbre\"\"\"
if a is None:
return Noeud(None, x, None)
if x < a.valeur:
return Noeud(ajoute(x, a.gauche), a.valeur, a.droit)
else:
return Noeud(a.gauche, a.valeur, ajoute(x, a.droit))
Tester le programme avec les instructions suivantes et conclure :
a1 = ajoute(8,None)
a1 = ajoute(4,a1)
a1 = ajoute(2,a1)
a1 = ajoute(5,a1)
a1 = ajoute(12,a1)
a1 = ajoute(10,a1)
a1 = ajoute(14,a1)
affiche1(a1)
print()
Efficacité
La complexité de notre fonction ajoute n'est pas différente de celle de la fonction appartient. En effet, on prend exactement les mêmes décisions quant à la descente dans l'arbre et, comme pour la fonction appartient, on fait un nombre borné d'opérations à chaque étape.
La conclusion est donc la même :
la complexité dépend de la forme de l'arbre et elle est, dans le pire des cas, majorée par sa hauteur.
En ce qui concerne l'utilisation de la
mémoire, la fonction ajoute construit autant de nœuds qu'elle fait d'appels
récursifs. Sa complexité en espace est donc comparable à sa complexité en temps.
Exactement comme pour la concaténation des listes chaînées, certaines parties de l'arbre a sont réutilisées dans le résultat renvoyé par ajoute(x, a) et d'autres parties sont en revanche «dupliquées».
Plus précisément, tous les nœuds le long de la descente sont dupliqués et
tous les sous-arbres dans lesquels on ne descend pas sont partagés. Re-
prenons l'exemple ci-dessus où on ajoute successivement les éléments 3, 1
et 4, dans cet ordre, dans un arbre initialement vide. Quand on exécute
a = ajoute(3, None), on obtient un arbre réduit à un seul nœud, qui vient
d'être créé :
_3_
/. \\
Quand ensuite on exécute a = ajoute(1,a), ce nœud contenant 3 est dupliqué, par le return Noeud(...) qui encadre l'appel récursif pour insérer 1 dans le sous-arbre gauche. Puis un nouveau nœud contenant 1 est créé et on obtient au final un arbre qui ne partage rien avec le précédent :
_3_
/ \\
_1_
/ \\
En revanche, les choses deviennent plus subtiles quand on poursuit avec a = ajoute(4,a) car cette fois le sous-arbre gauche est partagé entre l'argument et le résultat. La racine contenant 3 est de nouveau dupliquée et bien sûr un nouveau nœud contenant 4 est construit. On peut l'illustrer ainsi, avec à gauche l'arbre passé en argument et à droite l'arbre renvoyé en résultat :
*****
Comme pour les listes, il n'y a pas de danger à réaliser un tel partage, tant
qu'on ne modifie pas (par des affectations) les sous-arbres ainsi partagés. Vu que notre fonction ajoute ne fait aucune affectation, il n'y a aucun risque tant qu'on se limite à cette fonction.
En première approximation, on n'a pas vraiment besoin de se soucier de ce partage. On peut tout à fait l'ignorer. En particulier, on peut continuer à dessiner le résultat précédent comme nous le faisions auparavant,
__3__
/ \\
_1_ _4_
/ \\ / \\
c'est-à-dire sans expliciter que le sous-arbre gauche est commun avec un autre arbre.
Seules des considérations d'occupation mémoire pourraient éventuellement faire une différence, si tous ces arbres cohabitaient en mémoire. Mais le plus souvent, ce n'est pas le cas. Ainsi, lorsqu'on exécute une séquence d'instructions telle que
a = ajoute(3, None)
a = ajoute(1, a)
a = ajoute(4, a)
seul le dernier arbre construit est stocké dans la variable a. Tous les sous-
arbres qui ne participent pas au résultat final sont récupérés par le GC de Python. Une fois que c'est fait, il n'y a plus de partage.
","title":"Ajout dans un ABR","tagtitle":"h1"},{"edit":"Mettre le résultat ici (code et figure).
Doublons
Telle que nous l'avons écrite, notre fonction ajoute a la propriété de toujours ajouter un nouveau nœud à l'arbre.
En particulier, si l'élément x apparaît déjà dans l'arbre, un nouveau nœud contenant une nouvelle occurrence de x va être ajouté.
Plus précisément, lorsque x est égal à la racine a.valeur, on poursuit notre insertion dans le sous-arbre droit. Ainsi, si on insère 3 dans l'arbre donné en exemple plus haut qui contient déjà 1,2,3,4, alors on va obtenir l'arbre suivant :
____3____
/ \\
_1_ _4_
/ \\ / \\
_2_ _3_
/ \\ / \\
En effet, on commence par comparer l'élément à ajouter, 3, avec la racine, qui vaut 3 également. Dès lors, on se déplace vers le sous-arbre droit.
On pourrait tout à fait préférer insérer à gauche plutôt qu'à droite en cas d'égalité. Pour cela, il suffirait de remplacer la comparaison stricte < par une comparaison large <= dans le code de la fonction ajoute.
Nos ABR réalisent donc des multi-ensembles, c'est-à-dire des ensembles où un même élément peut paraître plusieurs fois. Si on veut en revanche réaliser des ensembles, où chaque élément apparaît exactement une fois, il ne faut pas ajouter de nouvelle occurrence de l'élément x lorsqu'il se trouve déjà
dans l'arbre.
Pour cela, il y a deux solutions. La première consiste à d'abord tester si x apparaît dans a, avec notre fonction appartient, et n'appeler la fonction ajouter qu'en cas de réponse négative.
La deuxième consiste à écrire une variante de la fonction ajoute qui n'ajoute pas de nouvelle occurrence de l'élément x s'il est déjà dans l'arbre a, mais renvoie un arbre identique à a.
","title":""},{"edit":"Alternatives
Comme nous l'avons évoqué plus haut, il n'est pas impossible de réaliser une modification en place d'un arbre pour lui ajouter un nouvel élément.
Voici à quoi pourrait ressembler une fonction ajoute qui modifie l'arbre a reçu en argument et ne renvoie rien.
def ajoute(x,a):
if x < a.valeur:
if a.gauche is None:
a.gauche = Noeud(None, x, None)
else:
ajoute(x,a.gauche)
elif x > a.valeur:
if a.droit is None:
a.droit = Noeud(None, x, None)
else:
ajoute(x,a.droit)
On a illustré ici le cas d'une insertion dans le sous-arbre gauche.
On teste si ce sous-arbre est vide. Le cas échéant, on greffe le nouveau nœud.
Sinon, on procède récursivement.
On fait de même pour une insertion dans le sous-arbre droit.
Comme on le voit, le code est devenu plus
complexe. Mais surtout, il ne traite pas le cas de l'insertion dans un arbre vide, c'est-à-dire lorsque a vaut None.
On serait obligé de le traiter dans le code englobant, c'est-à-dire dans le code qui appelle ajoute initialement.
Tester la fonction ajoute avec les instructions suivantes :
a6 = Noeud(None,8,None)
ajoute(4,a6)
ajoute(12,a6)
ajoute(2,a6)
ajoute(6,a6)
ajoute(10,a6)
ajoute(14,a6)
ajoute(1,a6)
ajoute(3,a6)
ajoute(5,a6)
ajoute(7,a6)
ajoute(9,a6)
ajoute(11,a6)
ajoute(13,a6)
ajoute(15,a6)
affiche1(a6)
Comparer avec le la fonction précédente ajoute et conclure.
Il y a d'autres manières de procéder pour réaliser une insertion en place, mais elles sont toutes complexes, d'une façon ou d'une autre.
Au final, le premier programme ajout est plus simple simple qui soit. Par ailleurs, son efficacité est comparable à celle de toute autre solution, y compris les solutions qui modifient l'arbre.
En effet, le nombre d'opérations est dans tous les cas défini par la descente dans l'arbre jusqu'au point d'insertion, quelle que soit la méthode choisie.
Enfin, dans la dernière section, nous allons encapsuler un ABR dans un objet
pour lui donner notamment une interface impérative, où la méthode d'ajout ne renvoie rien. Ainsi, nous aurons réconcilié la simplicité des arbres immuables avec une utilisation impérative idiomatique en Python.
Mettre le résultat ici (code et figure).
Pour supprmer un élément dans un ABR, on applique toujours le même principe, en procédant récursivement soit à gauche, soit à droite, selon le résultat de la comparaison.
Le cas de base, cependant, est plus délicat, car il s'agit de supprimer le nœud à la racine de l'arbre.
Pour conserver une structure d'arbre, il faut donner une racine à l'arbre renvoyé.
Pour cela, on peut prendre par exemple le plus petit élément du sous-arbre droit, pour en faire la racine, et le supprimer du sous-arbre droit. On est donc ramené à la suppression du plus petit élément d'un arbre, qui s'avère plus facile que la
suppression d'un élément quelconque.
En premier lieu, on suppose avoir écrit une fonction plus_petit(a) qui renvoie le plus petit élément de l'arbre a, c'est-à-dire l'élément se trouvant tout en bas à gauche de a en supposant l'arbre a non vide.
On écrit ensuite une fonction supprime_minimum(a) qui renvoie un arbre
contenant les mêmes éléments que a, à l'exclusion du plus petit élément de a.
Cela revient donc à supprimer l'élément situé tout en bas à gauche de a.
On suppose que l'arbre a est non vide. Cette fonction procède récursivement, avec un cas de
base et un cas récursif.
Le cas de base est celui d'un arbre dont le sous-arbre gauche est vide. Dans ce cas, le minimum est la racine et il suffit de renvoyer le sons-arbre droit. Sinon, on procède récursivement, en supprimant le minimum dans le sous-arbre gauche.
On peut enfin écrire une fonction supprime(x, a) qui supprime une occurrence de x dans a.
On rappelle en effet qu'on à potentiellement des doublons dans nos arbres et donc potentiellement plusieurs occurrences de x dans a.
Ici, on choisit de n'en supprimer qu'une.
Par ailleurs, on n'impose pas que l'élément x apparaisse dans a. S'il n'apparaît pas, la fonction supprime renvoie un arbre identique à a.
Le code de la fonction supprime est le suivant :
def plus_petit(a):
if a is None:
return None
if a.gauche is None:
return a.valeur
else:
return plus_petit(a.gauche)
def supprime_minimum(a) :
\"\"\"itisupprime Le plus petit élément de a
suppose a non vide\"\"\"
assert a is not None
if a.gauche is None:
# la racine est Le minimum
return a.droit
return Noeud(supprime_minimum(a.gauche) ,a.valeur,a.droit)
def supprime(x, a):
\"\"\"supprime une occurrence de x dans a\"\"\"
if a is None:
return None
if x < a.valeur:
return Noeud(supprime(x,a.gauche) ,a.valeur,a.droit)
elif x > a.valeur:
return Noeud(a.gauche,a.valeur,supprime(x,a.droit))
#il faut supprimer la racine
elif a.droit is None:
return a.gauche
else:
return Noeud(a.gauche, plus_petit(a.droit), \\
supprime_minimum(a.droit))
Tester le avec les instructions suivantes:
a6 = Noeud(None,8,None)
ajoute(4,a6)
ajoute(12,a6)
ajoute(2,a6)
ajoute(6,a6)
ajoute(10,a6)
ajoute(14,a6)
ajoute(1,a6)
ajoute(3,a6)
ajoute(5,a6)
ajoute(7,a6)
ajoute(9,a6)
ajoute(11,a6)
ajoute(13,a6)
ajoute(15,a6)
affiche1(a6)
print()
a7 = supprime(4,a6)
affiche1(a7)
Et conclure sur la fonction supprime.
Le cas d'un arbre vide est traité en premier lieu. Il suffit de renvoyer un arbre vide.
On traite ensuite le cas d'une valeur x située dans le sous-arbre gauche ou dans le sous-arbre droit, avec un appel récursif. Il reste enfin le cas où la valeur x est égale à a.valeur, c'est-à-dire le cas où l'on souhaite supprimer la racine de l'arbre. C'est 1à qu'on emploie les deux fonctions minimum et supprime_minimum, pour faire du plus petit élément de a.droit la nouvelle racine de l'arbre.
Bien entendu, on aurait pu utiliser tout autant le maximum du sous-arbre gauche, d'une façon totalement symétrique.
","title":"Suppression dans un ABR"},{"edit":"Mettre le résultat ici (code et figure).
Comme nous l'avons fait pour les listes chaînées, nous pouvons maintenant encapsuler nos arbres binaires de recherche dans une classe, ici appelée ABR.
Le code de cette classe est le suivant:
Programme — Encapsulation d'un ABR dans un objet
class Noeud:
\"\"\"un noeud d'un arbre binaire\"\"\"
def __init__(self, g, v, d):
self.gauche = g
self.valeur = v
self.droit = d
def __eq__(self, n):
return n is not None \\
and self.gauche == n.gauche \\
and self.valeur == n.valeur \\
and self.droit == n.droit
class ABR:
\"\"\"arbre binaire de recherche\"\"\"
def __init__(self):
self.racine = None
def ajouter(self, x):
if self.racine is None :
self.racine = Noeud(None,x,None)
else :
self.__ajoute__(x,self.racine)
def contient(self, x):
return self.__appartient__(x, self.racine)
def affiche(self):
self.__afficher__(self.racine)
print(\"\\n\")
def __afficher__(self,a):
if a is None:
return
print (\"(\", end=\"\")
self.__afficher__(a.gauche)
print(a.valeur, end=\"\")
self.__afficher__(a.droit)
print(\")\", end=\"\")
def __ajoute__(self,x,a):
if x < a.valeur:
if a.gauche is None:
a.gauche = Noeud(None, x, None)
else:
self.__ajoute__(x,a.gauche)
elif x > a.valeur:
if a.droit is None:
a.droit = Noeud(None, x, None)
else:
self.__ajoute__(x,a.droit)
def __appartient__(self,x, a):
\"\"\"détermine si x apparaît dans l'ABR\"\"\"
if a is None:
return False
if x < a.valeur:
return self.__appartient__(x, a.gauche)
elif x > a.valeur:
return self.__appartient__(x, a.droit)
else:
return True
Tester avec :
a8 = ABR()
a8.ajouter(8)
a8.ajouter(4)
a8.ajouter(12)
a8.ajouter(2)
a8.ajouter(6)
a8.ajouter(10)
a8.ajouter(14)
a8.ajouter(1)
a8.ajouter(3)
a8.ajouter(5)
a8.ajouter(7)
a8.ajouter(9)
a8.ajouter(11)
a8.ajouter(13)
a8.ajouter(15)
a8.affiche()
print(\"a8 contient 15? \",a8.contient(15))
print(\"a8 contient 17? \",a8.contient(17))
Et conclure.
Chaque objet de la classe ABR contient un unique attribut, racine, qui est l'arbre binaire de recherche qu'il représente. Le constructeur de la classe ABR renvoie un arbre vide, avec donc la valeur None dans l'attribut racine.
Ainsi, si on construit un arbre vide, que l'on stocke dans une variable a, on a la
situation suivante:
![\"arbre9.png](\"https://sciencesappliquees.com/images/nsi/arbre9.png\")
a = ABR()
La classe ABR fournit deux méthodes, ajouter et contient, correspondant aux deux fonctions ajoute et appartient des deux sections précédentes.
Ainsi, on peut construire un arbre contenant les éléments 1, 2, 3, 4 en les
ajoutant avec la méthode ajouter. I! faut comprendre que chaque appel à la méthode ajouter remplace l'attribut racine par un nouvel arbre, à savoir celui qui est renvoyé par la fonction ajoute.
L'arbre qui était précédemment dans l'attribut racine est perdu et sera récupéré par le GC de Python, à sa discrétion.
En pratique, il faudrait ajouter d'autres méthodes à la classe ABR, correspondant à d'autres fonctions comme taille, hauteur, parcours_infixe, suprimer, etc.
a = ABR()
a.ajouter(3)
a.ajouter(1)
a.ajouter(4)
a.ajouter(2)
![\"arbre9.png](\"https://sciencesappliquees.com/images/nsi/arbre10.png\")
Figure : Construction d'un ABR contenant quatre éléments.
Mettre le résultat ici (code et figure).
Comme on l'a expliqué plus précédemment, le coût de la recherche ou de l'ajout dans un ABR dépend de sa structure. Il est borné par la hauteur de l'ABR.
Dans le pire des cas, l'arbre peut être complètement linéaire et le coût peut
donc être proportionnel au nombre d'éléments, ce qui en fait une structure
de peu d'intérêt. Autant mettre tous les éléments dans un tableau ou une liste chaînée si c'est pour faire une recherche linéaire.
Néanmoins, il est possible de s'assurer, pendant leur construction, que la hauteur des ABR « ne sera pas trop grande ».
Pour cela, on réorganise la structure de l'ABR lorsque c'est nécessaire, tout en maintenant la propriété d'arbre binaire de recherche.
Il existe de multiples façons de procéder. Parmi les plus connues, on peut citer les arbres AVL ou encore les arbres rouges et noirs.
Le détail de ces méthodes dépasse largement le cadre du programme de terminale.
On peut se contenter de dire que l'idée est, pour chaque sous-arbre, de mettre approximativement la moitié des nœuds dans le sous-arbre gauche et l'autre moitié dans le sous-arbre droit.
Ainsi, on divise par deux le nombre de nœuds à considérer à chaque descente dans l'arbre, comme dans le cas de la recherche dichotomique dans un tableau trié. Dit autrement, ces méthodes d'équilibrage des arbres permettent de garantir une hauteur logarithmique, c'est-à-dire l'existence d'une constante C telle que
h ≤ C.log2(N)
où h désigne la hauteur et N la taille d'un ABR.
Par exemple, pour les arbres AVL, on a C=1,44. On parle d'arbres équilibrés lorsqu'on à une telle inégalité. Les opérations de recherche ou d'ajout sur les arbres équilibrés ont une complexité logarithmique, ce qui en fait des opérations très efficaces en pratique.
Par ailleurs, il n'y a plus aucun risque de provoquer l'erreur RecursionError lorsque les arbres sont équilibrés.
","title":"Arbre équilibré "},{"edit":"Un arbre binaire de recherche est un arbre binaire contenant des valeurs ordonnées, avec la propriété que tout nœud contient une valeur plus grande (resp. plus petite ou égale) que les valeurs contenues dans son sous-arbre gauche (resp. droit). Cette organisation permet de procéder par dichotomie, en n'ayant à considérer qu'un seul des
deux sous-arbres pendant une opération. Lorsqu'ils sont équilibrés, les arbres binaires de recherche constituent une méthode très efficace pour stocker et rechercher de l'information.
Pourquoi la bibliothèque donnée en exemple au début de ce
chapitre contient-elle 17576 salles ?
","title":"Exercice","tagtitle":"h1"},{"edit":"Mettre le résultat ici (code et figure).
Donner tous les ABR formés de trois nœuds et contenant les entiers 1, 2 et 3.
","title":"Exercice"},{"edit":"Mettre le résultat ici (code et figure).
_3_ / \\ _2_ / \\ _1_ / \\ | _3_ / \\ _1_ / \\ _2_ / \\ | __2__ / \\ _1_ _3_ / \\ / \\ |
_1_ / \\ _2_ / \\ _3_ / \\ | _1_ / \\ _3_ / \\ _2_ / \\ |
Dans un ABR, où se trouve le plus petit élément ? En déduire
unc fonction minimum(a) qui renvoie le plus petit élément de l'ABR a. Si
l'arbre à est vide, alors cette fonction renvoie None.
Tester avec :
a5 = Noeud(Noeud(Noeud(None,2,None),4,Noeud(None,5,None)), \\
8, \\
Noeud(Noeud(None,10,None),12,Noeud(None,14,None) ))
print(minimum(a5))
Résultat :
2
","title":"Exercice","tagtitle":"h1"},{"edit":"Mettre le résultat ici (code et figure).
Par définition d’un ARB, le plus petit élément se trouve en bas à gauche de l’arbre.
def minimum(a):
if a is None:
return None
if a.gauche is None:
return a.valeur
else:
return minimum(a.gauche)
def ajoute(x, a):
#ajoute x à l'arbre a, renvoie un nouvel arbre
if a is None:
return Noeud(None, x, None)
if x < a.valeur:
return Noeud(ajoute(x, a.gauche), a.valeur, a.droit)
else:
return Noeud(a.gauche, a.valeur, ajoute(x, a.droit))
Modifier la fonction ajoute qui n'ajoute pas l'élément x à l'arbre a s'il est déjà dedans.
Tester avec :
a5 = Noeud(Noeud(Noeud(None,2,None),4,Noeud(None,5,None)), \\
8, \\
Noeud(Noeud(None,10,None),12,Noeud(None,14,None) ))
a5 = ajoute(1,a5)
a5 = ajoute(15,a5)
a5 = ajoute(14,a5)
affiche1(a5)
Résultat :
(((1)2)4(5))8((10)12(14(15))))
","title":"Exercice"},{"edit":"Mettre le résultat ici (code et figure).
def ajoute(x, a):
#ajoute x à l'arbre a, renvoie un nouvel arbre
if a is None:
return Noeud(None, x, None)
if x < a.valeur:
return Noeud(ajoute(x, a.gauche), a.valeur, a.droit)
elif x > a.valeur:
return Noeud(a.gauche, a.valeur, ajoute(x, a.droit))
else :
return a # x est dans a
Écrire une fonction compte(x, a) qui renvoie le nombre d'occurrences de x dans l'ABR. a. On ne suppose pas que l'arbre a à été construit à partir de la fonction ajoute, mais seulement qu'il s'agit d'un ABR.
Cela veut dire qu'une valeur égale à la racine peut se trouver encore dans le sous-arbre gauche autant que dans le sous-arbre droit.
Cela étant, on s'attachera à ne pas descendre dans les sous-arbres dans lesquels on est certain que la
valeur x ne peut apparaître.
Tester avec :
a5 = Noeud(Noeud(Noeud(None,2,None),4,Noeud(None,5,None)), \\
8, \\
Noeud(Noeud(None,10,None),12,Noeud(None,14,None) ))
print(compte(4,a5))
print(compte(14,a5))
print(compte(1,a5))
Résultat :
1
1
0
","title":"Exercice"},{"edit":"Mettre le résultat ici (code et figure).
Lorsque x est strictement plus petit ou strictement plus grand que a.valeur, il suffit d’aller d’un seul côté. En cas d'égalité, en
revanche, il faut continuer à compter des deux côtés.
def compte(x, a):
if a is None:
return 0
if x < a.valeur:
return compte(x, a.gauche)
elif x > a.valeur:
return compte(x, a.droit)
else:
return 1 + compte(x, a.gauche) + compte(x, a.droit)
Écrire une fonction remplir(a, t) qui ajoute tous les éléments de l'arbre a dans le tableau t, dans l'ordre infixe. Chaque élément x est ajouté au tableau t avec t.append(x).
Ajouter ensuite une méthode lister(self)
à la classe ABR qui renvoie un nouveau tableau contenant tous les éléments de l'ABR self par ordre croissant.
Tester avec :
a5 = Noeud(Noeud(Noeud(None,2,None),4,Noeud(None,5,None)), \\
8, \\
Noeud(Noeud(None,10,None),12,Noeud(None,14,None) ))
t1 = []
remplir(a5,t1)
print(t1)
Pour la classe ABR :
a6 = ABR()
a6.ajouter(8)
a6.ajouter(4)
a6.ajouter(2)
a6.ajouter(5)
a6.ajouter(12)
a6.ajouter(14)
a6.ajouter(10)
t2 = a6.lister()
print(t2)
Résultat :
[2, 4, 5, 8, 10, 12, 14]
Mettre le résultat ici (code et figure).
C'est un cas particulier de parcours infixe (pro-
gramme 30 page 154) :
def remplir(a, t):
if a is None:
return
remplir(a.gauche, t)
t.append(a.valeur)
remplir(a.droit, t)
Pour la méthode lister dans la classe ABR, on crée un nouveau tableau, que l’on remplit avec la fonction remplir.
def lister(self):
t = []
remplir(self.racine, t)
return t
En utilisant l'exercice précédent, écrire une fonction trier(t) qui reçoit en argument un tableau d'entiers et renvoie un tableau trié contenant les mêmes éléments.
Quelle est l'efficacité de ce tri?
Tester avec :
t2 = [5,2,4,0,9,10,3,12,7]
t3 = trier(t2)
print(t3)
Résultat :
[0, 2, 3, 4, 5, 7, 9, 10, 12]
","title":"Exercice","tagtitle":"h1"},{"edit":"Mettre le résultat ici (code et figure).
L'idée est d'ajouter tous les éléments du tableau t dans un ABR, puis d'utiliser la méthode lister de l'exercice précédent.
def trier(t):
a = ABR()
for x in t :
a.ajouter(x)
return a.lister()
L'efficacité de ce tri dépend fortement de la répartition des éléments dans le tableau initial. Si par exemple les éléments sont déjà triés dans le tableau
initial, alors l’arbre sera un peigne et le coût de la construction de l'ABR sera donc quadratique.
"}],[{"text":"Ajouter la méthode hauteur(self) à la classe a qui renvoie la hauteur de l'arbre.
","title":"Exercice"},{"edit":"Mettre le résultat ici (code et figure).
Mettre le résultat ici (code et figure).