Trie

 Data structure - Trie

Introduction  - http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=usingTries

There are many algorithms and data structures to index and search strings inside a text, some of them are included in the standard libraries, but not all of them; the trie data structure is a good example of one that isn't.

Let word be a single string and let dictionary be a large set of words. If we have a dictionary, and we need to know if a single word is inside of the dictionary the tries are a data structure that can help us. But you may be asking yourself, "Why use tries if set <string> and hash tables can do the same?" There are two main reasons:

• The tries can insert and find strings in O(L) time (where L represent the length of a single word). This is much faster than set , but is it a bit faster than a hash table.
• The set <string> and the hash tables can only find in a dictionary words that match exactly with the single word that we are finding; the trie allow us to find words that have a single character different, a prefix in common, a character missing, etc.

The tries can be useful in TopCoder problems, but also have a great amount of applications in software engineering. For example, consider a web browser. Do you know how the web browser can auto complete your text or show you many possibilities of the text that you could be writing? Yes, with the trie you can do it very fast. Do you know how an orthographic corrector can check that every word that you type is in a dictionary? Again a trie. You can also use a trie for suggested corrections of the words that are present in the text but not in the dictionary.

e.g.  I just typed in "st" and Strings showed up. HashMap cannot do this because what I typed in is still not a full string.

Advantages of tries:

The basics:

• Predictable O(L) lookup time where L is the size of the key (String).
• Lookup can take less than k time if it's not there
• Supports ordered traversal
• No need for a hash function
• Deletion is straightforward