Qu'est-ce qu'un Trie ?

Un trie (prononcé "try", abréviation de retrieval ou recherche) est une structure de données en forme d'arbre conçue pour stocker et rechercher des chaînes de caractères par leurs caractères. Chaque arête de l'arbre est étiquetée avec un seul caractère, et chaque chemin allant de la racine vers un nœud marqué épelle un mot stocké.

Cette structure rend les questions sur les préfixes extrêmement rapides. Vérifier si le trie contient un mot commençant par "car" ne nécessite que trois recherches de caractères à partir de la racine, quel que soit le nombre de milliers de mots stockés. Les tries sont le moteur derrière des fonctionnalités telles que l'autocomplétion, le correcteur orthographique et les tables de routage IP.

Chaque nœud (node) du trie contient deux éléments d'état :

• children : une carte (map) allant d'un caractère au TrieNode suivant.
• isEndOfWord : un indicateur qui est true lorsque le chemin de la racine à ce nœud épelle un mot complet qui a été inséré.

Les cinq opérations principales sur un trie sont :

1. Insert : Ajouter un mot, en créant tous les nœuds manquants en chemin.
2. Search : Vérifier si un mot complet est stocké.
3. StartsWith : Vérifier si un mot stocké possède le préfixe donné.
4. Delete : Supprimer un mot et élaguer les branches mortes.
5. WordCount : Compter combien de mots distincts sont stockés.

Construisons une classe Trie !