java - tries - trie traduccion

¿Hay un Trie en Java?

Question

Posible duplicado:
¿Dónde encuentro una implementación de mapa estándar basada en Trie en Java?

Quiero usar Trie en Java, ¿hay alguna implementación que pueda usar? (Intenté buscar uno pero no lo encontré).

Answer 1

No hay ninguna estructura de datos trie en las bibliotecas de Java centrales.

Esto puede deberse a que los intentos generalmente están diseñados para almacenar cadenas de caracteres, mientras que las estructuras de datos Java son más generales, generalmente contienen cualquier Object (que define la igualdad y una operación de hash), aunque a veces se limitan a objetos Comparable (que definen un orden). No hay una abstracción común para "una secuencia de símbolos", aunque CharSequence es adecuado para cadenas de caracteres, y supongo que podría hacer algo con Iterable para otros tipos de símbolos.

Aquí hay otro punto a considerar: al intentar implementar un trie convencional en Java, se enfrenta rápidamente al hecho de que Java es compatible con Unicode. Para tener algún tipo de eficiencia de espacio, debe restringir las cadenas en su conjunto a algún subconjunto de símbolos, o abandonar el enfoque convencional de almacenar nodos secundarios en una matriz indexada por símbolo. Esta podría ser otra razón por la que los intentos no se consideran lo suficientemente generales como para incluirlos en la biblioteca central, y es algo que debe tener en cuenta si implementa uno propio o utiliza una biblioteca de terceros.