字典树（Trie，也称为前缀树或单词查找树）是一种用于存储字符串的树形数据结构。它是一种特殊的多叉树，其中每个节点都包含一个字符和一个指向其子节点的指针数组。字典树的主要作用是用于快速查找字符串和处理字符串的前缀。
使用字典树的场景包括：

1. 字符串匹配：在文本中查找一个模式串是否存在，例如在文本中查找某个关键词。
2. 字符串插入：将一个字符串插入到字典树中，以便在后续的查询中能够快速找到该字符串。
3. 字符串删除：从字典树中删除一个字符串，以便在后续的查询中不再能找到该字符串。
   以下是使用 Python 实现的一个简单字典树示例：

class TrieNode:
def init(self):
self.children = {}
self.is_end = False
class Trie:
def init(self):
self.root = TrieNode()
def insert(self, word):
node = self.root
for char in word:
if char not in node.children:
node.children[char] = TrieNode()
node = node.children[char]
node.is_end = True
def search(self, word):
node = self.root
for char in word:
if char not in node.children:
return False
node = node.children[char]
return node.is_end
def delete(self, word):
def _delete(node, word, index):
if index == len(word):
if not node.is_end:
return False
node.is_end = False
return len(node.children) == 0
char = word[index]
if char not in node.children:
return False
if _delete(node.children[char], word, index + 1):
del node.children[char]
return len(node.children) == 0 and not node.is_end
return False
_delete(self.root, word, 0)

示例

trie = Trie()
trie.insert("hello")
trie.insert("world")
print(trie.search("hello")) # 输出 True
print(trie.search("world")) # 输出 True
print(trie.search("helloworld")) # 输出 True
print(trie.search("hello")) # 输出 True
trie.delete("hello")
print(trie.search("hello")) # 输出 False
CopyCopy

在这个示例中，我们创建了一个字典树节点类TrieNode，包含一个子节点字典children和一个表示字符串是否结束的布尔值is_end。然后创建了一个字典树类Trie，包含一个根节点root。字典树类提供了insert、search和delete方法，分别用于插入、查询和删除字符串。