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

Question

从 trie 中删除一个词时，我试图删除该词的节点（如果它们未被用于另一个词）。

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

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

这是我的 Trie class:

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

我在这里错过了什么？

我正在这样调用函数，来自另一个 class:

的 trie 实例

self.trie.delete(user_input)

Answer 1

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

您的 append_word 方法显示节点没有 children 属性。它们是字典。唯一具有 children 属性的 object 是 Trie 实例，而您只有一个这样的实例。结构的其余部分是一个以 children 属性
开头的嵌套字典
与parent你只保留lastparent，而不是所有的祖先。要做到这一点，您需要回溯潜在的多个祖先，直到您遇到一个仍在使用另一个词的祖先。所以实际上你需要一个祖先列表而不是一个 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

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

Delete nodes of a word if they are not being used by another word in the Trie structure

python

trie