什么是Trie？

简介

在上一节中，我们介绍了几种常见的树结构，如红黑树、2-3 树等。

现在，我们将学习一种类树形的数据结构，它在解决与字符串相关的编程问题时表现出极高的效率。

这种数据结构被称为 trie，也称为 前缀树（Prefix Tree）。我们很快就会明白其中的原因。

“trie” 这个名字来源于 “retrieval”（检索）。顾名思义，这种结构的主要用途是实现快速查找。Trie 被广泛应用于词典查词、搜索引擎的自动补全以及 IP 路由等场景。

Trie 的常见应用场景

让我们通过一些实际例子来理解 trie 的作用。

自动补全单词

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

拼写检查

当需要对用户输入的单词进行拼写检查时，trie 非常有用。这项功能对于不清楚所查单词确切拼写的用户尤其有帮助。

查找通讯录联系人

另一个现实生活中的 trie 应用是在通讯录中搜索联系人。系统会根据我们输入的字母组合提供自动建议。正如我们后续将看到的，虽然哈希表也能实现类似功能，但其效率远不如 trie。

Trie 的特性

为了保持整体高效性，trie 遵循特定的结构设计：

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

• 每个节点可以指向 None 或其他子节点。

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

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

• Trie 的一个重要特性是：具有相同前缀的单词会共享相同的路径。例如，“there” 和 “their” 共享前缀 “the”，因此它们从根节点到 “e” 的路径完全相同，之后才分出两条分支。这一特性正是 trie 功能的核心所在。