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.
No comments:
Post a Comment