Index
- Definition
- Time-Complexity
- Programmatic representation
- Operations
- Insertion
- Search/Auto-completion
Definition
- Trie comes from word reTrieval.
- Trie is a k-way tree DS.
- It is optimised for retrieval where string have common prefix which are store on common nodes.
Time Complexity
- It has time complexity of O(N) where N is the maximum length of string.
Programmatic representation
- A Node is represented as class having 2 things –
- children representing one of 26 characters for a node.
- isLastNode – representing last node of string.
class TrieNode{
//representing one of 26 characters of alphabet for a node
TrieNode children;
//representing last node of string.
boolean isLastNode;
TrieNode(){
children=new TrieNode[26];
isLastNode=false;
}
}
Trie Operation and applications:
Insertion :
class TrieNode{
TrieNode children;
boolean isLastNode;
TrieNode(){
children=new TrieNode[26];
isLastNode=false;
}
}
Class Trie{
TrieNode root;
Trie(){
root=new TrieNode();
}
public static void main(){
Trie trie=new Trie;
trie.insert("parag");
trie.insert("parameter");
trie.insert("parashoot");
trie.autocomplete("para");
}
private void insert(String word){
TrieNode current=root;
}
private void autoComplete(String prefix){
TrieNode current=root;
}
}
Techglot 