The Trie Data Structure

A trie (pronounced like "try") is a tree structure for storing a set of
strings (like dictionaries) that come from an alphabet. However, unlike 
the typical tree structures that we've seen in class, a trie stores 
its data a little differently. Instead of storing a complete value, 
each internal node corresponds to a single letter of the alphabet. 
It may even contain nothing, and the the position of child in the list of 
children may implicitly give us the corresponding letter of alphabet. 
The leaves often contain data.

Here is an example: 
Assume alphabet is {a,b,c} then we will implicitly
assume the left child corresponds to letter a, the middle child to b, and the
right child to c. Then the following trie contains 6 strings (in the leaves) 
where x means null:

                          root
                       /    |    \
                     / | \  x   / | \
                     1 2  x    3  |  6
				 /|\
                                x 4 5
They are:
 1:aa
 2:ab
 3:ca
 4:cba
 5:cbc
 6:cc

Adding a string to a trie is fast by traversing the tree using its
letters. For example, if we want to add "acb" we start with its first letter
'a' (in the tree it's the left most child of root). 
then follow the branch using letter c (right of 2 in the diagram), 
we hit null so we create a new children array there:
                          root
                       /    |    \
                     / | \  x   / | \
                     1 2 |     3  |  6
			/|\      /|\
                       x x x     x 4 5

and now continue down for letter 'b' (the middle node),
since the string is just finished we create the leaf 7:
                          root
                       /    |    \
                     / | \  x   / | \
                     1 2 |     3  |  6
			/|\      /|\
                       x 7 x     x 4 5

Finding a string in the trie is easy, we just use the letter of 
the string one by one to go down the tree. If we hit a leaf when 
the string ends we have found the string otherwise (i.e. if we hit a 
null node or we hit a leaf but string isn't finished yet) it means it's 
not in the trie. 
For example, if you traverse the above trie using "ab" you hit the node 2 
when our string is also finished so it's there. But if you traverse the 
trie  with "accb", you hit a null in the node right of 7  and cannot continue 
so it's not in the trie. Similarly, if you traverse it with 
"aabba" you hit the leaf 1 but the string is not finished yet (the "bba" is left)
so it's not in the trie.

As you can see adding and fining is O(k) where k is the length of the string
which is often very short. 

One can store different information in a leaf. For example, in a dictionary we
can store the meaning of the corresponding word.