Ver el código de «Trie»

[[Archivo:trie example.svg|thumb|right|250px|Un trie de las claves "A", "to", "tea", "ted", "ten", "i", "in", y "inn"]]
Introducidos en 1959 independientemente  por [[Rene de la Briandais]]<ref>Rene de la Briandais, "File searching using variable length keys". In Proceedings of the Western Joint Computer Conference, pages 295-298, 1959</ref> y [[Edward Fredkin]],<ref>E. Fredkin, "Trie Memory" Comm. ACM 3 pp. 490-499 (1960).</ref> un '''trie''' es una [[estructura de datos]] de tipo [[Árbol (programación)|árbol]] que permite la recuperación de información (de ahí su nombre del [[Idioma inglés |inglés]] re'''TRIE'''val). La información almacenada en un trie es un conjunto de claves, donde una clave es una secuencia de símbolos pertenecientes a un alfabeto. Las claves son almacenadas en las hojas del árbol y los nodos internos son pasarelas para guiar la búsqueda. El árbol se estructura de forma que cada letra de la clave se sitúa en un nodo de forma que los hijos de un nodo representan las distintas posibilidades de símbolos diferentes que pueden continuar al símbolo representado por el nodo padre. Por tanto la búsqueda en un trie se hace de forma similar a como se hacen las búsquedas en un diccionario:

:Se empieza en la raíz del árbol. Si el símbolo que estamos buscando es A entonces la búsqueda continúa en el subárbol asociado al símbolo A que cuelga de la raíz. Se sigue de forma análoga hasta llegar al nodo hoja. Entonces se compara la cadena asociada al nodo hoja y si coincide con la cadena de búsqueda entonces la búsqueda ha terminado en éxito, si no entonces el elemento no se encuentra en el árbol.

Por eficiencia se suelen eliminar los nodos intermedios que sólo tienen un hijo, es decir, si un nodo intermedio tiene sólo un hijo con cierto carácter entonces el nodo hijo será el nodo hoja que contiene directamente la clave completa.

Es muy útil para conseguir búsquedas eficientes en repositorios de datos muy voluminosos. La forma en la que se almacena la información permite hacer búsquedas eficientes de cadenas que comparten prefijos.

== Definición formal ==
Un trie es un caso especial de [[autómata finito#Autómatas finitos deterministas|autómata finito determinista]] (S, Σ, T, s, A) llamado autómata finito determinista acíclico AFDA, que sirve para almacenar un conjunto de cadenas <math>E</math> en el que:
* <math>\Sigma</math> es el [[alfabeto]] sobre el que están definidas las cadenas;
* <math>S</math>, el conjunto de estados, cada uno de los cuales representa un prefijo de <math>E</math>;
* La función de transición: <math>T : S \times  \Sigma \to \mathcal S</math>; está definida como sigue: <math>T(x,\sigma)=x\sigma</math> si <math>x, x\sigma \in S</math>, e indefinida en otro caso;
* El estado inicial <math>s</math> corresponde a la cadena vacía <math>\lambda</math>;
* El conjunto de estados de aceptación <math>A \subseteq S</math> es igual a <math>E</math>.

== Ventajas ==
Las ventajas principales de los '''tries''' sobre los [[Árbol binario de búsqueda|árboles de búsqueda binaria (BST)]] son:
* búsqueda de claves más rápida. La búsqueda de una clave de longitud <math>m</math> tendrá en el peor de los casos un coste de <math>O(m)</math>. Un [[Árbol binario de búsqueda|BST]] tiene un coste de <math>O(mlog n)</math>, siendo n el número de elementos del árbol, ya que la búsqueda depende de la profundidad del árbol, logarítmica con el número de claves.
* menos espacio requerido para almacenar gran cantidad de cadenas pequeñas, puesto que las claves no se almacenan explícitamente
* mejor funcionamiento para el [[algoritmo de búsqueda]] del prefijo más largo

== Aplicaciones ==
Como sustitución de otras estructuras de datos

=== Como sustitución de una Tabla hash ===
Un Trie puede usarse para reemplazar una [[Tabla hash]], sobre la que presenta las siguientes ventajas:
* el tiempo de búsqueda en una Tabla hash imperfecta es del orden de <math>O(n)</math>, mientras que en un ''trie'' es del orden de <math>O(l)</math>, para l el número de niveles del trie. Esto es debido a las [[Tabla hash#Resoluci.C3.B3n de colisiones|colisiones de claves]].
* en un ''trie'' no se producen colisiones de claves
* no hay que definir una función de hash, o modificarla si añadimos más claves
* los contenedores que almacenan distintos valores asociados a una única clave sólo son necesarios si tenemos más de un valor asociada a una única clave. En una tabla hash siempre se necesitan estos contenedores para las colisiones de clave
* un ''trie'' puede proporcionarnos un ordenamiento alfabético de las entradas por clave

Las principales desventajas de los ''tries'' respecto a las tablas hash son:
* en determinados casos pueden ser más lentos que las tablas hash en la búsqueda de datos, especialmente si los datos son consultados desde dispositivos de almacenamiento secundario, como disco duro, donde el tiempo de acceso es elevado con respecto a memoria principal
* no es sencillo representar todas las claves como cadenas, como los números reales, que pueden tener distintas representaciones en forma de cadena para un mismo número, p.ej. 1, 100, 1.000, +1.000,...
* a menudo los ''tries'' son más ineficientes respecto al espacio que las tablas hash
* los ''tries'' no suelen estar disponibles con las herramientas de desarrollo software, todo lo contrario que las tablas hash

=== Como representación de diccionarios ===
Una aplicación frecuente de los ''tries'' es el almacenamiento de diccionarios, como los que se encuentran en los teléfonos móviles. Estas aplicaciones se aprovechan de la capacidad de los ''tries'' para hacer búsquedas, inserciones y borrados rápidos. Sin embargo, si sólo se necesita el almacenamiento de las palabras (p.ej. no se necesita almacenar información auxiliar de las palabras del diccionario) un autómata finito determinista acíclico mínimo usa menos espacio que un ''trie''.

Los ''tries'' también son útiles en la implementación de algoritmos de correspondencia aproximada, como los usados en el software de corrección ortográfica.

=== Algoritmos ===
El siguiente [[pseudocódigo]] determina si una cadena representa un ''trie''.

 function find(node, key) {
   if (key is an empty string) {  # base case
     return is node terminal?
   } else {  # recursive case
     c = first character in key  # this works because key is not empty
     tail = key minus the first character
     child = node.children[c]
     if (child is null) {  # unable to recurse, although key is non-empty
       return false
     } else {
       return find(child, tail)
     }
   }
 }

Nota: <code>children</code> es un array con los hijos del nodo; y un nodo terminal es aquel que contiene una palabra válida.

=== Ordenamiento ===
El [[orden lexicográfico]] de un conjunto de claves se puede realizar con un algoritmo simple basado en ''tries'' de la siguiente forma:
* insertar todas las claves en el ''trie''
* obtener todas las claves mediante un recorrido en pre-orden, para obtener un ordenamiento lexicográfico en orden ascendente; o mediante un recorrido en post-orden, para obtener un ordenamiento lexicográfico en orden descendente. El recorrido en pre-orden y el recorrido en post-orden son [[Árbol_binario#Recorridos_sobre_.C3.A1rboles_binarios|algoritmos de búsqueda en profundidad en árboles]].

== Referencias ==
{{listaref}}
* Hosam Mahmoud Mahmoud, "Evolution of random search trees". Ed. Wiley 1992

== Enlaces externos ==
*[https://web.archive.org/web/20160916103018/http://www.tecnohobby.net/ppal/index.php/programacion/java/35-solucionador-de-puzzles-usando-arboles-trie-trie-trees-o-prefix-trees ''- Implementación en Java para buscar palabras de un diccionario en una matriz]

{{Control de autoridades}}
[[Categoría:Árboles (estructura)]]
[[Categoría:Lenguajes formales]]