Posté le 09/01/2020 16:59
Planète Casio v4.3 © créé par Neuronix et Muelsaco 2004 - 2024 | Il y a 61 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
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 ?
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
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.
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
Même niveau vitesse ce n'est pas optimisé.
Citer : Posté le 09/01/2020 18:40 | #
Je crois que c'est mactul qui a posé la question
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.
Citer : Posté le 09/01/2020 18:42 | #
Je crois que c'est mactul qui a posé la question
Mince, je confond tout le temps désolé :/
Citer : Posté le 09/01/2020 20:05 | #
Qu'est ce qu'un arbre de recherche ?
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)
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 ?
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.
Citer : Posté le 09/01/2020 20:22 | #
Ah nice