当前位置：首页 > JavaScript

js实现前缀树

2026-02-03 05:56:17JavaScript

前缀树（Trie）的基本概念

前缀树是一种树形数据结构，用于高效存储和检索字符串集合。其核心特点是共享公共前缀，适合实现自动补全、拼写检查等功能。

实现前缀树的关键步骤

定义节点结构
每个节点包含子节点（通常用对象或Map表示）和标记是否为单词结尾的标识：

class TrieNode {
  constructor() {
    this.children = {}; // 子节点
    this.isEnd = false; // 是否为单词结尾
  }
}

实现前缀树类
初始化根节点并实现插入、搜索和前缀匹配方法：

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.isEnd = true;
  }

  // 搜索完整单词
  search(word) {
    let node = this.root;
    for (const char of word) {
      if (!node.children[char]) {
        return false;
      }
      node = node.children[char];
    }
    return node.isEnd;
  }

  // 检查前缀是否存在
  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

性能优化建议

子节点存储：使用Map替代对象可能提升性能（尤其在键为动态时）。
内存优化：对于大规模数据，考虑压缩前缀树（如Radix Tree）。
删除操作：可扩展实现删除功能，需递归清理无用的节点。

扩展：删除单词实现

delete(word) {
  const deleteHelper = (node, word, index) => {
    if (index === word.length) {
      if (!node.isEnd) return false;
      node.isEnd = 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);
}

js实现前缀树