Trie (albero dei prefissi)
Ultimo aggiornamento
Un trie (si pronuncia "trai"), o albero dei prefissi, memorizza un insieme di stringhe in base ai loro caratteri: ogni arco è etichettato con un carattere e un cammino dalla radice compone un prefisso. Le parole che condividono un prefisso condividono gli stessi nodi, quindi "car", "card" e "care" riusano tutte il cammino c-a-r. Premi Play qui sopra per vedere le parole inserite un carattere alla volta, con una diramazione solo dove differiscono.
Siccome la ricerca attraversa un nodo per carattere, cercare una parola di lunghezza m richiede tempo O(m) indipendentemente da quante parole contenga il trie. Per questo i trie sono ideali per l'autocompletamento, il controllo ortografico e la ricerca per prefisso.
Complessità temporale e spaziale
| Operazione | Complessità | Note |
|---|---|---|
| Inserimento | O(m) | m = lunghezza della parola |
| Ricerca | O(m) | Un passo per carattere |
| Query per prefisso | O(m) | Scendi fino al nodo del prefisso |
| Spazio | O(total chars) | I prefissi condivisi vengono memorizzati una sola volta |
Passo dopo passo (inserimento)
| Passo | Cosa succede |
|---|---|
| 1 | Parti dal nodo radice. |
| 2 | Per ogni carattere della parola, cerca un arco figlio corrispondente. |
| 3 | Se esiste, seguilo (riusando il prefisso condiviso). |
| 4 | Altrimenti, crea un nuovo nodo figlio per quel carattere. |
| 5 | Dopo l'ultimo carattere, segna quel nodo come fine parola. |
Esempio svolto
Inserimento di ["car", "card", "care"] in un trie vuoto:
| Passo | Struttura | Azione |
|---|---|---|
Inserisci car | root → c → a → r✓ | Non esistono figli corrispondenti, quindi crea c, a, r e segna r come fine parola. |
Inserisci card | root → c → a → r✓ → d✓ | Riusa il cammino esistente c-a-r, poi crea un nuovo figlio d e segnalo come fine parola. |
Inserisci care | root → c → a → r✓ → {d✓, e✓} | Riusa c-a-r, crea una diramazione da r con un nuovo figlio e e segna e come fine parola. |
Cerca care | root → c → a → r → e✓ | Percorri c, a, r, e; il nodo finale è segnato come fine parola, quindi care è presente. |
Cerca ca | root → c → a | Il cammino esiste ma a non è segnato come fine parola, quindi ca è un prefisso ma non una parola memorizzata. |
Quando usare un trie
| Usalo quando | Evitalo quando |
|---|---|
| Ti servono query per prefisso o autocompletamento su un insieme di stringhe. | Ti servono solo ricerche per chiave intera: una tabella hash è più veloce e leggera. |
| Molte parole memorizzate condividono prefissi comuni, quindi i nodi vengono riusati. | Le chiavi sono lunghe e raramente si sovrappongono, sprecando un nodo per carattere. |
| Vuoi ottenere le chiavi in ordine tramite una visita. | La memoria è scarsa: i puntatori ai figli di ogni nodo aggiungono un overhead considerevole. |
| Il costo della ricerca deve dipendere dalla lunghezza della chiave, non dalla dimensione dei dati. | L'alfabeto è enorme (per esempio tutto Unicode) e i figli sono memorizzati in modo denso. |
Codice Trie (Prefix Tree)
Un'implementazione di Trie (Prefix Tree) pulita ed eseguibile in Python, JavaScript, Java, C++, C. Scegli un linguaggio, copia il codice o aprilo già caricato nel Playground di Coddy.
Codice Trie (Prefix Tree) in 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"))Codice Trie (Prefix Tree) in 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"));Codice Trie (Prefix Tree) in 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}Codice Trie (Prefix Tree) in 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}Codice Trie (Prefix Tree) in 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}Domande frequenti sul trie
A cosa serve un trie?
I trie alimentano le funzioni basate sui prefissi: autocompletamento e suggerimenti di ricerca, correttori ortografici, tabelle di routing IP e ricerche nei dizionari. Ovunque ti serva rispondere in fretta a "qualche parola memorizzata inizia con questo prefisso?", un trie dà il meglio di sé.
Qual è la complessità di un trie?
Inserimento, ricerca e query per prefisso richiedono tutti tempo
O(m), dove m è la lunghezza della parola o del prefisso, indipendentemente da quante parole siano memorizzate. Il prezzo è la memoria: un trie può occupare molto spazio, anche se i prefissi condivisi vengono memorizzati una sola volta.Che differenza c'è tra un trie e una tabella hash?
Una tabella hash offre una ricerca media in
O(1) sulle chiavi intere ma non sa rispondere alle query per prefisso. Un trie è un po' più lento per singola ricerca ma supporta in modo naturale la ricerca per prefisso, la visita ordinata e l'autocompletamento, ed è per questo che si preferisce in quei casi.Quando usare un trie invece di un albero binario di ricerca?
Usa un trie quando le chiavi sono stringhe e ti servono ricerche per prefisso: costa
O(m) per operazione sulla lunghezza della chiave, mentre un BST bilanciato costa O(m log n) perché ogni confronto scorre la stringa e i confronti sono log n. Un BST è la scelta migliore quando le chiavi non sono stringhe o quando l'overhead di memoria conta più della velocità sui prefissi.Come si gestisce la fine di una parola in un trie?
Ogni nodo ha un flag di fine parola che viene impostato solo quando una parola inserita per intero termina lì. Senza di esso non potresti distinguere una parola memorizzata da un semplice prefisso: per esempio, dopo aver inserito
card, il nodo di car esiste ma va considerato una parola solo se anche car è stato inserito.I trie fanno sempre risparmiare memoria condividendo i prefissi?
Non sempre. La condivisione aiuta solo quando molte chiavi si sovrappongono; con chiavi lunghe e diverse un trie può usare molta più memoria di un set hash, perché ogni carattere diventa un nodo a sé con i suoi puntatori ai figli. Se lo spazio è un problema, un radix tree compresso unisce le catene di nodi con un solo figlio per ridurre quell'overhead.
Risorse correlate
Altre visualizzazioni
