Trie删除

Question

        remove(word) {
            if (!word.length) return;
            let cur = this.root;

            this.removeMatch(cur, word, 0)
        }

        removeMatch(node, word, index) {
            if(this.search(word)) {
                if (index === word.length) return false;

                let c = word.charAt(index);
                if (!node.next.has(c)) return;

                let cur = node.next.get(c),
                    del;
                del = this.removeMatch(cur, word, index + 1);
                if (this.isEnd(cur) && index === word.length - 1) {
                    node.next.delete(c);
                    return false
                } else if (cur.isWord && !del && index === word.length - 1) {
                    cur.isWord = false;
                    return true
                } else if (!del && !cur.isWord && !this.hasKey(cur)) {
                    node.next.delete(c)
                }
                return true
            }else{
                console.log('word is undefined')
            }
        }

        isEnd(node) {
            return node.next.size === 0
        }

        hasKey(node) {
            return node.next.size >= 1
        }

琢磨了一个下午出来的半成品，trie的删除操作考虑的情况似乎有点多？除了最简单的直接删除一列，还有比如加入了panda、pan、pad删除panda只能删除da，删除pan只能改isWord，删除pad只删除d等等，目前只想到这些情况，还有其他的情况这个code明显不能适应，不知老师可否给出点改进的思路

Answer 1

liuyubobobo 2018-10-10 03:13:45

你设想的边界条件都对：）

简单的说，对于当前要删除的单词，达到这个单词末尾节点，将isWord置为false以后，要看当前这个单词是否是已经存储的其他单词的前缀。如果是，则不能删除节点。否则向上删除，每次都要判断当前节点所表示的单词是否是一个已经在Trie中存储的单词，或者其他单词的前缀：）

我写了两版代码，供参考：

非递归实现：https://github.com/liuyubobobo/Play-with-Data-Structures/blob/master/10-Trie/Optional-02-Trie-Delete/src/Trie.java

递归实现：https://github.com/liuyubobobo/Play-with-Data-Structures/blob/master/10-Trie/Optional-02-Trie-Delete/src/TrieR.java

加油！：）

• 提问者 哈哈哈蜜瓜 #1

  多谢老师?