字典树的数据结构

**字典树（Trie）的数据结构**

字典树，也称为前缀树，是一种常见的数据结构，用于存储和检索字符串集合。它通过使用一个根节点和多个子节点来实现快速查找和插入操作。

**定义**

字典树是一棵多叉树，每个结点代表一个字符或空串。每个结点都有多个子结点，分别对应不同的下一个字符。如果某个结点的所有子结点都为空，则该结点表示一个单独的字符串。

**基本操作**

字典树支持以下基本操作：

1. **插入（Insert）**: 将一个新字符串添加到字典树中。
2. **查找（Search）**: 检索是否存在某个字符串在字典树中。
3. **删除（Delete）**: 从字典树中移除一个字符串。

**实现**

下面是使用 Python语言实现的字典树类：

class TrieNode:
 def __init__(self):
 self.children = {} # 子结点 self.is_end_of_word = False # 是否表示单独的字符串class Trie:
 def __init__(self):
 self.root = TrieNode() # 根结点 def insert(self, word: str) -> None:
 """
 将一个新字符串添加到字典树中。
 :param 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_of_word = True def search(self, word: str) -> bool:
 """
 检索是否存在某个字符串在字典树中。
 :param word: 要查找的字符串 :return: 是否找到该字符串 """
 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 delete(self, word: str) -> None:
 """
 从字典树中移除一个字符串。
 :param word: 要删除的字符串 """
 self._delete_helper(self.root, word,0)

 def _delete_helper(self, node, word, index):
 if index == len(word):
 if not node.is_end_of_word:
 return False node.is_end_of_word = False return True char = word[index]
 if char not in node.children:
 return False should_delete_current_node = self._delete_helper(node.children[char], word, index +1)

 if not node.is_end_of_word and not node.children[char].children and not should_delete_current_node:
 del node.children[char]

 return should_delete_current_node

trie = Trie()
trie.insert("apple")
trie.insert("app")
trie.insert("banana")

print(trie.search("apple")) # Trueprint(trie.search("app")) # Trueprint(trie.search("banana")) # Trueprint(trie.search("banan")) # Falsetrie.delete("apple")
print(trie.search("apple")) # False