![\"preview\"](\"https://sciencesappliquees.com/images/nsi/arbre1.png\")
La notion de liste chaînée explorée dans les deux chapitres précédents est parfaite pour structurer un ensemble d'éléments destiné à être énuméré séquentiellement.
Comme on l'a vu avec la réalisation de piles et de files, cette structure permet également un accès simple au début de la séquence et éventuellement à certaines autres positions choisies.
Elle n'est en revanche pas adaptée aux accès ponctuels à des positions arbitraires dans la séquence, puisqu'il faut pour cela à chaque nouvel accès parcourir tous les maillons depuis la tête de la liste jusqu'à la position cherchée, ce qui prend en moyenne
un temps proportionnel au nombre d'éléments stockés dans la structure.
","title":"S.D. - Arbres binaires","tagtitle":"h1"},{"edit":"Les structures arborescentes forment une autre famille de structures chaînées, dans lesquelles le nombre de sauts à effectuer pour aller depuis le point de départ jusqu'à une position souhaitée est potentiellement bien moindre.
Ces structures sont omniprésentes en informatique et nous en avons déjà observé une :
l'arborescence des fichiers d'un ordinateur.
administrator@vps:/$ tree /home/
/home/
├── administrator
│ ├── 11.0
│ ├── odoo_install.sh
│ ├── www
│ └── documents
├── user1
│ └── documents
├── invite
└── ubuntu
Cette organisation des fichiers permet notamment, partant du répertoire racine et voyageant de répertoire en sous-répertoire, d'accéder en un petit nombre d'étapes à n'importe quel fichier choisi parmi des dizaines de milliers, pour peu qu'on aille dans la bonne direction.
Ce principe d'un point de départ unique à partir duquel une structure chaînée se scinde à chaque étape en plusieurs branches donne l'idée générale de la structure d'arbre en informatique, qui est à la base d'innombrables structures de données.
Cette structure permet en outre une organisation hiérarchique de l'information, qui la rend utile pour représenter des programmes, des formules de logique, le contenu de pages web, etc.
Mettre le résultat ici (code et figure).
Un arbre binaire est un cas particulier de structure arborescente où chaque position ouvre sur exactement deux branches.
Plus précisément, un arbre binaire est un ensemble fini de nœuds correspondant à l'un des deux cas suivants.
- Soit l'arbre est vide, c'est-à-dire qu'il ne contient aucun nœud.
- Soit l'arbre n'est pas vide, et ses nœuds sont structurés de la façon suivante :
- un nœud est appelé la racine de l'arbre:
- les nœuds restant sont séparés en deux sous-ensembles, qui forment récursivement deux sous-arbres appelés respectivement sous-arbre gauche et sous-arbre droit ;
- la racine est reliée à ses deux sous-arbres gauche et droit, et plus précisément à la racine de chacun de ses sous-arbres (lorsqu'ils ne sont pas vides).
On peut rapprocher la notion de nœud d'un arbre binaire de la notion de cellule d'une liste chaînée.
L'arbre vide est alors similaire à la liste vide qui est noté par le symbole L.
La racine d'un arbre non vide est l'équivalent de la tête d'une liste non vide et les liens vers les deux sous-arbres correspondent à deux chaînages « suivants » menant à deux suites disjointes.
De même que la taille d'une liste était définie comme son nombre de cellules, la faille d'un arbre binaire est ainsi définie comme son nombre de nœuds.
Voici un exemple d'arbre binaire contenant quatre nœuds.
![\"preview\"](\"https://sciencesappliquees.com/images/nsi/arbre2.png\")
La racine de arbre cst représentée en haut — en informatique, les arbres poussent vers le bas.
Ici, le sous-arbre gauche contient deux nœuds et le sous-arbre droit un nœud.
Comme on le voit, chaque nœud est relié à ses deux sous-arbres, et plus précisément à la racine de chaque sous-arbre, le cas échéant.
On a également représenté les liaisons entre les nœuds et leurs sous-arbres vides, le cas échéant. Ainsi, on explicite le fait qu'un nœud possède toujours deux
sous-arbres, même si l'un ou l'autre ou les deux peuvent être vides.
Lorsqu'un nœud à deux sous-arbres vides, c'est-à-dire qu'il est de la forme
![\"preview\"](\"https://sciencesappliquees.com/images/nsi/arbre4.png\")
on parle de feuille, Il est important de ne pas confondre une feuille, qui contient un nœud, et un arbre vide, qui n'en contient pas.
On définit la hauteur d'un arbre comme le plus grand nombre de nœuds rencontrés en descendant de la racine jusqu'à une feuille (ou, de façon équivalente, jusqu'à un arbre vide).
Tous les nœuds le long de cette descente sont comptés, y compris la racine et la feuille.
Ainsi, l'arbre
a une hauteur 3.
De façon équivalente, on peut définir la hauteur récursivement sur la structure de l'arbre de la manière suivante :
- l'arbre vide a pour hauteur 0:
- un arbre non vide a pour hauteur le maximum des hauteurs de ses deux sous-arbres, auquel on ajoute 1.
Si N désigne la taille d'un arbre binaire, c'est-à-dire son nombre de nœuds, et si k désigne sa hauteur, alors ces deux quantités sont contraintes par les inégalités suivantes:
h ≤ N ≤ 2h - 1
L'inégalité de gauche s'interprète facilement comme le fait qu'un arbre de hauteur } possède au moins À nœuds, par définition de la hauteur. L'égalité
est possible lorsque l'arbre est complètement linéaire, avec un seul nœud à chaque profondeur.
Voici trois exemples d'arbres de taille de hauteur 4 :
![\"preview\"](\"https://sciencesappliquees.com/images/arbre5.png\")
Les arbres comme celui de gauche on celui de droite, où le sous-arbre non
vide est systématiquement du même côté, sont appelés des peignes, car leur
forme évoque celle d'un peigne. On note qu'un peigne n'est pas différent, par sa structure, d'une liste chaînée.
De l'autre côté, la limite 2% — 1 sur la taille de l'arbre est atteinte pour
un arbre binaire parfait où toutes les feuilles sont exactement à la même
![\"preview\"](\"https://sciencesappliquees.com/images/arbre6.png\")
est un arbre binaire parfait de hauteur 3 et sa taille est 2? —1=7.
La hauteur est une notion importante. Elle joue notamment un grand
rôle lorsque la complexité des algorithmes dépend directement de la hauteur
des arbres. Le chapitre suivant en donne plusieurs exemples.
Mettre le résultat ici (code et figure).
Comme nous le verrons dans la séquence suivant, l'intérêt des arbres est d'y
stocker de l'information.
Pour cela, on va attacher une ou plusieurs valeurs à chaque nœud. Voici par exemple un arbre où chacun des quatre nœuds
contient une chaîne de caractères :
![\"preview\"](\"https://sciencesappliquees.com/images/arbre7.png\")
Les arbres vides, en revanche, ne contiennent pas d'information.
Dans la pratique, il existe de nombreuses
variantes des arbres binaires que nous venons de présenter.
Ainsi, il arrive que les feuilles contiennent une information d'une nature différente, ou encore que seules les feuilles contiennent une information.
Nous nous en tiendrons à la version la plus simple, qui est celle que nous avons présentée.
Il y a de nombreuses façons de représenter un arbre binaire en Python.
Une manière traditionnelle consiste à représenter chaque nœud par un objet d'une classe, qu'on appellera ici Noeud.
Programme — Nœud d'un arbre binaire
class Noeud:
\"\"\"un noeud d'un arbre binaire\"\"\"
def __init__(self, g, v, d):
self.gauche = g
self.valeur = v
self.droit = d
Comme on le voit, un objet de cette classe contient trois attributs :
- un attribut gauche pour le sous-arbre gauche;
- un attribut valeur pour la valeur contenue dans le nœud;
- et un attribut droit pour le sous-arbre droit.
Par ailleurs, l'arbre vide est représenté par la valeur None.
Pour construire un arbre, il suffit d'appliquer le constructeur de la classe
Noeud autant de fois qu'il y a de nœuds dans l'arbre. Ainsi, arbre
est construit et stocké dans la variable a avec cette instruction :
a = Noeud(Noeud(None, \"B\", Noeud(None, \"C\", None)),
\"A\",
Noeud(None, \"D\", None))
On a ici créé quatre objets de la classe Noeud, qui sont illustrés dans la figure ci-dessous.
La valeur contenue dans la variable a est l'adresse mémoire de l'objet contenant la valeur \"A\", qui constitue la racine de l'arbre.
Ce nœud contient lui-même dans son attribut gauche l'adresse mémoire de l'objet contenant la valeur \"B\" et dans son attribut droit l'adresse mémoire de
l'objet contenant la valeur \"D\", et ainsi de suite.
Certains des attributs gauche ou droit ont une valeur None, lorsque le sous-arbre correspondant est vide.
Dans la séquence suivant, nous expliquerons comment un arbre peut être
encapsulé dans un objet, exactement comme nous l'avons fait pour les listes
![\"preview\"](\"https://sciencesappliquees.com/images/nsi/arbre8.png\")
Représentations alternatives
Exactement comme pour les listes chaînées, d'autres représentations sont possibles.
Plutôt qu'un objet de la classe Noeud, on pourrait utiliser un triplet, et dans ce
cas écrire
a = ((None,\"B\", (None, \"C\",None)) , \"A\", (None, \"D\" ,None))
,un dictionnaire, ou encore un tableau à trois éléments.
Cependant, l'utitisation d'une valeur structurée avec des champs nommés (ici les attributs gauche, valeur et droit) est idiomatique, y compris dans un langage comme Python.
Orientation des arbres
Comme avec les listes doublement chaînées, il est tout à fait envisageable d'avoir un chaînage bidirectionnel dans les arbres, où chaque nœud qui n'est pas la racine est également relié à son
nœud parent.
Pour cela, il suffit d'ajouter un quatrième attribut à la classe Noeud, appelé parent, qui contient None pour un nœud racine et un objet de la classe Noeud sinon.
Homogénéité
Exactement comme les listes chaînées, les les arbres peuvent contenir des valeurs de n'importe quel type et nous recommandons une utilisation homogène des arbres, où les valeurs contenues dans les nœuds d'un même arbre sont toutes du même type.
Mettre le résultat ici (code et figure).
La définition d'arbre binaire étant récursive, il est naturel d'écrire des
opérations sur les arbres binaires sous la forme de fonctions récursives.
L'exemple le plus simple est celui d'une fonction taille qui calcule la taille
d'un arbre.
def taille(a):
\"\"\"Le nombre de noeuds de l'arbre a\"\"\"
On commence par considérer le cas de base où l'arbre a est vide.
Dans ce cas, il convient de renvoyer 0, car il n'y à aucun nœud dans l'arbre.
if a is None:
return 0
Dans le cas contraire, l'arbre contient au moins un nœud (la racine de l'arbre), auquel on va ajouter la taille des sous-arbres gauche et droit, calculées récursivement.
else:
return 1 + taille(a.gauche) + taille(a.droit)
Il est important de noter que les expressions a.gauche et a.droite ne provoqueront pas d'erreur, car l'arbre a n'est pas vide.
Le code complet est le suivant:
Programme — Calcul de la taille et de la hauteur
def taille(a):
\"\"\"le nombre de noeuds de L'arbre a\"\"\"
if a is None:
return 0
else:
return 1 + taille(a.gauche) + taille(a.droit)
Ensuite, nous pouvons créer une fonction qui calcule la hauteur d'un arbre.Sa structure est très similaire à la fonction taille :
def hauteur(a):
\"\"\"la hauteur de l'arbre a\"\"\"
if a is None:
return 0
else:
return 1 + max(hauteur(a.gauche), hauteur(a.droit))
Efficacité. Il est clair que les deux fonctions taille et hauteur ont une
complexité directement proportionnelle au nombre de nœuds de l'arbre.
En effet, ces deux fonctions font un nombre d'opérations borné sur chaque nœud
(addition, maximum) et parcourent une fois et une seule chaque nœud.
Tester avec :
print(\"taille de a\",taille(a))
print(\"hauteur de a\",hauteur(a))
et conclure.
Mettre le résultat ici (code et figure).
Les deux fonctions que nous venons d'écrire, à savoir taille et hauteur, parcourent tous les nœuds de l'arbre.
L'ordre dans lequel ce parcours est
effectué n'est pas important. Que ce soit pour calculer la taille ou la hauteur, peu importe si on commence le calcul par le sous-arbre gauche ou droit.
Écrivons maintenant une autre fonction, qui affiche les valeurs contenues dans tous les nœuds de l'arbre, par exemple une par ligne.
L'ordre dans lequel le parcours des nœuds est effectué devient important. On peut
par exemple parcourir le sous-arbre gauche, puis afficher la valeur de la racine, puis enfin parcourir le sous-arbre droit.
On appelle cela un parcours infixe.
Le programme suivant contient le code d'une fonction parcours_infixe qui imprime les valeurs des nœuds d'un arbre dans un parcours infixe.
Programme — Parcours infixe d'un arbre binaire
def parcours_infixe(a):
\"\"\"affiche les éléments de a dans un parcours infite\"\"\"
if a is None:
return
parcours_infixe(a.gauche)
print (a.valeur)
parcours_infixe(a.droit)
Tester avec :
parcours_infixe(a)
Efficacité. La fonction parcours_infixe a une complexité directement proportionnelle au nombre de nœuds de l'arbre. Comme les fonctions taille et hauteur, elle fait un nombre d'opérations borné sur chaque nœud (ici, l'affichage de la valeur) et parcourt une fois et une seule chaque nœud.
Mettre le résultat ici (code et figure).
D'autres parcours
Le parcours infixe n'est pas la seule façon de parcourir
les nœuds d'un arbre. On pourrait afficher la valeur avant de parcourir les
sous-arbres (on parle alors de parcours préfixe) ou après (on parle alors de
parcours postfixe).
Si on ajoute la possibilité de parcourir le sous-arbre droit avant le sous-arbre gauche, cela fait encore trois autres solutions, même si elles sont peu utilisées en pratique et ne portent du coup pas de nom.
Attention au partage
Rien ne nous empêche de réutiliser plusieurs fois un même sous-arbre dans une construction d'arbre. Ainsi, on peut
écrire le code Python à gauche et obtenir (en mémoire) l'arbre à droite :
f = Noeud(None, 1, None)
r = Noeud( f , 2, f )
Il s'agit là d'un arbre de taille 3, avec un sous-arbre gauche contenant un nœud et un sous-arbre droit contenant également un nœud.
Le fait que ces deux nœuds sont en réalité un même nœud en mémoire n'est
pas observable en première approximation.
En particulier, un appel à taille(r) renvoie la valeur 3, car la fonction taille parcourt d'abord le sous-arbre gauche, puis le sous-arbre droit.
On peut tout à faire réaliser un tel partage intentionnellement, par exemple pour économiser de la mémoire.
Maïs il faut bien avoir conscience que le partage est difficilement compatible avec des modifications de la structure de l'arbre ou des valeurs contenues dans les
nœuds.
Un arbre binaire est un ensemble fini de nœuds, qui est soit vide, soit structuré à partir d'un nœud particulier, appelé la racine de l'arbre, et de deux sous-ensembles de nœuds formant récursivement
un sous-arbre gauche et un sous-arbre droit.
Un arbre peut être matérialisé en Python avec un objet par nœud, d'une classe qui à trois attributs : le sous-arbre gauche, le sous-arbre droit et une valeur stockée
dans le nœud,
La valeur None est utilisée pour représenter l'arbre vide.
Dessiner tous les arbres binaires ayant respectivement 3 et 4 nœuds.
","title":"Exercice"},{"edit":"Mettre le résultat ici (code et figure).
Il y a 5 arbres binaires possédant 3 nœuds :
_1_ _1_ _1_
/ \\ / \\ / \\
_2_ _3_ _2_ _2_
/ \\ / \\ / \\ / \\
_3_ _3_
/ \\ / \\
_1_ _1_
/ \\ / \\ / \\
_2_ _2_
/ \\ / \\
_3_ _3_
/ \\ / \\
Il y a 14 arbres binaires possédant 4 nœuds :
__1__ / \\ _2_ _3_ / \\ / \\ _4_ / \\ | __1__ / \\ _2_ _3_ / \\ / \\ _4_ / \\ | __1__ / \\ _2_ _3_ / \\ / \\ _4_ / \\ |
__1__ / \\ _2_ _3_ / \\ /. \\ _4_ / \\ | __1__ / \\ __2__ / \\ _3_ _4_ /. \\ / \\ | __1__ / \\ __2__ / \\ _3_ /. \\ _4_ /. \\ |
__1__ / \\ __2__ / \\ _3_ /. \\ _4_ / \\ | __1__ / \\ _2_ / \\ _3_ / \\ _4_ / \\ | __1__ / \\ _2_ / \\ _3_ / \\ _4_ / \\ |
| __1__ / \\ __2__ / \\ _3_ _4_ /. \\ / \\ | __1__ / \\ __2__ / \\ _3_ /. \\ _4_ /. \\ | __1__ / \\ __2__ / \\ _3_ /. \\ _4_ /. \\ |
| __1__ / \\ __2__ / \\ _3_ /. \\ _4_ /. \\ | __1__ / \\ __2__ / \\ _3_ /. \\ _4_ / \\ |
Sachant qu'il y à 1 arbre binaire vide, 1 arbre binaire contenant 1 nœud, 2 arbres binaires contenant 2 nœuds, 5 arbres binaires contenant 3
nœuds et 14 arbres binaires contenant 4 nœuds, calculer le nombre d'arbres binaires contenant 5 nœuds.
On ne cherchera pas à les construire tous, mais seulement à les dénombrer.
Mettre le résultat ici (code et figure).
Pour les dénombrer, on considère le nœud à la racine puis on répartit les quatre nœuds restants entre le sous-arbre gauche et le sous-arbre droit.
Par exemple, on peut mettre un nœud dans le sous-arbre gauche et trois dans le sous-arbre droit.
Au total, il y a cinq façons différentes
de répartir les nœuds (0+4, 1+3 , 2+2, 3+1, 4+0).
Pour chacune, on connaît le nombre de sous-arbres possibles, ce qui donne la somme
1x14 + 1x5 + 2x2 + 5x1 + 14x1
soit un total de 42 arbres binaires possédant 5 nœuds.
"}],[{"text":"Écrire une fonction affiche1(a) qui imprime un arbre sous la forme suivante :
- pour un arbre vide, on n'imprime rien;
- pour un nœud, ou sa valeur, son sous-arbre droit (récursivement), puis enfin une parenthèse fermante.
Ainsi, pour l'arbre :
on doit afficher ((B(C))A(D)).
Tester avec :
a1 = Noeud(Noeud(None,\"B\",Noeud(None,\"C\",None)),\"A\",Noeud(None,\"D\",None))
affiche1(a1)
Résultat :
((B(C))A(D))
","title":"Exercice"},{"edit":"Mettre le résultat ici (code et figure).
def affiche1(a):
if a is None:
return
print (\"(\", end=\"\")
affiche1(a.gauche)
print(a.valeur, end=\"\")
affiche1(a.droit)
print(\")\", end=\"\")
Dessiner l'arbre binaire sur lequel la fonction affiche1 de l'exercice précédent produit la sortie :
(1((2)3)).
D'une manière générale, expliquer comment retrouver l'arbre dont l'affichage est donné.
Mettre le résultat ici (code et figure).
Pour la sortie (1((2)3)), l'arbre est le suivant :
__1__
/ \\
_3_
/ \\
_2_
/ \\
D'une manière générale, on distingue deux cas : si l'affichage est vide, l’arbre
est vide; sinon, il y a une paire de parenthèses qui encadre la chaîne toute
entière. On cherche alors la valeur qui est contenue dans cette paire de parenthèses et qui n’est contenue dans aucune autre.
C’est la valeur que l'on place à la racine.
À gauche (resp. droite) de cette valeur, on trouve la sous-chaîne qui nous permet de reconstruire (récursivement) le sous-arbre gauche (resp. droit).
"}],[{"text":"Ajouter à la classe Noeud une méthode __eq__ permettant de tester l'égalité entre deux arbres binaires à l'aide de l'opération ==.
Tester avec :
a = Noeud(None,\"C\",None)
b = Noeud(None,\"B\",None)
c = Noeud(a,\"A\",b)
d = Noeud(a,\"A\",b)
e = Noeud(a,\"A\",a)
print(c==d)
print(c==e)
Résultat :
True
False
","title":"Exercice"},{"edit":"Mettre le résultat ici (code et figure).
Les sous-arbres étant également des nœuds, pour lesquels on est justement en train de définir une méthode __eq_., il suffit de les comparer récursivement avec ==. Il faut en revanche bien vérifier avant cela que n n’est pas l'arbre vide et il ne faut surtout pas le faire avec == car cela provoquerait un appel récursif.
Comme il arrive parfois dans les fonctions récursives, le piège est au niveau du cas de base.
En revanche la vérification pour self est inutile : la méthode n’aurait pas pu être appelée sur un arbre égal à None.
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
Écrire une fonction parfait(h) qui reçoit en argument un entier h supérieur ou égal à zéro et renvoie un arbre binaire parfait de hauteur h.
Tester avec :
a2 = parfait(4)
affiche1(a2)
Résultat :
((((1)2(1))3((1)2(1)))4(((1)2(1))3((1)2(1))))
","title":"Exercice"},{"edit":"Mettre le résultat ici (code et figure).
On procède récursivement :
def parfait(h):
\"\"\"construit un arbre binaire parfait de hauteur h\"\"\"
if h == 0:
return None
return Noeud(parfait(h-1), h, parfait(h-1))
On ne factorise pas l’appel récursif parfait(h-1) pour ne pas introduire de partage.
On a choisi ici de stocker la hauteur comme valeur dans chaque nœud.
"}],[{"text":"Écrire une fonction peigne_gauche(h) qui reçoit en argument un entier h supérieur ou égal à zéro et renvoie un peigne de hauteur h où chaque nœud à un sous-arbre droit qui est vide.
Tester avec :
a3 = peigne_gauche(4)
affiche1(a3)
Résultat :
((((4)3)2)1)
","title":"Exercice"},{"edit":"Mettre le résultat ici (code et figure).
On peut le faire au choix avec une fonction récursive
(comme dans l’exercice précédent) ou avec une boucle. On choisit ici la
seconde solution :
def peigne_gauche(h) :
\"\"\"construit un peigne gauche de hauteur h\"\"\"
a = None
while h > 0:
a = Noeud(a, h, None)
h -= 1
return a
Il est intéressant de noter que les nœuds de l’arbre sont ici construits de bas
en haut. C’est ce qui nous permet notamment de l'écrire facilement avec une
boucle.
Écrire une fonction est_peigne_gauche(a) qui renvoie True si et seulement a est un peigne à gauche.
Tester avec :
a3 = peigne_gauche(4)
print(est_peigne_gauche(a3))
a4 = parfait(4)
print(est_peigne_gauche(a4))
Résultat :
True
False
","title":"Exercice"},{"edit":"Mettre le résultat ici (code et figure).
On l'écrit ici comme une fonction récursive :
def est_peigne_gauche(a):
if a is None:
return True
if not a.droit is None:
return False
return est_peigne_gauche(a.gauche)
Mais on pourrait le faire tout aussi bien avec une boucle (cinq lignes de code
également).
Donner cinq arbres de taille 3, différents, dont les nœuds contiennent les valeurs 1, 2, 3 et pour lesquels la fonction parcours_infixe affiche à chaque fois
1
2
3
dans cet ordre.
","title":"Exercice"},{"edit":"Mettre le résultat ici (code et figure).
On reprend les cinq arbres de l’exercice sur le dessin des arbres et on les étiquette correctement à chaque fois:
_3_ / \\ _2_ / \\ _1_ / \\ | _3_ / \\ _1_ / \\ _2_ / \\ | __2__ / \\ _1_ _3_ / \\ / \\ |
_1_ / \\ _2_ / \\ _3_ / \\ | _1_ / \\ _3_ / \\ _2_ / \\ |