Trie (árvore de prefixos)
Última atualização
Um trie (pronuncia-se "trai"), ou árvore de prefixos, armazena um conjunto de strings por seus caracteres: cada aresta é rotulada com um caractere e um caminho a partir da raiz soletra um prefixo. Palavras que compartilham um prefixo compartilham os mesmos nós, então "car", "card" e "care" reutilizam todas o caminho c-a-r. Pressione reproduzir acima para ver as palavras sendo inseridas um caractere por vez, ramificando apenas onde diferem.
Como as buscas percorrem um nó por caractere, procurar uma palavra de comprimento m leva O(m) independentemente de quantas palavras o trie contém. Isso torna os tries ideais para autocompletar, verificação ortográfica e busca por prefixos.
Complexidade de tempo e espaço
| Operação | Complexidade | Notas |
|---|---|---|
| Inserir | O(m) | m = comprimento da palavra |
| Buscar | O(m) | Um passo por caractere |
| Consulta de prefixo | O(m) | Percorrer até o nó do prefixo |
| Espaço | O(total chars) | Prefixos compartilhados armazenados uma só vez |
Passo a passo (inserção)
| Passo | O que acontece |
|---|---|
| 1 | Comece no nó raiz. |
| 2 | Para cada caractere da palavra, procure uma aresta filha correspondente. |
| 3 | Se existir, siga-a (reutilizando o prefixo compartilhado). |
| 4 | Se não, crie um novo nó filho para esse caractere. |
| 5 | Após o último caractere, marque esse nó como fim de palavra. |
Exemplo resolvido
Inserindo ["car", "card", "care"] em um trie vazio:
| Passo | Estrutura | Ação |
|---|---|---|
Inserir car | root → c → a → r✓ | Não existem filhos correspondentes, então crie c, a, r e marque r como fim de palavra. |
Inserir card | root → c → a → r✓ → d✓ | Reutilize o caminho existente c-a-r, depois crie um novo filho d e marque-o como fim de palavra. |
Inserir care | root → c → a → r✓ → {d✓, e✓} | Reutilize c-a-r, ramifique a partir de r com um novo filho e e marque e como fim de palavra. |
Buscar care | root → c → a → r → e✓ | Percorra c, a, r, e; o nó final está marcado como fim de palavra, então care está presente. |
Buscar ca | root → c → a | O caminho existe, mas a não está marcado como fim de palavra, então ca é um prefixo, mas não uma palavra armazenada. |
Quando usar um trie
| Use quando | Evite quando |
|---|---|
| Você precisa de consultas por prefixo ou autocompletar sobre um conjunto de strings. | Você só precisa de buscas de chaves completas - uma tabela hash é mais rápida e leve. |
| Muitas palavras armazenadas compartilham prefixos comuns, então os nós são reutilizados. | As chaves são longas e raramente se sobrepõem, desperdiçando um nó por caractere. |
| Você quer que as chaves sejam retornadas em ordem por meio de um percurso. | A memória é escassa - os ponteiros para filhos por nó adicionam uma sobrecarga significativa. |
| O custo de busca deve depender do comprimento da chave, não do tamanho do conjunto de dados. | O alfabeto é enorme (por exemplo, todo o Unicode) e os filhos são armazenados de forma densa. |
Código de Trie (Prefix Tree)
Uma implementação limpa e executável de Trie (Prefix Tree) em Python, JavaScript, Java, C++, C. Escolha uma linguagem, copie o código ou abra-o já carregado no Playground da Coddy.
Código de Trie (Prefix Tree) em 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"))Código de Trie (Prefix Tree) em 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"));Código de Trie (Prefix Tree) em 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}Código de Trie (Prefix Tree) em 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}Código de Trie (Prefix Tree) em 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}Perguntas frequentes sobre tries
Para que serve um trie?
Tries impulsionam recursos baseados em prefixos: autocompletar e sugestões de busca, verificadores ortográficos, tabelas de roteamento IP e consultas de dicionário. Onde quer que você precise responder rápido a "alguma palavra armazenada começa com este prefixo?", um trie se destaca.
Qual é a complexidade de tempo de um trie?
Inserção, busca e consultas de prefixo rodam todas em
O(m), onde m é o comprimento da palavra ou prefixo - independentemente de quantas palavras estão armazenadas. O trade-off é a memória: um trie pode usar muito espaço, embora os prefixos compartilhados sejam armazenados apenas uma vez.Qual é a diferença entre um trie e uma tabela hash?
Uma tabela hash oferece busca média em
O(1) de chaves completas, mas não consegue responder consultas de prefixo. Um trie é um pouco mais lento por busca, mas suporta naturalmente busca por prefixo, percurso ordenado e autocompletar - a razão pela qual é preferido nesses casos.Quando devo usar um trie em vez de uma árvore binária de busca?
Use um trie quando suas chaves forem strings e você precisar de buscas por prefixo: ele roda em
O(m) por operação sobre o comprimento da chave, enquanto uma BST balanceada custa O(m log n) porque cada comparação percorre a string e há log n delas. Uma BST é a melhor escolha quando as chaves não são do tipo string ou quando a sobrecarga de memória importa mais que a velocidade de prefixos.Como se trata o fim de uma palavra em um trie?
Cada nó carrega uma marca de fim de palavra que é ativada apenas quando uma palavra completa inserida termina ali. Sem ela você não conseguiria distinguir uma palavra armazenada de um mero prefixo - por exemplo, após inserir
card, o nó de car existe, mas só deveria ser reportado como palavra se car também tiver sido inserido.Tries sempre economizam memória ao compartilhar prefixos?
Nem sempre. O compartilhamento ajuda apenas quando muitas chaves se sobrepõem; com chaves longas e distintas, um trie pode usar muito mais memória que um conjunto hash, já que cada caractere vira seu próprio nó com ponteiros para filhos. Se o espaço é a preocupação, uma árvore radix comprimida funde as cadeias de filho único para reduzir essa sobrecarga.
Recursos relacionados
Mais visualizações
