引子
Trie树（来自单词retrieval），又称前缀字，单词查找树，字典树，是一种树形结构，是一种哈希树的变种，是一种用于快速检索的多叉树结构。
它的优点是：最大限度地减少无谓的字符串比较，查询效率比哈希表高。
Trie的核心思想是空间换时间。利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。
Trie树也有它的缺点,假定我们只对字母与数字进行处理，那么每个节点至少有52＋10个子节点。为了节省内存，我们可以用链表或数组。在JS中我们直接用数组，因为JS的数组是动态的，自带优化。
基本性质
- 根节点不包含字符，除根节点外的每一个子节点都包含一个字符
- 从根节点到某一节点。路径上经过的字符连接起来，就是该节点对应的字符串
- 每个节点的所有子节点包含的字符都不相同
程序实现
return true;
} else {
return false;
}
}
remove(word){
if (this.isValid(word)) {
var cur = this.root;
var array = [],n = word.length
for (var i = 0; i < n; i++) {
var c = word.charCodeAt(i);
c = this.getIndex(c)
var node = cur.son[c];
if(node){
array.push(node)
cur = node
}else{
return false
}
}
if(array.length === n){
array.forEach(function(){
el.numPass--
})
cur.numEnd --
if( cur.numEnd == 0){
cur.isEnd = false
}
}}else{
return false
}
}
preTraversal(cb){//先序遍历
function preTraversalImpl(root,str,cb){
cb(root,str);
for(let i = 0,n = root.son.length; i < n; i ++){
let node = root.son[i];
if(node){
preTraversalImpl(node,str + node.value,cb);
}
}
}
preTraversalImpl(this.root,"",cb);
}
// 在字典树中查找是否存在某字符串为前缀开头的字符串(包括前缀字符串本身)
isContainPrefix(word) {
if (this.isValid(word)) {
var cur = this.root;
for (var i = 0; i < word.length; i++) {
var c = word.charCodeAt(i);
c -= 48; //减少”0“的charCode
if (cur.son[c]) {
cur = cur.son[c];
} else {
return false;
}
}
return true;
} else {
return false;
}
}
isContainWord(str) {
// 在字典树中查找是否存在某字符串(不为前缀)
if (this.isValid(word)) {
var cur = this.root;
for (var i = 0; i < word.length; i++) {
var c = word.charCodeAt(i);
c -= 48; //减少”0“的charCode
if (cur.son[c]) {
cur = cur.son[c];
} else {
return false;
}
}
return cur.isEnd;
} else {
return false;
}
}
countPrefix(word) {
// 统计以指定字符串为前缀的字符串数量
if (this.isValid(word)) {
var cur = this.root;
for (var i = 0; i < word.length; i++) {
var c = word.charCodeAt(i);
c -= 48; //减少”0“的charCode
if (cur.son[c]) {
cur = cur.son[c];
} else {
return 0;
}
}
return cur.numPass;
} else {
return 0;
}
}
countWord(word) {
// 统计某字符串出现的次数方法
if (this.isValid(word)) {
var cur = this.root;
for (var i = 0; i < word.length; i++) {
var c = word.charCodeAt(i);
c -= 48; //减少”0“的charCode
if (cur.son[c]) {
cur = cur.son[c];
} else {
return 0;
}
}
return cur.numEnd;
} else {
return 0;
}
}
}
class TrieNode {
constructor() {
this.numPass = 0;//有多少个单词经过这节点
this.numEnd = 0; //有多少个单词就此结束
this.son = [];
this.value = ""; //value为单个字符
this.isEnd = false;
}
}
我们重点看一下TrieNode与Trie的insert方法。 由于字典树是主要用在词频统计，因此它的节点属性比较多,包含了numPass,numEnd但非常重要的属性。
insert方法是用于插入重词，在开始之前，我们必须判定单词是否合法，不能出现 特殊字符与空白。在插入时是打散了一个个字符放入每个节点中。每经过一个节点都要修改numPass。
优化
现在我们每个方法中，都有一个c=-48的操作，其实数字与大写字母与小写字母间其实还有其他字符的，这样会造成无谓的空间的浪费
97 return c - 97 + 26+ 11 } }
