什么是Trie？

简介

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

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

这种数据结构称为 Trie，也被称为 前缀树。我们很快就会明白它的命名原因。

💡 小知识

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

[普通的 Trie 结构]

Trie 的常见应用场景

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

1. 自动补全功能

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

2. 拼写检查

当用户输入一个单词时，Trie 可以帮助进行拼写检查。这项功能在用户不确定某个单词确切拼写时非常有用。

3. 查找联系人

另一个实际应用是联系人搜索。当我们输入字母组合时，系统会根据输入提供自动建议。虽然哈希表也能实现类似功能，但 Trie 在效率上更具优势。

Trie 的特性

为了保持其高效的性能，Trie 遵循特定的结构：

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

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

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

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

• 另一个关键特性是：具有相同前缀的单词会共享相同的路径。例如，“there” 和 “their” 共享前缀 “the”，因此它们的路径会一直延续到字母 “e”。之后路径才会分叉为两条。这正是 Trie 功能的核心所在。