字典树TRIE（前缀树）

**字典树 Trie（前缀树）**

字典树 Trie，也称为前缀树，是一种常见的数据结构，用于存储和检索字符串集合。它是一棵多叉树，每个结点代表一个字符或空串，叶子结点代表完整的单词。

**定义和特性**

Trie 的定义如下：

* 每个结点都有一个值（也称为标签），表示该结点所代表的字符串的前缀。
* 每个结点都有多个孩子结点，每个孩子结点代表该结点所代表的字符串的后续字符。
* Trie 的根结点是空串，所有其他结点都有一个值。

Trie 的特性如下：

* **前缀匹配**: Trie 可以快速检索出包含某个前缀的所有单词。
* **高效存储**: Trie 可以高效地存储大量的字符串集合。
* **快速查找**: Trie 可以快速找到包含某个前缀的所有单词。

**Trie 的应用**

Trie 有许多应用：

* **自动补全**: Trie 可用于实现自动补全功能，例如在输入法中。
* **文本搜索**: Trie 可用于快速检索出包含某个关键字的所有文本。
* **密码验证**: Trie 可用于快速检验用户输入的密码是否正确。

**Trie 的构建**

构建 Trie 需要以下步骤：

1. **创建根结点**: 创建一个空结点作为 Trie 的根结点。
2. **插入单词**: 将每个单词插入 Trie 中，根据单词的前缀创建相应的结点。
3. **更新结点值**: 更新每个结点的值，以表示该结点所代表的字符串的前缀。

**Trie 的查找**

查找 Trie 中包含某个前缀的所有单词需要以下步骤：

1. **从根结点开始**: 从 Trie 的根结点开始遍历 Trie。
2. **匹配前缀**: 匹配当前结点所代表的字符串的前缀是否与目标前缀相等。
3. **递归查找**: 如果匹配成功，则递归地从当前结点开始继续查找包含该前缀的所有单词。

**Trie 的代码示例**

以下是 Trie 的 Python 实现：

class TrieNode:
 def __init__(self):
 self.children = {}
 self.is_end_of_word = Falseclass Trie:
 def __init__(self):
 self.root = TrieNode()

 def insert(self, word: str) -> None:
 node = self.root for char in word:
 if char not in node.children:
 node.children[char] = TrieNode()
 node = node.children[char]
 node.is_end_of_word = True def search(self, word: str) -> bool:
 node = self.root for char in word:
 if char not in node.children:
 return False node = node.children[char]
 return node.is_end_of_word def starts_with(self, prefix: str) -> bool:
 node = self.root for char in prefix:
 if char not in node.children:
 return False node = node.children[char]
 return True

trie = Trie()
words = ["apple", "banana", "orange"]
for word in words:
 trie.insert(word)

print(trie.search("apple")) # Output: Trueprint(trie.search("banana")) # Output: Trueprint(trie.search("orange")) # Output: Trueprint(trie.search("grape")) # Output: Falseprint(trie.starts_with("app")) # Output: Trueprint(trie.starts_with("ban")) # Output: Trueprint(trie.starts_with("ora")) # Output: Trueprint(trie.starts_with("gra")) # Output: False