Tries para búsquedas por prefijo
Almacene y consulte prefijos de palabras rápidamente
Tries para búsquedas por prefijo es una lección gratuita de Coding Interview Prep en CoddyKit. Esta es la lección 4 de 4. Puedes leer la lección completa abajo gratuitamente — luego la practicas en el navegador con un editor de código integrado y un tutor de IA 24/7. Forma parte de la ruta de aprendizaje de Coding Interview Prep, y tu progreso se sincroniza en la web y la app de CoddyKit. El curso de Coding Interview Prep incluye 4 lecciones en total.
Almacenar palabras de forma inteligente
Un trie es un árbol que almacena palabras compartiendo prefijos comunes. Hace que las consultas de prefijos sean rapidísimas. 🌳
Por qué no basta con un conjunto
Un conjunto permite buscar palabras completas, pero los tries también responden consultas de prefijos, como saber si alguna palabra comienza por pre.
Nodos y aristas
Cada nodo representa una posición dentro de alguna palabra, y cada arista está etiquetada con un carácter del camino desde la raíz.
Los hijos como diccionario
En Python, el nodo más sencillo es un diccionario que asigna cada carácter a su nodo hijo. Es una solución clara y flexible.
root = {}Insertar una palabra
Para insertar una palabra, recorra sus caracteres uno a uno y cree un hijo cuando falte.
node = root
for c in word:
node = node.setdefault(c, {})Marcar los finales de palabra
Después de insertar la palabra, establezca una marca de final para distinguir una palabra completa de un simple prefijo.
node['#'] = TrueBuscar una palabra completa
Para buscar, siga los caracteres; si falta algún paso, la palabra no está presente. Después, compruebe la marca de final.
for c in word:
if c not in node:
return False
node = node[c]Comprobar un prefijo
Una consulta de prefijo consiste en el mismo recorrido, pero sin comprobar la marca de final. Llegar al último nodo significa que sí existe.
Complejidad temporal
Insertar y buscar cuestan O(L), donde L es la longitud de la palabra, independientemente de cuántas palabras haya almacenado. Lo que cuenta es la longitud.
Contar palabras por prefijo
Almacene un contador en cada nodo para responder al instante cuántas palabras almacenadas comparten un prefijo determinado.
Dónde ayudan los tries
Los tries se usan en autocompletado, comprobaciones de diccionarios y problemas de máximo XOR sobre bits. Son fundamentales en los problemas de cadenas de los concursos.
Comprobación rápida
Confirme cuánto cuesta realmente una búsqueda en un trie.
Repaso: lo aprendido sobre tries
Ahora puede construir un trie, insertar y buscar en O(L), y responder rápidamente consultas de prefijos y de conteo. 🌟
Preguntas frecuentes
¿La lección «Tries para búsquedas por prefijo» es gratis?
Sí — el texto completo de «Tries para búsquedas por prefijo» es gratis para leer aquí en la web. Para practicarla de forma interactiva (editor de código integrado y tutor de IA 24/7) y desbloquear el resto del curso de Coding Interview Prep, actualiza a CoddyKit PRO. El curso de Coding Interview Prep incluye 4 lecciones en total.
¿Qué aprenderé en «Tries para búsquedas por prefijo»?
Almacene y consulte prefijos de palabras rápidamente Practicas Coding Interview Prep con código real que ejecutas directamente en el navegador, y un tutor de IA 24/7 responde tus preguntas mientras trabajas en la lección.
¿Necesito experiencia previa para empezar Coding Interview Prep?
No se requiere experiencia previa. Coding Interview Prep en CoddyKit está estructurado para principiantes hasta estudiantes avanzados, así que puedes empezar aquí o desde el inicio y avanzar a tu ritmo. Esta es la lección 4 de 4.
¿Cuánto tiempo toma la lección «Tries para búsquedas por prefijo»?
La mayoría de las lecciones de CoddyKit toman alrededor de 5–10 minutos. Cada una es compacta e interactiva, así que avanzas constantemente y retomas exactamente por donde dejaste en la web y la app.
¿Puedo escribir y ejecutar código en esta lección de Coding Interview Prep?
Sí. Cada lección de Coding Interview Prep incluye un editor de código integrado, así que escribes y ejecutas código real directamente en tu navegador y obtienes retroalimentación instantánea de IA — sin configuración local necesaria.
Todas las lecciones de este curso
- Función de prefijo de KMP
- Hash polinómico de cadenas
- Función Z para buscar patrones
- Tries para búsquedas por prefijo