Seuls les membres ayant 30 points peuvent parler sur le chat.

Forum Casio - Projets de programmation


Index du Forum » Projets de programmation » [Basic] Arbre de recherche simple
Kikoodx Hors ligne Membre Points: 1850 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 En ligne Administrateur Points: 17180 Défis: 142 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 Membre Points: 1850 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
Lephenixnoir En ligne Administrateur Points: 17180 Défis: 142 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 Membre Points: 1850 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é.
Milang Hors ligne Membre Points: 463 Défis: 2 Message

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


Je crois que c'est mactul qui a posé la question
Lephenixnoir En ligne Administrateur Points: 17180 Défis: 142 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 Membre Points: 1850 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é :/
Youstones Hors ligne Membre Points: 329 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 Hors ligne Modérateur Points: 1020 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)
Un adminsys qui aime les galettes.
Youstones Hors ligne Membre Points: 329 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 En ligne Administrateur Points: 17180 Défis: 142 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: 329 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
Pour coloriser votre code, cliquez ici.
Sinon cliquez sur le bouton ci-dessous.
: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 - 2020 | Il y a 26 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