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

Question

从特里树中删除单词时，如果该单词的节点没有用于另一个单词，我会尝试删除它们。

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

如果在 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)

Answer 1

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

• 您的

  append_word

  方法显示节点没有

  children

  属性。它们是字典。唯一具有

  children

  属性的对象是

  Trie

  实例，并且您只有一个这样的实例。该结构的其余部分是一个嵌套字典，以

  children

  属性
  开头

• 使用

  parent

  ，您只保留last父级，而不是所有祖先。为了正确地做到这一点，您需要回溯可能的多个祖先，直到遇到仍在使用另一个单词的祖先。所以实际上你需要一份祖先列表，而不仅仅是一个

  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

Answer 2

谈到@trincot的答案，我认为使用堆栈的内存效率不高。我们可以简单地使用变量

lowest_node

来表示我们可以安全地修剪下面的点。这是我的实现 -

class TrieNode:
    def __init__(self):
        self.children = {}
        self.endOfWord = False

class Trie(object):
    # omit the init etc.
    def delete(self, word):
        node = self.root
        lowest_node = self.root
        lowest_char = ''
        for char in word:
            if char not in node.children:
                return False
            if len(node.children) > 1 or node.endOfWord == True:
                lowest_node = node
                lowest_char = char
            node = node.children[char]
        if node.children:
            node.endOfWord = False
        else:
            lowest_node.children.pop(lowest_char)
        return True