介绍

Trie树(来自词检索)，也称为前缀词、词搜索树和词典树，是一种树结构，是哈希树的变体，是一种用于快速检索的多分支树结构。

其优点是：尽量减少不必要的字符串比较，其查询效率高于哈希表。

Trie的核心思想是以空间换时间。字符串的公共前缀被用来减少查询时间开销以提高效率。

Trie树也有它的缺点。假设我们只处理字母和数字，每个节点至少有52个10个子节点。为了节省内存，我们可以使用链表或数组。我们在JS中直接使用数组，因为JS数组是动态的，自带优化。

基本属性

根节点不包含字符，除了根节点之外的每个子节点都包含从根节点到某个节点的字符。通过路径的字符是连接的，即节点对应的字符串，每个节点的所有子节点都包含不同的字符。

//由司徒正美类Trie { constructor(){ this。root=new TrieNode()；}是有效的(str){返回/^[a-z1-9]$/i . test(str)；}插入(word){//addWord if(this。isvalid(word)){ var cur=this。根；for(var I=0；我。字长；I){ var c=word。charcodeat(一)；c-=48；//减少"0"的charCode var node=cur。儿子[c]；if(node==null){ var node=(cur。son[c]=new trie node())；节点。value=word。charat(一)；节点。numpass=1；//有普通个字符串经过它} else { node.numPass} cur=节点；} cur.isEnd=true//樯记有字符串到此节点已经结束cur.numEnd//这个字符串重复次数返回真；} else { return false } } remove(word){ if(this。isvalid(word)){ var cur=this。根；定义变量数组=[]，n=word。长度为(var I=0；I n；I){ var c=word。charcodeat(一)；c=这个。getindex(c)var node=cur。儿子[c]；if(node){ array。push(node)cur=node } else { return false } } if(array。长度===n){数组。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)；用于(设i=0，n=根。儿子。长度；I n；I){让node=root。子[我]；if(node){ preTraversalImpl(node，str node.value，CB)；} } } preTraversalImpl(this.root，'，CB)；} //在字典树中查找是否存在某字符串为前缀开头的字符串（包括前缀字符串本身)isContainPrefix(word){ if(this。isvalid(word)){ var cur=this。根；for(var I=0；我。字长；I){ var c=word。charcodeat(一)；c-=48；//减少"0"的charCode if(cur。son[c]){ cur=cur。儿子[c]；} else {返回false} }返回true } else { return false } } is continford(str){//在字典树中查找是否存在某字符串（不为前缀)如果(这个。是有效的(单词)){ var cur=this。根；for(var I=0；我。字长；I){ var c=word。charcodeat(一)；c-=48；//减少"0"的charCode if(cur。son[c]){ cur=cur。儿子[c]；} else {返回false} }返回cur . isend } else { return false } } count prefix(单词){ //统计以指定字符串为前缀的字符串数量如果(这个。是有效的(单词)){ var cur=this。根；for(var I=0；我。字长；I){ var c=word。charcodeat(一)；c-=48；//减少"0"的charCode if(cur。son[c]){ cur=cur。儿子[c]；} else { return 0；} }返回cur . NumPass } else { return 0；} } countWord(word) { //统计某字符串出现的次数方法如果(这个。是有效的(单词)){ var cur=this。根；for(var I=0；我。字长；I){ var c=word。charcodeat(一)；c-=48；//减少"0"的charCode if(cur。son[c]){ cur=cur。儿子[c]；} else { return 0；} }返回cur . NumMend } else { return 0；} } }类trie节点{ constructor(){ this。numpass=0；//有多少个单词经过这节点这个。NuMend=0；//有多少个单词就此结束这个。son=[]；this.value=//值为单个字符this.isEnd=false}}我们重点看一下节点类与特里的插入方法。由于字典树是主要用在词频统计，因此它的节点属性比较多，包含了数字签名但非常重要的属性。

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

优化

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

//由斯图亚特梅铮得到索引(c) {if (c 58) {//48-57返回c-48} else if (c 91) {//65-90返回c-65 11} else {//97返回c-97 26 11}}然后相关的方法将是c-=

试验

var Trie=new Trie()；trie . insert(' I ')；插入(‘爱’)；插入('中国')；插入('中国')；插入('中国')；插入('中国')；插入('中国')；插入('梁潇')；插入('梁潇')；trie . insert(' man ')；trie.insert('帅气')；trie . insert(' love ')；trie . insert(' Chinaha ')；trie . insert(' her ')；trie . insert(' know ')；Var map={} trie。pretravel(函数(节点，字符串){if(节点。isend) {map [str]=node。nu mend } })for(var I in map){ console . log(I '现身' map[I]' times ')} console . log//console . log(' China ')var map={ } trie . pretraversal(function(node，Str) {if (str。的索引(' chin')===0node。isend) {map [str]=node。numend}})为(var I in map) {console.log (I '出现' map[I]' times ')}

Trie树与其他数据结构的比较

特里树和二叉查找树

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

一般Trie树的高度n远大于搜索字符串的长度m，因此搜索操作的时间复杂度通常为O(m)，最差的时间复杂度为O(n)。很容易看出，在最坏的情况下，特里树比二叉查找树树快。

本文中的Trie树以字符串为例。事实上，它对密钥的适用性有严格的要求。如果key是浮点数，可能会导致整个Trie树非常长，节点可读性很差。在这种情况下，不适合使用Trie树保存数据；但是二叉查找树没有这个问题。

树和哈希表

考虑哈希冲突。哈希表通常说它的复杂度是O(1)，但严格来说，它接近于完美哈希表的复杂度。此外，还需要考虑哈希函数本身需要遍历搜索字符串，其复杂度为O(m)。当不同的关键字映射到“同一个位置”(考虑封闭Hashing，这个“同一个位置”可以用一个普通链表代替)时，搜索的复杂度取决于这个“同一个位置”的节点数，所以最坏的情况下，哈希表也可以变成单向链表。

Trie树可以方便地按照键的字母顺序进行排序(整个树应该遍历一次)，这与大多数哈希表不同(哈希表对于不同的键一般是无序的)。

在理想情况下，哈希表可以以O(1)的速度快速命中目标。如果表非常大，需要放在磁盘上，在理想情况下，哈希表的搜索和访问只能进行一次。但是，Trie树访问的磁盘数量需要等于节点深度。

在许多情况下，Trie树比哈希表需要更多的空间。当我们考虑一个字符存储在一个节点中时，没有办法将一个字符串保存为一个单独的块。Trie树的节点压缩可以明显缓解这个问题，这将在后面讨论。

Trie树的改进

逐位特里树(逐位特里)

原则上与普通Trie树类似，只是普通Trie树存储的最小单位是字符，但是Bitwise Trie只存储位。位数据的访问直接由CPU指令一次性实现。对于二进制数据，理论上比普通的Trie树快。

节点压缩。

分支压缩：对于一个稳定的Trie树，基本上是一个搜索和读取操作，可以完全压缩一些分支。比如上图最右分支的inn可以直接压缩成节点“inn”，不需要作为正则子树存在。根据这个原理，基数树解决了Trie树过深的问题。

节点映射表：当Trie树的节点可能已经几乎完全确定时，也采用这种方法。对于Trie树中节点的每个状态，如果状态的总数是重复的，则由元素为数字的多维数组(如三元数组Trie)来表示，这样存储Trie树本身的空间开销会更小，尽管会引入额外的映射表。

前缀树的应用

前缀树通俗易懂，应用广泛。

(1)字符串的快速检索

字典树的查询时间复杂度为O(logL)，l为字符串的长度。因此，效率相对较高。字典树比哈希表更有效。

(2)字符串排序

从上图很容易看出单词是排序的，先遍历字母顺序。减少了不必要的公共子串。

(3)最长的公共前缀

inn和int最长的公共前缀是in。当遍历字典树到字母n时，这些单词的公共前缀是in。

(4)自动匹配前缀以显示后缀

当我们使用字典或搜索引擎时，输入appl，一堆前缀为appl的东西就会自动显示出来。那么可以通过字典树来实现。如前所述，字典树可以找到公共前缀，我们只需要遍历并显示剩余的后缀。

以上就是本文的全部内容。希望对大家的学习有帮助，支持我们。