illegalCreed

中文

English

中文

English

Appearance

入门：多叉树、公共前缀压缩与空间换时间 ​

基于通用数据结构概念 · 核于 2026-07

速查 ​

  • 定义：Trie 是一棵多叉树，从根到任一节点的路径对应一个字符串前缀，每条边代表一个字符——它专门为「字符串集合上的前缀查询」而生。
  • 公共前缀压缩：共享前缀的单词（app/apple/apply）在树上共用前缀路径，只在分叉处分开——这是 Trie 省内存且能高效做前缀查询的根源。
  • 节点结构：每个节点含①一个 children 子节点映射（字符 → 子节点）②一个 isEnd 布尔标志（标记「到此为止构成一个完整单词」，区别于「只是某单词的前缀」）。
  • isEnd 的意义：插入了 apple 后，app 节点存在但 isEnd=false（不是完整单词）；只有再插入 app 才把它置 true——search 必须查到 isEnd 才算命中。
  • 核心复杂度：insert / search / startsWith 都是 O(L)（L = 单词长度，与词表规模 n 无关）；这是 Trie 区别于哈希表（O(L) 但无前缀能力）、BST（O(L log n)）的核心优势。
  • children 选型：Map 通用（任意字符集、Unicode 友好）但常数大、缓存差；定长 Array[26] 适配纯小写字母表，O(1) 定位、缓存友好，但只适合小字符集且空槽费空间。
  • 与哈希表对比：哈希表只能精确查找整词（O(L) 一次哈希），无法高效回答前缀查询「以 app 开头的单词有哪些」；Trie 的 startsWith 是独门绝技。
  • 空间换时间：Trie 用「每字符一节点」的额外空间换取 O(L) 的前缀查询——公共前缀多则省、公共前缀少则费（这也是压缩 Trie / Radix Tree 的动因）。
  • 应用主战场：搜索框自动补全、词频统计（节点存 count）、拼写检查、IP 路由最长前缀匹配、AC 自动机（多模式串匹配的底座）。
  • 删除复杂：删一个单词要递归判断「该节点删除后是否还有子节点 / 是否是其他单词结尾」，不能简单摘节点（否则破坏共享前缀的其他单词）。
  • 进阶顺序：核心操作 → 工程应用 → 参考。

一、Trie 是什么：多叉树 + 字符边 ​

Trie 的本质是「一棵多叉树，每条边代表一个字符」。把 app、apple、apply、bat 插入 Trie，树长这样：

(root)
├── a
│   └── p
│       └── p          ← "app" 的结尾（isEnd=true）
│           ├── l
│           │   └── e  ← "apple" 的结尾（isEnd=true）
│           │   └── y  ← "apply" 的结尾（isEnd=true）
└── b
    └── a
        └── t          ← "bat" 的结尾（isEnd=true）

三个推论：

  1. 根节点不存字符：字符记在「边」上（实现里记在子节点映射的 key 里），根是空起点。
  2. 从根到某节点的路径 = 一个前缀：走到 a→p→p 对应前缀 app，再走到 l→e 对应完整单词 apple。
  3. isEnd 区分「前缀」与「完整单词」：app 节点既是 apple/apply 的前缀，也可能本身是一个独立单词——靠 isEnd 标志区分。

二、公共前缀压缩：省内存与支持前缀查询 ​

apple 和 apply 共享前缀 appl，在 Trie 里共用 a→p→p→l 这条路径，只在最后 e/y 处分叉。这带来两个直接收益：

  • 省内存：公共前缀只存一份，长前缀的多个单词（如 precaution/precede/predict）共享 pre 路径。
  • 天然支持前缀查询：startsWith("app") 只要沿 a→p→p 走到 app 节点，该节点所在的子树就是所有以 app 开头的单词——O(L) 定位 + 子树遍历，哈希表做不到。

反过来，公共前缀越少，Trie 越费空间（每个单词几乎独占一条路径），极端情况退化成「每字符一节点」的链状结构，比直接存字符串数组还费——这是压缩 Trie（Radix Tree）把单链路径压缩成「单节点多字符」的动因。

三、节点结构：isEnd + children ​

js
class TrieNode {
  constructor() {
    this.children = new Map(); // 字符 -> 子节点（通用版，任意字符集）
    this.isEnd = false;        // 是否为某完整单词的结尾
  }
}

两个字段缺一不可：

  • children：子节点映射。键是「下一条边代表的字符」，值是子 TrieNode。实现上有两种主流选型（见下节）。
  • isEnd：标记「从根到此节点的路径构成一个完整单词」。search("app") 必须走到 app 节点且 isEnd=true 才算命中——光有节点不算（可能只是别的前缀的中转点）。

children 用 Map 还是数组 Array[26] ​

选型适用优点缺点
Map任意字符集（Unicode、中文）通用、内存随用随分配哈希常数大、缓存不友好
Array[26]纯小写字母 a-zO(1) 直接下标、缓存友好只适合小字符集；空槽费空间
Array[256]ASCII定位快256 个槽，稀疏时极费内存
js
// Array[26] 版节点（纯小写字母表）
class TrieNode26 {
  constructor() {
    this.children = new Array(26).fill(null);
    this.isEnd = false;
  }
  // 下标转换：char -> index
  idx(ch) { return ch.charCodeAt(0) - 97; } // 'a'.charCodeAt(0) === 97
}

四、与哈希表对比：前缀查询是 Trie 独有优势 ​

维度Trie哈希表
精确查找整词O(L)O(L)（一次哈希）
前缀查询 startsWithO(L) ✅不支持（需遍历全部 O(n·L)）❌
字典序遍历天然有序（按字符 DFS）✅无序，要额外排序 ❌
空间公共前缀多则省、少则费O(n·L)，常数小
哈希冲突无有（需处理）
最长前缀匹配支持（IP 路由）✅不支持 ❌

一句话：「要前缀查询 / 字典序 / 最长前缀匹配 → Trie；只要精确查找整词 → 哈希表更简单更快」。

五、空间换时间：Trie 的核心权衡 ​

Trie 的复杂度全部是 O(L)，与词表规模 n 无关——词表 1 万还是 1 亿，查 apple 都是走 5 步。这是「空间换时间」换来的：

  • 换来了什么：O(L) 的插入/查找/前缀搜索（哈希表虽然查找也 O(L)，但无前缀能力；BST 是 O(L log n)）。
  • 代价是什么：每个字符一个节点，节点还要存 children 映射与指针。公共前缀少时，n 个单词的节点数接近总字符数，比直接存字符串数组更费。

工程上的折中：

  • 字符集小且前缀集中（如英文单词）→ Trie 收益明显，省内存又快。
  • 字符集大或前缀分散（如全 Unicode、用户 ID）→ 考虑压缩 Trie（Radix Tree）或直接用哈希表。

下一步 ​

理解了 Trie 的多叉树模型与节点结构后，下一步是把它跑起来——insert / search / startsWith 三大核心操作的实现与 O(L) 复杂度，见核心操作。