Algo ABR

Identification

Infoforall

19 - ABR des Pokemons


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

Le coût est alors fonction de la hauteur h l'Arbre Binaire : θ(h). Du coup,

  1. Si l'AB est complet, on obtient alors un coût logarithmique sur la taille de l'Arbre : θ(log2(n))
  2. Si l'AB est filiforme, on retrouve juste un coût linéaire par rapport à la taille : θ(n)
  3. Si l'AB est quelconque, on est entre les deux.

Nous allons aujourd'hui utiliser à nouveau le fichier CSV sur les pokemons. Mais plutôt que de placer les enregistrements dans une Collection-tableau, nous allons placer les enregistrements dans une Collection-ABR.

Arbre de Pokémons
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)

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 (ici 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 ou champs sont séparés par une virgule (ou un point-virgule ou autre)
Si on rajoute les éléments importants en rouge (dont le passage à la ligne (invisible à l'affichage)):

1 2 3 4
#,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 (la 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'index 0 contenus dans pokemons ?

...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° Comment obtenir l'ensemble des clés disponibles sur cet enregistrement ?

Comment afficher une par une les clés ?

...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 un par un les couples (clé, valeur) sur cet enregistrement ?

...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 un par un les couples (c, v) sous la forme "La clé {c} est associée à la valeur {v}" ?

...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'index 0 contenus dans pokemons ?

...CORRECTION...

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

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

...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.py permettant de créer la collection sous forme d'un tableau de dictionnaire
  • Un module abr.py 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.

1 2 3 4 5 6
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 :

1 2 3 4 5 6 7 8
def nvND(cle:Cle, data:Data=None) -> Noeud: '''Renvoie la référence d'un nouveau Noeud ayant cle comme clé et data comme données annexes''' def nvABR(racine:Noeud, g:Arbre=nvAV(), d:Arbre=nvAV()) -> ABR: '''Renvoie la référence d'un nouvel Arbre dont le noeud-racine est racine et les sous-arbre g et d''' def inserer_noeud_dans_ABR(arbre:ABR, nd:Noeud) -> None: '''Insére le noeud dans l'ABR'''

La dernière fonction insère le Noeud en respectant l'algorithme vu pour les ABR.

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

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)
  1. Peut-on voir que certains paramètres ont une valeur par défaut ?
  2. Peut-on voir qu'en réalité les objets ABR, Noeud... sont issus du module abr.py ?

...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: abr.ABR, nd: abr.Noeud) -> None Insére le noeud dans l'ABR >>> help(nvND) Help on function nvND in module abr: nvND(cle: abr.Cle, data: abr.Data = None) -> abr.Noeud Renvoie la référence d'un nouveau Noeud ayant cle comme clé et data comme données annexes >>> help(nvABR) Help on function nvABR in module abr: nvABR(racine: abr.Noeud, g: abr.Arbre = None, d: abr.Arbre = None) -> abr.ABR
  1. On voit donc dans les prototypes si un paramètre a une valeur par défaut (exemple abr.Data = None)
  2. On trouve des indications comme abr.Arbre qui montre clairement qu'on parle d'une Classe inclue dans le module abr.

09° Dessiner sur papier l'arbre créer en utilisant la fonction de test de création suivante :

48 49 50 51 52 53 54 55
def creation_test(): '''Renvoie un ABR de test''' arbre = nvABR(nvND(20)) 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...

>>> 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...

>>> 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 l'une des fonctions pour importer le fichier CSV et placer ces données dans une Collection de dictionnaires.

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

En regardant les importations, expliquer :

  • dans quel module se trouve la fonction creer_collection
  • pourquoi on a le droit de l'utilisation en notant simplement creer_collection et pas nom_du_module.creer_collection
  • ...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 derrière le 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 index in range(0,10,1): print(collect[index]['Name']) Bulbasaur Ivysaur Venusaur VenusaurMega Venusaur Charmander Charmeleon Charizard CharizardMega Charizard X CharizardMega Charizard Y Squirtle

    ...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 dernière fonction : la fonction creation_aap.

    13° Observer le code de la fonction et répondre aux questions :

    25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47
    def creation_cp(): '''Renvoie une collection-tableau de dictionnaires des pokemons''' return creer_collection('mesdonnees.csv') def creation_aap(): '''Renvoi un arbre contenant des noeuds-pokemons''' pokemons = creer_collection('mesdonnees.csv') choix = 'Attack' arbre = nvAV() for index in range(len(pokemons)): d = pokemons[index] # d pour data (pour ne pas écraser la fonction data) c = int(d[choix]) # c pour cle (pour ne pas écraser la fonction cle) noeud = nvND(c, d) if estArbreVide(arbre): arbre = nvABR(noeud) elif index < 41 : inserer_noeud_dans_ABR(arbre, noeud) return arbre
    1. Ligne 33 : quel est l'attribut du dictionnaire choisi pour jouer le rôle de clé dans l'arbre ?
    2. Ligne 35 : quel est le contenu de l'arbre initialement ?
    3. Ligne 37 : la base des pokemons contient 800 pokemons. Quel va être la valeur finale de la variable de boucle index ?
    4. Ligne 38 : à chaque tour de boucle, la variable d va t-elle contenir un enregistrement ou la valeur de la clé choisie ?
    5. Ligne 39 : à chaque tour de boucle, la variable c va t-elle contenir un string ou un entier ?
    6. Ligne 40 : Quelle est la clé du noeud créé ? Quel est le contenu de l'attribut data associé à ce Noeud ?
    7. Ligne 42 et +
      1. Que fait-on si l'arbre est vide lors du premier tour de boucle ?
      2. Que fait-on si l'arbre n'est pas vide lors des autres tours de boucle ?
      3. Quelle va être la taille de l'arbre à la fin de la boucle POUR ?

    ...CORRECTION...

    1. Ligne 35 : on crée un Arbre Binaire de Recherche vide.
    2. Ligne 36 : on va prendra la valeur associée à 'Attack' visiblement.
    3. Ligne 37 : 800 donc de 0 à 799.
    4. Ligne 38 : la variable d va contenir l'un des enregistremens puisqu'on note pokemons[index]
    5. Ligne 39 : on va chercher la valeur associée à la clé "Attack" dans le dictionnaire et on tente de le transformer en entier.
    6. Ligne 40 : la clé du noeud est la valeur de l'attaque du Pokemon et les datas associées sont tout simplement l'enregistrement du Pokemon.
    7. Ligne 42 et +
      1. 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.
      2. Si l'arbre n'est pas vide et que l'index/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.
      3. 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 (aap):

    >>> arbre = creation_aap() >>> print(arbre)
    Arbre de Pokémons avec l'attaque en clé
    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 -.

    15° Utilisez les commandes suivantes pour réopndre aux questions :

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

    Version 1 :

    >>> cle(racine(arbre)) 49 >>> data(racine(arbre)) {'#': '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(arbre))['Name'] 'Bulbasaur' >>> g = gauche(arbre) >>> data(racine(g))['Name'] 'Squirtle' >>> cle(racine(g)) 48 >>> d = droite(arbre) >>> data(racine(d))['Name'] 'Ivysaur' >>> cle(racine(d)) 62

    Version 2 :

    >>> arbre.racine.cle 49 >>> arbre.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'} >>> arbre.racine.data['Name'] 'Bulbasaur' >>> g = arbre.gauche >>> g.racine.data['Name'] 'Squirtle' >>> g.racine.cle 48 >>> d = arbre.droite >>> d.racine.data['Name'] 'Ivysaur' >>> d.racine.cle 62

    ...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 au moins équilibré (voir l'activité précédente), quel est le coût d'une insertion ?

    ...CORRECTION...

    L'insertion d'un Noeud est linéaire par rapport à la hauteur.

    Pour un arbre complet ou un arbre équilibré, le coût est donc en Θ(log2(n)).

    3 - Recherche

    17° Ouvrir le module abr.py. Tenter de retrouver alors un algorithme permettant de rechercher un noeud dans un ABR en utilisant les fonctions d'interface du module.

    1 2 3
    def recherche(arbre:ABR, cr:Cle) -> Noeud: '''Recherche un noeud portant la bonne clé et renvoie sa référence''' return None

    Une fois l'algorithme retrouvé, tentez de l'implémenter en utilisant les fonctions d'interface.

    ...CORRECTION...

    Algorithme de recherche dans un ABR : version itérative

    Dans un Arbre Binaire de Recherche, la recherche d'une Clé cr est ciblée : inutile de faire une recherche linéaire en profondeur ou en largeur. Il suffit de comparer la valeur de la clé cr cherchée et la valeur de la clé c du noeud actuel pour savoir où aller ensuite.

    1. Si l'arbre actuel est un arbre vide, on renvoie une réponse VIDE.
    2. Si c'est la bonne clé (cr == c), on a trouvé.
    3. Si la clé cherchée est plus petite que la clé du noeud (cr < c): on va à gauche.
    4. Si la clé cherchée est plus grande que la clé du noeud (cr > c): on va à droite.

    Algorithme de recherche

    ENTREE 1 : un Arbre Binaire de Recherche arbre

    ENTREE 2 : une Clé cr

    SORTIE : la référence d'un Noeud portant cette clé

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

      TANT QUE NON estArbreVide(arbre)

        SI cr == cle(racine(arbre))

          Renvoyer racine(arbre)

        SINON SI cr < cle(racine(arbre))

          arbregauche(arbre)

        SINON SI cr > cle(racine(arbre))

          arbredroite(arbre)

        Fin SI

      Fin Tant Que

      Renvoyer VIDE

    Traduit en python avec les fonctions d'interface existantes, ca donne :

    1 2 3 4 5 6 7 8 9
    def recherche(arbre:ABR, cr:Cle) -> Noeud: '''Recherche un noeud portant la bonne clé et renvoie sa référence''' 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)

    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 :

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

    19° Si on suppose que l'ABR est au moins équilibré (voir l'activité précédente), quel est le coût d'une recherche ?

    ...CORRECTION...

    La recherche d'un Noeud est linéaire par rapport à la hauteur.

    Pour un arbre complet ou un arbre équilibré, le coût est donc en Θ(log2(n)).

    4 - Affichage particulier

    Affichage trié, max et min

    Premier avantage des ABR : 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) !

    Deuxième avantage : pour trouver la plus petite clé disponible, il suffit d'aller à gauche tant que le sous-arbre n'est pas vide.

    Troisième avantage : pour trouver la plus grande clé, il suffit d'aller à droite tant que le sous-arbre n'est pas vide.

    20° Afficher les attaques de 41 Pokemons stockées en utilisant simplement ceci :

    >>> parcours_infixe(arbre) 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
    Arbre de Pokémons avec l'attaque en clé

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

    >>> aap = creation_aap() >>> 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...

    1 2 3 4 5 6
    def parcours_infixe(arbre:Arbre) -> None: '''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 !

    1 2 3 4 5 6
    def cle_max(arbre, maximum=None): if estArbreVide(arbre): return maximum else: maximum = cle(racine(arbre)) return cle_max(droite(arbre), maximum)

    Utilisation :

    >>> aap = creation_aap() >>> cle_max(aap) 150 >>> recherche(aap, 150) <abr.Noeud object at 0x7fac40696f28> >>> data(recherche(aap, 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...

    1 2 3 4 5 6
    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_aap qui supprime la limitation sur l'index 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.

    1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
    def creation_aap(choix='Attack', limite=41): '''Renvoi un arbre contenant des noeuds-pokemons''' pokemons = creer_collection('mesdonnees.csv') arbre = nvAV() for index in range(len(pokemons)): d = pokemons[index] # d pour data (pour ne pas écraser la fonction data) c = int(d[choix]) # c pour cle (pour ne pas écraser la fonction cle) noeud = nvND(c, d) if estArbreVide(arbre): arbre = nvABR(noeud) if index < 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 :

    1. inserer_noeud_dans_ABR
    2. parcours_infixe

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

    ...CORRECTION parcours_infixe...

    1 2 3 4 5 6
    def parcours_infixe(arbre:Arbre) -> None: '''Exploration (et affichage) en profondeur en infixe GRD''' if not arbre == None: parcours_infixe(arbre.gauche) print(f"{arbre.racine.cle} pour {arbre.racine.data['Name']}") parcours_infixe(arbre.droite)

    ...CORRECTION inserer_noeud_dans_ABR...

    1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
    def inserer_noeud_dans_ABR(arbre:ABR, nd:Noeud) -> None: '''Insére le noeud dans l'ABR''' # Etape 1 arbre_parent = None # Etape 2 while not arbre == 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)) else: inserer_droite(arbre_parent, ABR(nd))

    6 - FAQ

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

    Les fonctions liées aux Noeuds :

    1. 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.
    2. cle(noeud:Noeud) -> Cle : renvoie la clé ou l'étiquette du noeud.
    3. data(noeud:Noeud) -> Data : renvoie les données associées au noeud.

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

    1. nvAV() -> Arbre : on le note ainsi pour dire nouvelArbreVide : on crée un nouvel ARBRE BINAIRE vide.
    2. 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.
    3. estArbreVide(arbre:Arbre) -> bool : True si l'arbre est un arbre vide.
    4. racine(arbre:Arbre) -> Noeud : renvoie le noeud jouant le rôle de la racine pour cet arbre.
    5. gauche(arbre:Arbre) -> Arbre : renvoie le sous-arbre gauche de arbre. On obtient bien un Arbre. Si vous voulez le noeud gauche, il faudra appliquer en plus la fonction racine.
    6. droite(arbre:Arbre) -> Arbre : renvoie le sous-arbre droit de arbre.

    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.

    Cette fois, c'est fini (pour cette année) : plus rien d'autres sur les Arbres, AB ou ABR.

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