Trie
AvanzadoPrioritaria
Estructura tipo árbol para almacenar strings con prefijos comunes.
¿Qué es un Trie?
Un Trie (también llamado árbol de prefijos) es una estructura de datos en forma de árbol usada para almacenar conjuntos de cadenas. Cada nodo representa un carácter y una ruta desde la raíz representa una palabra completa o parcial. Se utiliza para realizar búsquedas rápidas por prefijo.
Analogía del Mundo Real
Imagina un directorio de archivos:
- Cada carpeta representa una letra.
- Una ruta completa representa un nombre de archivo.
- Buscar todos los archivos que comienzan con 'doc' es tan simple como navegar hasta la carpeta 'd', luego 'o', luego 'c'.
Cómo Funciona Internamente un Trie
- Nodos por letra: Cada nivel del árbol representa una letra de la palabra.
- Ramas por posibles caracteres: Desde cada nodo, se ramifican nuevos nodos para los caracteres siguientes.
- Marcadores de fin de palabra: Se usan banderas para indicar cuándo una ruta representa una palabra válida.
- Búsqueda y autocompletado: Navegar letra por letra permite validar si una palabra o prefijo existe, o encontrar todas las coincidencias posibles desde ese punto.
Ejemplos de Código
// Trie implementation in JavaScript
class TrieNode {
constructor() {
this.children = {};
this.isEndOfWord = false;
}
}
class Trie {
constructor() {
this.root = new TrieNode();
}
insert(word) {
let node = this.root;
for (let char of word) {
if (!node.children[char]) {
node.children[char] = new TrieNode();
}
node = node.children[char];
}
node.isEndOfWord = true;
}
search(word) {
let node = this.root;
for (let char of word) {
if (!node.children[char]) return false;
node = node.children[char];
}
return node.isEndOfWord;
}
startsWith(prefix) {
let node = this.root;
for (let char of prefix) {
if (!node.children[char]) return false;
node = node.children[char];
}
return true;
}
}Explicación Visual (🚧 En progreso)
Pronto disponible
Estamos trabajando en un video para explicar esta estructura de datos
Complejidad en Tiempo y Espacio
| Operación | Promedio | Peor Escenario |
|---|---|---|
| Acceso | O(L) | O(L) |
| Búsqueda | O(L) | O(L) |
| Inserción | O(L) | O(L) |
| Eliminación | O(L) | O(L) |
Donde L es la longitud de la palabra que se quiere insertar, buscar o eliminar.
La eficiencia del Trie no depende del número de palabras, sino de la longitud de las palabras.
Operaciones Comunes
- insert(word)Agrega una palabra al Trie
- search(word)Verifica si una palabra existe
- startsWith(prefix)Verifica si existe una palabra que comience con un prefijo
Practica
Aplica lo que has aprendido