Trie (árbol de prefijos)
Última actualización
Un trie (se pronuncia "trai"), o árbol de prefijos, almacena un conjunto de cadenas por sus caracteres: cada arista se etiqueta con un carácter y un camino desde la raíz deletrea un prefijo. Las palabras que comparten un prefijo comparten los mismos nodos, así que "car", "card" y "care" reutilizan todas el camino c-a-r. Pulsa reproducir arriba para ver cómo se insertan las palabras un carácter a la vez, ramificándose solo donde difieren.
Como las búsquedas recorren un nodo por carácter, buscar una palabra de longitud m toma O(m) sin importar cuántas palabras contenga el trie. Eso hace que los tries sean ideales para autocompletado, corrección ortográfica y búsqueda por prefijos.
Complejidad temporal y espacial
| Operación | Complejidad | Notas |
|---|---|---|
| Insertar | O(m) | m = longitud de la palabra |
| Buscar | O(m) | Un paso por carácter |
| Consulta de prefijo | O(m) | Recorrer hasta el nodo del prefijo |
| Espacio | O(total chars) | Los prefijos compartidos se almacenan una sola vez |
Paso a paso (inserción)
| Paso | Qué ocurre |
|---|---|
| 1 | Comienza en el nodo raíz. |
| 2 | Por cada carácter de la palabra, busca una arista hija coincidente. |
| 3 | Si existe, síguela (reutilizando el prefijo compartido). |
| 4 | Si no, crea un nuevo nodo hijo para ese carácter. |
| 5 | Tras el último carácter, marca ese nodo como fin de palabra. |
Ejemplo resuelto
Insertando ["car", "card", "care"] en un trie vacío:
| Paso | Estructura | Acción |
|---|---|---|
Insertar car | root → c → a → r✓ | No existen hijos coincidentes, así que crea c, a, r y marca r como fin de palabra. |
Insertar card | root → c → a → r✓ → d✓ | Reutiliza el camino existente c-a-r, luego crea un nuevo hijo d y márcalo como fin de palabra. |
Insertar care | root → c → a → r✓ → {d✓, e✓} | Reutiliza c-a-r, ramifica desde r con un nuevo hijo e y marca e como fin de palabra. |
Buscar care | root → c → a → r → e✓ | Recorre c, a, r, e; el nodo final está marcado como fin de palabra, así que care está presente. |
Buscar ca | root → c → a | El camino existe pero a no está marcado como fin de palabra, así que ca es un prefijo pero no una palabra almacenada. |
Cuándo usar un trie
| Úsalo cuando | Evítalo cuando |
|---|---|
| Necesitas consultas por prefijo o autocompletado sobre un conjunto de cadenas. | Solo necesitas búsquedas de claves completas: una tabla hash es más rápida y ligera. |
| Muchas palabras almacenadas comparten prefijos comunes, así que se reutilizan nodos. | Las claves son largas y rara vez se solapan, desperdiciando un nodo por carácter. |
| Quieres que las claves se devuelvan en orden mediante un recorrido. | La memoria es escasa: los punteros a hijos por nodo añaden una sobrecarga considerable. |
| El coste de búsqueda debe depender de la longitud de la clave, no del tamaño del conjunto de datos. | El alfabeto es enorme (p. ej. todo Unicode) y los hijos se almacenan de forma densa. |
Código de Trie (Prefix Tree)
Una implementación limpia y ejecutable de Trie (Prefix Tree) en Python, JavaScript, Java, C++, C. Elige un lenguaje, copia el código o ábrelo ya cargado en el Playground de Coddy.
Código 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"))Código 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"));Código 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}Código 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}Código 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}Preguntas frecuentes sobre tries
¿Para qué se usa un trie?
Los tries impulsan funciones basadas en prefijos: autocompletado y sugerencias de búsqueda, correctores ortográficos, tablas de enrutamiento IP y consultas de diccionario. Allí donde necesitas responder rápido a "¿alguna palabra almacenada empieza por este prefijo?", un trie brilla.
¿Cuál es la complejidad temporal de un trie?
La inserción, la búsqueda y las consultas de prefijo se ejecutan todas en
O(m), donde m es la longitud de la palabra o prefijo, independientemente de cuántas palabras se almacenen. El compromiso es la memoria: un trie puede usar mucho espacio, aunque los prefijos compartidos se almacenan una sola vez.¿Cuál es la diferencia entre un trie y una tabla hash?
Una tabla hash ofrece búsqueda promedio en
O(1) de claves completas, pero no puede responder consultas de prefijo. Un trie es algo más lento por búsqueda, pero admite de forma natural la búsqueda por prefijo, el recorrido ordenado y el autocompletado, la razón por la que se prefiere para esos casos.¿Cuándo debería usar un trie en lugar de un árbol binario de búsqueda?
Usa un trie cuando tus claves sean cadenas y necesites búsquedas por prefijo: se ejecuta en
O(m) por operación sobre la longitud de la clave, mientras que un BST equilibrado cuesta O(m log n) porque cada comparación recorre la cadena y hay log n de ellas. Un BST es mejor opción cuando las claves no son de tipo cadena o cuando la sobrecarga de memoria importa más que la velocidad de prefijos.¿Cómo se maneja el fin de una palabra en un trie?
Cada nodo lleva una marca de fin de palabra que se activa solo cuando una palabra completa insertada termina ahí. Sin ella no podrías distinguir una palabra almacenada de un mero prefijo: por ejemplo, tras insertar
card, el nodo de car existe pero solo debería reportarse como palabra si car también se insertó.¿Los tries siempre ahorran memoria al compartir prefijos?
No siempre. La compartición ayuda solo cuando muchas claves se solapan; con claves largas y distintas, un trie puede usar mucha más memoria que un conjunto hash, ya que cada carácter se convierte en su propio nodo con punteros a hijos. Si el espacio es la preocupación, un árbol radix comprimido fusiona las cadenas de un solo hijo para reducir esa sobrecarga.
Recursos relacionados
Más visualizaciones
