老师，能帮忙看看我写的Trie的两种删除的版本对吗？

/**
 * 循环版本
 * @param word
 */
public void remove(String word) {
    // 如果不包含单词，直接返回
    if (!contains(word)) {
        return;
    }

    /*
    循环思路：
        从root开始，因为前面已经判断过包含这个word，所以在每轮遍历中：
            如果map内只有一组映射关系，即size==1，则必然是word中的字符，此时移除这个映射关系即可，移除前要拿到下一个节点的位置以便循环继续执行
            如果map还包含其他映射关系，即size>1，则不作处理
        到最后一个节点时，isWord必然为true，将其置为false
     */

    Node cur = root;
    for (int i = 0; i < word.length(); i++) {
        char c = word.charAt(i);
        if (cur.next.size() == 1) {
            Node next = cur.next.get(c);
            cur.next.remove(c);
            cur = next;
        }
        cur.isWord = false;
    }
    // 维护size
    size --;
}

/**
 * 递归版本
 * @param word
 */
public void removeR(String word){
    if (contains(word)){
        removeR(word, root, 0);
    }
}

private void removeR(String word, Node node, int index){
    // 退出条件：递归至word最后一个字符所对应的节点。此时，将这个节点的isWord置为false，开始返回
    if(index == word.length()){
        node.isWord = false;
        size --;
        return;
    }

    char c = word.charAt(index);
    // 递归至最末端，开始返回后，倒序删除每个map中对应字符的映射关系
    removeR(word, node.next.get(c), index+1);
    if (node.next.size() == 1){
        node.next.remove(c);
    }
}

好好撸代码 2021-12-06

源自：线段树，Trie 和并查集 2-7 更多和Trie字典树相关的话题

收起

1回答

liuyubobobo 回答被采纳获得+3积分 2021-12-07 07:45:29

是有问题的。

你的注释里这个假设是错的：

如果map内只有一组映射关系，即size==1，则必然是word中的字符，此时移除这个映射关系即可

map 内的这组映射关系确实肯定是 word 中的字符，但不一定仅仅是 word 中的字符。

比如 Trie 中存了 "ab" 和 "ac" 两个词。"a" 是 “ab" 和 "ac" 共有的前缀。此时，在你的逻辑下，删除 "ab"，将会导致把 a 这个节点删除。"ac" 这个词对应的所有节点也就没有了。

继续加油！：）

收起回答

好好撸代码提问者 #1

谢谢老师，我参考leetcode上的分析，重新写了一下删除的思路，您看这样还有什么问题吗？

/**
 * 参照 https://leetcode.com/problems/implement-trie-prefix-tree/discuss/156159/Java-solution-with-delete()-method
 * 删除思路--四种情况：
 * 1.如果参数word是一个单独的分支，不与其他词共享任何字符，删除这些字符对应的所有节点
 * 2.如果word是trie上其他词的前缀，将这个词的尾字符节点isWord置为false
 * 3.如果其他词是word的前缀，将前缀保留，后续删除
 * 4.如果word与其他词并不互为前缀，仅仅共享了部分字符，如 abcd 和 abefg, 则移除word中非共享的字符
 * 综上，四种情况的共通逻辑是，找到word中哪一个字符是最后一个不需要删除的字符，由此以后的字符对应的节点就可以全部删除了
 * 此外，在遍历的过程中，如果通过当前字符获取的下一个节点为null，或通过最后一个字符获取的节点isWord=false，
 * 说明word不在trie上，直接返回即可，可以省下一个contains()的执行时间。
 *
 */
public void remove(String word) {
    Node delBelow = root; // 最后一个不需要删除的节点
    Node next;
    char delChar = word.charAt(0);
    Node cur = root;
    for (int i = 0; i < word.length(); i++) {
        char c = word.charAt(i);
        next = cur.next.get(c);

        if(next == null){  //  对应【此外】的情形
            return;
        }

        if (cur.next.size() > 1 || cur.isWord){
            // size > 1说明必定与其他词共享了当前字符，最后一个不需要删除的节点更新至当前节点，对应第2和第4种情况
            // isWord=true说明其他词是word的前缀，或者word在trie上且已经遍历到最后一个字母，对应第3和第1种情况
            delBelow = cur;
            delChar = c;
        }
        cur = next;

    }
    if (!cur.isWord){  // 对应【此外】的情形
        return;
    }

    // 执行移除操作
    if (cur.next.isEmpty()){
        delBelow.next.remove(delChar);
    }else {
        cur.isWord = false;
    }
}

2021-12-07 22:47:54

liuyubobobo 回复提问者好好撸代码 #2

具体逻辑我不看了，你的注释是完全正确的：）如果感兴趣，可以尝试通过这个问题，如果能 ac，说明没有问题：https://leetcode.com/problems/implement-trie-ii-prefix-tree/ (注意，这个问题中允许存入多个同样的单词，需要记住同样单词的数目，所以 Node 的设计会和课程中介绍的稍有不同。不过是很好的练习：）加油！：）)

2021-12-08 04:50:36
好好撸代码提问者回复 liuyubobobo #3

谢谢老师！

2021-12-08 09:45:54