ATrie is a tree-like data structure that is used for efficiently storing and searching strings, especially in applications like autocomplete, spell checking, and IP routing.
Key Properties of a Trie:
- Nodes: Each node represents a character.
- Root: The root node is empty and serves as the starting point.
- Children: Each node has up to 26 children (for lowercase English letters) or more, depending on the character set.
- End-of-Word Marker: Some nodes are marked to indicate the end of a word.
Basic Trie Operations:
1.Insertion
Inserting a word involves traversing the trie and creating new nodes for characters that don’t exist.
2.Search
Search checks whether a word exists in the trie by traversing its nodes.
3.Prefix Search
This checks whether any word in the trie starts with a given prefix.
Implementation of Basic Trie in #"apple");console.log(trie.search("apple"));// trueconsole.log(trie.search("app"));// falseconsole.log(trie.startsWith("app"));// truetrie.insert("app");console.log(trie.search("app"));// true
Advanced Trie Operations:
1.Delete a Word:
Deleting a word involves a recursive approach, where we remove nodes that are no longer needed.
delete(word,node=this.root,depth=0){if(depth===word.length){if(!node.isEndOfWord)returnfalse;// Word doesn't existnode.isEndOfWord=false;returnObject.keys(node.children).length===0;// Check if node has children}constchar=word[depth];if(!node.children[char])returnfalse;constshouldDeleteChild=this.delete(word,node.children[char],depth+1);if(shouldDeleteChild){deletenode.children[char];returnObject.keys(node.children).length===0&&!node.isEndOfWord;}returnfalse;}2.Count Words with a Prefix:
Count how many words start with a given prefix.
countWordsWithPrefix(prefix){letnode=this.root;for(letcharofprefix){if(!node.children[char])return0;node=node.children[char];}returnthis._countWords(node);}_countWords(node){letcount=node.isEndOfWord?1:0;for(letcharinnode.children){count+=this._countWords(node.children[char]);}returncount;}3.Autocomplete Suggestions:
Given a prefix, return all words that start with it.
getWordsWithPrefix(prefix){letnode=this.root;for(letcharofprefix){if(!node.children[char])return[];node=node.children[char];}returnthis._collectWords(node,prefix);}_collectWords(node,prefix){letresults=[];if(node.isEndOfWord)results.push(prefix);for(letcharinnode.children){results=results.concat(this._collectWords(node.children[char],prefix+char));}returnresults;}Time Complexity:
- Insert: O(L) (L = length of the word)
- Search: O(L)
- Prefix Search: O(L)
- Delete: O(L)
Applications of Trie:
- Autocomplete Systems (e.g., search bars, text editors).
- Spell Checkers.
- IP Routing (longest prefix matching).
- Word Games (e.g., Boggle).
- DNA Sequence Matching.
Top comments(0)
Subscribe
For further actions, you may consider blocking this person and/orreporting abuse
