Home > Linked List, Overview, Tree, Trie > Tries (Overview)

Tries (Overview)

What is it? Trie? Did you mean “Tree”? No! I meant “Trie”. It is a data structure (also known as “prefix tree”) that is used in form of a dictionary. It is basically a way of representing data. I don’t think I can explain this without an example. So here we see the way to represent two words in English language using a trie. Shrey and Shayne.

As you can see, a trie gives us words with the same prefixes. In this example, “SH”. So that is how you represent words. You can do the same for numbers (in any format – binary, decimal, etc). Also, note that both have different “Y” nodes because a trie represents words on the base of prefixes. If we associate a count with each node, we can also tell the number of words starting with a particular prefix.

Please note that the insertion in a trie takes O(length) time where length is that of the word being inserted. We can create a trie for english language using a structure with information and 26 pointers for the corresponding letters. Easy, eh?

So a trie can be of many uses. In the next post, we’ll see an example of using Trie. 🙂

PS : For more information on Tries, visit http://en.wikipedia.org/wiki/Trie

PPS : Sorry for the long hiatus in posting!

Advertisements
  1. February 4, 2012 at 12:01 am

    A trie is just a fancy term for a finite state machine. 😛

  1. No trackbacks yet.

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

%d bloggers like this: