时间戳

首页 > 解决方案 > 如果单词的节点没有被 Trie 结构中的另一个单词使用，则删除它们

python - 如果单词的节点没有被 Trie 结构中的另一个单词使用，则删除它们

问题描述

从 trie 中删除一个单词时，如果该单词的节点不用于另一个单词，我会尝试删除它们。

所以我不想在删除单词时只标记一个节点。真正应该删除未使用的节点。

如果在 trie 中找不到单词，我希望删除方法返回 False，如果删除有效，它应该返回 True。

这是我的 Trie 课程：

class Trie(object):
    def __init__(self):
        self.children = {}
        self.end = "#"

    def append_word(self, word: str):
        node = self.children
        for c in word:
            node = node.setdefault(c, {})
        node[self.end] = self.end

这是delete我根据研究尝试实施的方法：

    def delete(self, word):
        node = self
        parent = self
        for char in word:
            if char in node.children:
                parent = node
                node = node.children[char]
            else:
                return False
        if not node.children:
            del parent.children[char]
            del node
            return True
        else:
            node.end = "#"
            return True

我在这里想念什么？

我正在从另一个类的 trie 实例中调用这样的函数：

self.trie.delete(user_input)

标签： pythontrie

解决方案

您尝试的问题与以下两点有关：

  • 您的append_word方法表明节点没有children属性。它们是字典。唯一具有children属性的对象是Trie实例，而您只有一个这样的实例。结构的其余部分是一个以该children属性开头的嵌套字典

  • 与parent您一起只保留最后一个父母，而不是所有祖先。要做到这一点，您需要回溯可能的多个祖先，直到遇到一个仍在用于另一个词的祖先。所以实际上你需要一个祖先列表而不是一个parent参考。

这是更正后的实现：

def delete(self, word):
    node = self.children
    stack = []
    for char in word:
        if char not in node:  # Word is not in the Trie
            return False
        stack.append(node)  # Collect as ancestor
        node = node[char]
    if self.end not in node:  # End-of-word marker is missing, so word is not in Trie
        return False
    del node[self.end]   # Remove end-of-word marker
    for char in reversed(word):  # Backtrack in reversed order
        if len(node):  # Still in use for another word?
            break
        node = stack.pop()
        del node[char]
    return True

推荐阅读