js实现trie

实现 Trie 数据结构

Trie（前缀树）是一种树形数据结构，用于高效地存储和检索字符串集合中的键。以下是 JavaScript 实现 Trie 的完整代码和详细说明。

Trie 节点结构

每个 Trie 节点包含一个子节点映射和一个标记表示是否为单词结尾：

class TrieNode {
  constructor() {
    this.children = {};  // 存储子节点的映射
    this.isEndOfWord = false;  // 标记是否为单词结尾
  }
}

Trie 类实现

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(n)，n 为单词长度
• 搜索时间复杂度：O(n)，n 为单词长度
• 空间复杂度：O(m*n)，m 为字符集大小，n 为所有单词总长度

扩展功能

实现删除操作需要递归处理节点：

delete(word, node = this.root, index = 0) {
  if (index === word.length) {
    if (!node.isEndOfWord) return false;
    node.isEndOfWord = false;
    return Object.keys(node.children).length === 0;
  }

  const char = word[index];
  if (!node.children[char]) return false;

  const shouldDeleteChild = this.delete(word, node.children[char], index + 1);
  if (shouldDeleteChild) {
    delete node.children[char];
    return Object.keys(node.children).length === 0 && !node.isEndOfWord;
  }
  return false;
}

这种实现方式适用于大多数需要字符串高效检索的场景，如自动补全、拼写检查等应用。