|
压缩Trie的性质和优势：? ?
????????与标准Trie比较，压缩Trie的结点数与串的个数成正比了，而不是与串的总长度成正比。
class TrieTree{
constructor(str,tail) {
this.val = str;
this.tail = tail;
this.child = new Array(26).fill(null);
}
}
class CompreeTrieTree{
constructor() {
this.root=new TrieTree('')
}
insert=(str)=>{
let root=this.root
let _getcommonlen=(str1,str2)=>{
let m=0;
while (m<str1.length&&m<str2.length&&str1[m] == str2[m]) m++;
return m;
}
let _insert=(str,node)=>{
if(str=="") return node;
let index=str[0].charCodeAt()-'a'.charCodeAt()
let childnode=node.child[index]
if(!childnode){
node.child[index]=new TrieTree(str,true)
}else{
let nodeval=childnode.val
let commonlen=_getcommonlen(nodeval,str)
if(commonlen==str.length||commonlen==nodeval.length){
node.child[index].tail=true;
}else{
node.child[index].tail=false;
}
node.child[index].val=str.substr(0,commonlen)
node.child[index]=_insert(str.substr(commonlen),node.child[index])
node.child[index]=_insert(nodeval.substr(commonlen),node.child[index])
}
return node
}
this.root=_insert(str,root,false)
}
find=(str)=>{
/*
* 查询
* */
let len=str.length
let node=this.root
for (let i = 0; i <len; i++) {
let index=str[i].charCodeAt()-'a'.charCodeAt()
let childnode=node.child[index]
if(!childnode){
return false
}
let nodeval=childnode.val
if(str.substr(i).length<nodeval.val) return false
if(str.substr(i,nodeval.length)!=nodeval){
return false
}
if(nodeval==str.substr(i)&&childnode.tail){
return true
}
i+=nodeval.length-1
node=childnode
}
return false;
}
}
const treetest=new CompreeTrieTree();
treetest.insert("abc")
treetest.insert("abcde")
treetest.insert("abcfe")
treetest.insert("bcaa")
treetest.insert("abcfed")
console.log(treetest.find("abcfedd"))
|