Trie删除
来源:10-7 更多和Trie字典树相关的话题
哈哈哈蜜瓜
2018-10-09
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明显不能适应,不知老师可否给出点改进的思路
写回答
1回答
-
你设想的边界条件都对:)
简单的说,对于当前要删除的单词,达到这个单词末尾节点,将isWord置为false以后,要看当前这个单词是否是已经存储的其他单词的前缀。如果是,则不能删除节点。否则向上删除,每次都要判断当前节点所表示的单词是否是一个已经在Trie中存储的单词,或者其他单词的前缀:)
我写了两版代码,供参考:
加油!:)
212018-10-10
相似问题