什么是 Trie？

简介

到目前为止，我们只学习了一些常见的树结构，例如 红黑树、2-3 树 等。在本章中，我们将探讨一种类树的数据结构，它在解决与 字符串 相关的编程问题时表现出极高的效率。这种数据结构被称为 Trie，也称为 “前缀树”；稍后我们会解释其名称的由来。

💡 你知道吗？

“Trie” 这个词源自 “retrieval”（检索），因为这种结构的主要用途就是实现快速检索。Trie 广泛应用于字典中查找单词、搜索引擎中的自动补全建议，以及 IP 路由等场景。

[一个 Trie 的示例。]

Trie 的常见应用场景

Trie 主要用于需要快速检索的场合。下面我们来看一些实际应用的例子，以了解 Trie 是如何被使用的：

1. 单词自动补全

如今，几乎所有主流应用程序都支持自动补全功能。借助 Trie 可以非常高效地实现这一功能，因为它能显著降低整体性能开销。

2. 拼写检查

当需要对用户输入的单词进行拼写检查，判断该单词是否存在于 字典 中，或提示用户可能存在的拼写错误时，Trie 就显得尤为有用。这一功能对于不清楚关键词确切拼写的用户来说非常有帮助。

3. 在手机中搜索联系人

另一个 Trie 的实际应用是在通讯录中查找联系人。当我们输入字母组合时，系统会基于输入内容提供自动建议。虽然这一功能也可以通过哈希表实现，但效率远不如 Trie；我们将在后续详细讨论这一点。

Trie 的特性

为了保持整体高效性，Trie 必须遵循以下规则：

• Trie 与图结构类似，由多个节点组成，每个节点代表一个唯一的字母。

• Trie 更像是一种有序树结构，其中每个子节点要么为空（Null），要么指向另一个节点。

• Trie 的大小取决于字符的数量。例如，在英文中有 26 个字母，因此每个 Trie 节点的子节点数量 不能超过 26 个。

• Trie 的深度取决于其所存储的 最长单词 的长度。

• Trie 的另一个重要特性是：具有相同前缀的单词会共享相同的路径。例如，"there" 和 "their" 都有共同前缀 "the"，因此它们会在 Trie 中共用从根到 "e" 的路径；之后才分出两个分支。Trie 的核心工作机制正是基于这一特性，我们将在后续深入讲解。

---

以上是每个 Trie 都必须具备的一些基本特性。