Menu
I am looking for a good introduction/tutorial on Tries.
Most of the links I find googling are either too succint and abstract for me or too trivial.
Could someone please provide a good reference with examples in Java for me to study?
Thanks
606
For example, if we assume that all strings are formed from the letters 'a' to 'z' in the English alphabet, each trie node can have a maximum of 26 points. Trie is also known as the digital tree or prefix tree. The position of a node in the Trie determines the key with which that node is connected.
A trie is a tree-like data structure whose nodes store the letters of an alphabet. By structuring the nodes in a particular way, words and strings can be retrieved from the structure by traversing down a branch path of the tree. Tries in the context of computer science are a relatively new thing.
Tries are an extremely special and useful data-structure that are based on the prefix of a string. They are used to represent the “Retrieval” of data and thus the name Trie. A Trie is a special data structure used to store strings that can be visualized like a graph.
In a trie indexing an alphabet of 26 letters, each node has 26 possible children and, therefore, 26 possible pointers. Each node thus features an array of 26 (pointers to) sub-trees, where each value could either be null (if there is no such child) or another node.
Googling found this blog with a series of articles in Java.
But I'd recommend buying a text book. Lots of Java oriented books on Data Structures and Algorithms are available from your favourite online bookstore.
196
I've recently coded up a Trie and Patricia Trie in Java. They are written to be easy to follow. All the data structures were built from their Wikipedia descriptions.
Related classes: Radix Trie, Suffix Trie, Trie Map.
If you have any questions, feel free to ask.
1
Sure, have a look at Steve Hanov's site, like Fast and Easy Levenshtein distance using a Trie.
1
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
