3.1.3. Evaluación de los tries.
Queremos representar n palabras, con p prefijos y una longitud total de L letras. (n ? p ? L). Un puntero ocupa k1 bytes y una letra k2 bytes.
Tabla de dispersión abierta
Las palabras se almacenan en un array de caracteres, en el que el final de cada palabra se indica con $ ? (L+n)·k2 bytes
Las celdas de las cubetas constan de dos apuntadores: uno para la lista de celdas y otro para apuntar al principio de cada palabra ? 2n·k1 bytes
Suponiendo B cubetas ? B·k1 bytes
Total: n(2·k1 + k2) + k2·L + B·k1 bytes
Trie representado con listas enlazadas
Cada celda almacena 1 carácter y 2 apuntadores ? 2·k1 + k2 bytes
Habrá una celda por cada prefijo y una por cada palabra (marca $) ? p + n celdas
Total: (2·k1 + k2)·(p + n) bytes
- ¿Cuál ocupa más memoria? ¿En qué circunstancias?
- ¿Dónde serán más eficientes las operaciones Inserta, Suprime y Miembro?