A trie is a tree-like data structure in which every node stores a character. A tire can store one or multiple words. After building a trie, strings or substrings can be retrieved by traversing down a path (a branch) of the trie. Tries are used to find substrings, autocomplete and many other string operations. In this post, the data structure to store child nodes is a hash map.
Why is a hash map used in a trie node?
In a trie, each trie node might have multiple branches. So a data structure is used to point to next nodes in branches. The data structure can be an array, a linked list or a hash map. When the data structure is a hash map, the next character stored in the current node is used as the key to find the node to hold the next character in the branch. Using a hash map is the best of three implementations since its put and get operations take O(1) time.
Table of Content
- Map of trie implementations
- Define classes
- Insert a word
- Delete a word
- Search a word
- Print all words in trie
- Free download
Map of trie implementations
Part 1 – trie implementation using array
Part 2 – trie implementation using linked list
Part 3 – trie implementation using hash map
Define classes in trie implementation
Like building a tree, you need to define a TrieNode class before a Trie class. A TrieNode class has three variables: data stores a character. children is a data structure that points to child nodes (branches). Here the data structure is hash map. isEnd is to mark whether this is the last node in the branch. In Trie class, there is one variable root. The operation of insertion, search or deletion always starts from root.
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
public class TrieMap { static class TrieNode { char data; HashMap<Character, TrieNode> children = new HashMap<>(); boolean isEnd = false; //Constructor, Time O(1), Space O(1) TrieNode(char c) { this.data = c; } } static class Trie { TrieNode root = new TrieNode(' '); } |
Javascript
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
class TrieNode { //Constructor, Time O(1), Space O(1) constructor(c) { this.data = c; this.isEnd = false; this.children = new Map(); //map } } class Trie { //Constructor, Time O(1), Space O(1) constructor() { this.root = new TrieNode(''); } } |
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 |
class TrieNode: #constructor, Time O(1) Space O(1) def __init__(self, c): self.data = c self.isEnd = False self.children = {} #map class Trie: #constructor, Time O(1) Space O(1) def __init__(self): self.root = TrieNode('') |
Insert a word in trie implementation
To insert a word, first check whether the word is in the trie so that you don’t insert a duplicate word. Then loop through each character in the word. Create a node to store the next character. Use the next character as the key and the new node as the value to create an entry. Store the new entry in the current node’s children. Then move to the child node. When the node is at the last character of the word, you mark the node‘s isEnd to be true.
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
//Add a word to trie, Iteration, Time O(s), Space O(s), s is word length void insert(String word) { if (search(word) == true) { System.out.println(word + " is already in trie."); return; } TrieNode node = root; for (char ch : word.toCharArray()) { if (!node.children.containsKey(ch)) node.children.put(ch, new TrieNode(ch)); node = node.children.get(ch); } node.isEnd = true; } |
Javascript
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
//inserts a word into the trie. Time O(s), Space O(s), s is word length insert (word) { if (this.search(word) == true) { System.out.println(word + " is already in trie."); return; } var node = this.root; for (let ch of word) { if (!node.children.has(ch)) node.children.set(ch, new TrieNode(ch)); node = node.children.get(ch); } node.isEnd = true; } |
Python
|
1 2 3 4 5 6 7 8 9 10 11 |
#Add a word to trie, Time O(s) Space O(1), s is word length def insert(self, word): if self.search(word) == True: print(word + " is already in trie.") return node = self.root for ch in word: if not ch in node.children: node.children[ch] = TrieNode(ch) node = node.children[ch] node.isEnd = True |
Doodle
Delete a word
To delete a word from a trie, first check whether the word exists in the trie. If not, the method can return. The same as insertion, loop through each character in the word. A pointer node starts from root. If the character is not in the node‘s children, the method returns directly. Otherwise, the node moves to the child node. When the node is at the last character of the word, mark the node‘s isEnd to be false.
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
//Remove a word from trie, Iteration, Time O(s), Space O(1), s is word length void delete(String word) { if (this.search(word) == false) { System.out.println(word + " does not exist in trie."); return; } TrieNode node = root; for (char ch : word.toCharArray()) { if (!node.children.containsKey(ch)) return; node = node.children.get(ch); } node.isEnd = false; } |
Javascript
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
//Remove a word from trie, Iteration, Time O(s), Space O(1), s is word length delete(word) { if (this.search(word) == null) { console.log(word + " does not exist in trie."); return; } let node = this.root; for (let ch of word) { if (!node.children.has(ch)) return; node = node.children.get(ch); } node.isEnd = false; } |
Python
|
1 2 3 4 5 6 7 8 9 10 11 |
#Remove a word from trie, Iteration, Time O(s), Space O(1), s is word length def delete(self, word) : if self.search(word) == False: print(word + " does not exist in trie.") return node = self.root for ch in word: if not ch in node.children: return node = node.children.get(ch) node.isEnd = False |
Search a word
To search a word in a trie, loop through each character in the word. A pointer node starts from root. If the character is not in the node‘s children, the method returns false. Otherwise, the node moves to the child node. When the node is at the last character of the word, return the node‘s isEnd value, which can be true or false (deleted).
Java
|
1 2 3 4 5 6 7 8 9 10 |
//Search a word in trie, Iteration, Time O(s), Space O(1), s is word length boolean search(String word) { TrieNode node = root; for (char ch : word.toCharArray()) { if (!node.children.containsKey(ch)) return false; node = node.children.get(ch); } return node.isEnd; } |
Javascript
|
1 2 3 4 5 6 7 8 9 10 |
//Search a word in trie, Iteration, Time O(s), Space O(1), s is word length search(word) { let node = this.root; for(let ch of word) { if (!node.children.has(ch)) return false; node = node.children.get(ch); } return node.isEnd; } |
Python
|
1 2 3 4 5 6 7 8 |
#Search a word in trie, Iteration, Time O(s), Space O(1), s is word length def search(self, word): node = self.root for ch in word: if not ch in node.children: return False node = node.children.get(ch) return node.isEnd |
Print all words in trie
To print all words in a trie, recursion is used to traverse all nodes in the trie. This is similar to preorder (DFS, depth first search) of a tree. When visiting the node, the method concatenates characters from previously visited nodes with the character of the current node. When the node‘s isEnd is true, the recursion reaches the last character of the word, and add the word to the result list.
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
//Print all words in trie, call recursion function //Time O(n), Space O(n), n is number of nodes in trie void print() { List<String> res = new ArrayList<String>(); helper(root, res, ""); System.out.println(res); } //recursive function, Time O(n), Space O(n), n is number of nodes in trie void helper(TrieNode node, List<String> res, String prefix) { if (node.isEnd) { String word = prefix + node.data; res.add(word.substring(1)); //skip the first space from root } for (Character ch : node.children.keySet()) helper(node.children.get(ch), res, prefix + node.data); } |
Javascript
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
//Print all words in trie, call recursion function //Time O(n), Space O(n), n is number of nodes in trie print() { let res = []; this.helper(this.root, res, ""); console.log(res); } //recursion function, Time O(n), Space O(n), n is number of nodes in trie helper (node, arr, perfix) { if (node.isEnd) arr.push(perfix + node.data); for (let c of node.children.keys()) this.helper(node.children.get(c), arr, perfix + node.data); } |
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
#Print all words in trie, call recursion function #Time O(n), Space O(n), n is number of nodes in trie def print (self) : res = [] self.helper(self.root,res, "") print(res) #recursion function, Time O(n), Space O(n), n is number of nodes in trie def helper(self, node, res, prefix): if node.isEnd: res.append(prefix + node.data) for child in node.children.values(): self.helper(child, res, prefix + node.data) |
Free download
Download trie implementation using hashmap in Java, JavaScript and Python
Data structures introduction PDF