19 - ABR des Pokemons

⏪

⏬

⏩

1 - Collection

2 - Récupération

3 - Recherche

4 - Particularités

5 - POO

6 - FAQ

Nous avons vu que la recherche dans un Arbre Binaire était plus efficace lorsqu'on sait où chercher.

On obtient alors un coût linéaire en fonction de la hauteur, qu'on peut écrire avec la complexité 𝓞(h). Du coup,

Si l'AB est complet, on obtient alors un coût logarithmique sur la taille n de l'Arbre : on peut écrire 𝓞(log₂(n))
Si l'AB est filiforme, on retrouve juste un coût linéaire par rapport à la taille n : on peut écrire 𝓞(n)
Si l'AB est quelconque, on est entre les deux.

Nous allons aujourd'hui utiliser le fichier CSV de 1er sur les pokemons (et faire quelques révisions sur leurs utilisations). Mais plutôt que de placer les enregistrements dans une Collection-tableau comme en 1er, nous allons placer les enregistrements dans une Collection-ABR pour optimiser les recherches.

Image tirée du site https://boutiquepokemon.com

Logiciel nécessaire pour l'activité : -

Prérequis :

Algos : ABR

Evaluation ✎ :

Résumé : Version HTML ou fond blanc ou ou PDF (couleur ou gris)

MODE COURS (cacher les questions)

1 - Collection des pokemons

⇩ ⇧ ⤊

Nous allons récupérer un fichier CSV contenant les données de 800 Pokémons. Pour rappel, il s'agit d'un simple fichier texte :

Un enregistrement (un Pokemon) par ligne : le passage à la ligne est donc le caractére séparateur pour les enregistrements.
Sur chaque enregistrement, les différents attributs sont séparés par une virgule (ou un point-virgule ou n'importe quel caractère précisé)

Si on rajoute les éléments importants en rouge (dont le passage à la ligne ↲ ) :

#,Name,Type 1,Type 2,Total,HP,Attack,Defense,Sp. Atk,Sp. Def,Speed,Generation,Legendary↲
1,Bulbasaur,Grass,Poison,318,45,49,49,65,65,45,1,False↲
2,Ivysaur,Grass,Poison,405,60,62,63,80,80,60,1,False↲
3,Venusaur,Grass,Poison,525,80,82,83,100,100,80,1,False↲

Le but ici n'est pas de refaire l'activité visant à récupérer ces données pour les stocker dans un tableau-collection mais juste d'utiliser les enregistrements pour construire l'ABR.

Au final, vous aurez donc une variable nommée pokemons qui est simple tableau qui contiendra les enregistrements (sous forme de dictionnaires).

Voici le début du contenu du tableau pokemons :


pokemons = [
    {
        '#': '1',
        'Name': 'Bulbasaur',
        'Type 1': 'Grass',
        'Type 2': 'Poison',
        'Total': '318',
        'HP': '45',
        'Attack': '49',
        'Defense': '49',
        'Sp. Atk': '65',
        'Sp. Def': '65',
        'Speed': '45',
        'Generation': '1',
        'Legendary': 'False'
    },
    {'#': '2', 'Name': 'Ivysaur', 'Type 1': 'Grass', 'Type 2': 'Poison', 'Total': '405', 'HP': '60', 'Attack': '62', 'Defense': '63', 'Sp. Atk': '80', 'Sp. Def': '80', 'Speed': '60', 'Generation': '1', 'Legendary': 'False'},
    {'#': '3', 'Name': 'Venusaur', 'Type 1': 'Grass', 'Type 2': 'Poison', 'Total': '525', 'HP': '80', 'Attack': '82', 'Defense': '83', 'Sp. Atk': '100', 'Sp. Def': '100', 'Speed': '80', 'Generation': '1', 'Legendary': 'False'},
    {'#': '3', 'Name': 'VenusaurMega Venusaur', 'Type 1': 'Grass', 'Type 2': 'Poison', 'Total': '625', 'HP': '80', 'Attack': '100', 'Defense': '123', 'Sp. Atk': '122', 'Sp. Def': '120', 'Speed': '80', 'Generation': '1', 'Legendary': 'False'},
    ...
]

01° Comment obtenir l'enregistrement d'indice 0 contenu dans pokemons ? Quel est le type de cet enregistrement ?

Correction ?

...CORRECTION...


>>> pokemons[0]
 {'#': '1', 'Name': 'Bulbasaur', 'Type 1': 'Grass', 'Type 2': 'Poison', 'Total': '318', 'HP': '45', 'Attack': '49', 'Defense': '49', 'Sp. Atk': '65', 'Sp. Def': '65', 'Speed': '45', 'Generation': '1', 'Legendary': 'False'}

02° Quelle est la méthode permettant d'obtenir l'ensemble des clés disponibles sur ce dictionnaire-enregistrement ?

Comment afficher les clés une par une avec un simple print() ?

Correction ?

...CORRECTION...


>>> pokemons[0].keys()
dict_keys(['#', 'Name', 'Type 1', 'Type 2', 'Total', 'HP', 'Attack', 'Defense', 'Sp. Atk', 'Sp. Def', 'Speed', 'Generation', 'Legendary'])
 
>>> for c in pokemons[0].keys(): print(c)
 #
 Name
 Type 1
 Type 2
 Total
 HP
 Attack
 Defense
 Sp. Atk
 Sp. Def
 Speed
 Generation
 Legendary

03° Comment afficher les couples (clé, valeur) (un par un) sur cet enregistrement-dictionnaire ?

Correction ?

...CORRECTION...


>>> for couple in pokemons[0].items(): print(couple)
 ('#', '1')
 ('Name', 'Bulbasaur')
 ('Type 1', 'Grass')
 ('Type 2', 'Poison')
 ('Total', '318')
 ('HP', '45')
 ('Attack', '49')
 ('Defense', '49')
 ('Sp. Atk', '65')
 ('Sp. Def', '65')
 ('Speed', '45')
 ('Generation', '1')
 ('Legendary', 'False')

04° Comment afficher les couples (c, v) (un par un) sous la forme "La clé {c} est associée à la valeur {v}" ?

Correction ?

...CORRECTION...


>>> for (c,v) in pokemons[0].items(): print(f"La clé {c} est associée à la valeur {v}")
 La clé # est associée à la valeur 1
 La clé Name est associée à la valeur Bulbasaur
 La clé Type 1 est associée à la valeur Grass
 La clé Type 2 est associée à la valeur Poison
 La clé Total est associée à la valeur 318
 La clé HP est associée à la valeur 45
 La clé Attack est associée à la valeur 49
 La clé Defense est associée à la valeur 49
 La clé Sp. Atk est associée à la valeur 65
 La clé Sp. Def est associée à la valeur 65
 La clé Speed est associée à la valeur 45
 La clé Generation est associée à la valeur 1
 La clé Legendary est associée à la valeur False

05° Comment obtenir la valeur associée à la clé "Attack" pour l'enregistrement d'indice 0 contenu dans pokemons ?

Correction ?

...CORRECTION...


>>> pokemons[0]["Attack"]
'49'

06° Comment faire la même chose mais en récupérant un entier ?

Correction ?

...CORRECTION...


>>> int(pokemons[0]["Attack"])
49

2 - Récupération des données

⇩ ⇧ ⤊

Nous allons maintenant télécharger directement le fichier CSV et différents modules :

Un module creation_collect permettant de créer la collection sous forme d'un tableau de dictionnaire
Un module abr permettant de gérer les ABR

07° Créer puis lancer ce programme Python en le nommant telechargement.py et en le plaçant dans un nouveau dossier nommé tp_pok.

📁 tp_pok

📄 telechargement.py

import urllib.request
 
urllib.request.urlretrieve('https://gist.githubusercontent.com/armgilles/194bcff35001e7eb53a2a8b441e8b2c6/raw/92200bc0a673d5ce2110aaad4544ed6c4010f687/pokemon.csv', 'mesdonnees.csv')
urllib.request.urlretrieve('https://doc.infoforall.fr/activite/algo/scripts/arbre_a_pokemons/creation_collect.py', 'creation_collect.py')
urllib.request.urlretrieve('https://doc.infoforall.fr/activite/algo/scripts/arbre_a_pokemons/tp_arbre_pokemons.py', 'tp_arbre_pokemons.py')
urllib.request.urlretrieve('https://doc.infoforall.fr/activite/algo/scripts/arbre_a_pokemons/abr.py', 'abr.py')

Vous allez alors normalement obtenir plusieurs nouveaux fichiers dans votre dossier :

📁 tp_pok

📄 telechargement.py

📄 abr.py

📄 creation_collect.py

📄 tp_arbre_pokemons.py

📄 mes_donnees.csv

En cas de problème, téléchargez simplement ces fichiers à la main...

Voici la description des 3 fonctions d'interface qui vont nous être utiles au début :

def nvND(cle, data=None):
    """Renvoie la référence d'un Noeud en y insérant la clé et les datas : nvND(Cle, Data) -> Noeud"""
 
def nvABR(racine, g, d):
    """Renvoie la référence d'un nouvel arbre : nvABR(Noeud, ABR, ABR) -> ABR"""
 
def inserer_noeud_dans_ABR(arbre, nd):
    """Insére le noeud au bon endroit dans l'ABR NON VIDE : inserer_noeud_dans_ABR(ABR, Noeud) -> None"""

La dernière fonction insère le Noeud au bon endroit dans l'ABR en respectant l'algorithme avec TANT QUE vu pour les ABR.

08° Ouvrir dans Thonny le fichier nommé tp_arbre_pokemons.py.

Importer dans Thonny le module nommé binarytree qui va être nécessaire au fonctionnement de notre propre module (Outils, puis Gérer les paquets).

Mettre le programme en mémoire puis lancer les commandes suivantes pour vérifier que la documentation est bien présente :


>>> help(inserer_noeud_dans_ABR)
 
>>> help(nvABR)
 
>>> help(nvND)

Peut-on voir que certains paramètres ont une valeur par défaut ?
Peut-on voir qu'en réalité les objets ABR, Noeud... sont issus du module abr.py ?

Correction ?

...CORRECTION...

Lorsqu'on demande à visualiser quelques explications d'aide, on obtient ceci :


>>> help(inserer_noeud_dans_ABR)
Help on function inserer_noeud_dans_ABR in module abr:
 
inserer_noeud_dans_ABR(arbre, nd)
    Insére le noeud au bon endroit dans l'ABR NON VIDE :
    inserer_noeud_dans_ABR(ABR, Noeud) -> None
 
>>> help(nvND)
Help on function nvND in module abr:
 
nvND(cle, data = None)
    Renvoie la référence d'un Noeud en y insérant la clé et les datas :
    nvND(Cle, Data) -> Noeud
 
>>> help(nvABR)
Help on function nvABR in module abr:
 
nvABR(racine, g, d)
    Renvoie la référence d'un nouvel arbre :
    nvABR(Noeud, ABR, ABR) -> ABR

On voit donc dans les prototypes si un paramètre a une valeur par défaut (exemple nvND(cle, data = None))
On trouve au début de chacune des lignes une indication comme Help on function *** in module abr qui montre clairement qu'on parle d'une fonction inclue dans le module abr.

09° Dessiner sur papier l'arbre créé en utilisant la fonction de test creation_test() suivante du script tp_arbre_pokemons.py :

def creation_test():
    """Renvoie un ABR de test"""
    arbre = nvABR(nvND(20), nvAV(), nvAV())
    inserer_noeud_dans_ABR(arbre, nvND(25))
    inserer_noeud_dans_ABR(arbre, nvND(15))
    inserer_noeud_dans_ABR(arbre, nvND(17))
    inserer_noeud_dans_ABR(arbre, nvND(10))
    return arbre

Vérifier ensuite votre réponse en tapant simplement ceci :


>>> arbre = creation_test()
>>> print(arbre)

Correction ?

...CORRECTION...


>>> arbre = creation_test()
>>> print(arbre)

     ____20
    /      \
  _15       25
 /   \
10    17

10° Rajoutons un noeud dont la clé est 21.

Vérifier qu'il se positionne bien en affichant l'arbre.


>>> inserer_noeud_dans_ABR(arbre, nvND(21))

Correction ?

...CORRECTION...


>>> inserer_noeud_dans_ABR(arbre, nvND(21))
>>> print(arbre)

     ____20___
    /         \
  _15         _25
 /   \       /
10    17    21

Voyons maintenant comment récupérer les données de nos Pokemons avec le module.

11° Nous allons utiliser la fonction creation_cp() présente dans tp_arbre_pokemons.py : elle ouvre le fichier CSV et place les données lues dans une Collection de dictionnaires dont elle renvoie la référence.

22
23
24

def creation_cp():
    """Renvoie une collection-tableau de dictionnaires des pokemons"""
    return creer_collection('mesdonnees.csv')

En regardant les importations présentes au début du fichier tp_arbre_pokemons.py, donner des explications liées à ces questions ::

dans quel module se trouve en réalité la fonction creer_collection()
pourquoi on a le droit de l'utiliser

en notant simplement creer_collection
mais pas nom_du_module.creer_collection

Correction ?

...CORRECTION...

La partie importation est celle-ci :

 1
 2

# Importations
from creation_collect import creer_collection

On voit donc que la fonction est dans le module creation_collect

On peut l'utiliser directement en notant creer_collection car creer_collection est directement derrière import.

12° Utiliser le jeu de commandes suivants pour comprendre de le principe :


>>> collect = creation_cp()
>>> len(collect)
800
 
>>> collect[0]
{'#': '1', 'Name': 'Bulbasaur', 'Type 1': 'Grass', 'Type 2': 'Poison', 'Total': '318', 'HP': '45', 'Attack': '49', 'Defense': '49', 'Sp. Atk': '65', 'Sp. Def': '65', 'Speed': '45', 'Generation': '1', 'Legendary': 'False'}
 
>>> collect[1]
{'#': '2', 'Name': 'Ivysaur', 'Type 1': 'Grass', 'Type 2': 'Poison', 'Total': '405', 'HP': '60', 'Attack': '62', 'Defense': '63', 'Sp. Atk': '80', 'Sp. Def': '80', 'Speed': '60', 'Generation': '1', 'Legendary': 'False'}
 
>>> for indice in range(0,10,1): print(collect[indice]['Name'])
 
 Bulbasaur
 Ivysaur
 Venusaur
 VenusaurMega Venusaur
 Charmander
 Charmeleon
 Charizard
 CharizardMega Charizard X
 CharizardMega Charizard Y
 Squirtle

Correction ?

...CORRECTION...

Nous retrouvons ce que nous avons vu en partie 1.

collection est un tableau qui contient des dictionnaires.

Chaque dictionnaire possède les mêmes clés : on dit que ce sont des enregistrements.

On accède à l'un des attributs d'un enregistrement en donnant simplement le nom de la clé correspondante.

Essayons maintenant de voir ce que fait la fonction creation_apok() (apok pour arbre à Pokemons) du fichier tp_arbre_pokemons.py.

13° Observer les instructions de la fonction apok() et répondre aux questions :

def creation_cp():
    """Renvoie une collection-tableau de dictionnaires des pokemons"""
    return creer_collection('mesdonnees.csv')
 
def creation_apok():
    """Renvoi un arbre contenant des noeuds-pokemons"""
 
    pokemons = creer_collection('mesdonnees.csv')
    attribut = 'Attack'
 
    arbre = nvAV()
 
    for indice in range(len(pokemons)):
        d = pokemons[indice] # d pour data (pour ne pas confondre avec la fonction data)
        c = int(d[attribut])   # c pour cle (pour ne pas confondre avec la fonction cle)
        noeud = nvND(c, d)
 
        if estArbreVide(arbre):
            arbre = nvABR(noeud, nvAV(), nvAV())
        elif indice < 41:
            inserer_noeud_dans_ABR(arbre, noeud)
 
    return arbre

Ligne 30 : quel est l'attribut du dictionnaire choisi pour jouer le rôle de clé dans l'arbre ?
Ligne 32 : quel est le contenu de l'arbre initialement ?
Ligne 34 : la base des pokemons contient 800 pokemons. Quel va être la valeur finale de la variable de boucle indice ?
Ligne 35 : à chaque tour de boucle, la variable d va t-elle contenir un enregistrement ou la valeur de la clé choisie ?
Ligne 36 : à chaque tour de boucle, la variable c va t-elle contenir un string ou un entier ?
Ligne 37 : Quelle est la clé du noeud créé ? Quel est le contenu de l'attribut data associé à ce Noeud ?
Ligne 39 et +

Que fait-on si l'arbre est vide lors du premier tour de boucle ?
Que fait-on si l'arbre n'est pas vide lors des autres tours de boucle ?
Quelle va être la taille de l'arbre à la fin de la boucle POUR ?

Correction ?

...CORRECTION...

Ligne 32 : on crée un Arbre Binaire de Recherche vide.
Ligne 30 : on va prendra la valeur associée à 'Attack' visiblement.
Ligne 34 : 800 donc de 0 à 799.
Ligne 35 : la variable d va contenir l'un des enregistremens puisqu'on note pokemons[indice]
Ligne 36 : on va chercher la valeur associée à la clé "Attack" dans le dictionnaire et on tente de le transformer en entier.
Ligne 37 : la clé du noeud est la valeur de l'attaque du Pokemon et les datas associées sont tout simplement l'enregistrement du Pokemon.
Ligne 39 et +

Si l'arbre est vide, on crée un premier noeud-racine : la clé de la racine est la valeur de l'attaque du Pokemon et les sous-arbres g et d sont vides.
Si l'arbre n'est pas vide et que l'indice de l'enregistrement est compris entre 0 et 40, on rajoute le nouveau à l'ABR en sachant que la Clé du Noeud est également la valeur de l'attaque du nouveau Pokemon.
Au total : on aura des noeuds correspondants aux pokemons n°0 à n°40. La taille de l'arbre est donc 41 puisqu'on aura 41 pokemons stockés.

14° Utilisez le code suivant pour voir le principe de nos enregistrements stockés dans l'arbre à Pokemons (apok):


>>> apok = creation_apok()
>>> print(apok)

Pour réduire la taille de la police de la console de Thonny, il suffit de placer la souris dans la console et d'appuyer sur CTRL et -.

Question : la création directe et brute de l'arbre à partir des Pokemons lus dans le fichier CSV donne-t-il un arbre équilibré (un arbre où la différence de profondeur entre les sous-arbres gauche et droite n'est que de un au maximum) ?

15° Utilisez les instructions suivantes pour répondre aux questions :

quelle est la version 1 ou 2 qui correspond à un utilisateur ne connaissant pas l'implémentation exacte de l'ABR ?
quelle est la version d'utilisation qui correspond à un utilisateur connaissant l'implémentation actuelle et la manipulant directement ?
sous quelle forme l'ABR est-il manifestement implémenté ?
En cas de modification future de l'implémentation, quelle est la version d'utilisation à privilégier ?

Version 1 :


>>> cle(racine(apok))
49
 
>>> data(racine(apok))
{'#': '1', 'Name': 'Bulbasaur', 'Type 1': 'Grass', 'Type 2': 'Poison', 'Total': '318', 'HP': '45', 'Attack': '49', 'Defense': '49', 'Sp. Atk': '65', 'Sp. Def': '65', 'Speed': '45', 'Generation': '1', 'Legendary': 'False'}
 
>>> data(racine(apok))['Name']
'Bulbasaur'
 
>>> g = gauche(apok)
>>> data(racine(g))['Name']
'Squirtle'
 
>>> cle(racine(g))
48
 
>>> d = droite(apok)
>>> data(racine(d))['Name']
'Ivysaur'
 
>>> cle(racine(d))
62

Version 2 :


>>> apok.racine.cle
49
 
>>> apok.racine.data
{'#': '1', 'Name': 'Bulbasaur', 'Type 1': 'Grass', 'Type 2': 'Poison', 'Total': '318', 'HP': '45', 'Attack': '49', 'Defense': '49', 'Sp. Atk': '65', 'Sp. Def': '65', 'Speed': '45', 'Generation': '1', 'Legendary': 'False'}
 
>>> apok.racine.data['Name']
'Bulbasaur'
 
>>> g = apok.gauche
>>> g.racine.data['Name']
'Squirtle'
 
>>> g.racine.cle
48
 
>>> d = apok.droite
>>> d.racine.data['Name']
'Ivysaur'
 
>>> d.racine.cle
62

Correction ?

...CORRECTION...

La version 1 est celle de l'utilisation des fonctions d'interface (ou primitives) : l'utilisateur ne se préoccupe pas de la façon dont l'implémentation a été faite.

La version 2 est celle de l'utilisateur qui sait que l'implémtation est en programmation objet. L'utilisateur connait d'ailleurs le nom des attributs des objets.

La version la plus stable dans le temps est la première : tant que les primitives restent identiques, l'utilisateur ne voit aucune différence.

16° Si on suppose que l'ABR est équilibré, quel est le coût d'une insertion ?

Correction ?

...CORRECTION...

L'insertion d'un Noeud possède un coût linéaire par rapport à la hauteur : 𝓞(h).

Pour un arbre complet ou équilibré, on obtient alors un coût logarithmique sur la taille n de l'Arbre : on peut écrire 𝓞(log₂(n))

3 - Recherche

⇩ ⇧ ⤊

17° Ouvrir le fichier abr.py du module abr.

Implémenter l'algorithme de recherche dans un arbre binaire de recherche en utilisant les fonctions d'interface disponibles. Voici le prototype visé :

recherche(arbre:ABR, cr:Cle) -> Noeud|Vide

Notre fonction devra donc renvoyer la référence d'un Noeud comportant cette clé, ou ne rien renvoyer si aucun noeud ne correspond.

1
2
3

def recherche(arbre, cr):
    """Recherche un noeud portant la bonne clé et renvoie sa référence"""
    return None

Une fois implémentée, tester la fonction puis fournir l'autre implémentation possible. Vous devriez au final avec une implémentation avec un TANT QUE et une implémentation récursive.

Correction ?

...CORRECTION...

Version avec TANT QUE :

def recherche(arbre, cr):
    """Recherche un noeud portant la bonne clé et renvoie sa référence
 
    :: param arbre(ABR)    :: un ABR, vide ou pas
    :: param cr(Cle)       :: un valeur de Clé
    :: return (Noeud|None) :: la référence d'un Noeud portant la Clé ou None si la clé n'est pas présente
 
    """
    while not estArbreVide(arbre):
        if cr == cle(racine(arbre)):
            return racine(arbre)
        elif cr < cle(racine(arbre)):
            arbre = gauche(arbre)
        elif cr > cle(racine(arbre)):
            arbre = droite(arbre)

Version RECURSIVE :

def recherche(arbre, cr):
    """Recherche un noeud portant la bonne clé et renvoie sa référence
 
    :: param arbre(ABR)    :: un ABR, vide ou pas
    :: param cr(Cle)       :: un valeur de Clé
    :: return (Noeud|None) :: la référence d'un Noeud portant la Clé ou None si la clé n'est pas présente
 
    """
    if estArbreVide(arbre):
        return None
    elif cr == cle(racine(arbre)):
        return racine(arbre)
     
    elif cr < cle(racine(arbre)):
        return recherche(gauche(arbre), cr)
    elif cr > cle(racine(arbre)):
        return recherche(droite(arbre), cr)

18° Tester l'absence d'erreur en lançant directement le module abr.py.

Vérifiez ensuite que la fonction fonctionne : relancer le programme tp_arbre_pokemons.py puis lancer ces commandes :


>>> apok = creation_apok()
>>> print(apok)
>>> recherche(apok, 49)
<abr.Noeud object at 0x7f0da76a0e48>
 
>>> reponse = recherche(apok, 102)
>>> data(reponse)['Name']
'Nidoking'

19° Si on suppose que l'ABR est au moins équilibré, quel est le coût d'une recherche ?

Correction ?

...CORRECTION...

La recherche d'un Noeud possède un coût linéaire par rapport à la hauteur : 𝓞(h).

Pour un arbre complet ou équilibré, on obtient alors un coût logarithmique sur la taille n de l'Arbre : on peut écrire 𝓞(log₂(n))

4 - Affichage particulier

⇩ ⇧ ⤊

3 avantages : affichage trié, max et min

Affichage trié :: les noeuds sont 'triés' entre eux. Du coup, on peut les afficher un par un de façon ... triée.

Il suffit de demander l'affichage infixe (la racine au milieu de l'affichage) !

Recherche facile du minimum : pour trouver la plus petite clé disponible, il suffit d'aller le plus à gauche possible (tant que le sous-arbre de destination n'est pas vide).
Recherche facile du maximum : pour trouver la plus grande clé, il suffit d'aller le plus à droite possible (tant que le sous-arbre de destination n'est pas vide).

20° Afficher les attaques des 41 Pokemons stockées pour l'instant en utilisant simplement la fonction parcours_infixe() :


>>> parcours_infixe(apok)
20
25
30
35
45
45
45
47
48
49
52
55
56
57
60
60
60
62
62
63
64
72
75
80
80
81
82
83
84
85
90
90
90
92
100
100
102
103
104
130
150

21° Modifier parcours_infixe() : il faudra afficher également le nom du Pokemon à côté de son score d'attaque.


>>> aap = creation_apok()
>>> parcours_infixe(aap)
 20 pour Metapod
 25 pour Kakuna
 30 pour Caterpie
 35 pour Weedle
 45 pour Butterfree
 45 pour Pidgey
 45 pour Clefairy
 47 pour Nidoran♀
 48 pour Squirtle
 49 pour Bulbasaur
 52 pour Charmander
 55 pour Pikachu
 56 pour Rattata
 57 pour Nidoran♂
 60 pour Pidgeotto
 60 pour Spearow
 60 pour Ekans
 62 pour Ivysaur
 62 pour Nidorina
 63 pour Wartortle
 64 pour Charmeleon
 72 pour Nidorino
 75 pour Sandshrew
 80 pour Pidgeot
 80 pour PidgeotMega Pidgeot
 81 pour Raticate
 82 pour Venusaur
 83 pour Blastoise
 84 pour Charizard
 85 pour Arbok
 90 pour Beedrill
 90 pour Fearow
 90 pour Raichu
 92 pour Nidoqueen
 100 pour VenusaurMega Venusaur
 100 pour Sandslash
 102 pour Nidoking
 103 pour BlastoiseMega Blastoise
 104 pour CharizardMega Charizard Y
 130 pour CharizardMega Charizard X
 150 pour BeedrillMega Beedrill

Correction ?

...CORRECTION...

def parcours_infixe(arbre):
    """Exploration (et affichage) en profondeur en infixe GRD"""
    if not estArbreVide(arbre):
        parcours_infixe(gauche(arbre))
        print(f"{cle(racine(arbre))} pour {data(racine(arbre))['Name']}")
        parcours_infixe(droite(arbre))

22° A droite toute : rajouter dans le programme TP la fonction récursive cle_max() : on transfère la plus grande valeur à chaque appel !

def cle_max(arbre, maximum=None):
    if estArbreVide(arbre):
        return maximum
    else:
        maximum = cle(racine(arbre))
        return cle_max(droite(arbre), maximum)

Utilisation :


>>> apok = creation_apok()
>>> cle_max(apok)
150
 
>>> recherche(apok, 150)
<abr.Noeud object at 0x7fac40696f28>
 
>>> data(recherche(apok, 150))['Name']
'BeedrillMega Beedrill'

23° A gauche toute : créer dans le programme TP la fonction récursive cle_min() : on transfère la plus petite valeur à chaque appel :!

Correction ?

...CORRECTION...

def cle_min(arbre, minimum=None):
    if estArbreVide(arbre):
        return minimum
    else:
        minimum = cle(racine(arbre))
        return cle_min(gauche(arbre), minimum)

24° Libérez les 800 Pokemons : mémoriser la nouvelle version de creation_apok() qui supprime la limitation sur l'indice 41 et qui permet de choisir la clé parmi les descripteurs. Attention, dans cette version, si vous voulez profiter de l'affichage avec print, la clé devra être un entier.

def creation_apok(attribut='Attack', conversion_cle=int,limite=41):
    """Renvoi un arbre contenant des noeuds-pokemons"""
 
    pokemons = creer_collection('mesdonnees.csv')
 
    arbre = nvAV()
 
    for indice in range(len(pokemons)):
        d = pokemons[indice] # d pour data (pour ne pas écraser la fonction data)
        c = conversion_cle(d[attribut])   # c pour cle (pour ne pas écraser la fonction cle)
        noeud = nvND(c, d)
 
        if estArbreVide(arbre):
            arbre = nvABR(noeud, nvAV(), nvAV())
        if indice < limite:
            inserer_noeud_dans_ABR(arbre, noeud)
 
    return arbre

5 - Version POO

⇩ ⇧ ⤊

25° Modifier les fonctions suivante du module abr de façon à ne pas utiliser les fonctions d'interface mais en codant directement en implémentation POO :

inserer_noeud_dans_ABR()
parcours_infixe()

Par exemple, on notera arbre.racine plutôt que de faire un appel à une fonction d'interface comme racine().

Correction parcours_infixe ?

...CORRECTION parcours_infixe...

def parcours_infixe(arbre):
    """Exploration (et affichage) en profondeur en infixe GRD"""
    if not (arbre.racine is None):
        parcours_infixe(arbre.gauche)
        print(f"{arbre.racine.cle} pour {arbre.racine.data['Name']}")
        parcours_infixe(arbre.droite)

Correction inserer_noeud_dans_ABR ?

...CORRECTION inserer_noeud_dans_ABR...

def inserer_noeud_dans_ABR(arbre, nd):
    """Insére le noeud dans l'ABR"""
 
    # Etape 1
    arbre_parent = None
 
    # Etape 2
    while not arbre.racine is None:
        arbre_parent = arbre
        if nd.cle < arbre.racine.cle:
            arbre = arbre.gauche
        else:
            arbre = arbre.droite
 
    # Etape 3
    if nd.cle < arbre_parent.racine.cle:
        inserer_gauche(arbre_parent, ABR(nd, nvAV(), nvAV()))
    else:
        inserer_droite(arbre_parent, ABR(nd, nvAV(), nvAV()))

6 - FAQ

⇩ ⇧ ⤊

Les fonctions d'interface d'un AB (primitives)

Les fonctions liées aux Noeuds :

nvND(cle:Cle, data:Data) -> Noeud : on crée un nouveau noeud et son élément attaché. Ce n'est pas une fonction d'interface de l'arbre mais on a besoin au moins de pouvoir créer un Noeud.
cle(noeud:Noeud) -> Cle : renvoie la clé ou l'étiquette du noeud.
data(noeud:Noeud) -> Data : renvoie les données associées au noeud.

Les fonctions liées à l'ABR lui-même :

nvAV() -> Arbre : on le note ainsi pour dire nouvelArbreVide : on crée un nouvel ARBRE BINAIRE vide.
nvAB(r:Noeud, g:Arbre, d:Arbre) -> Arbre : on crée un nouvel ARBRE BINAIRE dont la racine est r et dont les sous-arbres sont g et d fournis.
estArbreVide(arbre:Arbre) -> bool : True si l'arbre est un arbre vide.
racine(arbre:Arbre) -> Noeud : renvoie le noeud jouant le rôle de la racine pour cet arbre NON VIDE.
gauche(arbre:Arbre) -> Arbre : renvoie le sous-arbre gauche de arbre NON VIDE. On obtient bien un Arbre. Si vous voulez le noeud gauche, il faudra appliquer en plus la fonction racine.
droite(arbre:Arbre) -> Arbre : renvoie le sous-arbre droit de arbre NON VIDE.
inserer_gauche(arbre:Arbre, g:Arbre) -> None : on remplace le sous-arbre gauche de arbre par l'arbre g.
inserer_droite(arbre:Arbre, d:Arbre) -> None : on remplace le sous-arbre droite de arbre par l'arbre d.
recherche(arbre:ABR, cr:Cle) -> Noeud
parent(arbre:Arbre) -> Arbre : renvoie le parent de arbre si il existe.

On peut avoir un résumé ?

On part d'un fichier CSV contenant les données de Pokemons.

On utilise le module pour transformer ces données en collection : un tableau contenant des dictionnaires. Chaque enregistrement de Pokemon est donc stocké sous forme d'un dictionnaire.

Ensuite, on crée un ABR en rajoutant les noeuds un par un.

Chaque noeud possède une Clé dont la valeur est l'attaque du Pokemon et les Données sont le dictionnaire du Pokemon.

Activité publiée le 07 01 2021
Dernière modification : 30 01 2021
Auteur : ows. h.

⏪

⏫

⏩