什么是 Trie 数据结构？

“Trie”这个词是“retrieval”（检索）一词的摘录。Trie 是一种基于排序树的数据结构，用于存储字符串集合。它的每个节点中指针的数量等于字母表中字符的数量。它可以在字典中借助单词的前缀来搜索一个词。例如，如果我们假设所有字符串都由英文字母表中的 'a' 到 'z' 组成，那么每个 trie 节点最多可以有 26 个指针。

Trie 也被称为数字树（digital tree）或前缀树（prefix tree）。节点在 Trie 中的位置决定了与该节点连接的键。

Trie 对于字符串集合的属性

1. Trie 的根节点始终代表空节点。
2. 每个节点的子节点都按字母顺序排序。
3. 每个节点最多可以有 26 个子节点（A 到 Z）。
4. 每个节点（根节点除外）可以存储字母表中的一个字母。

下图描绘了 bell、bear、bore、bat、ball、stop、stock 和 stack 的 trie 表示。

Trie 的基本操作

Trie 有三种操作

1. 插入节点
2. 搜索节点
3. 删除节点

在 Trie 中插入节点

第一个操作是在 trie 中插入一个新节点。在我们开始实现之前，理解一些要点很重要：

1. 输入键（单词）的每个字母都作为一个独立的 Trie_node 插入。请注意，子节点指向 Trie 节点的下一层。
2. 键字符数组充当子节点的索引。
3. 如果当前节点已经有对当前字母的引用，则将当前节点设置为该被引用的节点。否则，创建一个新节点，将字母设置为等于当前字母，并用这个新节点启动当前节点。
4. 字符长度决定了 trie 的深度。

在 Trie 中插入新节点的实现

在 Trie 中搜索节点

第二个操作是在 Trie 中搜索节点。搜索操作与插入操作类似。搜索操作用于在 trie 中搜索一个键。搜索操作的实现如下所示。

在 Trie 中搜索节点的实现

在 Trie 中删除节点

第三个操作是在 Trie 中删除节点。在我们开始实现之前，理解一些要点很重要：

1. 如果在 trie 中未找到该键，删除操作将停止并退出。
2. 如果在 trie 中找到该键，则将其从 trie 中删除。

在 Trie 中删除节点的实现

Trie 的应用

1. 拼写检查器

拼写检查是一个三步过程。首先，在字典中查找该词，生成可能的建议，然后对建议词进行排序，将期望的词放在顶部。

Trie 用于在字典中存储单词。通过在数据结构上搜索单词，可以以最有效的方式轻松应用拼写检查器。使用 trie 不仅可以轻松地在字典中查找单词，而且构建一个算法来包含一组相关词或建议也很简单。

2. 自动完成

自动完成功能广泛用于文本编辑器、移动应用程序和互联网上。它提供了一种简单的方法来查找替代词以完成单词，原因如下：

• 它通过节点的键提供条目的字母顺序过滤。
• 我们只追踪指针以获取代表用户输入字符串的节点。
• 一旦你开始输入，它就会尝试完成你的输入。

3. 浏览器历史

它也用于在浏览器中补全 URL。浏览器会保留您访问过的网站 URL 的历史记录。

Trie 的优点

1. 它比哈希表和二叉搜索树能更快地插入和搜索字符串。
2. 它通过节点的键提供条目的字母顺序过滤。

Trie 的缺点

1. 它需要更多内存来存储字符串。
2. 它比哈希表慢。

C++ 完整程序

输出

Search the word ohh: Not Found
Search the word bag: Found!
Search the word can: Found!
Search the word ways: Not Found
Search the word way: Found!
 → h → e → l → l → o → w → a → y → i → t → e → a → b → a → g → c → a → n
deleting the word 'hello'...
 → w → a → y → h → i → t → e → a → b → a → g → c → a → n
deleting the word 'can'...
 → w → a → y → h → i → t → e → a → b → a → g