当前位置：首页 > JavaScript

js实现trie

2026-02-02 00:15:58JavaScript

实现 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

方法说明

insert(word)

时间复杂度：O(m)，m 为单词长度
从根节点开始遍历每个字符
为不存在的字符创建新节点
最后标记单词结束

search(word)

时间复杂度：O(m)
遍历每个字符检查是否存在对应节点
必须匹配完整单词（isEndOfWord为true）

startsWith(prefix)

时间复杂度：O(m)
只需检查前缀路径是否存在
不要求是完整单词

扩展功能

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

delete(word) {
  const deleteHelper = (node, word, index) => {
    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 shouldDelete = deleteHelper(node.children[char], word, index + 1);
    if (shouldDelete) {
      delete node.children[char];
      return Object.keys(node.children).length === 0;
    }
    return false;
  };
  deleteHelper(this.root, word, 0);
}