如果Trie结构中的另一个单词没有使用某个单词的节点，则删除该单词的节点

Question

当从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

    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)

Answer 1

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

>

您的append_word方法显示节点没有子属性。它们是字典。具有children属性的唯一对象是trie实例，而且只有一个这样的实例。结构的其余部分是以子属性开始的嵌套字典

对于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