3.1. Árboles Trie.
Aplicación: representación de diccionarios (o en general conjuntos) grandes de palabras. Muchas palabras ? Mucha memoria y operaciones lentas.
Idea: muchas palabras tienen prefijos comunes. P. ej.: operador, operando; encontrado, -a, -os, -as...
Definición: un trie es una estructura de árbol en la que:
- Cada nodo (excepto la raíz) está etiquetado con un carácter (a, ..., z) o una marca de fin (símbolo $).
- Un camino de la raíz a una hoja (etiquetada con $) corresponde a una palabra del diccionario.
- Cada nodo (excepto la raíz y las hojas) es un prefijo del conjunto.
Ejemplo: A= {EL, ELLA, ELLO, ELE, ELES, MANO, MAL}