Les membres ayant 30 points peuvent parler sur les canaux annonces, projets et hs du chat.

Forum Casio - Projets de programmation


Index du Forum » Projets de programmation » [Basic] Arbre de recherche simple
Kikoodx Hors ligne Labélisateur Points: 2727 Défis: 11 Message

[Basic] Arbre de recherche simple

Posté le 09/01/2020 16:59

Bonjour !
Sur une question de Mactul (désolé Milang), j'ai codé un arbre de recherche en Basic Casio.
Il est très simple, livré avec une table contenant des nombres aléatoires.
Je donnerai plus de détails si nécessaire, le programme est en pièce jointe.
(Je pense que ça ne valait pas le coup de le poster en tant que programme, c'est un très petit programme.)

Fichier joint


Lephenixnoir Hors ligne Administrateur Points: 20809 Défis: 143 Message

Citer : Posté le 09/01/2020 17:00 | #


Ça me rappelle le tuto de structures de données de Louloux. Peux-tu donner plus du détails, genre comment est encodé ton arbre ?
Kikoodx Hors ligne Labélisateur Points: 2727 Défis: 11 Message

Citer : Posté le 09/01/2020 17:09 | #


Oui bien sûr

L'arbre entier est stocké dans une matrice de 256 lignes et 4 colonnes.
Chaque ligne correspond à un élément de l'arbre et contient 4 informations (5 si on compte son identifiant).
(id implicite) valeur, id_parent, id_enfant_gauche, id_enfant_droite
La racine est la première ligne.
Ensuite, le programme est assez classique : le premier nœud à être exploré est la racine (1→I)
l'arbre commence de la racine, regarde si le nombre est égal à sa valeur. Sinon : si inférieur à la valeur, Mat A[I, 3]→I, si supérieur Mat A[I, 4]→I. Répéter jusqu'à ce que le nombre soit trouvé ou que I = 0.

J'espère que j'ai été assez clair
Protip
Ne me remerciez pas


Absent jusqu'à début Novembre.
Lephenixnoir Hors ligne Administrateur Points: 20809 Défis: 143 Message

Citer : Posté le 09/01/2020 17:25 | #


Oui t'inquiète c'est assez clair. Je me doutais un peu que ce serait comme ça aussi donc...

Puisque c'est un arbre de recherche il est certainement équilibré, donc tu pourrais te passer de toutes ces infos et le stocker ligne par ligne. Du coup tu aurais une liste (en fait) avec :

• Id_Parent = Id // 2
• Id_Left = 2Id
• Id_Right = 2Id+1

C'est classique pour les tas.
Kikoodx Hors ligne Labélisateur Points: 2727 Défis: 11 Message

Citer : Posté le 09/01/2020 17:31 | #


Oui je sais que ça pourrait être beaucoup mieux codé, mais j'ai voulu faire un projet simple et lisible (et à l'arrache aussi, c'était juste pour prouver que c'est possible).
L'arbre n'est pas équilibré pour le coup, c'est l'utilisateur qui rentre les nombres à ajouter un par un ("interactif" )
Même niveau vitesse ce n'est pas optimisé.
Protip
Ne me remerciez pas


Absent jusqu'à début Novembre.
Milang Hors ligne Membre Points: 488 Défis: 2 Message

Citer : Posté le 09/01/2020 18:40 | #


Je crois que c'est mactul qui a posé la question
Lephenixnoir Hors ligne Administrateur Points: 20809 Défis: 143 Message

Citer : Posté le 09/01/2020 18:41 | #


Je vois... c'est quand même pas mal

Edit : pour rééquilibrer, il y a les arbres rouge-noir (classique mais casse-pieds) ou les arbres AVL.
Kikoodx Hors ligne Labélisateur Points: 2727 Défis: 11 Message

Citer : Posté le 09/01/2020 18:42 | #


Milang a écrit :
Je crois que c'est mactul qui a posé la question

Mince, je confond tout le temps désolé :/
Protip
Ne me remerciez pas


Absent jusqu'à début Novembre.
Youstones Hors ligne Membre Points: 332 Défis: 0 Message

Citer : Posté le 09/01/2020 20:05 | #


Qu'est ce qu'un arbre de recherche ?
Mon cerveau se répète tous les jours la mythique phrase : "Houston, je crois que nous avons un problème"
Breizh_craft En ligne Modérateur Points: 1103 Défis: 7 Message

Citer : Posté le 09/01/2020 20:09 | #


https://fr.wikipedia.org/wiki/Arbre_de_recherche clique sur les liens qu’on met avant de poser des questions… (le lien que je viens de mettre est dans le post principal)
Breizh.pm – Un adminsys qui aime les galettes.
Youstones Hors ligne Membre Points: 332 Défis: 0 Message

Citer : Posté le 09/01/2020 20:10 | #


Désolé je n'avais pas compris le lien

Ajouté le 09/01/2020 à 20:13 :
Ah oui ça a l'air pas mal comme système, mais dans quel application concrète pourrait-on l'utiliser ?
Mon cerveau se répète tous les jours la mythique phrase : "Houston, je crois que nous avons un problème"
Lephenixnoir Hors ligne Administrateur Points: 20809 Défis: 143 Message

Citer : Posté le 09/01/2020 20:22 | #


Il y a plein d'applications. Par exemple un index de base de données. Ou pour modéliser des ensembles tout simplement ! N'importe quelle situation où tu veux pouvoir tester la présence d'éléments rapidement.
Youstones Hors ligne Membre Points: 332 Défis: 0 Message

Citer : Posté le 09/01/2020 20:22 | #


Ah nice
Mon cerveau se répète tous les jours la mythique phrase : "Houston, je crois que nous avons un problème"

LienAjouter une imageAjouter une vidéoAjouter un lien vers un profilAjouter du codeCiterAjouter un spoiler(texte affichable/masquable par un clic)Ajouter une barre de progressionItaliqueGrasSoulignéAfficher du texte barréCentréJustifiéPlus petitPlus grandPlus de smileys !
Cliquez pour épingler Cliquez pour détacher Cliquez pour fermer
Alignement de l'image: Redimensionnement de l'image (en pixel):
Afficher la liste des membres
:bow: :cool: :good: :love: ^^
:omg: :fusil: :aie: :argh: :mdr:
:boulet2: :thx: :champ: :whistle: :bounce:
valider
 :)  ;)  :D  :p
 :lol:  8)  :(  :@
 0_0  :oops:  :grr:  :E
 :O  :sry:  :mmm:  :waza:
 :'(  :here:  ^^  >:)

Σ π θ ± α β γ δ Δ σ λ
Veuillez donner la réponse en chiffre
Vous devez activer le Javascript dans votre navigateur pour pouvoir valider ce formulaire.

Si vous n'avez pas volontairement désactivé cette fonctionnalité de votre navigateur, il s'agit probablement d'un bug : contactez l'équipe de Planète Casio.

Planète Casio v42 © créé par Neuronix et Muelsaco 2004 - 2021 | Il y a 47 connectés | Nous contacter | Qui sommes-nous ? | Licences et remerciements

Planète Casio est un site communautaire non affilié à Casio. Toute reproduction de Planète Casio, même partielle, est interdite.
Les programmes et autres publications présentes sur Planète Casio restent la propriété de leurs auteurs et peuvent être soumis à des licences ou copyrights.
CASIO est une marque déposée par CASIO Computer Co., Ltd