Trie

ubergeekspot

Today we’ll see our first Data Structure concept called Trie (Infix of Retrieval).
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. Moreover the data structure such as Hash table or Set are used to search for the string in O(N*L) time, where N is the No of Records and L is the string length. Can we do better than this? Yes the answer is Trie Data Structure. How can we do this? The answer is obvious, Chuck the Memory! We have lots of it! Trade it for Speed! The Trie Data Structure is used to search if a string is present in the dictionary or not in O(L) time where L is the…

View original post 80 more words

Advertisements
Standard

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s