javascript trie前缀树的示例(2)

日期：2020-05-11 栏目：程序人生浏览：次

我们重点看一下TrieNode与Trie的insert方法。由于字典树是主要用在词频统计，因此它的节点属性比较多, 包含了numPass, numEnd但非常重要的属性。

insert方法是用于插入重词，在开始之前，我们必须判定单词是否合法，不能出现特殊字符与空白。在插入时是打散了一个个字符放入每个节点中。每经过一个节点都要修改numPass。

优化

现在我们每个方法中，都有一个c=-48的操作，其实数字与大写字母与小写字母间其实还有其他字符的，这样会造成无谓的空间的浪费

// by 司徒正美
getIndex(c){
   if(c < 58){//48-57
     return c - 48
   }else if(c < 91){//65-90
     return c - 65 + 11
   }else {//> 97 
     return c - 97 + 26+ 11
   }
 }

然后相关方法将c-= 48改成c = this.getIndex(c)即可

测试

var trie = new Trie(); 
  trie.insert("I"); 
  trie.insert("Love"); 
  trie.insert("China"); 
  trie.insert("China"); 
  trie.insert("China"); 
  trie.insert("China"); 
  trie.insert("China"); 
  trie.insert("xiaoliang"); 
  trie.insert("xiaoliang"); 
  trie.insert("man"); 
  trie.insert("handsome"); 
  trie.insert("love"); 
  trie.insert("Chinaha"); 
  trie.insert("her"); 
  trie.insert("know"); 
  var map = {}
  trie.preTraversal(function(node, str){
    if(node.isEnd){
     map[str] = node.numEnd
    }
  })
  for(var i in map){
    console.log(i+" 出现了"+ map[i]+" 次")
  }
  console.log("包含Chin（包括本身）前缀的单词及出现次数："); 
  //console.log("China")
  var map = {}
  trie.preTraversal(function(node, str){
    if(str.indexOf("Chin") === 0 && node.isEnd){
      map[str] = node.numEnd
    }
   })
  for(var i in map){
    console.log(i+" 出现了"+ map[i]+" 次")
  }

Trie树和其它数据结构的比较

Trie树与二叉搜索树

二叉搜索树应该是我们最早接触的树结构了，我们知道，数据规模为n时，二叉搜索树插入、查找、删除操作的时间复杂度通常只有O(log n)，最坏情况下整棵树所有的节点都只有一个子节点，退变成一个线性表，此时插入、查找、删除操作的时间复杂度是O(n)。

通常情况下，Trie树的高度n要远大于搜索字符串的长度m，故查找操作的时间复杂度通常为O(m)，最坏情况下的时间复杂度才为O(n)。很容易看出，Trie树最坏情况下的查找也快过二叉搜索树。

javascript trie前缀树的示例(2)

相关推荐