Diferencia entre revisiones de «Trie»
Contenido eliminado Contenido añadido
Sin resumen de edición |
mSin resumen de edición |
||
Línea 1:
[[Image:trie example.svg|thumb|right|250px|Un trie de las claves "A", "to", "tea", "ted", "ten", "i", "in", and "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 Fredking]]<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 a el nodo hoja y si coincide con la cadena de búsqueda entonces la búsqueda a terminado en éxito, si no entonces el elemento no se encuentra en el árbol.
| |||