什么是 Trie？

字典树（读作“try”，是 retrieval 的缩写）是一种树形数据结构，用于按字符存储和查找字符串。树中的每条边都标记着一个字符，从根节点到某个已标记节点的每条路径都会拼出一个已存储的单词。

这种结构让前缀查询变得非常快。检查字典树中是否有以 "car" 开头的单词，只需从根节点查找 3 个字符，无论其中存储了多少千个单词。自动补全、拼写检查和 IP 路由表等功能背后都离不开字典树。

字典树中的每个节点都保存着两项状态：

• children：从字符映射到下一个 TrieNode 的映射。
• isEndOfWord：一个标记。如果从根节点到当前节点的路径拼出了一个已插入的完整单词，它的值就是 true。

字典树的 5 种主要操作是：

1. 插入：添加一个单词，并沿途创建缺失的节点。
2. 查找：检查是否存储了完整的单词。
3. 前缀查找：检查是否有任何已存储的单词具有给定前缀。
4. 删除：移除一个单词，并清理不再使用的分支。
5. 单词计数：统计存储的不同单词数量。

让我们来构建一个 Trie 类吧！