Árvore de prefixos para busca eficiente de strings, autocomplete e verificação de prefixos em O(m) onde m é o tamanho da palavra.
Trie (pronuncia-se "try") é uma árvore onde cada nó representa um caractere. O caminho da raiz até um nó forma um prefixo. Nós marcados como "fim de palavra" indicam palavras válidas no dicionário. Vantagens sobre hash table: - Busca de prefixos em O(m) - impossível com hash - Autocomplete natural - basta percorrer subárvore do prefixo - Sem colisões - Ordenação lexicográfica grátis (DFS da esquerda para direita) Estrutura do nó: - children: mapa de caractere para nó filho (dict ou array de 26) - is_end: boolean indicando se é fim de palavra válida A complexidade é sempre O(m) onde m é o tamanho da string, independente de quantas palavras existem na trie.
“Cada nó compartilha o prefixo de seus ancestrais. Palavras com prefixos comuns compartilham nós, economizando espaço e permitindo buscas por prefixo eficientes.”
m é o tamanho da string. Cada operação percorre no máximo m nós.
Insert, search e startsWith visitam exatamente m nós, um por caractere.
No pior caso, n palavras de tamanho m sem prefixos comuns.
Sempre O(m) independente do número de palavras.
Mesmo no pior caso, só percorremos m nós.
| Algoritmo | Tempo | Espaco | Melhor Para |
|---|---|---|---|
| Trie(atual) | O(m) por operação | O(n * m) | Autocomplete, busca por prefixo, dicionários |
| Hash Table | O(m) médio | O(n * m) | Busca exata de strings |
| BST de Strings | O(m * log n) | O(n * m) | Strings ordenadas, range queries |
Pratique respondendo a perguntas comuns de entrevistas tecnicas. Clique em uma pergunta para iniciar uma sessao de pratica com IA.
1class TrieNode:Classe TrieNode2 def __init__(self):Classe TrieNode3 self.children = {}Classe TrieNode4 self.is_end = FalseMarcar Fim5 6 7class Trie:Classe TrieNode8 def __init__(self):Inicializar Raiz9 self.root = TrieNode()Inicializar Raiz10 11 def insert(self, word):Operação Insert12 node = self.rootTravessia13 for char in word:Travessia14 if char not in node.children:Verificar Existência15 node.children[char] = TrieNode()Criar Nó16 node = node.children[char]Travessia17 node.is_end = TrueMarcar Fim18 19 def search(self, word):Operação Search20 node = self._find_node(word)Operação Search21 return node is not None and node.is_endOperação Search22 23 def startsWith(self, prefix):Operação StartsWith24 return self._find_node(prefix) is not NoneOperação StartsWith25 26 def _find_node(self, s):Travessia27 node = self.rootTravessia28 for char in s:Travessia29 if char not in node.children:Verificar Existência30 return NoneVerificar Existência31 node = node.children[char]Travessia32 return nodeTravessia33 34 def autocomplete(self, prefix):35 node = self._find_node(prefix)36 if not node:37 return []38 results = []39 self._dfs(node, prefix, results)40 return results41 42 def _dfs(self, node, current, results):43 if node.is_end:44 results.append(current)45 for char, child in node.children.items():46 self._dfs(child, current + char, results)47