Aide exercice codage d'arbre binaire de recherche sur python

bast7 -
mamiemando Messages postés 33727 Date d'inscription Statut Modérateur Dernière intervention - 31 janv. 2022 à 14:01

Bonjour, je suis en terminale spé NSI et j'aurais besoin de votre aide pour un exercice qui me permettrais de mieux comprendre le codage d'ABR (arbre binaire de recherche en python)

Voici une des questions proposé dans l'exercice:

On dispose d’un fichier films.csv contenant des informations sur plus de 1000 films. Le délimiteur est
le point-virgule. Chaque ligne de ce fichier contient les 5 informations suivantes :
• l’identifiant du film,
• le titre original du film,
• l’année de sortie du film,
• sa durée en minutes,
• la recette qu’il a générée, exprimée en dollars.
Voici à quoi ressemblent les deux premières lignes de ce fichier :
8193;Napoleon Dynamite;2004;95;46118097
8195;Ronin;1998;122;41610884

a. Reprendre la classe Nœud adaptée aux ABR vue en cours, et apporter les
modifications nécessaires aux attributs et aux méthodes utiles à l’exercice pour :
• qu’elle puisse prendre en charge des clés de type tableau ;
• le tri se fasse sur les identifiants,
• il y ait au moins le constructeur, la méthode est_Vide et la méthode
inserer.
La classe obtenue s’appellera Abr_id. Indiquer par des commentaires les
endroits où se situent les changements que vous avez effectués.

Voici ce qu'on a vu en cours:

class Noeud():
    def __init__(self,val,fg=None,fd=None):
        if val!=None:
            self.val=val
            if fg==None:
                self.fg=Noeud(None)
            else:
                self.fg=fg
            if fd==None:
                self.fd=Noeud(None)
            else:
                self.fd=fd
        else:
            self.val=None

    def est_vide(self):
        return self.val==None

    def insertion(self, cle):
    # Si le noeud est vide, on insère la valeur
        if self.est_vide():
                ## self=Noeud(cle)
            self.val=cle
            self.fg=Noeud(None)
            self.fd=Noeud(None)
        else: #Sinon, on compare la nouvelle clé à celle du noeud
            if cle<self.val:
                if self.fg.est_vide():
                    self.fg=Noeud(cle)
                else: #récursif !
                    self.fg.insertion(cle)
            elif cle>self.val:
                if self.fd.est_vide():
                    self.fd=Noeud(cle)
                else: #récursif !
                    self.fd.insertion(cle)
            #Pas de else : on ne répète pas une valeur déjà présente.

A voir également:

Aide exercice codage d'arbre binaire de recherche sur python
Codage ascii - Guide
Codage binaire - Guide
Recherche automatique des chaînes ne fonctionne pas - Guide
Citizen code python avis - Accueil - Outils
Recherche photo - Guide

1 réponse

Réponse 1 / 1

baladur13 Messages postés 47674 Date d'inscription Statut Modérateur Dernière intervention 13 664

Bonjour,
Nous ne ferons pas votre exercice à votre place.
Merci de décrire précisément votre problème et en postant le code déjà réalisé.

Cliquez ici pour des conseils d'écriture des messages et ici concernant les devoirs scolaires ou PFE.

Pour poster votre code, merci de penser à la coloration syntaxique.

bast7

Oui désolé j'ai complétement oublié de vous mettre tout ce que j'ai fait:

class Noeud():

    def __init__(self,tab,fg=None,fd=None):
        if tab!=None:
            self.tab=tab
            if fg==None:
                self.fg=Noeud(None)
            else:
                self.fg=fg
            if fd==None:
                self.fd=Noeud(None)
            else:
                self.fd=fd
        else:
            self.tab=None

    def est_vide(self):
        return self.tab==None

    def insertion(self, cle):
    # Si le noeud est vide, on insère la valeur
        if self.est_vide():
                ## self=Noeud(cle)
            self.tab=cle
            self.fg=Noeud(None)
            self.fd=Noeud(None)
        else: #Sinon, on compare la nouvelle clé à celle du noeud
            if cle<self.tab:
                if self.fg.est_vide():
                    self.fg=Noeud(cle)
                else: #récursif !
                    self.fg.insertion(cle)
            elif cle>self.tab:
                if self.fd.est_vide():
                    self.fd=Noeud(cle)
                else: #récursif !
                    self.fd.insertion(cle)
            #Pas de else : on ne répète pas une valeur déjà présente.

EDIT : Ajout du LANGAGE dans les balises de code (la coloration syntaxique).
Explications disponibles ici :
https://codes-sources.commentcamarche.net/faq/10686-le-nouveau-codes-sources-comment-ca-marche#balises-code

Merci d'y penser dans tes prochains messages.

mamiemando Messages postés 33727 Date d'inscription Statut Modérateur Dernière intervention 7 868 > bast7

Bonjour,

Quelle est la différence par rapport à ce que tu as fait en cours (voir ton message #1) ?
- Pour le moment, tu as juste renommé
```
val
```
  en
```
tab
```
  , donc python va trier les données par rapport au tableau complet, alors que ton énoncé te demande de ne tenir compte que l'identifiant (en première colonne, d'après ton énoncé). Ça fera probablement ce qu'il faut car quand python compare deux tableaux, il les compare élément par élément jusqu'à les distinguer. Par exemple,
```
[1, 2, 3] < [1, 4, 1]
```
  car
```
2 < 4
```
  . Donc ça marche, mais ça n'est pas exactement ce qui t'est demandé.
- Par ailleurs, ton énoncé te demande d'indiquer clairement les lignes modifiées.
Ensuite, quelle est ta question et qu'est-ce que tu ne comprends pas ?
- Concernant les ABR (arbres binaires de recherche), si un élément de cours t'échappe, tu peux lire cette page wikipedia. L'idée derrière les arbres, c'est d'organiser des éléments (ici, conformément à une relation d'ordre, qui ordonne les feuilles) de sortes qu'à ce que que chaque fois que tu plonges dans l'arbre, tu restreignes le nombre de feuille candidates correspondant à ta recherche.
- Si ton arbre est parfaitement équilibré (ce qui serait le cas dans un arbre rouge noir) la recherche se fait en O(log(n)), c'est à dire que cela coûte au plus log(n) opérations pour trouver un élément parmi un ensemble de taille n.
- Si on utilisait une liste, la recherche se ferait en O(n), ce qui est significativement plus coûteux quand n est grand. Et c'est pourquoi les arbres sont intéressants, ils permettent d'accélérer la recherche et son empreinte énergétique.

Bonne chance

Discussions similaires

recherche à partir de la barre d'adresse

controleur de codage/décodage PCI

Recherche de pairs sur utorrent bloqué

1fichier

Python introuvable

Votre réponse

Discussions similaires