字典树（前缀树）
最后更新
字典树（trie，读作“try”），也叫前缀树，按字符存储一组字符串：每条边标记一个字符，从根节点出发的一条路径拼出一个前缀。有共同前缀的单词共享相同的节点，所以“car”“card”和“care”都复用 c-a-r 这条路径。点击上方的“播放”，观看单词如何一次一个字符地插入，只在不同的地方分叉。
因为查找时每个字符走一个节点，所以查找长度为 m 的单词只需 O(m) 时间，与字典树中存了多少单词无关。这让字典树非常适合自动补全、拼写检查和前缀搜索。
时间复杂度与空间复杂度
| 操作 | 复杂度 | 说明 |
|---|---|---|
| 插入 | O(m) | m = 单词长度 |
| 查找 | O(m) | 每个字符走一步 |
| 前缀查询 | O(m) | 走到前缀对应的节点 |
| 空间 | O(total chars) | 共享的前缀只存一次 |
分步说明（插入）
| 步骤 | 发生了什么 |
|---|---|
| 1 | 从根节点开始。 |
| 2 | 对单词中的每个字符，查找匹配的子节点边。 |
| 3 | 如果存在，就沿着它走（复用共享的前缀）。 |
| 4 | 如果不存在，就为这个字符新建一个子节点。 |
| 5 | 处理完最后一个字符后，把该节点标记为单词结尾。 |
实例演示
把 ["car", "card", "care"] 插入一棵空字典树：
| 步骤 | 结构 | 操作 |
|---|---|---|
插入 car | root → c → a → r✓ | 没有匹配的子节点，所以新建 c、a、r，并把 r 标记为单词结尾。 |
插入 card | root → c → a → r✓ → d✓ | 复用已有的 c-a-r 路径，再新建一个子节点 d，并标记为单词结尾。 |
插入 care | root → c → a → r✓ → {d✓, e✓} | 复用 c-a-r，从 r 分叉出新的子节点 e，并把 e 标记为单词结尾。 |
查找 care | root → c → a → r → e✓ | 依次走过 c、a、r、e；最后一个节点标记为单词结尾，所以 care 存在。 |
查找 ca | root → c → a | 路径存在，但 a 没有标记为单词结尾，所以 ca 只是前缀，不是已存储的单词。 |
什么时候用字典树
| 适合使用 | 不适合使用 |
|---|---|
| 你需要在一组字符串上做前缀查询或自动补全。 | 你只需要按完整的键查找：哈希表更快也更轻量。 |
| 很多存储的单词有共同前缀，节点能被复用。 | 键很长且很少重叠，每个字符都白白占用一个节点。 |
| 你希望通过遍历按排序后的顺序返回键。 | 内存紧张：每个节点的子节点指针会带来很大开销。 |
| 查找开销必须取决于键的长度，而不是数据集的大小。 | 字母表极大（例如完整的 Unicode），而子节点又是稠密存储的。 |
Trie (Prefix Tree) 代码
简洁、可运行的 Trie (Prefix Tree) 实现，提供 Python, JavaScript, Java, C++, C 版本。选择一种语言，复制代码，或在 Coddy 在线编辑器中直接打开。
Trie (Prefix Tree) 的 Python 代码
Python
1class TrieNode:2 def __init__(self):3 self.children = {}4 self.is_word = False5
6
7class Trie:8 def __init__(self):9 self.root = TrieNode()10
11 def insert(self, word):12 node = self.root13 for ch in word:14 node = node.children.setdefault(ch, TrieNode())15 node.is_word = True16
17 def search(self, word):18 node = self._walk(word)19 return node is not None and node.is_word20
21 def starts_with(self, prefix):22 return self._walk(prefix) is not None23
24 def _walk(self, s):25 node = self.root26 for ch in s:27 if ch not in node.children:28 return None29 node = node.children[ch]30 return node31
32
33trie = Trie()34for word in ["car", "card", "care", "dog"]:35 trie.insert(word)36
37print("search(card): ", trie.search("card"))38print("search(ca): ", trie.search("ca"))39print("starts_with(ca): ", trie.starts_with("ca"))40print("starts_with(do): ", trie.starts_with("do"))41print("starts_with(cat): ", trie.starts_with("cat"))Trie (Prefix Tree) 的 JavaScript 代码
JavaScript
1class TrieNode {2 constructor() {3 this.children = {};4 this.isEnd = false;5 }6}7
8class Trie {9 constructor() {10 this.root = new TrieNode();11 }12
13 insert(word) {14 let node = this.root;15 for (const ch of word) {16 if (!node.children[ch]) node.children[ch] = new TrieNode();17 node = node.children[ch];18 }19 node.isEnd = true;20 }21
22 // Walk the prefix; null when a character is missing23 findNode(prefix) {24 let node = this.root;25 for (const ch of prefix) {26 node = node.children[ch];27 if (!node) return null;28 }29 return node;30 }31
32 search(word) {33 const node = this.findNode(word);34 return node !== null && node.isEnd;35 }36
37 startsWith(prefix) {38 return this.findNode(prefix) !== null;39 }40}41
42const trie = new Trie();43for (const word of ["car", "card", "care", "dog"]) trie.insert(word);44console.log("search(\"card\"):", trie.search("card"));45console.log("search(\"ca\"):", trie.search("ca"));46console.log("startsWith(\"ca\"):", trie.startsWith("ca"));Trie (Prefix Tree) 的 Java 代码
Java
1public class Main {2 static class Node {3 Node[] children = new Node[26];4 boolean isWord;5 }6
7 static Node root = new Node();8
9 static void insert(String word) {10 Node cur = root;11 for (char c : word.toCharArray()) {12 int i = c - 'a';13 if (cur.children[i] == null) cur.children[i] = new Node();14 cur = cur.children[i];15 }16 cur.isWord = true;17 }18
19 // Follow the path for s; null means no word has this prefix20 static Node walk(String s) {21 Node cur = root;22 for (char c : s.toCharArray()) {23 cur = cur.children[c - 'a'];24 if (cur == null) return null;25 }26 return cur;27 }28
29 static boolean search(String word) {30 Node node = walk(word);31 return node != null && node.isWord;32 }33
34 static boolean startsWith(String prefix) {35 return walk(prefix) != null;36 }37
38 public static void main(String[] args) {39 insert("code");40 insert("coder");41 insert("cool");42 System.out.println("search code: " + search("code"));43 System.out.println("search cod: " + search("cod"));44 System.out.println("startsWith cod: " + startsWith("cod"));45 System.out.println("startsWith cat: " + startsWith("cat"));46 }47}Trie (Prefix Tree) 的 C++ 代码
C++
1#include <iostream>2#include <string>3#include <unordered_map>4
5struct TrieNode {6 std::unordered_map<char, TrieNode*> children;7 bool isEnd = false;8};9
10struct Trie {11 TrieNode* root = new TrieNode();12
13 void insert(const std::string& word) {14 TrieNode* node = root;15 for (char c : word) {16 if (!node->children.count(c)) node->children[c] = new TrieNode();17 node = node->children[c];18 }19 node->isEnd = true;20 }21
22 // Follow the path for s; nullptr if a link is missing23 TrieNode* walk(const std::string& s) const {24 TrieNode* node = root;25 for (char c : s) {26 auto it = node->children.find(c);27 if (it == node->children.end()) return nullptr;28 node = it->second;29 }30 return node;31 }32
33 bool search(const std::string& word) const {34 TrieNode* node = walk(word);35 return node != nullptr && node->isEnd;36 }37
38 bool startsWith(const std::string& prefix) const {39 return walk(prefix) != nullptr;40 }41};42
43int main() {44 Trie trie;45 for (const std::string& word : {"car", "card", "care", "dog"}) {46 trie.insert(word);47 }48 std::cout << std::boolalpha;49 std::cout << "search(card): " << trie.search("card") << "\n";50 std::cout << "search(ca): " << trie.search("ca") << "\n";51 std::cout << "startsWith(ca): " << trie.startsWith("ca") << "\n";52 std::cout << "startsWith(dot): " << trie.startsWith("dot") << "\n";53 return 0;54}Trie (Prefix Tree) 的 C 代码
C
1#include <stdbool.h>2#include <stdio.h>3#include <stdlib.h>4
5typedef struct TrieNode {6 struct TrieNode* children[26];7 bool isEnd;8} TrieNode;9
10TrieNode* newNode(void) {11 return calloc(1, sizeof(TrieNode)); // zeroed links and isEnd12}13
14void insert(TrieNode* root, const char* word) {15 for (; *word; word++) {16 int i = *word - 'a';17 if (root->children[i] == NULL) root->children[i] = newNode();18 root = root->children[i];19 }20 root->isEnd = true;21}22
23// Follow the path for s; NULL if a link is missing24TrieNode* walk(TrieNode* root, const char* s) {25 for (; *s; s++) {26 root = root->children[*s - 'a'];27 if (root == NULL) return NULL;28 }29 return root;30}31
32bool search(TrieNode* root, const char* word) {33 TrieNode* node = walk(root, word);34 return node != NULL && node->isEnd;35}36
37bool startsWith(TrieNode* root, const char* prefix) {38 return walk(root, prefix) != NULL;39}40
41int main(void) {42 TrieNode* root = newNode();43 const char* words[] = {"car", "card", "care", "dog"};44 for (int i = 0; i < 4; i++) insert(root, words[i]);45 printf("search(card): %s\n", search(root, "card") ? "true" : "false");46 printf("search(ca): %s\n", search(root, "ca") ? "true" : "false");47 printf("startsWith(ca): %s\n", startsWith(root, "ca") ? "true" : "false");48 printf("startsWith(dot): %s\n", startsWith(root, "dot") ? "true" : "false");49 return 0;50}字典树常见问题
字典树有什么用？
字典树支撑着各种基于前缀的功能：自动补全和搜索建议、拼写检查器、IP 路由表，以及词典查找。只要你需要快速回答“有没有已存储的单词以这个前缀开头？”，字典树就能大显身手。
字典树的时间复杂度是多少？
插入、查找和前缀查询都是
O(m)，其中 m 是单词或前缀的长度，与存储了多少单词无关。代价是内存：字典树可能占用很多空间，不过共享的前缀只存一次。字典树和哈希表有什么区别？
哈希表按完整的键查找，平均
O(1)，但无法回答前缀查询。字典树每次查找稍慢一些，却天然支持前缀搜索、有序遍历和自动补全，这正是这些场景更偏爱它的原因。什么时候该用字典树，而不是二叉搜索树？
当键是字符串，并且你需要前缀查找时，就用字典树：每次操作只需
O(m)，取决于键的长度；而平衡的二叉搜索树需要 O(m log n)，因为每次比较都要扫描字符串，一共要比较 log n 次。如果键不是类似字符串的数据，或者内存开销比前缀查询速度更重要，二叉搜索树是更好的选择。字典树如何处理单词的结尾？
每个节点都带一个单词结尾标记，只有当一个完整插入的单词在这里结束时才会设置。没有这个标记，你就分不清已存储的单词和单纯的前缀。例如插入
card 之后，car 对应的节点也存在，但只有同样插入过 car 时，它才应该被当作一个单词。字典树共享前缀就一定能省内存吗？
不一定。只有很多键相互重叠时，共享才有帮助；如果键很长且各不相同，字典树占用的内存可能远超哈希集合，因为每个字符都会变成一个带子节点指针的独立节点。如果关心空间，可以用压缩的基数树（radix tree），它把只有一个子节点的链合并起来，减少这部分开销。
相关资源
更多可视化
