Dans le cours général sur les arbres, nous avons vu deux mesures : la taille et la hauteur. Avant d'aller plus loin, retournez vérifier que vous êtes bien au point
sur ces deux notions.
Taille d'un arbre
D'un point de vue algorithmique, pour connaître la taille d'un arbre, il suffit de parcourir tout ses nœuds et de les compter...
Mais il serait dommage de ne pas profiter de la structure récursive de l'arbre binaire :
La taille d'un arbre binaire c'est :
La taille de son arbre gauche
+
La taille de son arbre droit
+
1 (et oui il ne faut pas oublier la racine...
Version non POO
L'algorithme précédent est directement transposable à l'écriture d'une fonction récursive calculant la taille d'un arbre passé en paramètre :
cas général : taille arbre = 1 + taille(fils gauche de l'arbre) + taille(fils droit de l'arbre)
cas de base : quand l'arbre est None, la récursion s'arrête ( cf.figure ci-contre ), on renvoie 0
Un arbre égal à None, qu'ils ne faut bien entendu pas compter comme nœud ( d'où le 0 renvoyé lors du cas de base ), déclenche l'arrêt de la
récursion lors du comptage des nœuds de l'arbre.
A vous de coder et tester cette fonction en l'appliquant par exemple à un arbre binaire de recherche.
Utiliser le code ci dessous pour générer un ABRaléatoire contenant les 20 premiers entiers.
Penser au préalable à importer le module Matplotlib et la classe classe_arbre dans l'éditeur.
from random import shuffle
from classe_arbre import *
class ABR(Arbre):
def inserer (self, v):
if self.valeur is None:
return ABR(v, None, None)
elif (v < self.valeur):
if self.filsgauche is None:
return ABR(self.valeur, ABR(v, None, None), self.filsdroit)
else:
return ABR(self.valeur, self.filsgauche.inserer(v), self.filsdroit)
elif (v > self.valeur):
if self.filsdroit is None:
return ABR(self.valeur, self.filsgauche, ABR(v, None, None))
else:
return ABR(self.valeur, self.filsgauche,self.filsdroit.inserer(v))
def taille(arbre: ABR)->int:
"""Renvoie le nombre de nœuds présents dans un ABR"""
pass
Il serait assez logique que le calcul de la taille d'un arbre soit plutôt une méthode de la classe ABR ( voire même de la classe Arbre )
A vous de rajouter ci-dessous à la classe ABR une méthode taille calculant la taille d'un ABR
.
Implémenter directement l'algorithme ci-dessus. Que constate-t-on ? Pourquoi ?
Proposer une solution pour régler ce problème...
from random import shuffle
from classe_arbre import *
class ABR(Arbre):
def inserer (self, v):
if self.valeur is None:
return ABR(v, None, None)
elif (v < self.valeur):
if self.filsgauche is None:
return ABR(self.valeur, ABR(v, None, None), self.filsdroit)
else:
return ABR(self.valeur, self.filsgauche.inserer(v), self.filsdroit)
elif (v > self.valeur):
if self.filsdroit is None:
return ABR(self.valeur, self.filsgauche, ABR(v, None, None))
else:
return ABR(self.valeur, self.filsgauche,self.filsdroit.inserer(v))
def taille(self):
"""Renvoie le nombre de nœuds présents dans l'ABR"""
pass
Nous considérerons pour ce calcul que la hauteur des la racine des arbres est à une hauteur de 0.
D'un point de vue algorithmique, pour connaître la hauteur d'un arbre, on est assez proche du problème précédent.
Il ne faut cependant pas additionner la hauteur du sous arbre gauche et du sous arbre droit, mais choisir le maximum parmi ces deux hauteurs.
La hauteur d'un arbre binaire c'est :
Le maximum, déterminé récursivement, entre :
La hauteur de son arbre gauche
La hauteur de son arbre droit
+1 ( et oui il ne faut pas oublier le lien entre la racine et ses sous arbres )
Version non POO
A vous de coder et tester une fonction hauteur, et de l'appliquer à un arbre binaire de recherche aléatoire. Attention au cas de base de la récursion !
L'ABR aléatoire aura toujours la même taille, mais pas la même hauteur ( pourquoi ? ); utiliser alors la méthode dessine pour vérifier le bon fonctionnement de votre
fonction !
On rappelle l'existence de la fonction Python max(a, b) qui renvoie le maximum entre les valeurs a et b.
from random import shuffle
from classe_arbre import *
class ABR(Arbre):
def inserer (self, v):
if self.valeur is None:
return ABR(v, None, None)
elif (v < self.valeur):
if self.filsgauche is None:
return ABR(self.valeur, ABR(v, None, None), self.filsdroit)
else:
return ABR(self.valeur, self.filsgauche.inserer(v), self.filsdroit)
elif (v > self.valeur):
if self.filsdroit is None:
return ABR(self.valeur, self.filsgauche, ABR(v, None, None))
else:
return ABR(self.valeur, self.filsgauche,self.filsdroit.inserer(v))
def hauteur(arbre: ABR)->int:
"""Renvoie la hauteur d'un ABR"""
pass
A vous de rajouter à la classe ABR une méthode hauteur calculant la hauteur de l'ABR; tester la méthode en l'appelant sur un ABR aléatoire de 20 nœuds.
from random import shuffle
from classe_arbre import *
class ABR(Arbre):
def inserer (self, v):
if self.valeur is None:
return ABR(v, None, None)
elif (v < self.valeur):
if self.filsgauche is None:
return ABR(self.valeur, ABR(v, None, None), self.filsdroit)
else:
return ABR(self.valeur, self.filsgauche.inserer(v), self.filsdroit)
elif (v > self.valeur):
if self.filsdroit is None:
return ABR(self.valeur, self.filsgauche, ABR(v, None, None))
else:
return ABR(self.valeur, self.filsgauche,self.filsdroit.inserer(v))
def hauteur(self):
"""Renvoie la hauteur d'un ABR"""
pass
Vous allez pouvoir tester un peu la fiabilité et la complexité expérimentale de ces fonctions récursives dans le cas du traitement des mesures des arbres.
Avec Pyzo :
Générez des arbres contenant les 100, 1000, 10 000 et 100 000 premiers entiers (n'essayez pas de les afficher...bien sur).
Mesurez la taille et la hauteur de ces arbres, et mesurez la durée d'exécution de ces mesures grâce au module timeit que vous avez déjà croisé ici
Conclure sur la complexité déterminée expérimentalement.
