Puis-je utiliser un trie qui a un mot entier sur chaque noeud?

Question

Je veux implémenter un trie pour vérifier la validité des chemins, donc j'aurais un arbre construit qui contiendrait toutes les constructions de chemins possibles en le décomposant par répertoire. Donc, quelque chose comme /guest/friendsList/search irait du nœud racine à son enfant guest, puis l'enfant de l'invité friendsList, puis l'enfant de l'ami de la liste search. Si search est un nœud feuille, alors ma chaîne /guest/friendsList/search sera considérée comme valide.

Est-ce quelque chose pour lequel un trie serait utile. Toutes les implémentations d'essais que j'ai vu traitent des lettres individuelles à chaque nœud, mais peuvent-elles être des chaînes entières à la place? Est-ce que ce type d'implémentation est spécifique à ce type d'implémentation et qu'est-ce que j'essaie de faire juste un arbre de base?

Merci!

Answer 1

Vous pouvez absolument faire cela, bien que j'appelle généralement cela un arbre de répertoire plutôt qu'un trie puisque vous modélisez essentiellement le système de fichiers comme une structure arborescente plutôt que de stocker beaucoup de préfixes de différentes chaînes. En fait, le système d'exploitation a probablement une structure de données similaire sur le disque pour représenter le système de fichiers!

Answer 2

L'arborescence des répertoires peut certainement le faire. Création d'un noeud racine d'abord, puis ajout des entrées de répertoire restantes au noeud racine en tant qu'enfants, et ainsi de suite. Donc, vérifier si un nom de chemin est valide ne fait qu'analyser toute la chaîne et passer par l'arborescence.

Si vous voulez accélérer les choses, vous pouvez utiliser un dictionnaire pour stocker un niveau de nœuds et la recherche d'un nom est linéaire dans un niveau. La recherche d'un nom de chemin dans l'arborescence de répertoires prend donc O (h) et h est la hauteur de l'arborescence. En outre, pour éviter une recherche redondante, le suivi de la hauteur de l'arborescence peut optimiser le temps de recherche; Lorsque la longueur du nom de chemin analysé dépasse la hauteur, nous savons que nous n'avons pas besoin de chercher dans l'arborescence.