JavaScript实现Trie树(字典树)

背景

先说下背景,最近在找前端开发的工作,一面基础压力不大,发现到了二面三面经常会出现一些类似的问题,比如在公司的组织架构中快速查找一个人,查找IP白名单中的某一IP,当时没有很好的思路,事后发现用Trie树是个不错的解决方案,故而来学习一下。在网上一找,发现资料虽多,但大部分都是JAVA和C实现的,但是没找到用JS完整实现的代码,所以我就根据自己对trie树的理解,写了一个JS实现的版本,供大家参考,介绍部分引用一些网上的资料,实现部分会根据自己理解详细解释。

BTW. 随着现在前端的发展,我们可以承担的工作越来越丰富,已经不是当初验证个表单,上传个文件那么简单了,数据结构也是一个前端工程师必备的知识,可能现在你要实现的功能用不到Trie,不过后面搞不好哪个需求就会用到,学一下做个知识储备。当然你可能早就已经掌握这个结构了,那就帮忙看看有没有可以优化的地方,和我没实现的实用功能,评论区给我一点建议,让我多学一些~

1. Trie树

Trie树,即字典树,又称单词查找树或前缀树,是一种多叉树结构。典型应用是用于快速查找,统计和排序大量的字符串(但不仅限于字符串),所以经常被用于文本词频统计,前缀匹配等。在前端的应用比如即时响应用户输入的AJAX搜索框时,为了提高查询速度,就可以用Trie结构。

Trie树的优点是最大限度地减少无谓的字符串比较,查询效率比较高。核心思想是空间换时间,利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。

  1. 插入、查找的时间复杂度均为O(N),其中N为字符串长度,其实在插入的过程中就能顺便查找了,正因为他们是几乎一样的过程,所以trie才这么高效。
  2. 空间复杂度可能是26^N级别的,非常庞大。

Trie树有3个基本性质

  1. 根节点不包含字符,除根节点外每一个节点都只包含一个字符。
  2. 从根节点到某一节点,路径上经过的字符连接起来,为该节点对应的字符串。
  3. 每个节点的所有子节点包含的字符都不相同。

2. 字典树的构建

经过前面的介绍,大家心里应该有个Trie树的雏形了。本质上,Trie是一颗存储多个字符串的树。相邻节点间的边代表一个字符(可以存储在对应节点的一个属性中),这样树的每条分支代表一则子串,而树的叶节点则代表完整的字符串(在下面的实现中就是从根节点遍历到该节点的字符相加的结果)。和普通树不同的地方是,相同的字符串前缀共享同一条分支。下面举一个例子。给出一组单词,inn, int, at, age, adv, ant, 我们可以得到下面的Trie(图是网上找的,水印是自动上的- -):

JavaScript实现Trie树(字典树)
可以看出:

  1. 每条边对应一个字母。
  2. 每个节点对应一项前缀。叶节点对应最长前缀,即单词本身。
  3. 单词inn与单词int有共同的前缀“in”, 因此他们共享左边的一条分支,root->i->in。同理,ate, age, adv, 和ant共享前缀"a",所以他们共享从根节点到节点"a"的边。

可能你会有疑问,那如果再加个单词'in'怎么办,难道被淹没在前缀中了? 对于这个问题,我的实现是,每个节点都会有个this.isWord属性,用于判断到这里是不是一个单词,还会有个this.count属性记录该字符的出现次数,如我先后添加单词'int', 'in', 'inn', 那么此时'in'节点的this.isWord为true,this.count == 3。

3. 代码实现(JavaScript)

有了前面的介绍,实现代码已经呼之欲出,这里为了兼容,采用ES5语法,要点部分都加了注释,应该比较好理解,实现了插入单词,打印全部单词,查找和删除单词方法。
javascript 代码

结语

上面就是根据本人的个人理解,用JS实现的Trie树,只实现了基本功能,欢迎补充讨论~ 如果对您有帮助,麻烦点个赞或者收藏下~~~

扩展阅读: 图文翔解HashTree(哈希树)

评论 ( 0 )
最新评论
暂无评论

赶紧努力消灭 0 回复