SorryToPerson logo
返回
算法2026-04-15·6 分钟

算法知识库：Trie 字典树实现

Trie 字典树的插入、查询和前缀搜索的 JavaScript/TypeScript 实现。

Trie 字典树实现

1. Trie 节点定义

ts
class TrieNode {
  children: Record<string, TrieNode> = {};
  isEnd = false;
}

2. Trie 树实现

ts
class Trie {
  root = new TrieNode();

  // 时间复杂度: O(m)，空间复杂度: O(m) (m为单词长度)
  insert(word: string) {
    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;
  }

  // 时间复杂度: O(m)，空间复杂度: O(1)
  search(word: string): boolean {
    let node = this.root;
    for (const char of word) {
      if (!node.children[char]) return false;
      node = node.children[char];
    }
    return node.isEnd;
  }

  // 时间复杂度: O(m)，空间复杂度: O(1)
  startsWith(prefix: string): boolean {
    let node = this.root;
    for (const char of prefix) {
      if (!node.children[char]) return false;
      node = node.children[char];
    }
    return true;
  }
}

3. 应用场景

  • 自动补全。
  • 单词搜索。
  • 前缀匹配。

4. 实现要点

  • Trie 的查询复杂度为 O(k)，k 为单词长度。
  • 需要注意节点对象的创建开销。
  • 可扩展为计数节点频率和删除功能。
算法TrieJavaScript