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:

10 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-> EST Problem - CodeChef
Problem On spoj → SPOJ.com - Problem PHONELST

For Tutorial see Topcoder Tutorial-> Topcoder

11 Likes
3

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

1 Like
4

@viaan read this very helpful hope this help !!

implementation of trie.

4 Likes
5

Another set of useful links for Trie

insertion and search Trie | (Insert and Search) - GeeksforGeeks
and Deletion : Trie | (Delete) - GeeksforGeeks

Very simple explanation and implementation.

As @chandan11111 has provided with the link Simplest Codings: Trie implementation in C 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.

4 Likes
6

maybe this lecture will help you

1 Like
7

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

1 Like
8

@chandan11111 nice links

9

thank you @hardworkpays :slight_smile:

1 Like
10

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

11

pleasure is mine bro :slight_smile:

12

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

1 Like
13

@n1tz53 thanks

14

These Lectures on Algorithm from IIT Delhi are Best