I was going through data structures and came across TRIE ( prefix tree ) (I don’t know much about it except for the fact that it is used for fast searching of stings and used in auto completion).
So I went through it’s wiki page, few tutorials (like one on TopCoder here ) but could not get what exactly it is.
I searched the discussion forum here on CodeChef but could not find a question with a tag trie
I wanted a basic knowledge like why is it needed, how is it different from normal trees, its construction and the searching process. I am more interested in how is it constructed and how do we take advantage of the structure of the trie in searching for a string.
So any help is welcomed and would be really appreciated, since I really want to know about Trie.
And there will be many more CodeChef users who would like to know about this advanced data structure and any help would be really beneficial for novice coder like me to grow.
EDIT : Adding links in the question so that they can be referenced quickly
The trie is also at the heart of one of the fastest known sorting algorithms: Burstsort. The implementation involves building a trie and then traversing it depth-first. It’s speed is attained from it’s cache-efficient properties. See: http://goanna.cs.rmit.edu.au/~jz/fulltext/acsc03sz.pdf