Exploring Trie Data Structure in JavaScript
Trie, also known as a prefix tree, is a tree-like data structure that is commonly used to store and retrieve a dynamic set of strings. It offers efficient insertion, deletion, and search operations for strings, making it a popular choice in various applications such as autocomplete systems and spell checkers.
Let's delve into implementing a Trie data structure in JavaScript:
Trie Implementation
class Node {
constructor() {
this.children = {};
this.endWord = false;
}
}
class Trie {
constructor() {
this.root = new Node();
}
// Insertion Operation
insert(word) {
let node = this.root;
for (let i = 0; i < word.length; i++) {
let ch = word[i];
if (!node.children[ch]) {
node.children[ch] = new Node();
}
node = node.children[ch];
}
node.endWord = true;
}
// Searching Operation
search(word) {
let node = this.root;
for (let i = 0; i < word.length; i++) {
let ch = word[i];
if (!node.children[ch]) {
return false;
}
node = node.children[ch];
}
return node.endWord;
}
// Deletion Operation
delete(word) {
this._delete(this.root, word, 0);
}
_delete(node, word, index) {
if (index === word.length) {
if (!node.endWord) {
return false;
}
node.endWord = false;
return !Object.keys(node.children).length === 0;
}
let ch = word[index];
let chNode = node.children[ch];
if (chNode == null) {
return false;
}
let shouldDeleteCurrentNode = this._delete(chNode, word, index + 1);
if (shouldDeleteCurrentNode) {
delete node.children[ch];
}
return !Object.keys(node.children).length;
}
// Finding Words with Prefix
findWordWithPrefix(prefix) {
let node = this.root;
for (let ch of prefix) {
if (!node.children[ch]) {
return [];
}
node = node.children[ch];
}
return this.findAllWords(node, prefix);
}
findAllWords(node, prefix) {
let words = [];
if (node.endWord) {
words.push(prefix);
}
for (let ch in node.children) {
words.push(...this.findAllWords(node.children[ch], prefix + ch));
}
return words;
}
// Finding Longest Word
findLongestWord() {
return this.findLongest(this.root, "");
}
findLongest(node, word) {
let longestWord = node.endWord ? word : "";
for (let ch in node.children) {
let childLongestWord = this.findLongest(node.children[ch], word + ch);
if (childLongestWord.length > longestWord.length) {
longestWord = childLongestWord;
}
}
return longestWord;
}
}
// Usage Example
const t = new Trie();
t.insert("apple");
t.insert("applecyder");
t.insert("orange");
console.log(t.search("apple")); // Output: true
t.delete("apple");
console.log(t.search("apple")); // Output: false
console.log(t.findWordWithPrefix("app")); // Output: ["applecyder"]
console.log(t.findLongestWord()); // Output: "applecyder"
Conclusion
In conclusion, Trie data structure proves to be an efficient solution for storing and managing collections of strings. While insertion and searching operations are straightforward, deletion can be a bit more challenging due to the need for node traversal. Nonetheless, Tries offer immense value, especially in scenarios where fast prefix-based searches or autocomplete functionalities are required.
For a deeper understanding and to explore the implementation details, you can find the complete code in my GitHub repository:
GitHub Repository: Trie Data Structure
Feel free to experiment with this implementation and incorporate it into your projects for enhanced string manipulation capabilities.
Happy coding!
Top comments (0)