Understanding Trie and its applications

general
, ,
1

Hey folks.

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.

Thanks.

EDIT : Adding links in the question so that they can be referenced quickly

Some problems related to Tries:

8 Likes
2

You will find trie structures at the heart of many bioinformatic applications ( DNA sequen alignment, etc ). See: http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=89F5C5F504C452DFA838F1E4AD659D7C?doi=10.1.1.57.2897&rep=rep1&type=pdf

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

Problem On codechef-> http://www.codechef.com/problems/EST
Problem On spoj ->http://www.spoj.com/problems/PHONELST/

For Tutorial see Topcoder Tutorial-> http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=usingTries

8 Likes
3

@chandan11111 nice links

4

@chandan11111 Thanks for all those links.

I had already gone through the TopCoder link, but by posting it here it will definitely help other users.

But if you could please explain the construction and the searching phase of the Trie, it would be more helpful.

Thanks anyways.

5

thank you @hardworkpays :slight_smile:

1 Like
6

@viaan read this very helpful hope this help !!

implementation of trie.

3 Likes
7

Another set of useful links for Trie

insertion and search http://www.geeksforgeeks.org/trie-insert-and-search
and Deletion : http://www.geeksforgeeks.org/trie-delete

Very simple explanation and implementation.

As @chandan11111 has provided with the link http://simplestcodings.blogspot.in/2012/11/trie-implementation-in-c.html It is explained there with great detail with the help of figures.

Thanks @chandan11111 for your help.

Looking forward to solve some problems on Trie.

3 Likes
8

@chandan11111 Thank you very much :). was of great help!!!

9

pleasure is mine bro :slight_smile:

10

@chandan11111 Infact I should thank you for the links. Thank you.

1 Like
11

maybe this lecture will help you

1 Like
12

@n1tz53 thanks

13

another question which can be solved by implementing trie( not necessarily) is 1.

1 Like
14

These Lectures on Algorithm from IIT Delhi are Best