prueba
En informática , un trie , también llamado árbol digital o árbol de prefijos , es un tipo de árbol de búsqueda , una estructura de datos de árbol utilizada para localizar claves específicas dentro de un conjunto. Estas claves suelen ser cadenas , con enlaces entre nodos definidos no por la clave completa, sino por caracteres individuales . Para acceder a una clave (para recuperar su valor, cambiarla o eliminarla), el trie se recorre primero en profundidad , siguiendo los enlaces entre nodos, que representan cada carácter de la clave.
A diferencia de un árbol de búsqueda binario , los nodos del trie no almacenan su clave asociada. En cambio, la posición de un nodo en el trie define la clave con la que está asociado. Esto distribuye el valor de cada clave en la estructura de datos y significa que no todos los nodos necesariamente tienen un valor asociado.
Todos los hijos de un nodo tienen un prefijo común de la cadena asociada con ese nodo principal, y la raíz está asociada con la cadena vacía . Esta tarea de almacenar datos accesibles por su prefijo se puede lograr de una manera optimizada para memoria empleando un árbol radix .
Aunque los intentos pueden codificarse mediante cadenas de caracteres, no es necesario que lo sean. Los mismos algoritmos se pueden adaptar para listas ordenadas de cualquier tipo subyacente, por ejemplo, permutaciones de dígitos o formas. En particular, un trie bit a bit se codifica en los bits individuales que forman una pieza de datos binarios de longitud fija, como un número entero o una dirección de memoria .
La idea de un trie para representar un conjunto de cadenas fue descrita abstractamente por primera vez por Axel Thue en 1912. [1] [2] Los tries fueron descritos por primera vez en un contexto informático por René de la Briandais en 1959. [3] [4] [ 2] La idea fue descrita de forma independiente en 1960 por Edward Fredkin , [5] quien acuñó el término trie , pronunciándolo / ˈ t r iː / (como "árbol"), después de la sílaba media de recuperación . [6] [7] Sin embargo, otros autores lo pronuncian / ˈ t r aɪ/ (como "intentar"), en un intento de distinguirlo verbalmente de "árbol". [6] [7] [2]
Las aplicaciones comunes de los intentos incluyen almacenar un texto predictivo o un diccionario de autocompletar e implementar algoritmos de coincidencia aproximados, [8] como los que se usan en el software de revisión ortográfica y separación de sílabas [7] . Estas aplicaciones aprovechan la capacidad de un trie para buscar, insertar y eliminar entradas rápidamente. Sin embargo, si todo lo que se requiere es almacenar palabras del diccionario (es decir, no es necesario almacenar metadatos asociados con cada palabra), un autómata de estado finito acíclico determinista mínimo (DAFSA) o un árbol radixusaría menos espacio de almacenamiento que un trie. Esto se debe a que los árboles DAFSA y radix pueden comprimir ramas idénticas del trie que corresponden a los mismos sufijos (o partes) de diferentes palabras almacenadas.
