Trie（也被称为前缀树或字典树）是一种用于检索键值数据集中的键的数据结构。它是一种树形结构，常用于处理字符串检索问题，如搜索引擎和单词查找。
Trie 的基本概念
- 节点：Trie 的每个节点代表一个字符。
- 根节点：Trie 的起始节点，通常不包含任何字符。
- 子节点：每个节点可以有多个子节点，代表字符串中的不同字符。
- 前缀：从根节点到某个节点的路径上的所有字符组成的字符串。
Trie 的操作
插入
- 从根节点开始，依次匹配字符串中的每个字符。
- 如果节点不存在，则创建一个新的节点。
- 当匹配到字符串的最后一个字符时，标记该节点为结束节点。
搜索
- 从根节点开始，依次匹配字符串中的每个字符。
- 如果在任何位置匹配失败，则字符串不存在。
- 当匹配到字符串的最后一个字符时，检查当前节点是否为结束节点。
删除
- 从根节点开始，依次匹配字符串中的每个字符。
- 如果匹配成功，则递归删除该节点及其所有子节点。
- 在删除节点之前，检查是否还有其他字符串共享该节点，如果有，则不删除。
Trie 的应用
- 字符串匹配：例如，在文本编辑器中查找和替换文本。
- 搜索引擎：快速检索网页中的关键词。
- 电话号码簿：快速查找电话号码。
示例
假设我们要将以下字符串插入 Trie 中：
apple
apply
banana
插入过程如下：
插入 "apple"
- 根节点：a
- a 的子节点：p
- p 的子节点：p
- p 的子节点：l
- l 的子节点：e
- e 的子节点：空（标记为结束节点）
插入 "apply"
- 根节点：a
- a 的子节点：p
- p 的子节点：p
- p 的子节点：l
- l 的子节点：y
- y 的子节点：空（标记为结束节点）
插入 "banana"
- 根节点：b
- b 的子节点：a
- a 的子节点：n
- n 的子节点：a
- a 的子节点：n
- n 的子节点：a
- a 的子节点：空（标记为结束节点）
Trie 树示例