Overview
Un Trie (arbre de préfixes) est une structure arborescente pour stocker des chaînes où les nœuds partagent des préfixes communs.
Analogy
Comme les suggestions de saisie automatique de ton téléphone — les mots commençant par les mêmes lettres partagent les mêmes nœuds initiaux.
Step-by-step
- Chaque nœud représente un caractère
- Insère un mot lettre par lettre
- Marque le dernier nœud comme fin de mot
- La recherche suit les arêtes des caractères
Visual
Insérer: "chat","chant","chien"
ch
├─a─t (fin)
│ └─n─t (fin)
└─i─e─n (fin)
Common mistakes
- Oublier de marquer la fin de mot
- Supposer des caractères ASCII uniquement (utiliser un dict pour Unicode)
Practice questions
- Implémente un Trie avec insertion et recherche
- Construis une fonction d'autocomplétion
Time
O(L) par opération, L = longueur du mot