Trie Tree Algoritham
Tries are an extremely special and useful data-structure that are based on the prefix of a string. They are used to represent the “Retrieval” of data and thus the name Trie.
The strings can essentially be viewed as the most important and common topics for a variety of programming problems. String processing has a variety of real world applications too, such as:
- Search Engines
- Genome Analysis
- Data Analytics
Inserting and search elements
Trie is an efficient information reTrieval data structure. It using Trie, search complexities can be brought to optimal limits (key length).
If we will store keys in binary search tree, a well balanced BST will need time proportional to M * log N, where M is maximum of string length and N is number of keys in tree. Using Trie, we can search the key in O(M) time.
However the penalty is on Trie storage requirements (Please refer Applications of Trie for more details)
The prefix of a string is nothing but any number N letters N<_|S| that can be considered beginning of strictly from the starting of a string.
EX: The words “abacaba” has been following prefixes:
Each node consists of at max 26 children and edges connect each parent node to its children. These 26 pointers are nothing but pointers for each of the 26 letters of the English alphabet A separate edge is maintained for every edge.
Strings are stored in a top to bottom manner on the basis of their prefix in a trie. All prefixes of length 1 are stored at until level 1, all prefixes of length 2 are sorted at until level 2.
This is pseudo code for insertion of a string:
void insert(String s)
for(every char in string s)
if(child node belonging to current char is null)
child node=new Node();
/ \ \
t a b
| | |
h n y
| | \ |
e s y e
/ | |
i r w
| | |
r e e
This data structure is used to store Strings and search strings, String stored can also be deleted.
- Key may not be there in tries. Delete operation should not modify tries.
- Key present as unique key (no part of key contains another key (prefix), nor the key itself is prefix of another key in trie). Delete all the nodes.
- Key is prefix key of another long key in trie. Unmark the leaf node.
- Key present in tries, having at least one other key as prefix key. Delete nodes from end of key until first leaf node of longest prefix key.
HOW TO USE NODE JS
To use the Trie, install and save it to your package dependencies:
Each branch in the tree represents a single character which allows for fast and efficient depth-first searching.
EX: we have a dictionary with the words: CAR, CAT and CURL. We can visualise the trie
npm install trie-prefix-tree –save
To create a new Trie:
var trie = require(‘trie-prefix-tree’);
// using ES2015 Modules
import trie from ‘trie-prefix-tree’;