Trie Data structure

Refer : http://linux.thai.net/~thep/datrie/datrie.html


 "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.

Refer for java program : http://www.technicalypto.com/2010/04/trie-data-structure-part-2-node-and.html

http://flexaired.blogspot.com/2009/12/flex-email-client-for-google-app-engine_13.html

http://www1bpt.bridgeport.edu/~dichter/cs201/Trie.Handout.doc



Q)best way , Memory-wise, to store 10 Crores mobile numbers ?
a trie can be considered as a tree with 26 child nodes, i.e. from 'a' to 'z'....where each node consists of a character.E.g. to represent sachin, we create a trie which has s->a->c->h->i->n,  i.e. 6 nodes. Now when we want to add sachim into the database, we just create another child node of i, which would be m. Now there are two nodes going out from i.This way we keep on adding nodes as and when required. Now to detect each word, we end the word with a spl character, which will be inserted after the last child node so that whenever we  encounter that character, we know that we have reached the end of a word.


Trie is better in terms of scalability and performance.With Hashtable,There is a problem of rehashing when all buckets are full and rehashing takes O(N).Although it happens once in a blue moon.That can impact the performance in a production environment.Trie doesn't have this problem. 
http://www.youtube.com/watch?v=uhAUk63tLRM