C'è un Trie in Java?

Question

Eventuali duplicati:
Where do I find a standard Trie based map implementation in Java?

voglio usare Trie in Java, c'è un'implementazione che posso usare? (Ho provato a cercarne uno ma non l'ho trovato).

Answer 1

Non esiste una struttura dati trie nelle librerie Java core.

Ciò può essere dovuto tentativi sono generalmente progettati per memorizzare stringhe di caratteri, mentre le strutture di dati Java sono più generali, di solito ospitare ogni Object (che definisce l'uguaglianza e un'operazione di hash), anche se a volte sono limitati a Comparable oggetti (la definizione di un ordine). Non esiste un'astrazione comune per "una sequenza di simboli", sebbene lo CharSequence sia adatto per le stringhe di caratteri e suppongo che potresti fare qualcosa con Iterable per altri tipi di simboli.

Ecco un altro punto da considerare: quando si tenta di implementare un trie convenzionale in Java, si è rapidamente confrontati con il fatto che Java supporti Unicode. Per avere qualsiasi tipo di efficienza dello spazio, devi limitare le stringhe nel tuo trie a qualche sottoinsieme di simboli, o abbandonare l'approccio convenzionale di memorizzare i nodi figli in una matrice indicizzata dal simbolo. Questo potrebbe essere un altro motivo per cui i tentativi non sono considerati sufficientemente generici per l'inclusione nella libreria principale e qualcosa da tenere a mente se si implementa il proprio o si utilizza una libreria di terze parti.