Classe TrieNode : insertion et recherche
Construisez un TrieNode avec un dictionnaire children et un indicateur is_end, implémentez insert et exact-search, puis analysez le temps O(m) par opération, où m est la longueur du mot.
Classe TrieNode : insertion et recherche est une leçon DSA Interview Prep gratuite sur CoddyKit. Ceci est la leçon 1 sur 4. Tu peux lire la leçon complète ci-dessous gratuitement — puis la pratiquer en direct dans le navigateur avec un éditeur de code intégré et un tuteur IA 24/7. Elle fait partie du parcours d'apprentissage DSA Interview Prep, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours DSA Interview Prep comprend 4 leçons au total.
Qu’est-ce qu’un Trie ?
Un Trie (arbre de préfixes) est une structure de données en forme d’arbre où chaque nœud représente un caractère. Les mots sont stockés en enchaînant les caractères de la racine à la feuille. La racine représente une chaîne vide. Chaque chemin de la racine vers un nœud is_end = True forme un mot stocké. Les Trie sont idéaux pour les requêtes fondées sur les préfixes, comme autocomplete, la vérification orthographique et le routage IP, pour lesquels ils sont plus performants que les tables de hachage.
Conception de la classe TrieNode
Un TrieNode possède deux champs : children — un dictionnaire associant les caractères aux TrieNodes enfants — et is_end — un booléen indiquant si ce nœud termine un mot stocké. Utiliser un dictionnaire plutôt qu’un tableau fixe de 26 caractères permet de prendre en charge n’importe quel jeu de caractères et économise de la mémoire lorsque le Trie est peu dense. Chaque nœud du Trie représente exactement une position de caractère dans les mots situés en dessous.
class TrieNode:
def __init__(self):
self.children = {} # char -> TrieNode
self.is_end = False # True if a word ends here
class Trie:
def __init__(self):
self.root = TrieNode()
def __repr__(self):
return f'Trie(root with {len(self.root.children)} children)'
t = Trie()
print(t) # Trie(root with 0 children)Opération d’insertion
Pour insérer un mot, parcourez le Trie depuis la racine en créant un nouveau TrieNode pour chaque caractère qui n’existe pas encore dans le dictionnaire children du nœud courant. Après avoir traité tous les caractères, définissez is_end = True sur le dernier nœud. Insérer « pomme » et « pom » crée la chaîne p→o→m→m→e (is_end=True pour « pomme »), le m en position 3 étant également marqué is_end=True pour « pom ».
class TrieNode:
def __init__(self):
self.children = {}
self.is_end = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word):
node = self.root
for char in word:
if char not in node.children:
node.children[char] = TrieNode()
node = node.children[char]
node.is_end = True
t = Trie()
t.insert('apple')
t.insert('app')
print('Inserted apple and app')
print('app is_end:', t.root.children['a'].children['p'].children['p'].is_end)Opération de recherche
Pour rechercher un mot exact, parcourez le Trie en suivant chaque caractère. Si un caractère manque dans le dictionnaire children du nœud courant, renvoyez faux. Si tous les caractères sont trouvés, renvoyez node.is_end — vrai uniquement si un mot se termine exactement ici, et pas seulement si un préfixe y existe. Cette distinction entre « le préfixe existe » et « le mot exact existe » est essentielle et fait souvent l’objet de tests.
class TrieNode:
def __init__(self):
self.children = {}
self.is_end = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word):
node = self.root
for c in word:
if c not in node.children:
node.children[c] = TrieNode()
node = node.children[c]
node.is_end = True
def search(self, word):
node = self.root
for c in word:
if c not in node.children:
return False
node = node.children[c]
return node.is_end # must be a complete word
t = Trie()
t.insert('apple')
print(t.search('apple')) # True
print(t.search('app')) # False (app not inserted)
print(t.search('orange')) # FalseMéthode starts_with (recherche de préfixe)
La méthode starts_with vérifie si un mot inséré possède le préfixe donné. Elle suit le même parcours que search, mais au lieu de vérifier is_end, elle renvoie vrai dès que tous les caractères du préfixe ont été suivis avec succès — ce qui signifie que le chemin du préfixe existe dans le Trie.
class TrieNode:
def __init__(self):
self.children = {}
self.is_end = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word):
node = self.root
for c in word:
if c not in node.children:
node.children[c] = TrieNode()
node = node.children[c]
node.is_end = True
def search(self, word):
node = self.root
for c in word:
if c not in node.children: return False
node = node.children[c]
return node.is_end
def starts_with(self, prefix):
node = self.root
for c in prefix:
if c not in node.children: return False
node = node.children[c]
return True # prefix path exists
t = Trie()
t.insert('apple')
print(t.starts_with('app')) # True
print(t.starts_with('ape')) # False
print(t.search('app')) # False (not inserted)Complexité temporelle et spatiale
Chaque opération du Trie, insert, search ou starts_with, prend un temps O(m), où m est la longueur du mot : nous parcourons au plus m nœuds. Espace : O(taille de l’alphabet × N × M), où N est le nombre de mots et M leur longueur moyenne. En pratique, les préfixes partagés réduisent considérablement l’espace utilisé. Un dictionnaire children fondé sur une table de hachage utilise moins d’espace qu’un tableau fixe de 26 caractères pour les Trie peu denses, au prix d’une surcharge constante légèrement supérieure pour chaque recherche.
Utiliser un tableau plutôt qu’un dictionnaire
Pour les seules lettres minuscules anglaises, utilisez un tableau de taille fixe children = [None] * 26 avec l’indice ord(c) - ord('a'). Cette solution est plus rapide, avec une recherche d’enfant en O(1) contre une table de hachage, et offre une disposition prévisible en mémoire. Utilisez la version avec dictionnaire lorsque le jeu de caractères est vaste ou inconnu, par exemple Unicode, et la version avec tableau pour les problèmes de type concours limités aux lettres minuscules.
class TrieNodeArray:
def __init__(self):
self.children = [None] * 26
self.is_end = False
class TrieArray:
def __init__(self):
self.root = TrieNodeArray()
def insert(self, word):
node = self.root
for c in word:
idx = ord(c) - ord('a')
if node.children[idx] is None:
node.children[idx] = TrieNodeArray()
node = node.children[idx]
node.is_end = True
def search(self, word):
node = self.root
for c in word:
idx = ord(c) - ord('a')
if node.children[idx] is None: return False
node = node.children[idx]
return node.is_end
t = TrieArray()
t.insert('cat')
print(t.search('cat')) # True
print(t.search('car')) # FalseOpération de suppression
La suppression dans un Trie doit gérer trois cas : (1) le mot n’est pas présent — ne rien faire ; (2) le mot est présent, mais constitue le préfixe d’un autre mot — désactiver uniquement is_end ; (3) le mot est présent et n’est le préfixe d’aucun autre — supprimer les nœuds de bas en haut, en s’arrêtant lorsqu’un nœud possède d’autres enfants ou marque la fin d’un autre mot. La suppression est rarement évaluée lors des entretiens, mais il est utile d’en comprendre le principe.
Compter les mots ayant un préfixe
Ajoutez à chaque nœud un champ count, incrémenté à chaque passage lors d’une insertion. Pour compter les mots possédant un préfixe donné, parcourez le Trie jusqu’au nœud qui termine le préfixe, puis renvoyez son compteur. Cela permet d’effectuer des requêtes autocomplete en O(m) sans parcourir tous les enfants — une extension utile pour les systèmes autocomplete réels.
class TrieNodeCount:
def __init__(self):
self.children = {}
self.is_end = False
self.count = 0 # words passing through this node
class TrieCount:
def __init__(self):
self.root = TrieNodeCount()
def insert(self, word):
node = self.root
for c in word:
if c not in node.children:
node.children[c] = TrieNodeCount()
node = node.children[c]
node.count += 1 # increment on each level
node.is_end = True
def count_with_prefix(self, prefix):
node = self.root
for c in prefix:
if c not in node.children: return 0
node = node.children[c]
return node.count
t = TrieCount()
for w in ['apple','app','application','apply']:
t.insert(w)
print(t.count_with_prefix('app')) # 4
print(t.count_with_prefix('appl')) # 3Comparaison entre Trie et table de hachage
Une table de hachage peut effectuer une recherche exacte en temps moyen O(m), mais ne peut pas répondre efficacement aux requêtes de préfixe, car elle doit parcourir toutes les clés. Un Trie répond aux requêtes de préfixe en O(p), où p est la longueur du préfixe, regroupe naturellement les mots partageant des préfixes et n’a pas besoin de hachage. Utilisez un Trie lorsque les requêtes de préfixe, autocomplete ou la vérification orthographique sont fréquentes. Utilisez une table de hachage lorsque seules les recherches exactes sont nécessaires.
Les Trie dans les systèmes réels
Les utilisations réelles des Trie comprennent : autocomplete, comme les suggestions de recherche Google ; les correcteurs orthographiques, pour trouver les mots correspondants les plus proches ; le routage IP, pour la correspondance avec le préfixe le plus long dans les routeurs ; la saisie prédictive T9, pour lever l’ambiguïté entre les caractères ; et les résolveurs DNS, pour la recherche hiérarchique de noms de domaine. Dans chaque cas, le compromis entre O(m) par opération et un espace O(ALPHABET × nœuds) fait du Trie l’outil adapté aux recherches rapides tenant compte des préfixes, à grande échelle.
Vérification rapide
Évaluez votre compréhension des concepts de structures de données et d’algorithmes — préparation aux entretiens de programmation présentés dans cette leçon.
Récapitulatif de la leçon
Dans cette leçon, vous avez appris que : un TrieNode possède un dictionnaire children et un booléen is_end ; insert parcourt les caractères un par un, crée les nœuds nécessaires et définit is_end à la fin ; et search vérifie is_end, tandis que starts_with vérifie seulement si le chemin du préfixe existe. Nous allons ensuite approfondir autocomplete fondée sur les préfixes et la méthode starts_with.
Questions Fréquemment Posées
La leçon « Classe TrieNode : insertion et recherche » est-elle gratuite ?
Oui — le texte complet de « Classe TrieNode : insertion et recherche » est gratuit à lire ici sur le web. Pour la pratiquer de manière interactive (un éditeur de code intégré et un tuteur IA 24/7) et déverrouiller le reste du cours DSA Interview Prep, passe à CoddyKit PRO. Le cours DSA Interview Prep comprend 4 leçons au total.
Qu'est-ce que j'apprendrai dans « Classe TrieNode : insertion et recherche » ?
Construisez un TrieNode avec un dictionnaire children et un indicateur is_end, implémentez insert et exact-search, puis analysez le temps O(m) par opération, où m est la longueur du mot. Tu pratiques DSA Interview Prep avec du code pratique que tu exécutes directement dans le navigateur, et un tuteur IA 24/7 répond à tes questions au fur et à mesure que tu avances dans la leçon.
Dois-je avoir de l'expérience pour commencer DSA Interview Prep ?
Aucune expérience préalable n'est requise. DSA Interview Prep sur CoddyKit est structuré pour les débutants jusqu'aux apprenants avancés, donc tu peux commencer ici ou depuis le début et avancer à ton rythme. Ceci est la leçon 1 sur 4.
Combien de temps prend la leçon « Classe TrieNode : insertion et recherche » ?
La plupart des leçons CoddyKit prennent environ 5–10 minutes. Chacune est courte et interactive, tu progresses régulièrement et tu repiques exactement où tu t'es arrêté sur le web et l'app.
Peux-tu écrire et exécuter du code dans cette leçon DSA Interview Prep ?
Oui. Chaque leçon DSA Interview Prep inclut un éditeur de code intégré, tu écris et exécutes du vrai code directement dans ton navigateur et tu reçois des retours IA instantanés — aucune configuration locale requise.
Toutes les leçons de ce cours
- Classe TrieNode : insertion et recherche
- Recherche de préfixes et Starts-With
- Recherche avec caractères génériques et expressions régulières dans un trie
- Recherche de mots II : trie et retour arrière sur une grille