数据结构笔记总结(9.1)什么是Trie字典树

什么是Trie

这种数据结构和我们之前介绍的所有树结构都不同的一种树,之前介绍的所有树结构,无论是二分搜素树还是堆还是线段树都是二叉树,但是Trie是一个多叉树,下面和字典来做一下比较
数据结构笔记总结(9.1)什么是Trie字典树

Trie是怎么做到查询的时间复杂度和条目数无关而只和单词中有多少个字符相关的呢?
数据结构笔记总结(9.1)什么是Trie字典树
之前我们在考察字符串、单词这样一个数据的时候,我们会把整个字符串看成一个整体。

但是Trie打破了这个思路,它将整个字符串以字母为单位一个个拆开,从根节点开始一直到叶子节点去遍历,遍历到一个叶子节点就形成了一个单词。

图中Trie中存储了四个单词,查询任何一个单词,从根节点出发,只需要经过单词有多少个字母相应就经过多少个节点,最终到达叶子节点就成功查找到单词,这样的结构就是Trie。
数据结构笔记总结(9.1)什么是Trie字典树
考虑到语言和情景的不同,有可能26个指针是富余的,有可能是不够的,如果要考虑大小写的问题相应就需要52个指针,因此我们应该采用动态的思想来实现Trie。
数据结构笔记总结(9.1)什么是Trie字典树

我们使用动态的思想,相应的next就可以用Map来实现,实际上这个Map就是指一个char和一个Node之间的映射。

Map中要存放多少个映射我不知道,但是每一个映射一定是一个字符到一个新的节点。

之前学习的映射只是一种抽象的数据结构,背后我们具体可以使用树来实现,也可以使用哈希表来实现,由于这一章还没有接触哈希表,所以直接使用之前的TreeMap来实现这种映射,底层不是之前讲的二分搜素树,而是改良的平衡的二叉树,具体在java的底层是红黑树(后续再学习)

在绘制出Trie的时候,在每个节点都绘制了一个字母,但是其实从根节点找到下一个节点之前已经知道字母是谁了,其实更准确的来讲,应该把字母标在边上,所以在节点的实现中,每一个节点不存储char的值也是没有问题的
数据结构笔记总结(9.1)什么是Trie字典树

还有一个关键的问题是,之前说Trie查询一个单词都是从根节点出发一直到叶子节点,到了叶子节点就到了单词结束的地方。
数据结构笔记总结(9.1)什么是Trie字典树

不过这里要注意,在英语中很多单词可能是另外一个单词的前缀,比如下图中的pan和panda,此时对于pan结尾的根并不是叶子节点,正因如此,每一个node需要一个标识来告诉大家当前的节点是否是某一个单词的结尾,单词的结尾只靠叶子节点是不能区分出来的,因此我们设计的这个Node节点相应的应该存一个布尔值isWord,表示当前的节点是否能代表单词的结尾,如图所示,下一小节我们具体编程实现我们这个Trie。

数据结构笔记总结(9.1)什么是Trie字典树

源码下载

[dm href=’https://www.jikewenku.com/product/1487.html’]下载地址[/dm]

导航目录

[dm href=’https://www.jikewenku.com/geeknote/2241.html’]查看导航[/dm]

本站所有文章均来自互联网,如有侵权,请联系站长删除。极客文库 » 数据结构笔记总结(9.1)什么是Trie字典树
分享到:
赞(0)

评论抢沙发

评论前必须登录!