Trie (pronunciado como «intentar»): Trie (también conocido como árbol digital o árbol de prefijos) es una estructura de datos especial ordenada y eficiente basada en árboles que se utiliza para almacenar y recuperar claves en un conjunto de datos de strings. La ideología básica detrás de esto es recuperar información. Se basa en el prefijo de una string. Se puede visualizar como un gráfico que consta de Nodes y aristas. Otro nombre para Trie es el árbol digital. Cada Node de un trie puede tener hasta 26 punteros/referencias. Estos 26 punteros representan los 26 caracteres del idioma inglés.
Operaciones básicas de Trie:
- Inserción
- Supresión
- buscando
Aplicaciones de la estructura de datos Trie:
Tiene una amplia variedad de aplicaciones en compresión de datos , biología computacional, algoritmo de coincidencia de prefijo más largo utilizado para tablas de enrutamiento para direcciones IP , implementación del diccionario, búsqueda de patrones, almacenamiento/consulta de documentos XML, etc.
Aplicaciones en tiempo real de la estructura de datos Trie:
1. Historial del navegador: los navegadores web realizan un seguimiento del historial de los sitios web visitados por el usuario. Por lo tanto, cuando el prefijo de una URL visitada anteriormente se escribe en la barra de direcciones, el usuario recibe sugerencias sobre el sitio web que debe visitar.
Trie se utiliza para almacenar el número de visitas a un sitio web como valor clave y organizar este historial en la estructura de datos de Trie.
Sugerencias del historial del navegador (geeks para geeks)
2. Autocompletar: es una de las aplicaciones más importantes de la estructura de datos trie. Esta característica acelera las interacciones entre un usuario y la aplicación y mejora enormemente la experiencia del usuario. La función Autocompletar es utilizada por navegadores web, correo electrónico, motores de búsqueda, editores de código, intérpretes de línea de comandos (CLI) y procesadores de texto.
Trie proporciona el orden alfabético de los datos por claves. Trie se usa porque es el más rápido para sugerencias de autocompletado, incluso en el peor de los casos, es O(n) (donde n es la longitud de la string) veces más rápido que el algoritmo de tabla hash imperfecto alternativo y también supera el problema de la clave Colisiones en tablas hash imperfectas.
Sugerencias de autocompletar al ingresar el prefijo (geeks para geeks)
3. Correctores ortográficos/Corrección automática: es un proceso de 3 pasos que incluye:
- Comprobación de la palabra en el diccionario de datos.
- Generación de posibles sugerencias.
- Ordenar las sugerencias con mayor prioridad en la parte superior.
Trie almacena el diccionario de datos y facilita la creación de un algoritmo para buscar la palabra en el diccionario y proporciona la lista de palabras válidas para la sugerencia.
Corrección automática (geeks para geeks)
4. Algoritmo de coincidencia de prefijo más largo (coincidencia de longitud máxima de prefijo): este algoritmo se utiliza en redes por los dispositivos de enrutamiento en redes IP. La optimización de las rutas de red requiere un enmascaramiento contiguo que limite la complejidad de la búsqueda a O(n), donde n es la longitud de la dirección URL en bits.
Para acelerar el proceso de búsqueda, se desarrollaron esquemas de prueba de bits múltiples que realizan las búsquedas de bits múltiples más rápido.
Enrutamiento IP (geeks para geeks)
Ventajas de la estructura de datos Trie:
- Trie nos permite ingresar y encontrar strings en tiempo O(l), donde l es la longitud de una sola palabra. Es más rápido en comparación con las tablas hash y los árboles de búsqueda binarios.
- Proporciona filtrado alfabético de entradas por la clave del Node y, por lo tanto, facilita la impresión de todas las palabras en orden alfabético.
- Trie ocupa menos espacio en comparación con BST porque las claves no se guardan explícitamente, sino que cada clave requiere solo una cantidad fija amortizada de espacio para almacenarse.
- La búsqueda de prefijos/la coincidencia de prefijos más largos se puede realizar de manera eficiente con la ayuda de la estructura de datos trie.
- Dado que trie no necesita ninguna función hash para su implementación, generalmente son más rápidas que las tablas hash para claves pequeñas como números enteros y punteros.
- Los intentos admiten la iteración ordenada, mientras que la iteración en una tabla hash dará como resultado un orden pseudoaleatorio dado por la función hash, que suele ser más engorrosa.
- La eliminación también es un algoritmo sencillo con O(l) como su complejidad temporal, donde l es la longitud de la palabra que se eliminará.
Desventajas de la estructura de datos Trie:
- La principal desventaja del trie es que se necesita mucha memoria para almacenar todas las strings. Para cada Node, tenemos demasiados punteros de Node que son iguales al número de caracteres en el peor de los casos.
- Una tabla hash construida eficientemente (es decir, una buena función hash y un factor de carga razonable) tiene O(1) como tiempo de búsqueda, que es mucho más rápido que O(l) en el caso de un trie, donde l es la longitud de la string.