Trie的删除操作

Question

波波老师您好，我是这样想的：在正常删除的过程中只遍历一遍，记录一个分支的节点和后一个字母，例如teach和teachers中删除teachers就记录h所在的节点和’e’，这样只调用一次remove即可删除后续所有节点。我简单测试过一些数据没问题，但是不知道有没有逻辑上遗漏的地方，还请老师指点指点 : }

public Boolean remove(String word){
    Node cur = root;
    Node divide = root;     //用来标记可能存在的最后一个分支节点
    char flagLetter=' ';    //用来记录remove中字母

    for(char c:word.toCharArray()){
        //如果没有待删除单词就直接返回false
        if(!cur.next.containsKey(c)){
            return false;
        }

        //如果待删单词前面有别的单词或者某个字母有多个后续节点就记录当前位置
        //tea teach teacher
        //删除teacher：先记录a所在节点和'c'，再记录h所在节点和'e'，最后执行remove('e')
        //tell tall
        //删除tall：记录t所在节点和'a'，最后在t所在节点上执行remove('a')
        
        if(cur.isWord || cur.next.size()>1){
            divide = cur;
            flagLetter = c; //记录后一个字母
        }
        cur = cur.next.get(c);
    }

    // 遍历结束到了待删单词的末尾
    // 首先如果isWord=false则表明并没有此单词
    if(!cur.isWord){
        return false;
    }

    // 如果有后续节点就直接设置isWord=false
    if(!cur.next.isEmpty()){
        cur.isWord = false;
    }else {
        //如果单词末尾没有节点了，就一直删除到前一个单词末尾或者分支处(divide)
        divide.next.remove(flagLetter);
    }
    size --;
    return true;
}

Answer 1

liuyubobobo 2019-09-27 01:58:16

大赞！我没有具体测试你的逻辑，看思路完全没有问题！divide记录的是最后一个不可以删除的节点：）

感谢分享！：）

继续加油！：）

• 提问者 笨蛋某某某 #1

  感谢老师凌晨两点半的在线答疑！是我对递归不够了解，所以觉得把每种情况罗列出来再非递归比较容易接受。刚学习完并查集，我记得LeetCode上第200号岛屿问题的题目每次算法竞赛都会有，以前都是用递归，今天又有了新的认识。不过我觉得等学习完数据结构还是得学习老师的另一部算法视频，以前讨厌指针所以:Q..这次得捡起来了。恩师！