A prefix tree (Trie), also known as a dictionary tree or word lookup tree, is a tree-like data structure used for efficiently storing and retrieving keys in a set of strings. The prefix tree is particularly suitable for handling string-related problems, such as autocomplete, spell checking, and IP routing.
Basic Concepts of Prefix Trees
- Node Structure:
- Each node represents a character.
- The path from the root node to a specific node represents a prefix of a string.
- Nodes typically include:
- A mapping of child nodes (usually implemented with an object or Map).
- A boolean flag indicating whether the node marks the end of a word.
- Characteristics:
- The root node does not contain a character.
- The path from the root to any node forms a prefix of a string.
- Strings with the same prefix share node paths.
- Time Complexity:
- Insertion: O(m), where m is the length of the string.
- Search: O(m).
- Deletion: O(m).
Implementation of Prefix Trees
Basic Implementation
class TrieNode {
constructor() {
this.children = {}; // Child node mapping
this.isEndOfWord = false; // Marks whether it is the end of a word
}
}
class Trie {
constructor() {
this.root = new TrieNode();
}
// Insert a word
insert(word) {
let node = this.root;
for (const char of word) {
if (!node.children[char]) {
node.children[char] = new TrieNode();
}
node = node.children[char];
}
node.isEndOfWord = true;
}
// Search for a complete word
search(word) {
let node = this.root;
for (const char of word) {
if (!node.children[char]) {
return false;
}
node = node.children[char];
}
return node.isEndOfWord;
}
// Check if a prefix exists
startsWith(prefix) {
let node = this.root;
for (const char of prefix) {
if (!node.children[char]) {
return false;
}
node = node.children[char];
}
return true;
}
}
// Usage example
const trie = new Trie();
trie.insert("apple");
console.log(trie.search("apple")); // true
console.log(trie.search("app")); // false
console.log(trie.startsWith("app")); // true
trie.insert("app");
console.log(trie.search("app")); // true
Optimized Implementation (Supporting Deletion)
class TrieNode {
constructor() {
this.children = {};
this.isEndOfWord = false;
this.count = 0; // Tracks the number of words passing through this node (for deletion optimization)
}
}
class Trie {
constructor() {
this.root = new TrieNode();
}
insert(word) {
let node = this.root;
for (const char of word) {
if (!node.children[char]) {
node.children[char] = new TrieNode();
}
node = node.children[char];
node.count++;
}
node.isEndOfWord = true;
}
search(word) {
let node = this._searchPrefix(word);
return node !== null && node.isEndOfWord;
}
startsWith(prefix) {
return this._searchPrefix(prefix) !== null;
}
_searchPrefix(prefix) {
let node = this.root;
for (const char of prefix) {
if (!node.children[char]) {
return null;
}
node = node.children[char];
}
return node;
}
delete(word) {
const deleteHelper = (node, word, index) => {
if (index === word.length) {
if (!node.isEndOfWord) {
return false; // Word does not exist
}
node.isEndOfWord = false;
return Object.keys(node.children).length === 0;
}
const char = word[index];
if (!node.children[char]) {
return false; // Word does not exist
}
const shouldDeleteChild = deleteHelper(node.children[char], word, index + 1);
if (shouldDeleteChild) {
delete node.children[char];
return Object.keys(node.children).length === 0 && !node.isEndOfWord;
}
return false;
};
deleteHelper(this.root, word, 0);
}
// More precise deletion implementation (considering count)
deletePrecise(word) {
const deleteHelper = (node, word, index) => {
if (index === word.length) {
if (!node.isEndOfWord) {
return false;
}
node.isEndOfWord = false;
return node.count === 1; // Delete only when no other words pass through this node
}
const char = word[index];
if (!node.children[char]) {
return false;
}
const shouldDeleteChild = deleteHelper(node.children[char], word, index + 1);
if (shouldDeleteChild) {
delete node.children[char];
return node.count === 1 && !node.isEndOfWord;
}
node.count--;
return false;
};
// Update count first
let node = this.root;
for (const char of word) {
if (!node.children[char]) {
return false;
}
node = node.children[char];
}
// Reset count to 1 (since we are deleting the entire word)
let currentCount = 0;
const countHelper = (n, w, i) => {
if (i === w.length) {
n.count = 1;
return;
}
const c = w[i];
if (!n.children[c]) {
return;
}
countHelper(n.children[c], w, i + 1);
n.count = Object.values(n.children).reduce((sum, child) => sum + child.count, 0) + (n.isEndOfWord ? 1 : 0);
};
countHelper(this.root, word, 0);
deleteHelper(this.root, word, 0);
}
}
Supporting Fuzzy Search (Wildcards)
class TrieNode {
constructor() {
this.children = {};
this.isEndOfWord = false;
}
}
class Trie {
constructor() {
this.root = new TrieNode();
}
insert(word) {
let node = this.root;
for (const char of word) {
if (!node.children[char]) {
node.children[char] = new TrieNode();
}
node = node.children[char];
}
node.isEndOfWord = true;
}
search(word) {
return this._search(this.root, word, 0);
}
_search(node, word, index) {
if (index === word.length) {
return node.isEndOfWord;
}
const char = word[index];
if (char === '.') {
for (const childChar in node.children) {
if (this._search(node.children[childChar], word, index + 1)) {
return true;
}
}
return false;
} else {
if (!node.children[char]) {
return false;
}
return this._search(node.children[char], word, index + 1);
}
}
startsWith(prefix) {
let node = this.root;
for (const char of prefix) {
if (!node.children[char]) {
return false;
}
node = node.children[char];
}
return true;
}
}
// Usage example
const trie = new Trie();
trie.insert("apple");
console.log(trie.search("apple")); // true
console.log(trie.search("a.ple")); // false
console.log(trie.search(".pple")); // false
console.log(trie.search("a..le")); // false
trie.insert("app");
console.log(trie.search("app")); // true
console.log(trie.search("a..")); // false (requires more complex implementation)
Note: Fully supporting wildcard searches requires a more complex implementation, typically involving backtracking algorithms.
Applications of Prefix Trees
Autocomplete System
class AutocompleteSystem {
constructor() {
this.trie = new Trie();
this.currentInput = "";
}
insert(word, frequency = 1) {
// In practical applications, frequency information may need to be stored
this.trie.insert(word);
}
input(c) {
if (c === "#") {
this.trie.insert(this.currentInput);
this.currentInput = "";
return [];
}
this.currentInput += c;
const prefix = this.currentInput;
const matches = this._findMatches(prefix);
// Sort by frequency or other criteria
return matches.map(match => match.word);
}
_findMatches(prefix) {
let node = this.trie.root;
const results = [];
// First find the node at the end of the prefix
for (const char of prefix) {
if (!node.children[char]) {
return results;
}
node = node.children[char];
}
// Collect all words starting from this node
this._collectWords(node, prefix, results);
return results;
}
_collectWords(node, prefix, results) {
if (node.isEndOfWord) {
results.push({ word: prefix });
}
for (const char in node.children) {
this._collectWords(node.children[char], prefix + char, results);
}
}
}
Spell Checker
class SpellChecker {
constructor(dictionary) {
this.trie = new Trie();
dictionary.forEach(word => this.trie.insert(word));
}
check(word) {
return this.trie.search(word);
}
suggest(word) {
// Simple implementation - practical applications may require more complex algorithms
const suggestions = [];
this._generateSuggestions(this.trie.root, word, "", suggestions);
return suggestions;
}
_generateSuggestions(node, word, current, suggestions) {
if (word.length === 0 && node.isEndOfWord && current !== word) {
suggestions.push(current);
return;
}
if (word.length === 0) {
return;
}
const char = word[0];
if (node.children[char]) {
this._generateSuggestions(node.children[char], word.slice(1),
current + char, suggestions);
}
// Try replacing one character
if (word.length > 1) {
for (const c in node.children) {
if (c !== char) {
this._generateSuggestions(node.children[c], word.slice(1),
current + c, suggestions);
}
}
} else if (Object.keys(node.children).length > 0) {
// For single character, try all possible replacements
for (const c in node.children) {
this._generateSuggestions(node.children[c], "",
current + c, suggestions);
}
}
// Try inserting one character
if (word.length > 0) {
for (const c in node.children) {
this._generateSuggestions(node.children[c], word.slice(1),
current + char + c, suggestions);
}
} else {
for (const c in node.children) {
this._generateSuggestions(node.children[c], "",
current + c, suggestions);
}
}
// Try deleting one character
if (word.length > 1) {
this._generateSuggestions(node, word.slice(1),
current, suggestions);
}
}
}
Note: The suggest method of the spell checker above is relatively simple. In practical applications, more efficient algorithms like Levenshtein distance may be needed.
IP Routing Table
class RouteTrieNode {
constructor() {
this.children = {};
this.handler = null; // Route handler function
}
}
class Router {
constructor() {
this.root = new RouteTrieNode();
}
addRoute(path, handler) {
const parts = path.split('/').filter(part => part.length > 0);
let node = this.root;
for (const part of parts) {
if (!node.children[part]) {
node.children[part] = new RouteTrieNode();
}
node = node.children[part];
}
node.handler = handler;
}
findHandler(path) {
const parts = path.split('/').filter(part => part.length > 0);
let node = this.root;
for (const part of parts) {
if (!node.children[part]) {
return null;
}
node = node.children[part];
}
return node.handler;
}
}
// Usage example
const router = new Router();
router.addRoute('/home', () => 'Home Page');
router.addRoute('/about', () => 'About Page');
router.addRoute('/products', () => 'Products Page');
console.log(router.findHandler('/home')()); // Home Page
console.log(router.findHandler('/about')()); // About Page
console.log(router.findHandler('/contact')); // null
Predictive Text Input
class PredictiveText {
constructor(dictionary) {
this.trie = new Trie();
dictionary.forEach(word => this.trie.insert(word));
}
predict(prefix) {
let node = this.trie.root;
const results = [];
// Find the node at the end of the prefix
for (const char of prefix) {
if (!node.children[char]) {
return results;
}
node = node.children[char];
}
// Collect all possible words
this._collectWords(node, prefix, results);
return results;
}
_collectWords(node, prefix, results) {
if (node.isEndOfWord) {
results.push(prefix);
}
for (const char in node.children) {
this._collectWords(node.children[char], prefix + char, results);
}
}
}
// Usage example
const dict = ['apple', 'app', 'application', 'banana', 'ball', 'bat'];
const predictor = new PredictiveText(dict);
console.log(predictor.predict('ap')); // ['app', 'apple', 'application']
console.log(predictor.predict('ba')); // ['banana', 'ball', 'bat']
Optimization Techniques for Prefix Trees
- Compressed Prefix Tree (Radix Tree):
- Merge nodes with only one child.
- Reduce tree height to save space.
- Supporting Fuzzy Search:
- Implement wildcard matching (. or *).
- May require backtracking algorithms.
- Supporting Multiple Languages:
- Handle Unicode characters.
- Consider word segmentation rules for different languages.
- Memory Optimization:
- Use arrays instead of objects to store child nodes (when the character range is limited).
- Share common prefixes.
- Concurrent Access:
- Implement thread-safe versions.
- Consider read-write lock mechanisms.
Comparison of Prefix Trees with Other Data Structures
| Feature | Prefix Tree | Hash Table | Balanced Binary Search Tree |
|---|---|---|---|
| Insertion | O(m) | O(1) average | O(log n) |
| Search | O(m) | O(1) average | O(log n) |
| Prefix Search | O(m + k) | Not supported | O(m + k) |
| Space Complexity | High (shared prefixes) | Low | Medium |
| Orderliness | None | None | Yes |
| Fuzzy Search Support | Possible | Not supported | Not supported |
Practical Application Scenarios
- Autocomplete: Search engines, input methods.
- Spell Checker: Word processing software.
- IP Routing: Network devices.
- Predictive Text: Mobile keyboards.
- Dictionary Implementation: Fast word lookup.
- File System: Path lookup.
- Gene Sequence Analysis (Bioinformatics): DNA sequence matching.
- Version Control: Branch name management.
Summary
The prefix tree is a powerful data structure, particularly suitable for handling string-related problems. It saves space by sharing common prefixes and provides efficient prefix search capabilities. Although its implementation is relatively complex, its performance advantages make it an ideal choice in many practical applications.
Understanding the working principles and implementation methods of prefix trees is crucial for solving string processing problems. In actual development, you can choose the appropriate data structure based on specific requirements or combine the strengths of multiple data structures to achieve more efficient solutions.
