Trie树，也称前缀树，是一种用于高效存储和检索字符串的数据结构，广泛应用于自动补全、拼写检查和IP路由等场景。
Trie树的关键特性：
节点: 每个节点代表一个字符。根节点: 根节点为空，作为树的起始点。子节点: 每个节点可拥有多个子节点，数量取决于字符集大小（例如，英文字母为26个）。单词结束标记: 特定节点标记，指示该节点代表一个完整单词的结尾。
基本Trie树操作：
1. 插入单词:
插入新单词需要遍历Trie树，对于不存在的字符，创建新的节点。
2. 查找单词:
查找单词通过遍历Trie树，检查单词是否存在。
3. 前缀查找:
检查Trie树中是否存在以特定前缀开头的单词。
JavaScript实现基本Trie树：
class TrieNode { constructor() { this.children = {}; // 存储子节点 this.isWordEnd = false; // 标记单词结尾 }}class Trie { constructor() { this.root = new TrieNode(); } // 插入单词 insert(word) { let node = this.root; for (let char of word) { if (!node.children[char]) { node.children[char] = new TrieNode(); } node = node.children[char]; } node.isWordEnd = true; // 标记单词结尾 } // 查找单词 search(word) { let node = this.root; for (let char of word) { if (!node.children[char]) { return false; } node = node.children[char]; } return node.isWordEnd; } // 检查是否存在以指定前缀开头的单词 startsWith(prefix) { let node = this.root; for (let char of prefix) { if (!node.children[char]) { return false; } node = node.children[char]; } return true; }}// 示例用法const trie = new Trie();trie.insert("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
高级Trie树操作：
1. 删除单词:
删除单词需要递归方法，删除不再需要的节点。
delete(word, node = this.root, depth = 0) { if (depth === word.length) { if (!node.isWordEnd) return false; // 单词不存在 node.isWordEnd = false; return Object.keys(node.children).length === 0; // 检查节点是否有子节点 } const char = word[depth]; if (!node.children[char]) return false; const shouldDeleteChild = this.delete(word, node.children[char], depth + 1); if (shouldDeleteChild) { delete node.children[char]; return Object.keys(node.children).length === 0 && !node.isWordEnd; } return false;}
2. 统计以指定前缀开头的单词数量:
计算有多少单词以给定前缀开头。
countWordsWithPrefix(prefix) { let node = this.root; for (let char of prefix) { if (!node.children[char]) return 0; node = node.children[char]; } return this._countWords(node);}_countWords(node) { let count = node.isWordEnd ? 1 : 0; for (let char in node.children) { count += this._countWords(node.children[char]); } return count;}
3. 自动补全建议:
给定前缀，返回所有以该前缀开头的单词。
getWordsWithPrefix(prefix) { let node = this.root; for (let char of prefix) { if (!node.children[char]) return []; node = node.children[char]; } return this._collectWords(node, prefix);}_collectWords(node, prefix) { let results = []; if (node.isWordEnd) results.push(prefix); for (let char in node.children) { results = results.concat(this._collectWords(node.children[char], prefix + char)); } return results;}
时间复杂度：
插入: O(l) (l = 单词长度)查找: O(l)前缀查找: O(l)删除: O(l)
Trie树的应用场景：
自动补全系统 (例如搜索框、文本编辑器)拼写检查器IP路由 (最长前缀匹配)文字游戏 (例如，Boggle)DNA序列匹配
以上就是Trie（前缀树）简介的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1500738.html
微信扫一扫 
支付宝扫一扫 
