js实现trie
实现 Trie 数据结构
Trie（前缀树）是一种树形数据结构，用于高效存储和检索字符串集合。以下是 JavaScript 实现 Trie 的完整代码示例。
Trie 节点结构
每个 Trie 节点包含一个子节点映射和一个标志表示是否为单词结尾。
class TrieNode {
constructor() {
this.children = {}; // 子节点映射
this.isEndOfWord = false; // 标记是否为单词结尾
}
}Trie 类实现
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) {
let node = this.root;
for (const char of word) {
if (!node.children[char]) {
return false;
}
node = node.children[char];
}
return node.isEndOfWord;
}
// 检查前缀是否存在
startsWith(prefix) {
let node = this.root;
for (const 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")); // true
console.log(trie.search("app")); // false
console.log(trie.startsWith("app")); // true
trie.insert("app");
console.log(trie.search("app")); // true复杂度分析
- 插入操作：O(m)，其中 m 为单词长度
- 搜索操作：O(m)，其中 m 为单词长度
- 前缀检查：O(m)，其中 m 为前缀长度
应用场景
Trie 适用于需要快速前缀匹配的场景，如：
- 自动补全系统
- 拼写检查
- IP 路由表
- 字典实现
