Trie: el árbol de prefijos, paso a paso

El árbol contiene dieciséis palabras, con una letra en cada nodo. Las que empiezan igual comparten el tramo inicial: car, card y cart siguen el mismo camino por c, a y r. Un doble círculo señala dónde termina una palabra. Escribe una palabra, elige una operación y avanza paso a paso.

Ejemplo resuelto — Trie: el árbol de prefijos, paso a paso

Trie, búsqueda de “car”: letras leídas	3, guardada
Tabla hash sin colisiones: letras leídas	6
Palabras que empiezan por “car”	6: car, card, care, careful, cargo, cart
Tabla hash: palabras leídas (todas)	16
Al insertar “car” se añaden	0 nodos: 0 bytes al trie, 0 a la lista
Nodos del trie: uno por cada prefijo distinto	30 para 70 letras (57,1 % compartidas)
Lista simple: las letras más 9 bytes por palabra	214
Trie con nodos de 18 bytes, incluida la raíz	558

Estos son los valores que muestra la calculadora al abrir la página. Cambia cualquier entrada de arriba para recalcularlos.

Cargando simulación interactiva...

Lección

La teoría — Trie: el árbol de prefijos, paso a paso

Un trie, o árbol de prefijos, guarda un conjunto de palabras en un árbol con un nodo por cada prefijo distinto. La raíz representa el prefijo vacío. Cada arista lleva una letra, de modo que el camino desde la raíz hasta un nodo forma el prefijo de ese nodo. El nodo está marcado si su prefijo es una palabra completa del conjunto. Las palabras que empiezan igual comparten el tramo de camino correspondiente a ese comienzo. Una búsqueda sigue las letras de la palabra desde la raíz; una búsqueda por prefijo llega hasta el nodo del prefijo y recoge todos los nodos marcados que hay debajo. Edward Fredkin dio nombre a esta estructura en 1960 a partir de la palabra inglesa retrieval, con la intención de que se pronunciara como tree.

Qué significa cada símbolo

W: número de palabras de la lista
L: número total de letras de esas palabras
N: número de nodos, uno por cada prefijo distinto, sin contar la raíz

Supone: Se usan letras minúsculas de la a a la z, un byte por letra y punteros de 64 bits. En ninguna de las estructuras se cuentan los bytes de relleno ni la memoria adicional que necesita el gestor de memoria. La búsqueda binaria cuenta cada par de letras que compara y se detiene en el primero que difiere; llegar al final de una palabra no tiene coste. La tabla hash funciona sin ninguna colisión, su caso más favorable. Los nodos de 18 bytes mantienen sus hijos en orden alfabético, de modo que la búsqueda entre ellos se detiene en cuanto pasa de la letra buscada.

La búsqueda binaria lee c, a y r cuatro veces; el trie, una 🖖

Pulsa Buscar car. El trie sigue una letra por paso y encuentra car con una marca de fin de palabra: 3 letras. La búsqueda binaria en las mismas 16 palabras ordenadas consulta catch, careful, card y car. Todas empiezan por ca, así que cada comparación lee 3 letras antes de decidir por dónde seguir: 12 en total. La tabla hash lee las 3 letras para calcular una posición y otras 3 para comprobar la palabra que encuentra allí: 6. Al buscar las 16 palabras guardadas, el trie lee 70 letras, la tabla hash 140 y la búsqueda binaria 169. Los comienzos compartidos que ahorran nodos al trie alargan las comparaciones de la búsqueda binaria. Si guardas las 17.576 cadenas de 3 letras, de aaa a zzz, la búsqueda binaria necesita leer una media de 26,4 letras para encontrar una; el trie sigue leyendo 3.

Una lista ordenada también permite autocompletar. Una tabla hash tiene que leer todas las palabras 🖖

Pulsa Palabras con car. El trie recorre c, a y r y después visita los 8 nodos que hay debajo de car: 11 nodos en total, de los que 6 marcan el final de una palabra. No pasa por dog, plan ni por las demás. Una lista ordenada también permite limitar el recorrido, porque las palabras que empiezan por car quedan juntas. La búsqueda binaria encuentra la primera en 5 consultas. Desde ahí, basta con leer las palabras siguientes para recoger las 6 y detenerse en cat, la primera que no encaja: 12 palabras leídas. La tabla hash está diseñada para enviar car, card y cargo a posiciones sin relación entre sí, por lo que tiene que leer las 16 palabras y comprobarlas una a una. El trie aventaja a la lista ordenada cuando hay que añadir palabras. Pulsa Insertar carpet: el trie añade 3 nodos sin mover nada; la lista ordenada desplaza una posición los punteros de 11 palabras para hacer sitio.

Incluso compartiendo 40 de 70 letras, el trie ocupa 2,6 veces lo que ocupa la lista 🖖

Las 16 palabras suman 70 letras, que el trie guarda en 30 nodos: car, card, care y las demás comparten sus nodos c, a y r. Cada nodo necesita espacio para algo más que su letra. En la representación compacta, lleva un byte para la letra, otro para la marca de fin de palabra y dos punteros de 8 bytes: uno al primer hijo y otro al siguiente hermano. Son 18 bytes por nodo; los 31 nodos, incluida la raíz, suman 558. La lista simple guarda cada letra en un byte, más un byte de fin y un puntero de 8 bytes por palabra: 214. Si cada nodo tiene un puntero por cada letra del alfabeto, cada paso se resuelve con un acceso a un vector, pero el trie ocupa 6.479 bytes, 30 veces lo que ocupa la lista. Con palabras de hasta 14 letras, como aquí, añadir una palabra solo ocupa menos espacio en el trie si no requiere ningún nodo nuevo, como ocurriría con plan en un trie que ya contuviera planet, o si añade un solo nodo y tiene al menos 10 letras. La representación compacta también tiene un coste en tiempo: para encontrar cada letra, recorre los nodos hermanos. Buscar doorbell requiere entonces 10 comparaciones, una más que la búsqueda binaria.

Problema resuelto al detalle

¿Cuántas letras habría que compartir para que el trie ocupara menos? 4 pasos
Pulsa Palabras largas: 85 letras en 21 nodos, tres cuartas partes compartidas, y el trie con nodos de 18 bytes aún ocupa 396 bytes frente a los 157 de la lista. Si todas las palabras tienen k letras, el caso más favorable para el trie frente a la lista es el que contiene todas las palabras posibles. Con los bytes que cuenta esta página, ¿cuál es el menor valor de k para el que ese trie ocupa menos que la lista simple?

Abre este problema en la herramienta
1. En la página hay 21 nodos más la raíz: 22 × 18 = 396 bytes. La lista guarda 85 letras y, por cada una de sus 8 palabras, un byte de fin y un puntero de 8 bytes: 85 + 9 × 8 = 157.
  
  $22 \times 18 = 396, 85 + 9 \times 8 = 157$
2. El conjunto de todas las cadenas de k letras contiene 26^k palabras, cada una de k letras. La lista ocupa, por tanto, (k + 9) × 26^k bytes.
  
  $list = (k + 9) \cdot 2 6^{k}$
3. El trie necesita un nodo por cada cadena de 1 a k letras: 26 + 26² + … + 26^k, algo menos que 26/25 × 26^k. Al añadir la raíz y multiplicar por 18, el trie ocupa algo menos de 18,72 × 26^k bytes.
  
  $N = 26 + 2 6^{2} + \dots + 2 6^{k} = \frac{26}{25} (2 6^{k} - 1), 18 (N + 1) < 18.72 \cdot 2 6^{k}$
4. La lista pasa a ocupar más cuando k + 9 supera 18,72. El primer valor que lo cumple es k = 10. Para k = 9, el trie ocupa un 4,0 % más que la lista; para k = 10, un 1,5 % menos.
  
  $k + 9 > 18.72 ⟺ k \geq 10 : \frac{trie}{list} = 1.040 (k = 9), 0.985 (k = 10)$
Respuesta

10 letras, con las 26¹⁰ palabras posibles en la lista: unas 1,4 × 10¹⁴ palabras. Con nodos de 209 bytes, la misma suma exige que k + 9 supere aproximadamente 217; hacen falta palabras de 209 letras.

$k = 10, 2 6^{10} \approx 1.4 \times 1 0^{14} words$

Ruta de aprendizaje

Qué operaciones abarata una estructura de datos

Referencias (3)

The name, its origin in "retrieval", and Fredkin's intended pronunciation, quoted in the definition: Paul E. Black, "trie", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed., NIST, entry modified 12 February 2019.
The paper that named the structure: Edward Fredkin, "Trie memory," Communications of the ACM 3(9), September 1960, pp. 490–499.
The earlier description of searching on letter-by-letter keys: René de la Briandais, "File searching using variable length keys," Papers presented at the Western Joint Computer Conference, San Francisco, 3–5 March 1959, pp. 295–298.

Por el equipo de 42Math · Contrastado con fuentes publicadas. Se agradecen correcciones.