06 — Le trie (arbre préfixe)

Ce que tu vas apprendre

• Le principe du trie : un arbre où le chemin code le mot
• Insertion et recherche en O(longueur du mot)
• Pourquoi il bat la hashmap pour les recherches par préfixe
• Son coût mémoire et ses usages réels

Prérequis

• 05 — Les arbres équilibrés

Le trie (prononcé « traï », de retrieval) est un arbre conçu pour stocker des chaînes de caractères. Sa particularité : ce n'est pas la valeur d'un nœud qui porte l'information, mais le chemin depuis la racine. Cette idée le rend imbattable pour une opération que la hashmap ne sait pas faire : trouver tous les mots qui partagent un préfixe. C'est la structure derrière l'autocomplétion.

Le principe : le chemin code le mot

Dans un trie, chaque arête est étiquetée par un caractère. Pour stocker un mot, on descend depuis la racine en suivant un caractère par niveau, en créant les nœuds manquants. Un drapeau marque les nœuds qui terminent un mot complet. Les mots qui commencent pareil partagent le même début de chemin.

Trie contenant "chat", "chien", "chien" et "chaud" :

        (racine)
          |
          c
          |
          h
         / \
        a   i
       / \   \
      t   u   e
     (✓)  d   n
         (✓) (✓)

« chat » et « chaud » partagent le chemin c-h-a, puis divergent. Le préfixe commun n'est stocké qu'une fois. C'est la clé de l'efficacité du trie pour les préfixes.

Implémentation

Chaque nœud a une table de ses enfants, indexée par caractère, et un booléen indiquant la fin d'un mot.

typescriptclass NoeudTrie {
  enfants: Map<string, NoeudTrie> = new Map();
  finDeMot = false;
}

class Trie {
  racine = new NoeudTrie();

  inserer(mot: string): void {
    let noeud = this.racine;
    for (const c of mot) {
      if (!noeud.enfants.has(c)) noeud.enfants.set(c, new NoeudTrie());
      noeud = noeud.enfants.get(c)!;
    }
    noeud.finDeMot = true;
  }

  contient(mot: string): boolean {
    const noeud = this.descendre(mot);
    return noeud !== null && noeud.finDeMot;
  }

  // existe-t-il au moins un mot avec ce préfixe ?
  aPrefixe(prefixe: string): boolean {
    return this.descendre(prefixe) !== null;
  }

  private descendre(s: string): NoeudTrie | null {
    let noeud = this.racine;
    for (const c of s) {
      const suivant = noeud.enfants.get(c);
      if (!suivant) return null;
      noeud = suivant;
    }
    return noeud;
  }
}

L'insertion et la recherche descendent d'un niveau par caractère du mot. Le coût est O(L), où L est la longueur du mot, indépendamment du nombre de mots stockés. Un trie contenant un million de mots cherche aussi vite qu'un trie en contenant dix : c'est la longueur du mot qui compte, pas la taille du dictionnaire.

Trie ou hashmap

Pour la simple question « ce mot exact existe-t-il ? », une hashmap répond aussi en O(L) (le temps de hacher la chaîne) et consomme moins de mémoire. Le trie ne gagne pas là.

Le trie gagne sur les préfixes. « Quels mots commencent par algo ? » : avec le trie, on descend jusqu'au nœud algo en O(L), puis on collecte tous les mots du sous-arbre. Avec une hashmap, il faudrait parcourir toutes les clés et tester chacune, en O(nombre de clés × L). Pour l'autocomplétion, où l'on doit trouver les complétions d'un préfixe à chaque frappe, le trie est la bonne structure.

pythondef completions(noeud, prefixe):
    resultats = []
    def explorer(n, mot_courant):
        if n.fin_de_mot:
            resultats.append(mot_courant)
        for c, enfant in n.enfants.items():
            explorer(enfant, mot_courant + c)
    explorer(noeud, prefixe)
    return resultats

Le coût mémoire et les usages

Le défaut du trie est la mémoire. Chaque caractère de chaque mot peut créer un nœud, et chaque nœud porte une table d'enfants. Pour un grand dictionnaire avec peu de préfixes partagés, ça consomme beaucoup. Des variantes existent pour compresser (le trie radix, ou Patricia trie, fusionne les chaînes de nœuds à enfant unique), au prix d'une implémentation plus complexe.

Les usages réels du trie :

• Autocomplétion et suggestions : barres de recherche, complétion d'éditeurs de code.
• Correction orthographique : trouver les mots proches d'une saisie.
• Routage IP : les tables de routage utilisent des tries pour le préfixe le plus long (longest prefix match).
• Filtrage par préfixe : numéros de téléphone, codes, identifiants hiérarchiques.

Le trie est l'exemple d'une structure ultra-spécialisée : inutile pour la plupart du code, irremplaçable quand le problème porte sur des préfixes de chaînes. L'article suivant clôt la série avec une autre structure spécialisée, conçue pour une question précise sur les regroupements : union-find.

Sources

• Fredkin, E. (1960). Trie Memory. Communications of the ACM, 3(9). (Article fondateur, origine du nom)
• Cormen, T. H., et al. (2009). Introduction to Algorithms (3rd ed.), Problème 12-2 (tries). MIT Press.
• Sedgewick, R., & Wayne, K. (2011). Algorithms (4th ed.), Section 5.2 "Tries". Addison-Wesley.
• Morrison, D. R. (1968). PATRICIA — Practical Algorithm to Retrieve Information Coded in Alphanumeric. Journal of the ACM, 15(4). (Trie compressé)