Clase TrieNode: inserción y búsqueda
Construya un TrieNode con un diccionario children y una marca is_end, implemente insert y exact-search, y analice el tiempo O(m) por operación, donde m es la longitud de la palabra.
Clase TrieNode: inserción y búsqueda es una lección gratuita de DSA Interview Prep en CoddyKit. Esta es la lección 1 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 DSA Interview Prep, y tu progreso se sincroniza en la web y la app de CoddyKit. El curso de DSA Interview Prep incluye 4 lecciones en total.
¿Qué es un Trie?
Un Trie (árbol de prefijos) es una estructura de datos con forma de árbol en la que cada nodo representa un carácter. Las palabras se almacenan encadenando caracteres desde la raíz hasta una hoja. La raíz representa una cadena vacía. Cada ruta desde la raíz hasta un nodo is_end = True forma una palabra almacenada. Los Tries son ideales para consultas basadas en prefijos, como el autocompletado, la corrección ortográfica y el enrutamiento IP, y superan a las tablas hash en estos casos de uso.
Diseño de la clase TrieNode
Un TrieNode tiene dos campos: children — un diccionario que asigna caracteres a TrieNodes secundarios — y is_end — un booleano que indica si este nodo es el final de una palabra almacenada. Usar un diccionario, en lugar de un arreglo fijo de 26 caracteres, permite generalizar a cualquier conjunto de caracteres y ahorra memoria en los Tries dispersos. Cada nodo del Trie representa exactamente una posición de carácter en las palabras que hay debajo.
class TrieNode:
def __init__(self):
self.children = {} # char -> TrieNode
self.is_end = False # True if a word ends here
class Trie:
def __init__(self):
self.root = TrieNode()
def __repr__(self):
return f'Trie(root with {len(self.root.children)} children)'
t = Trie()
print(t) # Trie(root with 0 children)Operación de inserción
Para insertar una palabra, recorra el Trie desde la raíz y cree un nuevo TrieNode para cada carácter que aún no exista en los children del nodo actual. Después de procesar todos los caracteres, establezca is_end = True en el nodo final. Insertar 'apple' y 'app' crea la cadena a→p→p→l→e (is_end=True para 'apple'), y la p de la posición 3 también queda marcada con is_end=True para 'app'.
class TrieNode:
def __init__(self):
self.children = {}
self.is_end = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word):
node = self.root
for char in word:
if char not in node.children:
node.children[char] = TrieNode()
node = node.children[char]
node.is_end = True
t = Trie()
t.insert('apple')
t.insert('app')
print('Inserted apple and app')
print('app is_end:', t.root.children['a'].children['p'].children['p'].is_end)Operación de búsqueda
Para buscar una palabra exacta, recorra el Trie siguiendo cada carácter. Si falta algún carácter en los children del nodo actual, devuelva False. Si se encuentran todos los caracteres, devuelva node.is_end: True únicamente si una palabra termina exactamente aquí, no solo un prefijo. Esta distinción entre «existe el prefijo» y «existe la palabra exacta» es fundamental y se evalúa con frecuencia.
class TrieNode:
def __init__(self):
self.children = {}
self.is_end = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word):
node = self.root
for c in word:
if c not in node.children:
node.children[c] = TrieNode()
node = node.children[c]
node.is_end = True
def search(self, word):
node = self.root
for c in word:
if c not in node.children:
return False
node = node.children[c]
return node.is_end # must be a complete word
t = Trie()
t.insert('apple')
print(t.search('apple')) # True
print(t.search('app')) # False (app not inserted)
print(t.search('orange')) # Falsestarts_with (búsqueda por prefijo)
El método starts_with comprueba si alguna palabra insertada tiene el prefijo indicado. Sigue el mismo recorrido que search, pero, en lugar de comprobar is_end, devuelve True en cuanto se han seguido correctamente todos los caracteres del prefijo; esto significa que la ruta del prefijo existe en el Trie.
class TrieNode:
def __init__(self):
self.children = {}
self.is_end = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word):
node = self.root
for c in word:
if c not in node.children:
node.children[c] = TrieNode()
node = node.children[c]
node.is_end = True
def search(self, word):
node = self.root
for c in word:
if c not in node.children: return False
node = node.children[c]
return node.is_end
def starts_with(self, prefix):
node = self.root
for c in prefix:
if c not in node.children: return False
node = node.children[c]
return True # prefix path exists
t = Trie()
t.insert('apple')
print(t.starts_with('app')) # True
print(t.starts_with('ape')) # False
print(t.search('app')) # False (not inserted)Complejidad temporal y espacial
Cada operación del Trie (insert, search, starts_with) tarda O(m) de tiempo, donde m es la longitud de la palabra, ya que recorremos como máximo m nodos. Espacio: O(ALPHABET_SIZE × N × M), donde N es el número de palabras y M es la longitud media de las palabras. En la práctica, los prefijos compartidos reducen considerablemente el espacio. Un diccionario children basado en una tabla hash utiliza menos espacio que un arreglo fijo de 26 caracteres en Tries dispersos, a cambio de una sobrecarga constante ligeramente mayor en cada búsqueda.
Usar un arreglo en lugar de un diccionario
Si solo se utilizan letras inglesas minúsculas, use un arreglo de tamaño fijo children = [None] * 26 con el índice ord(c) - ord('a'). Es más rápido (búsqueda de hijos en O(1) frente a una tabla hash) y tiene una disposición de memoria predecible. Use la versión con diccionario cuando el conjunto de caracteres sea grande o desconocido, por ejemplo, Unicode, y la versión con arreglo en problemas de programación competitiva que solo utilicen letras minúsculas.
class TrieNodeArray:
def __init__(self):
self.children = [None] * 26
self.is_end = False
class TrieArray:
def __init__(self):
self.root = TrieNodeArray()
def insert(self, word):
node = self.root
for c in word:
idx = ord(c) - ord('a')
if node.children[idx] is None:
node.children[idx] = TrieNodeArray()
node = node.children[idx]
node.is_end = True
def search(self, word):
node = self.root
for c in word:
idx = ord(c) - ord('a')
if node.children[idx] is None: return False
node = node.children[idx]
return node.is_end
t = TrieArray()
t.insert('cat')
print(t.search('cat')) # True
print(t.search('car')) # FalseOperación de eliminación
La eliminación de un Trie debe gestionar tres casos: (1) la palabra no está presente — no hacer nada; (2) la palabra está presente, pero es un prefijo de otra palabra — solo desmarcar is_end; (3) la palabra está presente y no es un prefijo — eliminar los nodos de abajo arriba, deteniéndose cuando un nodo tenga otros hijos o sea el final de otra palabra. La eliminación rara vez se evalúa en entrevistas, pero es conveniente conocerla conceptualmente.
Contar palabras con un prefijo
Añada a cada nodo un campo count que se incremente cada vez que una inserción pase por él. Para contar las palabras que tienen un prefijo determinado, recorra el Trie hasta el nodo final del prefijo y devuelva su count. Esto permite realizar consultas de autocompletado en O(m) sin recorrer todos los hijos: una extensión útil para sistemas de autocompletado reales.
class TrieNodeCount:
def __init__(self):
self.children = {}
self.is_end = False
self.count = 0 # words passing through this node
class TrieCount:
def __init__(self):
self.root = TrieNodeCount()
def insert(self, word):
node = self.root
for c in word:
if c not in node.children:
node.children[c] = TrieNodeCount()
node = node.children[c]
node.count += 1 # increment on each level
node.is_end = True
def count_with_prefix(self, prefix):
node = self.root
for c in prefix:
if c not in node.children: return 0
node = node.children[c]
return node.count
t = TrieCount()
for w in ['apple','app','application','apply']:
t.insert(w)
print(t.count_with_prefix('app')) # 4
print(t.count_with_prefix('appl')) # 3Comparación entre Trie y tabla hash
Una tabla hash puede realizar una búsqueda exacta en un tiempo medio de O(m), pero no puede responder de forma eficiente a consultas de prefijos, ya que requiere recorrer todas las claves. Un Trie responde a las consultas de prefijos en O(p), donde p es la longitud del prefijo, agrupa de forma natural las palabras con prefijos compartidos y no necesita hashing. Use un Trie cuando haya consultas frecuentes de prefijos, autocompletado o corrección ortográfica. Use una tabla hash cuando solo se necesiten búsquedas exactas.
Tries en sistemas reales
Entre los usos de los Tries en sistemas reales se encuentran: autocompletado (sugerencias de búsqueda de Google), correctores ortográficos (para encontrar las palabras coincidentes más cercanas), enrutamiento IP (búsqueda del prefijo más largo en routers), texto predictivo T9 (desambiguación de caracteres) y resolutores DNS (búsqueda jerárquica de nombres de dominio). En cada caso, la relación entre O(m) por operación y el espacio O(ALPHABET × nodes) hace que el Trie sea la herramienta adecuada para realizar búsquedas rápidas y basadas en prefijos a gran escala.
Comprobación rápida
Evalúe su comprensión de los conceptos de Data Structures & Algorithms — Coding Interview Prep de esta lección.
Resumen de la lección
En esta lección aprendió: un TrieNode tiene un diccionario children y un booleano is_end, insert recorre carácter por carácter, crea nodos cuando es necesario y establece is_end al final, y search comprueba is_end, mientras que starts_with solo comprueba si existe la ruta del prefijo. A continuación, añadiremos el autocompletado basado en prefijos y estudiaremos con más detalle el método starts_with.
Preguntas frecuentes
¿La lección «Clase TrieNode: inserción y búsqueda» es gratis?
Sí — el texto completo de «Clase TrieNode: inserción y búsqueda» 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 DSA Interview Prep, actualiza a CoddyKit PRO. El curso de DSA Interview Prep incluye 4 lecciones en total.
¿Qué aprenderé en «Clase TrieNode: inserción y búsqueda»?
Construya un TrieNode con un diccionario children y una marca is_end, implemente insert y exact-search, y analice el tiempo O(m) por operación, donde m es la longitud de la palabra. Practicas DSA 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 DSA Interview Prep?
No se requiere experiencia previa. DSA 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 1 de 4.
¿Cuánto tiempo toma la lección «Clase TrieNode: inserción y búsqueda»?
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 DSA Interview Prep?
Sí. Cada lección de DSA 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
- Clase TrieNode: inserción y búsqueda
- Búsqueda por prefijo y Starts-With
- Búsqueda con comodines y expresiones regulares en un trie
- Word Search II: trie y retroceso en una cuadrícula