Arbre Trie
Bill
-
kilian Messages postés 8854 Statut Modérateur -
kilian Messages postés 8854 Statut Modérateur -
Bonjour,
Je sollicite votre aide car je souhaiterais obtenir des informations sur le fonctionnement des arbres dits "trie" (le mot vient de l'anglais "retrieval")
J'ai un projet de correcteur orthographique en informatique à réaliser et je pensais initialement le faire grâce à un arbre binaire, mais notre chargé de projet ne le souhaite pas. Il veut absolument que l'on utilise la méthode des arbres "trie".
Quelqu'un pourrait-il me renseigner sur le fonctionnement de ces arbres ?
Merci d'avance pour vos réponses
Bill
Je sollicite votre aide car je souhaiterais obtenir des informations sur le fonctionnement des arbres dits "trie" (le mot vient de l'anglais "retrieval")
J'ai un projet de correcteur orthographique en informatique à réaliser et je pensais initialement le faire grâce à un arbre binaire, mais notre chargé de projet ne le souhaite pas. Il veut absolument que l'on utilise la méthode des arbres "trie".
Quelqu'un pourrait-il me renseigner sur le fonctionnement de ces arbres ?
Merci d'avance pour vos réponses
Bill
A voir également:
- Arbre Trie
- Arbre généalogique famille michelin - Télécharger - Généalogie
- Trie excel - Guide
- Il est trié sur la plateforme de départ signification ✓ - Forum Consommation & Internet
- Trie photo - Guide
- Logiciel arbre généalogique ✓ - Forum Bureautique
1 réponse
Ben il fait probablement référence aux arbres de fouilles:
https://fr.wikipedia.org/wiki/Arbre_de_fouille
Dommage qu'il y ait peu d'explication dessus.
Voilà comment je l'imagine dans votre cas:
Premier noeud: la racine, pas de valeur dedans: nil
Possède 26 enfants: a,b,c.....z
Chacune de ces enfants possède de 0 à 26 enfants:
Par exemple les enfants de a:
aa, ab, ac, ad.....
Mais attention! S'il n'y a pas de mot qui commence par aa, on ne crée pas cet enfant, donc pas de aa, par contre ab oui.
Et voilà, ainsi de suite, par contre il faudra un flag pour chacun de ces noeuds pour savoir si le mot existe ou bien s'il est juste le début d'un autre.
Par exemple "e" aura comme fils "et" qui aura comme fils "eta", qui aura comme fils "etal" et ainsi de suite jusqu'à "etalage".
e et eta auront le flag 0 => n'existe pas, est un début de mot
et, etal et etalage auront le flag 1 => existe.
C'est une vision des choses, je suis peut être à côté de le plaque....
https://fr.wikipedia.org/wiki/Arbre_de_fouille
Dommage qu'il y ait peu d'explication dessus.
Voilà comment je l'imagine dans votre cas:
Premier noeud: la racine, pas de valeur dedans: nil
Possède 26 enfants: a,b,c.....z
Chacune de ces enfants possède de 0 à 26 enfants:
Par exemple les enfants de a:
aa, ab, ac, ad.....
Mais attention! S'il n'y a pas de mot qui commence par aa, on ne crée pas cet enfant, donc pas de aa, par contre ab oui.
Et voilà, ainsi de suite, par contre il faudra un flag pour chacun de ces noeuds pour savoir si le mot existe ou bien s'il est juste le début d'un autre.
Par exemple "e" aura comme fils "et" qui aura comme fils "eta", qui aura comme fils "etal" et ainsi de suite jusqu'à "etalage".
e et eta auront le flag 0 => n'existe pas, est un début de mot
et, etal et etalage auront le flag 1 => existe.
C'est une vision des choses, je suis peut être à côté de le plaque....
Enfin bref du plus petit au plus grand de gauche à droite.
En fait ça ressemble à ça:
https://fr.wikipedia.org/wiki/Arbre_binaire_de_recherche
Sauf que c'est pas binaire...