Trie Arbre préfixe
Structure de données arborescente où chaque nœud représente un caractère — ce qui ramène la recherche par préfixe à O(longueur du préfixe).
Usages classiques : l'autocomplétion, la correction orthographique, les tables de routage IP (correspondance du plus long préfixe). Variante : l'arbre radix (compressé). Utilisateurs modernes : le routage de nginx, le routage du noyau Linux, de nombreux index de bases de données.