Saltar al contenido

Fundamentos de tries

Lección 1 de 4 · 5 min

Fundamentos de tries

Paso 1 de 10

Un trie (árbol de prefijos) vacío es un solo nodo raíz. Cada palabra empieza su camino aquí.

La idea

Un trie (árbol de prefijos) deletrea las palabras en vez de guardarlas enteras. Cada arista lleva un carácter, así que el camino que baja desde la raíz es un prefijo. Las palabras que comparten un prefijo comparten esos nodos.

Una marca por nodo indica “aquí termina una palabra”; sin ella no puedes distinguir la palabra car del prefijo que está dentro de cart.

Ejemplo del mundo real

El viejo catálogo de fichas de una biblioteca: cajones rotulados A–C y, dentro, separadores para la segunda letra y luego para la tercera. Nadie guarda el título dos veces porque dos libros empiecen con “Ca”: recorres los rótulos y cada libro detrás de ese separador es un acierto.

El código

Te toca

¿Qué imprime esto?

root = {}
for word in ["do", "dorm"]:
  node = root
  for ch in word:
      node = node.setdefault(ch, {})
  node["$"] = True
print(sorted(root["d"]["o"]))

Mini quiz

1 / 3

¿Qué representa una arista de un trie?