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)