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 路由表
• 字典实现