Arbre binaire de recherche (2 classes)
graph TB;
A((8))-->B((3))
A-->C((10))
B-->D((1))
B-->E((6))
C-->F((9))
C-->G((14))
E-->H((4))
E-->I((7))
On donne une partie de la classe ABR
pour implémenter les Arbres Binaires de Recherche sans doublon : un ensemble fini de nœuds, éventuellement vide, organisés de manière hiérarchique. C'est une arborescence d'éléments comparables.
Un ABR est une structure de nature récursive :
- Soit c'est un ABR vide,
- Soit il possède une valeur et a deux enfants qui sont aussi des ABRs.
Dans ce dernier cas, il existe une contrainte concernant les valeurs présentes dans les sous-arbres gauche et droit, par rapport à la valeur en cours :- Toutes les valeurs présentes dans le sous-arbre gauche sont inférieures à la valeur en cours.
- Toutes les valeurs présentes dans le sous-arbre droit sont supérieures à la valeur en cours.
On considérera ici des ABRs sans doublons : il ne sera pas possible d'y insérer plusieurs fois la même valeur.
Choix d'implémentation⚓︎
Dans cet exercice on choisit d'implémenter les ABR à l'aide de deux classes :
Attributs⚓︎
class ABR:
racine: None|Noeud
class Noeud:
element: Comparable
gauche: ABR
droit: ABR
- L'ABR vide est une instance de la classe
ABR
où l'attribut racine prend la valeurNone
. - Un ABR non vide est une instance de la classe
ABR
avec une instance deNoeud
en racine.
C'est l'instance deNoeud
qui porte la valeur et les enfantgauche
etdroit
:gauche
: le sous-ABR à gaucheelement
: un élément comparable aux autres (des entiers, des chaînes de caractères, ...)droit
: le sous-ABR à droit
Constructeurs⚓︎
-
Les objets
ABR
sont créés vides avecABR()
. -
Les objets
Noeud
sont créés avec une valeur et deux sous-ABR vides:Noeud(ABR(), element, ABR())
.
Contrats & Méthodes⚓︎
-
Les objets
ABR
peuvent être mutés pour ajouter de nouvelles valeurs à la structure. -
Les objets
Noeud
n'ont pas de méthodes implémentées. -
Les objets
ABR
ont, ou devront, implémenter les méthodes suivantes :abr.est_vide() -> bool
, qui indique si l'ABR contient des valeurs ou non.abr.insere(v) -> None
, qui permet d'ajouter la valeurv
à un emplacement approprié dans l'ABR en cours.abr.contient(v) -> bool
, qui permet de savoir si l'ABR en cours contient la valeurv
ou pas.abr.infixe() -> str
, qui renvoie une chaîne de caractères représentant le contenu de l'ABR, traversé en mode infixe.
Conséquences
Ce choix d'implémentation à deux classes permet d'utiliser le cas de base "arbre vide", dans les implémentations récursives.
Il présente cependant un léger désavantage concernant l'impact sur la mémoire, car pour stocker une valeur, il faut systématiquement deux objets (+ tous les arbres vides des feuilles de l'ABR).
Exemples
>>> nombres = ABR()
>>> nombres.est_vide()
True
>>> for x in [3, 7, 9, 1, 9]:
... nombres.insere(x)
>>> nombres.est_vide()
False
>>> nombres.contient(7)
True
>>> nombres.contient(8)
False
>>> nombres.infixe()
'|1|3|7|9|'
>>> panier = ["kiwi", "pomme", "abricot", "mangue", "poire"]
>>> fruits_ranges = ABR()
>>> for fruit in panier:
... fruits_ranges.insere(fruit)
>>> fruits_ranges.contient("pomme")
True
>>> fruits_ranges.contient("cerise")
False
>>> fruits_ranges.infixe()
'|abricot|kiwi|mangue|poire|pomme|'
Implémentation⚓︎
Compléter les méthodes de la classe ABR ci-dessous, en prenant soin de respecter la complexité en temps attendue pour la méthode contient
.
Quelques remarques concernant les tests :
-
Dans les tests, la fonction
insere_abr(lst, abr)
ajoute toutes les valeurs de la listelst
dansabr
, en utilisant sa méthodeabr.insere(element)
, dans l'ordre des valeurs danslst
. -
Durant les tests, le dernier ABR construit est systématiquement affiché dans la zone ci-dessous (il est conseillé de travailler en mode "2 colonnes". Les arbres des tests de performances ne sont pas affichés).
-
Une fois que toutes les méthodes sont implantées et renvoient des réponses correctes, la complexité en temps de la méthode
abr.contient(element)
est testée, pour vérifier qu'elle respecte les spécifications attendues pour un ABR. Ces tests peuvent être relativement long...
Fonctions ou méthodes avec types
Python n'est pas un langage à typage fort, mais il est possible de renseigner les types des données manipulées, à titre informatif.
Ils sont intéressants notamment dans les signatures de fonctions ou de méthodes, pour rappeler succinctement quels sont les types des données attendus en arguments, ainsi que le type de ce que la fonction renvoie.
Les deux signatures suivantes sont strictement équivalentes, la seconde ajoutant les informations de typage :
def compteur(lst):
...
def compteur_avec_type(lst: list[int]) -> dict[int,int] :
...
lst: list[int]
indique que l'argumentlst
est une liste python d'entiers.- La flèche après les parenthèses définissant les arguments,
->
, permet d'indiquer le type des données renvoyées par la fonction. Ici, il s'agit dedict[int,int]
, soit un dictionnaire avec des entiers en clés et en valeurs.
Il peut aussi arriver que l'on trouve des signatures avec None
en type de renvoi :
def mélange_liste(lst: list) -> None:
...
-> None
indique en fait que la fonction ne renvoie rien.
Comme son nom le suggère, cette fonction a à priori pour but de mélanger une liste en place, par mutation. Elle ne comporte donc pas de
return
.
Dernier ABR créé:
Tests de performances
# Tests
(insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)