前缀树原理与实现

前缀树原理与实现 (2025-04-10 15:33:49)

User什么是前缀树，原理讲解，用 js 实现，什么情况下使用

---

Assistant

---

前缀树 (Trie)

什么是前缀树

前缀树（Trie），也称为字典树，是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。与二叉查找树不同，前缀树中的键不是直接存储在节点中，而是由从根到节点的路径所决定。

原理

前缀树的基本原理包括：

1. 根节点不包含字符，除根节点外的每个节点都只包含一个字符
2. 从根节点到某一节点的路径上的字符连接起来，即为该节点对应的字符串
3. 每个节点的所有子节点包含的字符都不相同
4. 通常在节点中设置一个标志，用于标记该节点处是否构成一个完整的单词

前缀树最大的优势在于查询和插入的效率，时间复杂度为 O(m)，其中 m 是键的长度。

JavaScript 实现

下面是一个基本的前缀树 JavaScript 实现：

// 定义前缀树节点
class TrieNode {
  constructor() {
    this.children = {}; // 子节点映射
    this.isEndOfWord = false; // 标记是否是单词结尾
  }
}

// 前缀树类
class Trie {
  constructor() {
    this.root = new TrieNode(); // 根节点
  }

  // 插入单词
  insert(word) {
    let current = this.root;
    
    for (let i = 0; i < word.length; i++) {
      const char = word[i];
      // 如果当前字符不存在于子节点中，创建新节点
      if (!current.children[char]) {
        current.children[char] = new TrieNode();
      }
      // 移动到下一个节点
      current = current.children[char];
    }
    
    // 标记单词结尾
    current.isEndOfWord = true;
  }

  // 搜索单词
  search(word) {
    let current = this.root;
    
    for (let i = 0; i < word.length; i++) {
      const char = word[i];
      // 如果当前字符不存在于子节点中，单词不存在
      if (!current.children[char]) {
        return false;
      }
      // 移动到下一个节点
      current = current.children[char];
    }
    
    // 只有当节点被标记为单词结尾时，才表示单词存在
    return current.isEndOfWord;
  }

  // 检查是否有以指定前缀开头的单词
  startsWith(prefix) {
    let current = this.root;
    
    for (let i = 0; i < prefix.length; i++) {
      const char = prefix[i];
      // 如果当前字符不存在于子节点中，前缀不存在
      if (!current.children[char]) {
        return false;
      }
      // 移动到下一个节点
      current = current.children[char];
    }
    
    // 找到前缀
    return true;
  }
}

// 使用示例
const trie = new Trie();
trie.insert("苹果");
trie.insert("香蕉");
trie.insert("苹");

console.log(trie.search("苹果")); // true
console.log(trie.search("苹")); // true
console.log(trie.search("橙子")); // false
console.log(trie.startsWith("苹")); // true
console.log(trie.startsWith("香")); // true
console.log(trie.startsWith("梨")); // false

使用场景

前缀树适用于以下场景：

1. 自动补全功能：当用户输入部分文字时，系统可以快速找出所有以该前缀开头的单词
2. 拼写检查：可以快速检查单词是否正确拼写
3. IP路由表：用于存储和查找IP地址
4. 字典查找：高效实现字典功能，特别是对于前缀搜索
5. 文本压缩：某些压缩算法使用前缀树来优化
6. 搜索引擎：用于实现搜索关键词的快速匹配
7. 数据库索引：某些场景下可作为索引结构

相比于哈希表等其他数据结构，前缀树在处理字符串前缀相关的操作时效率更高，且能够按字典序遍历所有键。当您需要频繁进行前缀查询或按字典序访问数据时，前缀树是一个很好的选择。

---

---