Trie data structure

Standard trie for a set of strings S in a tree such that,

1.   Each node other than root is labeled with a character

2.   The children of a tree are alphabetically ordered

3.   The path from external node to root yields a string.

Let’s say I had sample data like S = {stock ,bear, bid, bell, buy, bull, sell, stop}

Trie looks like below.

 

Suppose if you want to construct a trie for English dictionary, then root node of trie has 26 children, where each child node represents an alphabet and each child has at most 26 children again.

Let’s see the time complexity of trie data structure.

W : Total size of the strings in set S.

m : Size of the string involved in operation.

d : alphabet size (If you want to construct trie for English language, then d is 26).

For the above notations:

Space complexity in worst case is : O(W)

To insert, remove, search: O(md)

Applications

1.   You can find a word in proportional time to the size of the word.

2.   Used for prefix matching: If you want to find all the words where prefix is “st”, you can get {stock, stop} in above data.

Note:

The main problem with trie is, space it is consuming. We can address this problem with compressed trie.

Prevoius                                                 Next                                                 Home