Python 字典树的插入、查询、删除操作

2023-04-11 00:00:00 删除插入字典

字典树（Trie树）是一种树形结构，用于存储和查找字符串。它的基本思想是将字符串拆成单个字符，每个字符作为一个节点存储在树中，从根节点根据字符顺序遍历到对应的叶子节点，表示该字符串的存储和查找。

Python字典树的实现需要定义节点和字典树类，可以在节点中存储字符和指向下一个节点的指针，而在字典树类中，需要定义插入、查找、删除等操作。

下面是Python字典树的代码实现：

class TrieNode:
    def __init__(self):
        self.chars = {}    #存储下一个节点的指针
        self.is_end = False  # 标识是否为单词结尾

class 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.chars:   
                 # 新建节点，存储字符
                node.chars[char] = TrieNode()  
            node = node.chars[char]   #从父节点转移到子节点
        node.is_end = True  #标识该节点为单词的结尾

    def search(self, word: str) -> bool:
        node = self.root   #从根节点开始查找
        for char in word:
            if char not in node.chars:
                return False   #未找到单词
            node = node.chars[char]   #从父节点转移到子节点
        return node.is_end  #判断是否为单词结尾

    def delete(self, word: str) -> None:
        node = self.root
        parent = None   #标识当前节点的父节点
        for char in word:
            if char not in node.chars:
                return
            parent, node = node, node.chars[char]   #从父节点转移到子节点
        node.is_end = False   #取消该节点为单词结尾标志
        if not node.chars:   #如果该节点没有子节点
            del parent.chars[char]   #删除该节点

可以通过以下代码测试字典树的功能：

trie = Trie()
words = ['pidancode.com', '皮蛋编程', 'python']
for word in words:
    trie.insert(word)

assert trie.search('pidancode.com') == True
assert trie.search('皮蛋编程') == True
assert trie.search('python') == True
assert trie.search('编程') == False

trie.delete('pidancode.com')
assert trie.search('pidancode.com') == False

相关文章