Trie (arbre préfixe)
Dernière mise à jour
Un trie (prononcé « traï »), ou arbre préfixe, stocke un ensemble de chaînes par leurs caractères : chaque arête est étiquetée par un caractère et un chemin depuis la racine épelle un préfixe. Les mots qui partagent un préfixe partagent les mêmes nœuds, si bien que « car », « card » et « care » réutilisent tous le chemin c-a-r. Appuyez sur lecture ci-dessus pour voir les mots insérés un caractère à la fois, ne se ramifiant que là où ils diffèrent.
Comme les recherches parcourent un nœud par caractère, chercher un mot de longueur m prend O(m) quel que soit le nombre de mots contenus dans le trie. Cela rend les tries idéaux pour l'autocomplétion, la correction orthographique et la recherche par préfixe.
Complexité en temps et en espace
| Opération | Complexité | Notes |
|---|---|---|
| Insertion | O(m) | m = longueur du mot |
| Recherche | O(m) | Une étape par caractère |
| Requête de préfixe | O(m) | Parcourir jusqu'au nœud du préfixe |
| Espace | O(total chars) | Les préfixes partagés sont stockés une seule fois |
Étape par étape (insertion)
| Étape | Ce qui se passe |
|---|---|
| 1 | Commencez au nœud racine. |
| 2 | Pour chaque caractère du mot, cherchez une arête enfant correspondante. |
| 3 | Si elle existe, suivez-la (en réutilisant le préfixe partagé). |
| 4 | Sinon, créez un nouveau nœud enfant pour ce caractère. |
| 5 | Après le dernier caractère, marquez ce nœud comme fin de mot. |
Exemple résolu
Insertion de ["car", "card", "care"] dans un trie vide :
| Étape | Structure | Action |
|---|---|---|
Insérer car | root → c → a → r✓ | Aucun enfant correspondant n'existe, donc créez c, a, r et marquez r comme fin de mot. |
Insérer card | root → c → a → r✓ → d✓ | Réutilisez le chemin existant c-a-r, puis créez un nouvel enfant d et marquez-le comme fin de mot. |
Insérer care | root → c → a → r✓ → {d✓, e✓} | Réutilisez c-a-r, ramifiez depuis r avec un nouvel enfant e, et marquez e comme fin de mot. |
Rechercher care | root → c → a → r → e✓ | Parcourez c, a, r, e ; le nœud final est marqué comme fin de mot, donc care est présent. |
Rechercher ca | root → c → a | Le chemin existe mais a n'est pas marqué comme fin de mot, donc ca est un préfixe mais pas un mot stocké. |
Quand utiliser un trie
| Utilisez-le quand | Évitez-le quand |
|---|---|
| Vous avez besoin de requêtes de préfixe ou d'autocomplétion sur un ensemble de chaînes. | Vous n'avez besoin que de recherches de clés entières - une table de hachage est plus rapide et plus légère. |
| De nombreux mots stockés partagent des préfixes communs, donc les nœuds sont réutilisés. | Les clés sont longues et se recoupent rarement, gaspillant un nœud par caractère. |
| Vous voulez que les clés soient renvoyées dans l'ordre via un parcours. | La mémoire est limitée - les pointeurs enfants par nœud ajoutent une surcharge importante. |
| Le coût de recherche doit dépendre de la longueur de la clé, pas de la taille du jeu de données. | L'alphabet est énorme (par ex. tout Unicode) et les enfants sont stockés de façon dense. |
Code de Trie (Prefix Tree)
Une implémentation propre et exécutable de Trie (Prefix Tree) en Python, JavaScript, Java, C++, C. Choisissez un langage, copiez le code ou ouvrez-le préchargé dans le Playground Coddy.
Code de Trie (Prefix Tree) en Python
Python
1class TrieNode:2 def __init__(self):3 self.children = {}4 self.is_word = False5
6
7class Trie:8 def __init__(self):9 self.root = TrieNode()10
11 def insert(self, word):12 node = self.root13 for ch in word:14 node = node.children.setdefault(ch, TrieNode())15 node.is_word = True16
17 def search(self, word):18 node = self._walk(word)19 return node is not None and node.is_word20
21 def starts_with(self, prefix):22 return self._walk(prefix) is not None23
24 def _walk(self, s):25 node = self.root26 for ch in s:27 if ch not in node.children:28 return None29 node = node.children[ch]30 return node31
32
33trie = Trie()34for word in ["car", "card", "care", "dog"]:35 trie.insert(word)36
37print("search(card): ", trie.search("card"))38print("search(ca): ", trie.search("ca"))39print("starts_with(ca): ", trie.starts_with("ca"))40print("starts_with(do): ", trie.starts_with("do"))41print("starts_with(cat): ", trie.starts_with("cat"))Code de Trie (Prefix Tree) en JavaScript
JavaScript
1class TrieNode {2 constructor() {3 this.children = {};4 this.isEnd = false;5 }6}7
8class Trie {9 constructor() {10 this.root = new TrieNode();11 }12
13 insert(word) {14 let node = this.root;15 for (const ch of word) {16 if (!node.children[ch]) node.children[ch] = new TrieNode();17 node = node.children[ch];18 }19 node.isEnd = true;20 }21
22 // Walk the prefix; null when a character is missing23 findNode(prefix) {24 let node = this.root;25 for (const ch of prefix) {26 node = node.children[ch];27 if (!node) return null;28 }29 return node;30 }31
32 search(word) {33 const node = this.findNode(word);34 return node !== null && node.isEnd;35 }36
37 startsWith(prefix) {38 return this.findNode(prefix) !== null;39 }40}41
42const trie = new Trie();43for (const word of ["car", "card", "care", "dog"]) trie.insert(word);44console.log("search(\"card\"):", trie.search("card"));45console.log("search(\"ca\"):", trie.search("ca"));46console.log("startsWith(\"ca\"):", trie.startsWith("ca"));Code de Trie (Prefix Tree) en Java
Java
1public class Main {2 static class Node {3 Node[] children = new Node[26];4 boolean isWord;5 }6
7 static Node root = new Node();8
9 static void insert(String word) {10 Node cur = root;11 for (char c : word.toCharArray()) {12 int i = c - 'a';13 if (cur.children[i] == null) cur.children[i] = new Node();14 cur = cur.children[i];15 }16 cur.isWord = true;17 }18
19 // Follow the path for s; null means no word has this prefix20 static Node walk(String s) {21 Node cur = root;22 for (char c : s.toCharArray()) {23 cur = cur.children[c - 'a'];24 if (cur == null) return null;25 }26 return cur;27 }28
29 static boolean search(String word) {30 Node node = walk(word);31 return node != null && node.isWord;32 }33
34 static boolean startsWith(String prefix) {35 return walk(prefix) != null;36 }37
38 public static void main(String[] args) {39 insert("code");40 insert("coder");41 insert("cool");42 System.out.println("search code: " + search("code"));43 System.out.println("search cod: " + search("cod"));44 System.out.println("startsWith cod: " + startsWith("cod"));45 System.out.println("startsWith cat: " + startsWith("cat"));46 }47}Code de Trie (Prefix Tree) en C++
C++
1#include <iostream>2#include <string>3#include <unordered_map>4
5struct TrieNode {6 std::unordered_map<char, TrieNode*> children;7 bool isEnd = false;8};9
10struct Trie {11 TrieNode* root = new TrieNode();12
13 void insert(const std::string& word) {14 TrieNode* node = root;15 for (char c : word) {16 if (!node->children.count(c)) node->children[c] = new TrieNode();17 node = node->children[c];18 }19 node->isEnd = true;20 }21
22 // Follow the path for s; nullptr if a link is missing23 TrieNode* walk(const std::string& s) const {24 TrieNode* node = root;25 for (char c : s) {26 auto it = node->children.find(c);27 if (it == node->children.end()) return nullptr;28 node = it->second;29 }30 return node;31 }32
33 bool search(const std::string& word) const {34 TrieNode* node = walk(word);35 return node != nullptr && node->isEnd;36 }37
38 bool startsWith(const std::string& prefix) const {39 return walk(prefix) != nullptr;40 }41};42
43int main() {44 Trie trie;45 for (const std::string& word : {"car", "card", "care", "dog"}) {46 trie.insert(word);47 }48 std::cout << std::boolalpha;49 std::cout << "search(card): " << trie.search("card") << "\n";50 std::cout << "search(ca): " << trie.search("ca") << "\n";51 std::cout << "startsWith(ca): " << trie.startsWith("ca") << "\n";52 std::cout << "startsWith(dot): " << trie.startsWith("dot") << "\n";53 return 0;54}Code de Trie (Prefix Tree) en C
C
1#include <stdbool.h>2#include <stdio.h>3#include <stdlib.h>4
5typedef struct TrieNode {6 struct TrieNode* children[26];7 bool isEnd;8} TrieNode;9
10TrieNode* newNode(void) {11 return calloc(1, sizeof(TrieNode)); // zeroed links and isEnd12}13
14void insert(TrieNode* root, const char* word) {15 for (; *word; word++) {16 int i = *word - 'a';17 if (root->children[i] == NULL) root->children[i] = newNode();18 root = root->children[i];19 }20 root->isEnd = true;21}22
23// Follow the path for s; NULL if a link is missing24TrieNode* walk(TrieNode* root, const char* s) {25 for (; *s; s++) {26 root = root->children[*s - 'a'];27 if (root == NULL) return NULL;28 }29 return root;30}31
32bool search(TrieNode* root, const char* word) {33 TrieNode* node = walk(root, word);34 return node != NULL && node->isEnd;35}36
37bool startsWith(TrieNode* root, const char* prefix) {38 return walk(root, prefix) != NULL;39}40
41int main(void) {42 TrieNode* root = newNode();43 const char* words[] = {"car", "card", "care", "dog"};44 for (int i = 0; i < 4; i++) insert(root, words[i]);45 printf("search(card): %s\n", search(root, "card") ? "true" : "false");46 printf("search(ca): %s\n", search(root, "ca") ? "true" : "false");47 printf("startsWith(ca): %s\n", startsWith(root, "ca") ? "true" : "false");48 printf("startsWith(dot): %s\n", startsWith(root, "dot") ? "true" : "false");49 return 0;50}FAQ sur les tries
À quoi sert un trie ?
Les tries alimentent les fonctionnalités basées sur les préfixes : autocomplétion et suggestions de recherche, correcteurs orthographiques, tables de routage IP et recherches dans un dictionnaire. Partout où vous devez répondre rapidement à « un mot stocké commence-t-il par ce préfixe ? », un trie excelle.
Quelle est la complexité temporelle d'un trie ?
L'insertion, la recherche et les requêtes de préfixe s'exécutent toutes en
O(m), où m est la longueur du mot ou du préfixe - indépendamment du nombre de mots stockés. Le compromis est la mémoire : un trie peut utiliser beaucoup d'espace, bien que les préfixes partagés ne soient stockés qu'une seule fois.Quelle est la différence entre un trie et une table de hachage ?
Une table de hachage offre une recherche moyenne en
O(1) de clés entières mais ne peut pas répondre aux requêtes de préfixe. Un trie est légèrement plus lent par recherche mais prend naturellement en charge la recherche par préfixe, le parcours ordonné et l'autocomplétion - la raison pour laquelle il est préféré dans ces cas.Quand devrais-je utiliser un trie plutôt qu'un arbre binaire de recherche ?
Utilisez un trie lorsque vos clés sont des chaînes et que vous avez besoin de recherches par préfixe : il s'exécute en
O(m) par opération sur la longueur de la clé, alors qu'un ABR équilibré coûte O(m log n) car chaque comparaison parcourt la chaîne et il y en a log n. Un ABR est le meilleur choix quand les clés ne sont pas de type chaîne ou quand la surcharge mémoire compte plus que la vitesse des préfixes.Comment gère-t-on la fin d'un mot dans un trie ?
Chaque nœud porte un indicateur de fin de mot qui n'est activé que lorsqu'un mot complet inséré s'y termine. Sans lui, vous ne pourriez pas distinguer un mot stocké d'un simple préfixe - par exemple, après avoir inséré
card, le nœud pour car existe mais ne devrait être signalé comme un mot que si car a aussi été inséré.Les tries économisent-ils toujours de la mémoire en partageant les préfixes ?
Pas toujours. Le partage n'aide que lorsque de nombreuses clés se recoupent ; avec des clés longues et distinctes, un trie peut utiliser bien plus de mémoire qu'un ensemble haché, puisque chaque caractère devient son propre nœud avec des pointeurs enfants. Si l'espace est le souci, un arbre radix compressé fusionne les chaînes à enfant unique pour réduire cette surcharge.
Ressources associées
Plus de visualisations
